基于遗传算法的模糊聚类在高校绩效考核中的应用

2005年2月第28卷第1期北京邮电大学学报Jo urnal of Beijing U niv ersit y o f Posts and T eleco mmunicatio nsFeb.2005Vo l.28N o.1 文章编号:1007-5321(2005)01-0075-04基于遗传算法的动态模糊聚类郑　岩1,2,　黄荣怀2,　战晓苏3,　周春光4(1.北京邮电大学计算机科学与技术学院,北京100876;2.北京师范大学信息科学学院,北京100875;3.北京邮电大学电子工程学院,北京100876;4.吉林大学计算机科学与技术学院,长春130023)摘要:提出了一种基于遗传算法的动态模糊聚类方法.通过计算样本之间的模糊相似性,不失真地反映它们之间的内在关联.同时将样本之间的模糊相似性映射到样本之间的欧氏距离,即将高维样本映射到二维平面.利用遗传算法不断优化两者之间的映射,使样本之间的欧氏距离逐步趋近于其模糊相似性,实现动态模糊聚类.克服了聚类有效性对样本分布的依赖性;同时,增加了聚类的灵活性和可视化.该方法在性能上较经典的模糊聚类算法有一定改进,具有较好的聚类效果和较快的收敛速度.仿真实验结果证明了该方法的可行性和有效性.关　键　词:动态模糊聚类;模糊相似矩阵;遗传算法中图分类号:T P183 文献标识码:ADynamic Fuzzy Clustering Method Based on Genetic AlgorithmZHENG Yan1,2,　HUA NG Rong-huai2,　ZHA N Xiao-su3,　ZHOU Chun-guang4(1.Sch ool of Computer Scien ce and Techn ology,Beijing University of Pos ts and T elecom munications,Beijing100876,Chin a;2.S chool of Information S cience,Beijing Normal Univer sity,Beijing100875,Ch ina;3.Sch ool of E lectronic Engineer ing,Beijing University of Posts an d T elecommunications,Beijing100876,Ch ina;4.Sch ool of Computer Scien ce and Techn ology,J ilin University,Changchu n130023,Chin a)Abstract:A dynamic fuzzy cluster ing method is presented based on the genetic algo rithm.By calculating the fuzzy similarity betw een sam ples the essential associations amo ng samples are modeled factually.T he fuzzy similarity between tw o samples is mapped into their Euclidean distance,that is,the high dim ensio nal samples ar e mapped into the tw o dimensional plane.T he mapping is o ptimized glo bally by the g enetic alg orithm,w hich adjusts the coo rdinates of each sam ple,and thus the Euclidean distance,to approx imate to the fuzzy similarity betw een samples gradually.A key advantag e o f the proposed method is that the clustering is independent of the space distr ibutio n of input samples,w hich im pr oves the flexibility and v isualization.T his metho d po ssesses char acteristics o f faster co nverg ence rate and more exact clustering results than some typical clustering algo rithms.Simulated ex perim ents sho w the feasibility and availability of the pr opo sed method.Key words:dynamic fuzzy clustering;fuzzy sim ilar ity matrix;g enetic alg orithm收稿日期:2003-10-28基金项目:国家自然科学基金项目(60175024);教育部科学技术研究重点项目(02090)作者简介:郑　岩(1970—),女,副教授,博士后,硕士生导师,E-mail:yanz hen g@.黄荣怀(1965—),男,教授,博士,博士生导师,E-mail:huangrh@b . “物以类聚”深刻揭示了聚类的本质.聚类是依据事物的某些属性将其聚集成类,使类间相似性尽量小,类内相似性尽量大,是一种无监督的模式识别问题.传统的聚类方法如模糊c-均值聚类(FCM)[1]和c-均值聚类等,都是直接利用样本进行聚类,没有进行相关的预处理,其有效性在很大程度上取决于样本的分布情况[2].例如,c-均值聚类对于特征空间呈超球体的情况聚类效果较好[3],而对于呈任意形状簇分布的情况则聚类效果较差.为此,笔者提出了一种基于遗传算法的动态模糊聚类方法,旨在实现分布呈任意形状簇的样本聚类.该方法既克服了聚类有效性对于样本分布的依赖性,又增加了聚类的灵活性和可视化.首先,对样本进行降维预处理,通过构造模糊相似矩阵,直观地反映各样本之间的内在关联,将高维样本映射到二维平面.然后,利用遗传算法(GA)对初始时随机分布在平面内各聚类样本的坐标值进行全局优化,使样本之间的欧氏距离逐步趋近于它们之间的模糊相似性,实现动态模糊聚类.GA是一种全局搜索算法[4],而FCM和c-均值聚类算法,本质上是一种局部搜索算法,收敛于部分最优,容易陷入局部极小值[5,6],对于聚类样本数量较大的情况尤为明显.本文提出的方法在性能上较经典聚类方法有一定改进,聚类更准确,收敛时间较快.仿真实验验证了其有效性和可行性.1　基于遗传算法的动态模糊聚类1.1　建立模糊相似矩阵模糊相似矩阵用于存储各样本之间的相似性度量.建立模糊相似矩阵的方法有多种,常用的有数量积法、夹角余弦法、最大-最小法和算术平均法等.建立模糊相似矩阵,必须对样本进行标准化处理,压缩到[0,1]区间内.设样本空间,X={x1,x2,…,x n},P x i∈X,其特征矢量为x i=(x i1,x i2,…, x ip),x ik表示第i个样本的第k个特征属性.记n个样本第k个特征属性的平均值和标准方差分别为L k=1n ∑ni=1x ik(1)R k=1n ∑ni=1(x ik-L k)2(2)则原始样本可标准化为x′i k=(x ik-L k)/R k(3)利用极值标准化公式进行规一化,即y ik=x′i k-x′m in kx′m ax k-x′m in k(4)其中x′m ax k和x′m in k分别为x′1k,x′2k, (x)n k中的最大值和最小值.模糊相似矩阵(r ij)nn是一个n×n维的对角线元素为1的对称矩阵,即1r211r31r321……………r n1r n2 (1)(5)其中r ij代表样本i和样本j之间相似性的量化表示.通常,它是一个非负的数值.样本i和样本j越相似或“接近”,r ij的值越接近1;否则,其值越小.采用夹角余弦法计算,即r ij=∑pk=1y ik y j k∑pk=1y2ik∑pk=1y2jk(6)1.2　映射优化准则构建模糊相似矩阵之后,可将高维样本映射到二维平面.通过遗传算法对各个样本的坐标值进行迭代优化,使各样本间的欧氏距离趋近于模糊相似性.因此,遗传算法的误差函数定义为E=12n∑ni=1∑nj=iûr′i j-r ijû(7)其中,r′i j表示映射到二维平面的样本i和j之间的欧氏距离.设样本i和j的坐标值分别为(a i,b i)和(a j,b j),i=1,2,…,n,j=1,2,…,n,则r′i j为r′i j=(a i-a j)2+(bi-b j)2(8)误差函数值越小,个体的适应度越高,因此个体适应度函数定义为f=1E+a(9)其中,为了避免适应度函数值过大,取a= 1.1.3　基于遗传算法的动态模糊聚类基于遗传算法的动态模糊聚类方法描述如下:¹初始化.将待聚类样本随机分布在二维平面的一定区域内,即随机赋给每个样本一对坐标值(a i,b i),其中a i,b i∈[0,1],i=1,2,…,n.º建立模糊相似矩阵.利用式(1)～(6)建立模糊相似矩阵(r ij)nn.76北京邮电大学学报第28卷　»形成初始群体.将每个样本的一对坐标值(a i ,b i )作为一个基因,采用8位二进制编码,共有n 个基因,将所有基因链接起来构成一个染色体(又称为个体),则染色体长度L =8n 位.按照不同的基因排列次序,可生成N 条染色体,构成初始群体S .¼计算适应度.利用式(7)计算出每一个体的误差函数值,然后根据式(9)计算其适应度.½选择父本.采用roulette w heel 选择与最优保持策略相结合的方法.首先选择群体中适应度值最大的个体作为一个父本.然后,计算其余每个个体的选择概率p k =fk∑Nm =1f m 以及累计概率q i =∑ij =1pj,产生一个[0,1)区间的均匀随机数r ,若r <q 1,则选择第一个个体;否则若k 满足q k -1≤r <q k ,则选择个体k ,旋转M -1次,即可选择出M 个个体,构成子群体S ′,S ′<S .¾随机地将S ′中的个体两两配对.¿交叉操作.S ′中的每对个体产生[0,1]之间的随机数r ,若r <p c (p c 为选定的交叉概率),则进行交叉操作.随后,产生[1,8n ]之间的随机数以确定交叉的位置,交叉后的新染色体构成子群体S ″.À变异操作.对S ″中的每一个体的每一位产生[0,1]之间的随机数r ,若r <p m (p m 为变异概率),则该位变异.Á计算S +S ″中所有个体的适应度,并淘汰掉适应度较小的M 个个体,形成新一代群体S .b k终止操作.若新一代群体S 中个体的适应度值满足给定的终止条件,即适应度值小于E (E 取值为0.01),解码后得到求解;否则,转至½.遗传算法本身是一种并发的全局优化算法,通过各种遗传算子实现信息传递,并逐渐趋近于全局最优解.此外,通过引入最优保持策略以及将高维样本映射到二维空间的降维预处理,可使本文提出的方法较FCM 算法的迭代次数大大减少.2　仿真实验为了验证所提出方法的有效性和可行性,对U CI 机器学习数据库中有关酒的测试数据集1)进行了仿真实验,如表1所示.表1　酒类样本数据编号属　性12345678910111213114.23 1.71 2.4315.6127 2.80 3.060.28 2.29 5.64 1.04 3.921065213.20 1.78 2.1411.2100 2.65 2.760.26 1.28 4.38 1.05 3.401050313.16 2.36 2.6718.6101 2.80 3.240.30 2.81 5.68 1.03 3.171185414.37 1.95 2.5016.8113 3.85 3.490.24 2.187.800.86 3.451480……………………………………17713.17 2.59 2.3720.0120 1.650.680.53 1.469.300.60 1.6284017814.134.102.7424.5962.050.760.561.359.200.611.605601)http:∥/～mlear n/M LRepo sitory.html 该测试数据集样本个数为178,条件属性个数为13,聚类类别为3.类别1、2和3所包括的样本数分别为59、71和48.初始时,样本的随机分布情况如图1所示.采用提出的新方法,经过80次迭代,取种群规模N =150,变异概率p m =0.5,交叉概率p c =0.2,则动态模糊聚类结果如图2所示.与FCM 算法相比,新方法其聚类正确率高于FCM 算法,收敛速度较FCM 算法快,比较结果如表2所示.图1　样本在二维平面的随机分布77　第1期郑　岩等:基于遗传算法的动态模糊聚类图2　动态模糊聚类结果表2　2种模糊聚类算法的比较算法迭代次数正确率类别1类别2类别3FCM 15090%92%100%本文方法8093%98%100%3　结　论传统聚类方法的有效性依赖于样本的分布情况,若样本界限分明,则聚类效果好.但是实际情况往往是样本分布呈任意形状簇.对于这类情形,已有的方法效果不佳.本文提出的基于遗传算法的动态模糊聚类方法,通过遗传算法和模糊相似矩阵将高维样本映射到二维平面,迭代优化各样本的坐标值,使样本之间的欧氏距离逐步趋近于它们之间的模糊相似性,最终得到全局最优解,动态实现模糊聚类.仿真结果表明,该方法在性能上较经典的模糊聚类算法有一定改进,不依赖于样本特征空间的分布 情况,具有更准确的聚类能力和较快的收敛速度.参考文献:[1]　黄凤岗,宋克欧.模式识别[M ].哈尔滨:哈尔滨工程大学出版社,1998.Huang Fengg ang ,So ng K eo u.Pat tern reco gnition [M ].Harbin :Har bin Engineer ing U niv ersity Pr ess ,1998.[2]　张莉,周伟达,焦李成.核聚类算法[J].计算机学报,2002,25(6):587-590.Zhang L i ,Zho u Weida ,Jiao L icheng .A ker nel cluster ingalgo rithm [J ].ChineseJo urnalofComputer s,2002,25(6):587-590.[3]　高新波,谢维信.模糊聚类理论发展及应用的研究进展[J ].科学通报,1999,21:2241-2251.G ao Xinbo ,Xie W eix in.Aresear ch o n fuzzycluster ing theor y and it s applications [J ].Science Bulletin ,1999,21:2241-2251.[4]　Holland J H .A daptation in natural and art ificialsystem [M ].A nn A rbor :U niv ersity of M ichigan Pr ess,1975.[5]　K amel S M .N ew algo rithms fo r so lving the fuzzy c -means clustering pr oblem [J].Patt ern Recog nitio n,1994,27:421.[6]　赵艳厂,谢帆,宋俊德.一种新的聚类算法:等密度线算法[J ].北京邮电大学学报,2002,25(2):8-13.Zhao Y anchang ,Xie F an,Song Junde.DIL C:acluster ing alg or ithm based on densit y-isoline [J ].JournalofBeijingU niver sityo fP ostsandT elecommunications ,2002,25(2):8-13.简　讯学报工作会顺利召开2004年12月20～21日召开了建校以来的第一次以学报工作为主题的工作会,王德宠书记和林金桐校长出席了会议并讲话.校学术委员会主任钟义信教授做了报告.会议由学术委员会办公室主任冯中主持,《北京邮电大学学报》自然版、社科版的全体编委,《中国邮电高校学报》的北邮编委、各学院主管科研的院长和教务处、研究生院、人事处、宣传部的领导出席了会议.与会代表经过热烈地讨论,明确了学报的定位,确立了奋斗目标.78北京邮电大学学报第28卷　。

基于模糊聚类的综合评价方法研究综合评价是一个重要的决策，用于评估一个系统或事物的整体表现。

在现实生活中，一些系统或事物的评价很难通过单个指标来进行量化，需要多个因素综合考虑。

因此，基于模糊聚类的综合评价方法成为了一种很有用的解决方案。

本文将介绍模糊聚类和基于模糊聚类的综合评价方法。

一、模糊聚类模糊聚类是一种基于概率的聚类分析方法，通过将样品分组成为多个簇，以表征它们在某些方面上的相似性。

不同于传统聚类方法，模糊聚类将样品分配组的界限模糊化，相比之下，样品可能同时属于多个组。

模糊聚类通过基于欧几里得距离或曼哈顿距离的相似度进行计算，并在每一轮迭代中生成一个簇的质心。

该簇质心会在下一轮迭代中被用作识别新簇的起始点。

在这种方法中，首先需要确定评价因素和其对应的因素指标。

然后，对每个因素指标进行标准化处理，以消除不同维度之间的单位差异。

接下来，将标准化后的每个因素指标作为输入变量，进行模糊聚类分析。

利用聚类结果，可以将各个因素指标分为不同的模糊子集，从而表达出对系统或事物综合表现的不同评价。

最后，需要针对聚类结果进行后处理，以得出最终的综合评价。

一种经典的方法是通过为每个评价因素的某个指标分配一个权重，并对每个指标进行加权求和来得出综合评价。

三、结论基于模糊聚类的综合评价方法是为多因素评价提供了一种强大的工具。

该方法将聚类分析与综合评价较好地集成在了一起，不仅可以避免了传统评价方法中存在的局限性，而且可以为决策者提供更全面的信息，从而更好地帮助他们做出正确的决策。

当然，该方法也存在一些缺陷，例如在多变量和混合模式条件下的精度和可解释性有局限性，需要在具体应用中进一步改进。

基于改进遗传算法的模糊聚类研究及应用朱长江;柴秀丽【摘要】Fuzzy C-means clustering algorithm is an iterative hill-climbing technique for the local search algorithm, due to the sensitive dependence on initial conditions and easy to fall into the local minimum. Genetic algorithm is a global optimization algorithm, can overcome the fuzzy C- means clustering algorithm to fall into the local minimum problem, but the genetic algorithm has slow convergence, premature convergence. Application of niche theory on genetic algorithm improvements, design based on shortest distance arithmetic crossover operator, mutation operator, boundary double elite seed in evolutionary strategy, in order to protect the population genetic diversity. The simulation results show that, the improved algorithm can improve the convergence speed of fuzzy clustering and clustering quality.%模糊C-均值聚类算法是一种局部搜索算法,采用迭代的爬山技术,对初值敏感易陷入局部最小值.遗传算法是一种全局优化算法,能够克服模糊C-均值聚类算法陷入局部最小值的问题,但遗传算法收敛速度慢,易早熟.应用小生境思想对遗传算法进行了改进,以保护种群中基因的多样性,设计了基于最短距离的算术交叉算子、边界变异算子及双精英种子参与进化的策略.仿真实验结果表明,改进后的算法能够提高模糊聚类的收敛速度和聚类质量.【期刊名称】《科学技术与工程》【年(卷),期】2013(013)010【总页数】5页(P2863-2866,2870)【关键词】模糊聚类;遗传算法;小生境;试卷分析【作者】朱长江;柴秀丽【作者单位】河南大学计算机与信息工程学院,开封475004【正文语种】中文【中图分类】TP301.6模糊聚类以Zadeh提出的模糊集理论［1］为基础，描述了样本在性态和类属方面存在着不确定性，能够客观地反映现实世界，已经成为聚类分析研究的热点。

模糊聚类分析和模糊综合评价法[1]在独立学院评估中的应用摘要本文基于客户——学生满意的视角,在借鉴非营利组织绩效评价指标要素、我国大学综合竞争力评价指标体系以及我国高职教育评价指标体系基础上，构建了独立学院绩效评价指标体系，包括办学设施、人才培养、综合声誉三个一级指标。

本文首先对10所独立学院的三个一级指标进行模糊综合评价，并分别给出这十所高校的排名，然后利用模糊聚类分析法进行聚类, 最后结合排名给出每一个学校的类型，为独立学院的未来办学思路提供了一些建议，最后并给出Matlab 的程序算法。

关键词：综合评价；模糊聚类；指标体系1、引言独立学院是由普通本科高校（申请者）与社会力量（合作者，包括企业、事业单位，社会团体或个人和其他有合作能力的机构）合作举办的进行本科层次教育的高等教育机构。

国家规定，申请者要对独立学院的教学和管理负责，并保证办学质量；合作者要负责提供独立学院办学所需的各项条件和设施，参与学院的管理、监督和领导。

独立学院应具有独立法人资格，独立的校园校舍，独立进行教学和财产管理、招生和颁发毕业证书。

由于独立学院属于本科层次，所以由教育部负责审批。

对于国家设立的普通高等院校，我国已经形成了较为完善的政府评价制度，但针对独立学院的教育评价指标尚未出台。

本文首先根据一级指标进行模糊综合评价，并对十所高校进行排名，最后运用聚类分析法进行聚类，将十所高校分为五类。

2、研究方法 2.1模糊综合评价法模糊综合评价的基本步骤如下： （1）确定因素集...{,,3,2,1u u u u n U =（2）确定评判集}...{,2,1v v v m V =（3）求出模糊评价矩阵，其中)(ij r R =表示方案X 的第i 个目标u i 处于第j 级评语v j 的隶属度，当对多个目标进行综合评价时，还要对各个目标分别加权，设第i 个目标权系数为a i ，则可得权系数向量： A ＝（n a a a a ...,3,2,1）（4）综合评判：对于权重A=（n a a a a ...,3,2,1)∈F(U),用模型),(∨∧M 取最大最小合成运算，可以得到综合评价B=A*R 2.2模糊聚类分析法聚类分析的职能：建立一种分类方法，它是将一批样品或变量，按照它们在性质上的亲疏程度进行分类。

基于模糊聚类算法的教学质量评价体系研究毕业论文目录摘要 .............................................................................................. 错误！未定义书签。

Abstract........................................................................................... 错误！未定义书签。

目录 .. (I)第1章绪论 (1)1.1研究背景及意义 (1)1.2国内外研究现状 (2)1.3本文的研究思路 (4)1.4 本章小结： (5)第2章聚类与模糊聚类 (6)2.1聚类分析的基本概念 (6)2.1.1聚类的定义 (7)2.1.2相异度的度量 (7)2.1.3聚类特征的描述 (9)2.2聚类算法 (9)2.2.1聚类算法概述 (9)2.2.2系统聚类法 (10)2.2.3 k-平均算法 (13)2.3模糊理论与模糊聚类 (14)2.3.1模糊集合理论 (14)2.3.2模糊集合的表示 (15)2.3.3模糊聚类 (15)2.4 FCM算法 (16)2.4.1 FCM算法简介 (16)2.4.2算法过程描述 (17)2.4.3 FCM算法的优势 (18)2.5 本章小结： (18)第3章教学质量评价体系 (19)3.1模糊综合评判法 (19)3.1.1二级模糊综合评判法的数学模型 (19)3.1.2使用模糊综合评判法的评价模型 (20)3.1.3计算因素和二级得分以改进模型 (21)3.1.4模型实现示例 (22)3.2基于聚类的教学质量评价模型 (23)3.2.1使用聚类算法改进模糊综合评判法 (23)3.2.2模型构建 (24)3.2.3模型实现示例 (25)3.3教学质量评价模型的改进思路 (25)3.4本章小结： (26)第4章模糊聚类算法实现 (27)4.1什么是java语言： (27)4.1.1起源： (27)4.1.2组成： (27)4.1.3体系： (28)4.1.4优势 (28)4.2运行环境及配置： (28)4.3代码编写： (29)4.4 本章小结 (32)结论及建议 (34)致谢 (36)参考文献 (37)第1章绪论1.1研究背景及意义首先我们来了解什么是教学质量。

《基于遗传算法和模糊聚类的目标识别技术研究》一、引言随着计算机视觉技术的飞速发展，目标识别技术在众多领域中得到了广泛应用。

遗传算法和模糊聚类作为两种重要的优化和聚类技术，其与目标识别技术的结合，能够显著提高识别的准确性和效率。

本文将重点探讨基于遗传算法和模糊聚类的目标识别技术研究，通过分析和研究两种算法的特点及其在目标识别中的应用，以期为相关领域的研究和应用提供理论和技术支持。

二、遗传算法及其在目标识别中的应用遗传算法是一种基于生物进化原理的优化算法，其通过模拟自然选择和遗传机制，实现对问题的全局优化。

在目标识别中，遗传算法主要用于优化分类器的参数和特征选择。

通过设置适当的适应度函数，遗传算法可以在大量可能的参数和特征组合中寻找到最优的组合，从而提高目标识别的准确性和鲁棒性。

具体而言，遗传算法通过种群初始化、选择、交叉和变异等操作，不断产生新的个体，并通过适应度函数对个体进行评价和选择。

在目标识别中，可以将分类器的参数或特征组合看作个体，通过遗传算法的优化过程，找到最适合目标识别的参数和特征组合。

三、模糊聚类及其在目标识别中的应用模糊聚类是一种基于模糊数学理论的聚类方法，其通过引入模糊性概念，实现对数据的软划分。

在目标识别中，模糊聚类主要用于对图像或特征进行聚类分析，从而实现对目标的识别和分类。

模糊聚类通过计算数据之间的相似性或距离，将数据划分为不同的聚类，每个聚类代表一个潜在的目标。

在目标识别中，可以利用模糊聚类分析图像或特征的空间分布、颜色、纹理等特性，从而实现对目标的准确识别和分类。

四、基于遗传算法和模糊聚类的目标识别技术将遗传算法和模糊聚类相结合，可以实现对目标识别的进一步优化。

具体而言，可以利用遗传算法优化模糊聚类的参数和规则，从而提高聚类的准确性和效率；同时，可以利用模糊聚类对图像或特征进行预处理和分析，为遗传算法提供更准确的适应度评价依据。

在实际应用中，可以将这两种算法进行融合和优化，形成一种基于遗传算法和模糊聚类的目标识别系统。

聚类方法在高等学校绩效评价中的应用[摘要] 高等学校都试图构建绩效评价体系,增强本校的竞争力和综合实力。

本文以绩效评价、平衡计分卡等理论为指导,借鉴国内外高校绩效评价的经验,建立了高等学校绩效评价指标体系, 指标体系综合考虑高等学校的财务绩效、办学效果、内部管理、学习与成长等4个方面。

并且通过建立的指标体系,应用聚类挖掘方法,分别横向和纵向分析了教育部直属的72所高校2002-2006年的绩效评价指标数据,指出高等学校绩效评价分析系统中存在的问题,评价结果的信息主要用于帮助各级管理人员迅速获得高校运行的准确信息,在没有限定类别的情况下,运用数据挖掘的聚类方法把评价指标相似的学校划分到一个类中,对高等学校进行聚类评价,为分析使用提供依据,以期构建一个有利于高等学校绩效评价的决策支持环境。

[关键词] 高等学校;绩效评价;聚类1引言随着经济的全球化和信息化,人力资源流动加快,人才竞争空前激烈,社会对高等学校要求的改变也促使高校进行资源的内部整合以实现人才培养和科技创新的社会服务目标。

而高等学校资源整合的关键是调动员工积极性,形成团队合作、鼓励创新的学校文化和氛围,因此,高等学校试图通过构建绩效评价体系来反映教育与研究的组织目标。

本文试图在绩效评价研究与实践探索的基础上,分析目前各国教育行业的指标体系,结合平衡计分卡与关键绩效指标的原理,建立高等学校绩效评价指标体系。

绩效评价方法应将定性评价与定量评价有机组合,但定量指标设定要避免生硬的量化所导致的绩效评价对高等学校的师资队伍工作热情的消极影响,定性指标衡量要避免缺乏客观依据。

本文应用数据挖掘的聚类分析方法进行大量的数据分析,分别横向和纵向分析了教育部直属的72所高校2002-2006年的绩效评价指标数据,在没有限定类别的情况下,把有相似性的学校划分到一个类中,找出高校之间存在的差距及问题,分析影响结果的评价指标,为领导决策提供强有力的依据,提高学校工作质量和改善组织绩效[1]。

收稿日期:2004205230.作者简介:许松荣(19792),男,硕士研究生;厦门,厦门大学计算机与信息工程学院(361005).E 2mail:xsr abc@基于遗传算法的模糊聚类方法许松荣(厦门大学计算机与信息工程学院,福建厦门361005)摘要:针对模糊c 2均值算法容易收敛于局部极小点的缺陷,将遗传算法应用于模糊c 2均值算法的优化计算中.算法采用实数编码,提高了试验精度.实验证明基于遗传算法的模糊聚类方法能够在一定程度上克服初值的影响,跳出局部极小点,在大样本的聚类方面有较大的优势.关 键 词:聚类;模糊c 2均值算法;遗传算法中图分类号:TP391 文献标识码:A 文章编号:167124512(2004)S120217203The fuzzy clustering method based on genetic arithmeticXu SongrongAbstr act:This paper applies genetic arithmetic to optimization of the fuzzy c 2mean arithmetic since the fuzzy c 2mean arithmetic has the limitation of converging to the local infinitesimal point.The arithmetic adopts the real code and thus increases the precision of the experiments.The experiments prove that the fuzzy c 2means arithmetic based on genetic arithmetic can overcome the influence of initial values and possess the predominance in the clustering of huge samples.Key words:clustering;fuzzy c 2mean arithmetic;genetic arithmeticXu Songr ong Postgraduate;Computer &Information Engineering College,Xiamen U niversity.Fujian,Xiamen 361005,China. 聚类[1]是根据数据的不同特征,将其划分为不同的数据类.聚类的目的是使得属于同一类别的个体之间的距离尽可能地小,而不同类别上的个体间的距离尽可能地大.聚类方法包括统计方法、机器学习方法、神经网络方法等.模糊聚类方法具有简便易行,聚类效果较好的优点,在实际应用中获得广泛的运用.但是普通的模糊聚类易于陷入局部极小点而不能搜索到全局的聚类中心.而遗传算法作为一种新型的进化优化算法,可以概率地在状态空间搜索最佳点,特别适合于非线性多峰值的函数优化问题.1 普通的模糊聚类方法模糊聚类是将样本空间X ={x 1,x 2,,,x n }的样本点分成c 类,任意一个样本点x i I X 几乎不可能被严格地划分给某一类,定义样本点x i 属于第j (1[j [c)类的程度w ij (0[w i j [1).样本空间X 的模糊聚类用模糊矩阵W =(w ij )描述,元素w ij 是矩阵W 的第i 行第j 列元素,代表第i 个样本点隶属于第j 类的隶属度.W 具有以下性质:w ij I [0,1];(1)E c j=1w ij =1;(2)0<E n i =1w ij <n.(3)为了计算各个样本点相对于聚类中心的隶属度,一般采用FCM 算法.定义目标函数:J m (W ,Z )=E ni =1E cj =1w ij d 2ij (x i ,z j ),Z =(z 1,z 2,,,z c ),其中z j 表示第j 类的聚类中心,d 2ij (x i ,z j )=+x i -z j +是样本点x i 到聚类中心z j 的欧氏距离.聚类即是求目标函数在式(1)~(3)约束下的第32卷增刊 华 中 科 技 大 学 学 报(自然科学版) Vol.32 Sup.2004年 10月J.Huazhong Univ.of Sci.&Tech.(Nature Science Edition)Oct.2004最小值.FCM 算法通过对目标函数的迭代优化来取得对样本集的模糊分类.具体算法参见文献[2].该算法对初值敏感,很大程度上依赖初始聚类中心的选择,当初始聚类中心严重偏离全局最优聚类中心时,用FCM 很可能陷入局部极小值.当聚类数目较大时,该缺点更为明显.2 基于遗传算法的模糊聚类方法遗传算法[3]是基于/优胜劣汰、适者生存0的一种高度并行、随机和自适应的全局优化算法.它从某一随机种群出发,按照一定的操作规则,根据每一个个体的适应度,存优去劣,引导搜索过程向最优解逼近.遗传算法不要求连续、可微等条件,具有较强的鲁棒性.对于所定义的目标函数,聚类问题即是求满足式(1)~(3)的W 和Z ,使得目标函数值最小,这实际上是一个优化的问题.用遗传算法求解,主要考虑以下因素[4]:染色体编码、个体适应度评价、遗传算子(选择算子、交叉算子、变异算子)以及遗传参数设置等.2.1 染色体编码方法设n 个样本被分成c 类:Z 1,Z 2,,,Z c ,模糊分类矩阵W =(w ij )共有n @c 个元素.这里采用实数编码方案[5,6].一个染色体可以被编码成为:[z 1z 2,z c w 11w 12,w 1c w 21w 22,w 2c ,w n 1w n 2,w nc ].2.2 始化群体的生成当聚类个数c 给定时,随机选取聚类中心并随机生成w ij 组成模糊矩阵W .2.3 适应度函数用适应度函数模拟自然选择,评价染色体的相对优劣程度,由此决定各种遗传操作.个体以J m (W ,Z )为目标函数值,J m (W ,Z )越小,个体的适应度就越高.取f i =1/J m (W ,Z )作为第i个个体的适应度,总的适应度为F =E cj =1f i ,平均适应度为 f =f i /F.2.4 选择选择操作建立在对个体的适应度评价的基础上,用来将父代中的优秀个体保存到下一代.常用的选择操作有轮赌盘选择、余数选择法、保留最佳个体等.这里采用期望值选择法.a .计算群体中每个个体在下一代生存的期望数目N i =f i / f .b .若某个个体被选中并要参与配对和交叉,则它在下一代的期望数目减去0.5;若不参与配对和交叉,则该个体的生存期望数目减去1.c .在上面两种情况中,若一个个体的期望值小于0,则该个体不参与选择.2.5 交叉交叉用于组合新个体,使子代继承父代优秀基因.a .对每个个体产生[0,1]的随机数r ,若r <p c ,则该个体参加交叉操作,选出交叉操作的一组染色体后进行随机配对.b .对每一对染色体X 、Y,产生(0,1)之间的随机数e.c .做如下交叉运算:X z e X +(1-e )Y,Y z e Y +(1-e)X.2.6 变异变异用来保持种群的多样性.这里变异操作分为两个部分.首先对染色体的前c 位基因进行变异操作.a .产生随机数r ,若p m <r ,则进行变异操作.b .产生随机正整数h (1[h [c/2).c .产生h 个随机正整数t 1,t 2,,,t h ,对第t i 位基因产生随机数,代替原来的基因.d .若前c 位发生重复,则对重复的基因再进行变异.然后对染色体第c 位后的基因(记做Z )进行变异操作.a .产生(0,1)之间的随机数A .b .产生nc 维随机向量V =[v 1v 2,v nc ],v i I [0,1].c .做变异Z z Z +A V.2.7 合法性检查遗传操作可能产生非法的个体,要对产生的非法个体进行修正.修正的规则如下:a .如果w ij >1或w ij <0,则w ij =0.5.b .如果E cj =1w ij >1,且所有w ij 都相同,则令w ij =1/c,j =1,2,,,c;否则,令w ik =max (w i 1,w i 2,,,w i c ),于是w ik =1-E c j =1,j X kw ij ,j =1,2,,,c.c .如果E cj =1w ij <1,且所有w ij 都相同,则令w ij =1/c,j =1,2,,,c;否则,令w ik =min (w i 1,w i 2,,,w ic ,于是w ik =1-E cj =1,j X kw ij ,218 华 中 科 技 大 学 学 报(自然科学版) 第32卷j =1,2,,,c.d .如果E ni =1w ij \n,则w ij z 0.5,i =1,2,,,n.3 实例应用基于遗传算法的模糊c 2均值算法对二维数据集进行聚类.图1(a)为聚类样本.初始种图1 聚类样本和聚类结果群300,最大进化世代数500,p c =0.2,p m =0.05.运算结果为J =2.619.聚类中心为(0.749,0.218)和(0.234,0.238).图1(b)为聚类结果.参考文献[1]张红云,刘向东,段晓东等.数据挖掘中聚类算法比较研究.计算机应用与软件,2003(2):5~6[2]李洪兴,汪培庄.模糊数学.北京:国防工业出版社,1994.[3]褚蕾蕾,陈绥阳,周 梦.计算智能的数学基础.北京:科学出版社,2002.[4]史忠植.知识发现.北京.清华大学出版社,2002.[5]张 维,潘福铮.一种基于遗传算法的模糊聚类.湖北大学学报,2002(2):101~104[6]王 敞,陈增强,袁著祉.基于遗传算法的K 均值分析.计算机科学,2003(2):162~164219增刊 许松荣:基于遗传算法的模糊聚类方法。