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

1、第22卷第6期吉林大学学报(信息科学版V ol.22No.6 2004年11月Journal of Jilin University(Information Science EditionNov.2004文章编号:1671-5896(200406-0643-05基于模糊聚类和信息熵的综合评价算法张运凯1,王方伟1,戴敬书2,黄文艳3,陈艳红4(1.河北师范大学网络中心,河北石家庄050016;2.河北电视台新闻中心,河北石家庄050031;3.河北师范大学数学与信息学院,河北石家庄050016;4.秦皇岛外国语职业学院,河北秦皇岛066311摘要:针对目前综合评价技术存在的主旨不相协调、忽略了

2、简洁性与有效性问题,在分析已有算法的基础上,提出了一种基于模糊聚类和信息熵的综合评价算法,该算法有针对性地克服了原有评价算法的缺陷,具有较好的实用性,最后通过实际数据对该算法的有效性进行了验证。关键词:模糊聚类;信息熵;综合评价中图分类号:TP312文献标识码:ANew comprehensive evaluation algorithm based on fuzzyclustering and information entropyZH ANG Yun-kai1,W ANG Fang-wei1,DAI Jing-shu2,HUANG Wen-yan3,CHEN Yan-hong4(1.Net

3、work Center Hebei Normal Univers ity,Shijiazhuang050016,China;2.News Center,Hebei Television Station,Shijiaz huang050031,China;3.College of Mathe matics and Infor mation Science,Hebei Normal Univers ity,Shijiazhuang050016,China;4.QingHuangDao Foreign Language Professional Coll ege,Qinghuangdao066311

4、,ChinaA bstract:Aims at inc onsistent leitmotiv in current comprehensive evaluation technology,neglects the pr oblem of suc-cinctness and validity,analyzes the ago algorithms in the foundation,propases a comprehensive evaluation algovithm based on fuzzy dustering and information entropy.This algorit

5、hm hurdles flaws of original algorithms,has a good prac-ticabitity.The validity of this algorithm has been validated through the actual data.Keywords:fuzzy clustering;information entropy;comprehensive evaluatio引言评价是随着人类社会活动的发展而产生的。为了进行管理,就要进行一系列的评价。评价活动广泛存在于社会生活的各个领域。如教师授课绩效考核、员工工作能力的考核等。长期以来,评价主要是依

6、靠人的经验,属于经验评价范畴。单凭个人的知识、经验、智慧和胆略来做评价难免出现重大失误,这主要由于同一事物具有多种属性,受到多种因素的影响。其次,随着科学技术的不断深化,研究的对象越来越复杂,而复杂的东西难以精确表示。为了能客观公正地对事物进行评价,出现了模糊综合评价方法。很多学者对此进行了深入研究,提出了一些方法13。但是现在综合评价技术还存在下面主要问题:存在一种与综合评价主旨不相协调的倾向,人们似乎比较关心评价方法的复杂性而忽略了简洁性与有效性,盲目追求数学方法形式的复杂性,有意无意的将评价方法的复杂性和评价方法的有效性混为一谈。为此,笔者提出一个基于模糊聚类和信息熵的综合评价算法,该算

7、法具有操作简单、易于实现和良好实用性的特点。收稿日期:2004-02-12作者简介:张运凯(1965,男,河北望都人,河北师范大学副教授,主要从事计算机网络研究,Tel:86-311-6268469,E-mail: zhyk。1改进后的综合评价算法1.1模糊聚类和信息熵传统的聚类分析是一种硬划分,它把每个待辨识的对象严格地划分到某个类中,具有非此即彼的性质,因此这种分类的类别界限是分明的。而实际上大多数对象并没有严格区分的属性,它们在形态和类属方面存在着中介性,适合进行软划分。Zadeh 4提出的模糊集理论为这种软划分提供了有力的分析工具,人们开始用模糊的方法来处理聚类问题,并称之为模糊聚类分

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

9、而借助经典数学的非线性规划理论求解,并易于计算机实现。因此,该类方法成为聚类研究的热点。在模糊聚类的具体应用过程中,认为被分类对象集合X 中的样本x i ,i =1,2,n ,以一定的隶属度隶属于某一类,也就是说,所有的样本都分别以不同的隶属度隶属于某一类。因此,每一类认为是样本集合X 上的一个模糊子集,每种这样的分类结果所对应的分类矩阵R ,就是一个模糊矩阵。该分类矩阵满足下列3个条件:1r ij 0,1,即分类矩阵元素在0和1之间取值;2ci =1r i j =1,即每列中分别属于各类的隶属度之和为1,对一个样本而言,它对各类的隶属度之和为1;3nj =1r i j >0,即每行的元

10、素之和大于0,这保证了每类都必须有样本。模糊聚类的主要算法有模糊等价矩阵法、模糊I SODATA 聚类分析法等。按照人们的常识:小概率事件所蕴含的信息量较大;就随机性而言,基本事件个数相同者,以等概率分布场平均信息量大。上面的表述只是从定性的角度对信息进行了描述,在处理相关信息时没有任何信息的损失,但该方法不能提供基于对象的各因素的重要性大小,所以还需要提供先验的权重分配,必须借助于熵的概念,才能定量表达,熵是描述信息不确定性的度量。设X 是取有限个值的随机变量,p i =P X =x i ,i =1,2,n ,则X 的熵定义为H (X =ni =1p i log a1p i其中,底数a 为任

11、何正数,并规定当p i =0时,p i log a1p i=0。上述表达式即为Shannon 信息熵表达式。由此可见,信息熵是由事物内部属性客观决定的,如果能够用信息熵来确定权重,则能够保证权重的客观性。关于信息熵对确定权重的意义详见文献10,11。1.2算法的具体实现1.2.1经典模糊聚类的改进对目标函数的改进主要是在目标函数中引入权重,使目标函数能反映事物属性之间的轻重关系J (R ,V =n j =1ci =1r qi j d 2ij 其中 =(w 1,w 2,w m 644吉林大学学报(信息科学版第22卷1.2.2算法的具体步骤1据标准化处理,这里采用极大值标准化处理方法。2确定评价因

12、素的权重系数,形成权重向量。3对待评价对象的集合进行聚类。a 用阈值矩阵法对所有样本进行大致的分类:固定c 值,将所有样本进行初始化,c 即为评价结果论域中元素的个数;构造相似矩阵R =(r i j H H ,i =1,2,H ,j =1,2,H ,表示样本i 与样本j 的相似程度。样本之间相似程度可以用相似系数法、距离法和贴近度法来表示,这里选取贴近度法r i j =mk =1(x i k x jk /mk =1(x ik x jk 求出等价关系R *。通过平方计算法可以快速求得R *。依次求得R 2,R 4,R 8,R 2k,直到R 2k=R2k -1,则有R *=R 2k。采用截集矩阵法

13、进行分类。是R *中的隶属度,选择不同的隶属度使样本分为不同的c 类。b 在大致分类基础上,进行精确分类:对求得的分类采用平均值法计算出初始的聚类中心(V 01,V 02,V 0c ;根据公式对聚类中心进行修正;若满足结束条件,则迭代结束,否则回到。2算法的分析与验证该算法以综合评价工作的本质要求为突破点,根据综合评价工作的具体特点,采用了改进后的模糊聚类方法;针对模糊聚类与综合评价工作的不同,在算法中引入了由信息熵得到的权重向量,从而保证了算法的有效。笔者以1997年中国经济统计年鉴提供的统计数据为基础,采用基于模糊聚类和信息熵的综合评价算法对6个城市的经济指标进行综合评测。已知决策对象集A

14、 =a 1,a 2,a 3,a 4,a 5,a 6,分别为石家庄、苏州、武汉、乌鲁木齐、兰州、呼和浩特;指标集Z =z 1,z 2,z 3,z 10,其中,z -1表示土地面积,z 2表示年末总人口,z 10,表示职工平均工资,具体数据详见表1。表11997年全国6市主要经济指标Tab .1The main economic targets of six cities in 1997城市名称土地面积/km2年末总人口/万人国民生产总值/万元人均生产总值/元实现利税总额/万元固定资产投资完成额/万元出口总值/万美元实际利用外资/万美元财政总收入/万元职工均工资/元石家庄15848860.1978

15、1399891146529942981487125998291933842116256兰州13086280.462436800875716247410364863500087862319576578乌鲁木齐12000151.942169045144681115288992543699024654002767702武汉8467723.90912325612673640502408179794109453338541986406呼和浩特17224200.371287130647282713265964387930301539275195苏州8488574.991132594119713116756

16、5405176050439024472376538484431专家调查法得到的权重向量为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个城市

17、经济发展水平排行为:苏州、武汉、石家庄、兰州、乌鲁木齐、呼和浩特;4由信息熵理论得到的权重向量为0.017,0.05,0.06,0.03,0.17,0.18,0.23,0.21,0.043,0.01。1997年中国县域经济基本竞争力评价中心对这6个城市的经济发展水平的排行为:苏州、武汉、石家庄、乌鲁木齐、兰州、呼和浩特。通过和上面几种方法的计算结果比较,可以看出,多少都存在一645第6期张运凯,等:基于模糊聚类和信息熵的综合评价算法定出入:专家调查法得到的6个城市的排行中,发生了两对错误,即武汉和石家庄以及乌鲁木齐和兰州,可见该方法的实用性具有一定的局限性;比较矩阵法和Delphi 法由于对专

18、家的调查信息作了一定的数学处理,在对6个城市的排行中只发生了一对错误,即兰州和乌鲁木齐。而本算法将城市的经济发展水平分为3类:高、中、低,求得聚类的中心;根据上述6个城市与聚类中心的距离计算各个城市所属的类别,可以求得苏州的经济发展水平为“高”;武汉和石家庄的经济发展水平为:“中”;而乌鲁木齐、兰州和呼和浩特的经济发展水平为“低”;为了进一步区分,将武汉和石家庄到经济发展水平“中”的距离归一化,分别为:1和0.9166。乌鲁木齐、兰州和呼和浩特相应距离归一化为:1,0.9421和0.74444;综上所述,6个城市的排行为:苏州、武汉、石家庄、乌鲁木齐、兰州、呼和浩特。这个结果与“中国县域经济网

19、”(www .china -county .or g 的评价结果一致。3应用实例教师素质评测系统对学校而言,教师对学校教学水平的提高起了极其重要的作用。如何公正、科学的评价一个教师的图1教师素质评价的因素Fig .1The factors of the teach ability evaluating system综合素质,调动他们工作的积极性,对提高学校的教学水平乃至整个国家的教育水平都十分重要。该系统是模糊综合评价系统平台的一个实例,主要侧重于定量指标。教师综合素质评测的评测体系包括以下4个模块:信息采集、信息管理、系统维护、系统帮助。其中信息管理包括信息查询、信息统计、信息评价,信息评价

20、是本系统的核心部分。由于教师职业的基本特点是劳动者与劳动工具二者的统一,所以教师素质有以下几个特点:全面性、示范性、稳定性、再创性。鉴于此,该系统主要考虑的因素如图1所示。3.1新算法的应用3.1.1数据规格化度量单位的选取对于评价结果有很大影响。例如将身高的单位从米变为尺,将体重的单位从公斤变为磅将直接影响计算的结果。为了避免出现这种情况,必须将数据标准化,将数据中的单位“去掉”,为此采用平均数规格化。3.1.2确定评价要素及其权重根据实际要求确定:课堂教学、教学实践、获奖专利等11项为评价要素,其权重均为1/11。3.1.3对待评价对象的集合进行聚类1用阈值矩阵法对所有样本进行大致的分类:

21、c =5,将所有样本进行初始化,c 即为评价结果论域(优、良、中、及格、不及格中元素的个数;构造相似矩阵R =(r ij H H ,r i j ,i =1,2,H ;j =1,2,H ,表示样本与样本的相似程度,样本之间相似程度用贴近度法表示;求出等价关系R *;采用截集矩阵法进行分类。2在大致分类基础上,进行精确分类:对求得的分类采用平均值法计算出初始的聚类中心,(V 01,V 02,V 05;根据公式对聚类中心进行修正;若满足结束条件,则迭代结束,否则回到。3.2系统主要运行界面该系统主要侧重于对定量指标进行评价,通过综合评价模块的处理,将评价结果直观地反映出来,如图2,3所示。646吉林

22、大学学报(信息科学版第22卷 从图3可以直观地看出某个教师的综合素质评价结果,还可以知道所有教师的综合排名,方便教师了解自己的不足之处,以便及时改正,有助于整个教师队伍综合素质的提高。4结论综合评价方法在很多领域(如网络优化、教学、施工的决策研究、质量分析等方面都有广泛的应用。笔者提出了一个基于模糊聚类和信息熵的综合评价算法,具有操作简单,易于实现等优点,通过实验分析,该算法的评价结果更符合实际情况,具有良好的实用性,当评价指标很多时,该算法更具优越性。参考文献:1黄淑琴(HU ANG Shu -qin .公路路线方案的多级综合模糊评价(Fu zzy model for transp ort

23、pro ject app rais al J .中国公路学报(China Journal of Highway and Trans port ,1997,10(3:3744.2沈敏德,朱建公(SHEN M in -de ,ZH U Jian -gong .对机械传动设计方案模糊评价中几个问题的探讨(An appr och toso me pro blems of fu zzy evaluation for mechnaical transm iss ion concept J .西南工学院学报(Jou rnal of Southwest Ins titute of Technolog y ,1

24、998,13(4:4043.3张邦礼,尹朝东,曹龙汉(ZH ANG Bang -li ,YIN Chao -dong ,CA O Long -han .柴油机故障诊断中的遗传与模糊C -均值混合聚类分析算法(Clus tering by hybird genetic /C -means algor ithm in fault diagno sis for dies el engines J .计算机工程与应用(Co mputer Engineering and A pplicatio ns ,2002,38(3:254256.4ZA DEH L A .Fu zzy s ets J .Info rmation an d Control ,1965,8(3:338353.5R USPINI E H .Numerical metho ds fo r fu zzy clustering J .Information Science ,1970,2(3:319350.6TAM U RA S ,HIG UCHI S ,TANA KAK .Pattern clas sification based on fu zzy relations J .IEEE SM C ,1971,1(1:217242.7ZKIM LE .Fu zzy relation c