基于模糊聚类和信息熵的综合评价算法

第22卷　第6期2004年11月

文章编号:1671-5896(2004)06-0643-05

吉林大学学报(信息科学版)

JournalofJilinUniversity(InformationScienceEdition)Vol.22　No.6

Nov.2004

基于模糊聚类和信息熵的综合评价算法

张运凯1,王方伟1,戴敬书2,黄文艳3,陈艳红4

(1.河北师范大学网络中心,河北石家庄050016;2.河北电视台新闻中心,河北石家庄050031;3.河北师范大学数学与信息学院,河北石家庄050016;4.秦皇岛外国语职业学院,河北秦皇岛066311)

摘要:针对目前综合评价技术存在的主旨不相协调、忽略了简洁性与有效性问题,在分析已有算法的基础上,提出了一种基于模糊聚类和信息熵的综合评价算法,该算法有针对性地克服了原有评价算法的缺陷,具有较好的实用性,最后通过实际数据对该算法的有效性进行了验证。关键词:模糊聚类;信息熵;综合评价中图分类号:TP312　　　文献标识码:A

Newcomprehensiveevaluationalgorithmbasedonfuzzy

clusteringandinformationentropy

ZHANGYun-kai1,WANGFang-wei1,DAIJing-shu2,HUANGWen-yan3,CHENYan-hong4

(1.NetworkCenterHebeiNormalUniversity,Shijiazhuang050016,China;2.NewsCenter,HebeiTelevisionStation,Shijiazhuang050031,China;

3.CollegeofMathematicsandInformationScience,HebeiNormalUniversity,Shijiazhuang050016,China;

4.QingHuangDaoForeignLanguageProfessionalCollege,Qinghuangdao066311,China)

Abstract:Aimsatinconsistentleitmotivincurrentcomprehensiveevaluationtechnology,neglectstheproblemofsuc-cinctnessandvalidity,analyzestheagoalgorithmsinthefoundation,propasesacomprehensiveevaluationalgovithmbasedonfuzzydusteringandinformationentropy.Thisalgorithmhurdlesflawsoforiginalalgorithms,hasagoodprac-ticabitity.Thevalidityofthisalgorithmhasbeenvalidatedthroughtheactualdata.Keywords:fuzzyclustering;informationentropy;comprehensiveevaluatio

引　言

评价是随着人类社会活动的发展而产生的。为了进行管理,就要进行一系列的评价。评价活动广泛存在于社会生活的各个领域。如教师授课绩效考核、员工工作能力的考核等。长期以来,评价主要是依靠人的经验,属于经验评价范畴。单凭个人的知识、经验、智慧和胆略来做评价难免出现重大失误,这主要由于同一事物具有多种属性,受到多种因素的影响。其次,随着科学技术的不断深化,研究的对象越来越复杂,而复杂的东西难以精确表示。为了能客观公正地对事物进行评价,出现了模糊综合评价方

法。很多学者对此进行了深入研究,提出了一些方法[1～3]。但是现在综合评价技术还存在下面主要问题:存在一种与综合评价主旨不相协调的倾向,人们似乎比较关心评价方法的复杂性而忽略了简洁性与有效性,盲目追求数学方法形式的复杂性,有意无意的将评价方法的复杂性和评价方法的有效性混为一谈。为此,笔者提出一个基于模糊聚类和信息熵的综合评价算法,该算法具有操作简单、易于实现和良好实用性的特点。

①

收稿日期:2004-02-12作者简介:张运凯(1965—　),男,河北望都人,河北师范大学副教授,主要从事计算机网络研究,Tel:86-311-6268469,E-mail:

zhyk@hebtu.edu.cn。644

吉林大学学报(信息科学版)　　　　　　　　　　　　　　　第22卷

1　改进后的综合评价算法

1.1　模糊聚类和信息熵

传统的聚类分析是一种硬划分,它把每个待辨识的对象严格地划分到某个类中,具有非此即彼的性

质,因此这种分类的类别界限是分明的。而实际上大多数对象并没有严格区分的属性,它们在形态和类属方面存在着中介性,适合进行软划分。Zadeh提出的模糊集理论为这种软划分提供了有力的分析工具,人们开始用模糊的方法来处理聚类问题,并称之为模糊聚类分析。由于模糊聚类能表示样本类属的中介性,即建立起了样本对于类别不确定性的描述,从而能更客观地反映现实世界,从而成为聚类分析研究的主流。模糊划分的概念最早由Ruspini[5]提出,利用这一概念人们提出了多种聚类方法,比较典型的有:基于相似性关系和模糊关系的方法[6]、基于模糊等价关系的传递闭包方法[7]、基于模糊图论最大树方法[8]等。然而由于上述方法不适用于大数据量情况,难以满足实时性要求高的场合,因此其实际的应用领域狭小。文献[9]用模糊集来划分边界,并提出数量型属性模糊关联规则的概念,但没有给出相应的算法。实际中受到普遍欢迎的是基于目标函数的方法,该方法设计简单、解决问题的范围广,最终还可以转化为优化问题而借助经典数学的非线性规划理论求解,并易于计算机实现。因此,该类方法成为聚类研究的热点。

在模糊聚类的具体应用过程中,认为被分类对象集合X中的样本xi,i=1,2,…,n,以一定的隶属度隶属于某一类,也就是说,所有的样本都分别以不同的隶属度隶属于某一类。因此,每一类认为是样本集合X上的一个模糊子集,每种这样的分类结果所对应的分类矩阵R,就是一个模糊矩阵。该分类矩阵满足下列3个条件:

1)rij∈[0,1],即分类矩阵元素在0和1之间取值;

2)∑rij=1,即每列中分别属于各类的隶属度之和为1,对一个样本而言,它对各类的隶属度之和

i=1c

[4]

为1;

n

3)∑rij>0,即每行的元素之和大于0,这保证了每类都必须有样本。

j=1

模糊聚类的主要算法有模糊等价矩阵法、模糊ISODATA聚类分析法等。

按照人们的常识:小概率事件所蕴含的信息量较大;就随机性而言,基本事件个数相同者,以等概率分布场平均信息量大。

上面的表述只是从定性的角度对信息进行了描述,在处理相关信息时没有任何信息的损失,但该方法不能提供基于对象的各因素的重要性大小,所以还需要提供先验的权重分配,必须借助于熵的概念,才能定量表达,熵是描述信息不确定性的度量。

设X是取有限个值的随机变量,pi=P{X=xi},i=1,2,…,n,则X的熵定义为

H(X)=

i=1

∑piloga

n

1pi

其中,底数a为任何正数,并规定当pi=0时,piloga

1=0。上述表达式即为Shannon信息熵表达式。pi

由此可见,信息熵是由事物内部属性客观决定的,如果能够用信息熵来确定权重,则能够保证权重

的客观性。关于信息熵对确定权重的意义详见文献[10,11]。

1.2　算法的具体实现1.2.1　经典模糊聚类的改进

对目标函数的改进主要是在目标函数中引入权重,使目标函数能反映事物属性之间的轻重关系

J(R,V)=

mj=1i=1

2

ijdij∑∑rq

2nc

其中

dij=‖xj-Vi‖=k=1xjk-Vik),　W∑wk(=(w1,w2,…,wm)

第6期　　　　　　　　　　　　　张运凯,等:基于模糊聚类和信息熵的综合评价算法

645

1.2.2　算法的具体步骤

1)据标准化处理,这里采用极大值标准化处理方法。2)确定评价因素的权重系数,形成权重向量。3)对待评价对象的集合进行聚类。

a用阈值矩阵法对所有样本进行大致的分类:①固定c值,将所有样本进行初始化,c即为评价结果论域中元素的个数;②构造相似矩阵R=(rij)1,2,…,H,,j=1,2,…,H,表示样本iHH,i=与样本j的相似程度。样本之间相似程度可以用相似系数法、距离法和贴近度法来表示,这里选取贴近度法

rij=

k=1

(xik∑

m

∧xjk)/

k=1

xik∑(

m

∨xjk)k

k

③求出等价关系R＊。通过平方计算法可以快速求得R＊。依次求得R2,R4,R8,…,R2,直到R2=R

2

k-1

,则有R=R。④采用λ截集矩阵法进行分类。λ是R＊中的隶属度,选择不同的隶属度使样本

2

＊

k

分为不同的c类。

b在大致分类基础上,进行精确分类:①对求得的分类采用平均值法计算出初始的聚类中心(V01,

0V0;②根据公式对聚类中心进行修正;③若满足结束条件,则迭代结束,否则回到②。2,…,Vc)

2　算法的分析与验证

该算法以综合评价工作的本质要求为突破点,根据综合评价工作的具体特点,采用了改进后的模糊聚类方法;针对模糊聚类与综合评价工作的不同,在算法中引入了由信息熵得到的权重向量,从而保证了算法的有效。

笔者以1997年《中国经济统计年鉴》提供的统计数据为基础,采用基于模糊聚类和信息熵的综合评价算法对6个城市的经济指标进行综合评测。已知决策对象集A={a1,a2,a3,a4,a5,a6},分别为石家庄、苏州、武汉、乌鲁木齐、兰州、呼和浩特;指标集Z={z1,z2,z3,…,z10},其中,z -1表示土地面积,z2表示年末总人口,z10,…,表示职工平均工资,具体数据详见表1。

表1　1997年全国6市主要经济指标Tab.1Themaineconomictargetsofsixcitiesin1997

城市名称石家庄

兰州

土地面积/km

2

年末总人口/万人860.19280.46151.94723.90200.37574.99

国民生产人均生产实现利税总值/万元总值/元总额/万元7813998

243680021690459123256128713011325941

911487571446812673647219713

652994162474111528640502827131167565

固定资产投资完成额/万元2981487103648689925440817972659644051760

出口总值/万美元1259983500036990941093879504390

实际利用外资/万美元2919387862465453333030244723

财政总职工均

收入/万元工资/元384211231957400276854198153927765384

625665787702640651958443

1584813086

乌鲁木齐12000武汉8467呼和浩特17224苏州8488

1)专家调查法得到的权重向量为{0.2,0.1,0.05,0.05,0.2,0.05,0.15,0.15,0.05,0.05},由此6城市经济发展水平排行为:苏州、石家庄、武汉、兰州、乌鲁木齐、呼和浩特;

2)由比较矩阵法得到的权重向量为{0.15,0.05,0.1,0.05,0.15,0.1,0.1,0.2,0.05,0.05},由此6个城市经济发展水平排行为:苏州、武汉、石家庄、兰州、乌鲁木齐、呼和浩特;

3)由Delphi方法得到的权重向量为{0.17,0.05,0.1,0.03,0.15,0.1,0.1,0.2,0.05,0.05},由此6个城市经济发展水平排行为:苏州、武汉、石家庄、兰州、乌鲁木齐、呼和浩特;

4)由信息熵理论得到的权重向量为{0.017,0.05,0.06,0.03,0.17,0.18,0.23,0.21,0.043,0.01}。

1997年中国县域经济基本竞争力评价中心对这6个城市的经济发展水平的排行为:苏州、武汉、石家庄、乌鲁木齐、兰州、呼和浩特。通过和上面几种方法的计算结果比较,可以看出,多少都存在一646

吉林大学学报(信息科学版)　　　　　　　　　　　　　　　第22卷

定出入:专家调查法得到的6个城市的排行中,发生了两对错误,即武汉和石家庄以及乌鲁木齐和兰州,可见该方法的实用性具有一定的局限性;比较矩阵法和Delphi法由于对专家的调查信息作了一定的数学处理,在对6个城市的排行中只发生了一对错误,即兰州和乌鲁木齐。而本算法将城市的经济发展

水平分为3类:高、中、低,求得聚类的中心;根据上述6个城市与聚类中心的距离计算各个城市所属的类别,可以求得苏州的经济发展水平为“高”;武汉和石家庄的经济发展水平为:“中”;而乌鲁木齐、兰州和呼和浩特的经济发展水平为“低”;为了进一步区分,将武汉和石家庄到经济发展水平“中”的距离归一化,分别为:1和0.9166。乌鲁木齐、兰州和呼和浩特相应距离归一化为:1,0.9421和0.74444;综上所述,6个城市的排行为:苏州、武汉、石家庄、乌鲁木齐、兰州、呼和浩特。这个结果与“中国县域经济网”(www.china-county.org)的评价结果一致。

3　应用实例———教师素质评测系统

对学校而言,教师对学校教学水平的提高起了极其重要的作用。如何公正、科学的评价一个教师的综合素质,调动他们工作的积极性,对提高学校的教学水平乃至整个国家的教育水平都十分重要。该系统是模糊综合评价系统平台的一个实例,主要侧重于定量指标。教师综合素质评测的评测体系包括以下4个模块:信息采集、信息管理、系统维护、系统帮助。其中信息管理包括信息查询、信息统计、信息评价,信息评价是本系统的核心部分。由于教师职业的基本特点是劳动者与劳动工具二者的统一,所以教师素质有以下几个特点:全面性、示范性、稳定性、再创性。鉴于此,该系统主要考虑的因素如图1所示。

图1　教师素质评价的因素

Fig.1Thefactorsoftheteachabilityevaluatingsystem

3.1　新算法的应用3.1.1　数据规格化

度量单位的选取对于评价结果有很大影响。例如将身高的单位从米变为尺,将体重的单位从公斤变为磅将直接影响计算的结果。为了避免出现这种情况,必须将数据标准化,将数据中的单位“去掉”,

为此采用平均数规格化。

3.1.2　确定评价要素及其权重

根据实际要求确定:课堂教学、教学实践、获奖专利等11项为评价要素,其权重均为1/11。

3.1.3　对待评价对象的集合进行聚类

1)用阈值矩阵法对所有样本进行大致的分类:①c=5,将所有样本进行初始化,c即为评价结果论域(优、良、中、及格、不及格)中元素的个数;②构造相似矩阵R=(rij)1,2,…,HH,rij,i=H;j=1,2,…,H,表示样本与样本的相似程度,样本之间相似程度用贴近度法表示;③求出等价关系R＊;④采用λ截集矩阵法进行分类。

2)在大致分类基础上,进行精确分类:

00

①对求得的分类采用平均值法计算出初始的聚类中心,(V0;②根据公式对聚类中1,V2,…,V5)

心进行修正;③若满足结束条件,则迭代结束,否则回到②。

3.2　系统主要运行界面

该系统主要侧重于对定量指标进行评价,通过综合评价模块的处理,将评价结果直观地反映出来,如图2,3所示。

第6期　　　　　　　　　　　　　张运凯,等:基于模糊聚类和信息熵的综合评价算法

647

从图3可以直观地看出某个教师的综合素质评价结果,还可以知道所有教师的综合排名,方便教师了解自己的不足之处,以便及时改正,有助于整个教师队伍综合素质的提高。

4　结　论

综合评价方法在很多领域(如网络优化、教学、施工)的决策研究、质量分析等方面都有广泛的应用。笔者提出了一个基于模糊聚类和信息熵的综合评价算法,具有操作简单,易于实现等优点,通过实验分析,该算法的评价结果更符合实际情况,具有良好的实用性,当评价指标很多时,该算法更具优越性。参考文献:

[1]黄淑琴(HUANGShu-qin).公路路线方案的多级综合模糊评价(Fuzzymodelfortransportprojectappraisal)[J].中国公

路学报(ChinaJournalofHighwayandTransport),1997,10(3):37—44.

[2]沈敏德,朱建公(SHENMin-de,ZHUJian-gong).对机械传动设计方案模糊评价中几个问题的探讨(Anapprochto

someproblemsoffuzzyevaluationformechnaicaltransmissionconcept)[J].西南工学院学报(JournalofSouthwestInstituteofTechnology),1998,13(4):40—43.

[3]张邦礼,尹朝东,曹龙汉(ZHANGBang-li,YINChao-dong,CAOLong-han).柴油机故障诊断中的遗传与模糊C-均值

混合聚类分析算法(Clusteringbyhybirdgenetic/C-meansalgorithminfaultdiagnosisfordieselengines)[J].计算机工程与应用(ComputerEngineeringandApplications),2002,38(3):254—256.[4]ZADEHLA.Fuzzysets[J].InformationandControl,1965,8(3):338—353.

[5]RUSPINIEH.Numericalmethodsforfuzzyclustering[J].InformationScience,1970,2(3):319—350.

[6]TAMURAS,HIGUCHIS,TANAKAK.Patternclassificationbasedonfuzzyrelations[J].IEEESMC,1971,1(1):217—242.[7]ZKIMLE.Fuzzyrelationcompositionsandpatternrecognition[J].InfSci,1996,89(1):107—130.

[8]WUZ,LEATHYR.Anoptimalgraphtheoreticapproachtodataclustering:Theoryanditsapplicationtoimagesegmentation[J].

IEEEPAMI,1993,15(11):1101—1113.

[9]KUOKCM,FUA,WONGMH.Miningfuzzyassociationrulesindatabase[J].ProcoftheACMSixthInternationalConference

onInformationandKnowledgeManagement,1997,27(1):10—14.

[10]曾谦,曾黄麟(ZENGQian,ZENGHuang-lin).系统参数重要性评价方法(Methodofevaluatingthesignificanceofsystem

parameters)[J].四川轻化工学院学报(JournalofSichuanInstituteofLightIndustryandChemicalTechnonogy),1999,12(2):10—13.

[11]郭亚军(GUOYa-jun).一种新的动态综合评价方法(Newtheoryandmethodofdynamiccomprehensiveevaluation)[J].管

理科学学报(JournalofManagementSciencesinChina),2002,5(2):49—54.

(Ed.:H)

本文来源：https://www.bwwdw.com/article/h92v.html