基于佳点集遗传算法的模糊聚类技术

1、合肥工业大学学报(自然科学版D第28卷第4期Vol.28No.4J0URNAL0FEFEIUNIVERSITY0FTECN0L0GY2005年4月Apr.2005=基于佳点集遗传算法的模糊聚类技术苏守宝摘陈明华237012D(皖西学院计算机科学与技术系 安徽六安要:文章提出了2种基于佳点集遗传算法的模糊聚类新方法GgaFca和GgaFcaOGgaFca可用于发现指定簇数(cD的聚类中心 具有对初始输入不敏感收敛快精度高并可避免早熟的特点;而混合方法GgaFcm是利用传统模糊c-均值(FcmD聚类算法对GgaFca聚类结果的进一步提炼 实验结果表明它具有更好的聚类效果和综合性能 可适用于不同数据

2、库下的模糊聚类挖掘研究O关键词:模糊聚类;佳点集;遗传算法;模糊C-均值文献标识码:A中图分类号:TP18;TN911.72文章编号:1003-5060(2005D04-0402-05Fuzzyclusteringtechniguesbasedongoodpoint-setgeneticalgorithmSUShou-baoCENMing-hua(Dept.ofComputerSciencegTechnology WestAnhuiUniversity Lu an237012 ChinaDAbstract:TWoneWfuzzyclusteringapproaches GgaFcaandGga

3、Fca areproposedbasedonthegoodpoint-setgeneticalgorithm.ItisshoWnhoWGgaFcacanbeusedtofindthecentroidofauserspecifiednumber(cDofclusters Whichischaracterizedbyinferiorsensitivitytoinitialinput guickconvergence higheraccuracyandremovalofpremature.Thehybridalgorithm GgaFca basicallyusesfuzzyc-means(FcmD

4、clusteringalgorithmtorefinetheclustersformedbyGgaFca.TheexperimentresultsshoWbycomparisonthatthehybridalgorithm GgaFca hasbettergeneralperformanceandcanbeappliedtovariousdatabasesforclusteringdataindatamining.KeyWords:fuzzyclustering;goodpoint-set;geneticalgorithm;fuzzyc-means(FCMD大树法基于数据集的凸分解法基于目标函

5、数法基于等价矩阵与目标函数结合的摄动模糊聚类方法动态规划难以辨识关系法编网法以及模糊c-均值方法等13 其主要思想是将经典划分的定义模糊化O模糊聚类分析能够从研究对象的特征数据中挖掘出关联规则 因而被广泛地应用于模式识别数据挖掘生物工程及信息科学等许多领域O模糊划分的思想由Ruspini首先提出 Dunn将其用于基于目标函数最小化的模糊聚类方法 Bezdek通过使用模糊隶属度加权指数m 将之推引言聚类分析是指按照事物间的相似程度对事物进行区分和分类的过程 在这一过程中没有任何关于分类的先验知识没有教师指导 是一种无监督的学习方法(unsupervisedlearningDO很多聚类分析方法是实

6、现对数据对象的 硬划分 但是 客观事物的类属往往并不十分明确 自从Zedeh提出了模糊集理论以来 人们不断地提出模糊聚类分析算法 如基于模糊等价关系的传递闭包法基于相似性关系和模糊关系法基于模糊图论的最收稿日期:2004-07-05;修改日期:2005-01-09基金项目:安徽省高校自然科学研究资助项目(2005kj095D作者简介:苏守宝(1965-D 男 安徽六安人 硕士 皖西学院副教授;陈明华(1954-D 男 浙江鄞县人 皖西学院教授.第4期苏守宝 等 基于佳点集遗传算法的模糊聚类技术V的计算如下Uzk=40广为一种模糊c 均值聚类算法(F ) F 的应用最为广泛 但其本质上仍是一种基

7、于划分准则的局部搜索算法 它采用了迭代的爬山技术来寻找最优解 存在着对初始化敏感和容易陷入局部极小的致命缺点理节省了时间Ik Uznm 16j=1nIk Ujm 1z=1 2 - 6;k=1 2 - nUz=( )采用神经网络技术试图克服其耗时的缺点 而神经网络虽然以其并行处(Uk=1zk)Ik (Uzk)mk=1m但本质上还是基于梯度下降的学习算法 仍然没有解决对初始敏感的问题 也就很难获得全局最优解 遗传算法(GA)是一种随机z=1 2 - 6(4)(4)式的反复迭代 当F 算法通过对(J2(UV)或Jm(UV)收敛到极小时 就得到了最全局寻优方法 具有简单通用鲁棒性强和适于并行处理的特点

8、 利用遗传算法可降低传统模糊聚类算法对初始化的要求 8 但其收敛效率也限制了算法的实用性本文改造了佳点集遗传操作 提出了一种利用佳点集GA 9 进行模糊聚类的新算法GgaFca 不仅具有对初始数据的弱依赖性 而且具有收敛快聚类效果好以及可避免早熟等特点 而利用GgaFca和F 的混合方法具有更好的综合性能1F (模糊6均值)聚类算法1.1模糊划分设有限集X=I1 I2 - In XERP(P维欧几里德空间) 将n个对象IzEX划分到6个簇中 IPk=Ik1 Ik2 - IkPER k=1 2 - n 将Ik划分到6个簇 第z个簇的质心Uz=Uz1 Uz2 - UzP 每个对象Ik隶属于第z个簇

9、的隶属度为Uzk 则将n个P维数据对象分类到6个簇中的模糊划分方式组成的集合为6Mf6=UER6nUzkE0 1 Vz k; z=1Uzk=1 Vk;n0< k=1Uzk<n Vz;1 z 6 1 k n(1)1.2F 算法模糊聚类目标函数6nJU V)= mm(z=1 j=1(uzk) Ik UzUEMf6 VER6n(2)目标函数表示了各簇中数据对象到质心的加权距离平方和 聚类问题就是要求满足(1)式的U和V使目标函数Jm值最小 应用Lagrange乘数法求解在Uzk Uj满足约束条件下 使J最小时U终的聚类结果 即模糊6划分矩阵U和聚类中心矩阵V F 算法描述如下Fuzzyc

10、-meanS luSteringAlgorithm()给定类数6允许误差E迭代次数t-1;初始化6个聚类中心U(t)z z=1 2 - 6;repeat按( )式计算隶属度U(t)zk z=1 2 - 6 k=1 2 - n;按(4)式修正所有聚类中心U(t-1)z z=1 2 - 6;计算矩阵范数误差6= U(t)z U(t-1)z ;until6 E佳点集遗传算法遗传算法本质上是一种具有定向制导的随机搜索技术 其定向制导的原则是导向以高适应值模式为祖先的O家族 方向 任何一种交叉操作都无非是在以其父代为O祖先 的家族中寻找一个适应值高的后代 现有的交叉操作如 单点交叉两点交叉多点交叉树交叉

11、以及解 问题中的部分匹配交叉顺序交叉和周期交叉等都是随机操作 后代简单地继承了双亲的部分基因 只能保证求到的后代落在上述的家族中 而无法保证所求到的后代的适应值较高 而佳点理论能保证在所有取n个点的子集中 用佳点法求到的子集(在均值意义下)最能代表其家族性能 故用佳点法构造的交叉操作 从理论上看就更符合遗传算法的机理 9 其次 从钟开莱定理得知 用佳点集法取n点比随机法取n点 其偏差要小得多(差平方倍) 这是佳点集方法收敛速度快的理论依据 佳点集交叉操作的基本思想是使子代保留双亲的共同基因段 而不相同的基因段由佳点确定 这样同时具有O遗传 和O进化 的思想4042.1改造的佳点集交叉操作合肥工

12、业大学学报(自然科学版)第28卷设有一规模为 的染色体集合A,有一适应度函数f(.)0设每个染色体可表示为 维的向量(其每个分量只取有限值),则所有长为 的染色体集合就是一个 维向量空间,记为B ,而染色体池A是一个染色体集(B 中的子集),其中AAIA 可表示为 A A1,A2, ,A 9A1 C1,1,C1,2, ,C1, 9A2 C2,1,C2,2, ,C2, 9C ,I 1, ,k9I 1, , , 1, , 9其适应度函数GoodPointsetGeneticalgorithm(初始群体M,交叉概率pc,变异概率pm,最大代数T)随机生成M个初始群体9repeat进行遗传操作,以概率

13、fI/ fI选择AI,其I 1中fI是AI的适应值9以赌轮法随机取2个染色体,以概率pc对其进行佳点集交叉操作9f(.) B+其中R+-R,表示非负实数集合,记为f(AI) fI0J是分量不同的位置集合,令J IIC1,I9C2,I,1 I 不妨设A1A2的前t个分量不同,后 -t个分量相同0令模式H (I1, ,I )IEJ,II 9I J,II C1,I(5)如果取A1A2进行交叉操作(显然不管是单点交叉或是多点交叉),其后代必属于H,于是要在高适应度模式为祖先的家族方向上搜索出更好的个体,就是要在H中搜索出更好的个体来0现按下面的方法构造佳点集交叉操作将H的前t个分量看成一个t维的立方体

14、(仍记为H),然后在H上求佳点集0在t维空间H中作含 个点的佳点集(当H是二进制立方体时)P (I) (11I,12I, ,1tI),I 1,2, , (6)其中,1l el或1l 2cos(2Tl/p)(1 l t),p是满足p 2t+3的最小素数9记号C表示取C的小数部分0令杂交后次产生的 个后代中第l个染色体Zl (Zl,1,Zl,2, ,Zl, ),其中Cl,mm J,1 mZl,m (1m t EJ,1 l ,(7)Lt l>1 S(C>表示C的小数部分乘以k+0.5后取整0如此从双亲中产生的 个后代,取其中适应值最大者(或最大的几个)作为杂交后的后代0这种利用佳点集理论

15、构造的交叉操作称为佳点集交叉操作02.2佳点集遗传算法佳点集遗传算法描述如下以概率pm进行变异操作9把经过遗传操作后得到的染色体都放到染色体池中,对新得到的染色体,计算其适应值,假定染色体池的容量一定,当染色体的个数超过容量时,就将适应值小的染色体从池中删去9until满足终止条件或达到最大代数在最后一代的染色体中取适应值最大者0新的模糊聚类算法 GgafcaGgafca是一种用佳点集Ga进行模糊聚类的方法,其基本思想是 通过遗传编码建立起问题的解空间与算法的搜索空间之间的映射,通过执行佳点集遗传操作产生下一代基因串,计算数据点的隶属度和群体适应值,达到较快地收敛到全局最优解的目的03.1Gg

16、afca的关键问题3.1.1染色体编码对聚为中心设 个样本要分成6类,模糊分类矩阵U (Ik)中有 X6个元素,基因串S(U1, ,U6)表示Ga的染色体结构,将每个Ik用3位二进制数编码,组成 X6个基因串,最后将所有基因串连接起来形成染色体,染色体中共有(3 X6+6)个基因0此时Ik所对应的二进制串的转换关系为decimal( )3Ik 2/(2-1),其中( )2是Ik对应的二进制串值03.1.2适应度函数的构造由聚类目标函数知,Jm越小,聚类效果越好0为了便于选择策略的应用,将求极小值变换为求极大值,设f为适应度函数,则f 1/Jm,其中Jm如(2)式所定义03.1.3定义遗传操作遗

17、传操作包括选择操作交叉操作及变异操作等0第4期苏守宝 等:基于佳点集遗传算法的模糊聚类技术405(1)赌轮选择策略G按照选定的适应度函数 使用赌轮策略进行选择 并且保留上一代M个较优的个体作为下一代样本 以保证算法的收敛性G同时每一代中最好染色体在子代中优先选择;每一代同一染色体在子代被选择其一G(2)佳点集交叉操作GVOidGPCROSSVER()/佳点集交叉规则n=pOp-size;/计算M个个体适应值( )对基因串S译码 按(3)式计算隶属数UIk;fOr(j=1;j<=k;j-)更新聚类原型按(4)式计算Vj;计算串S的适应值fI I=1 . M;/计算M个个体的适应值RWSEL

18、ECT();/赌轮策略选择INVERMUTATION();fOr(I=1;I<=pOp-size/2;I-)rc=rand(0 1);if(rc<pc)int1=rand(0 pOp-size);/选择第1个交叉个体c1inth=rand(0 pOp-size);/选择第2个交叉个体chfOr(j=1;j<=1chrOm;j-)H-=按(1)式生成c1 ch不同分量模式;fOr(j=1;j<=n;j-)/生成n个后代按(2)式和(3)式生成第Pn(j)个佳点;childj =Pn(j)和c1 ch相同分量构成并加入到染色体池中;(3)变异规则 改进的进化逆转操作G由于在

19、选择机制中采用了保留最佳样本方式 以及引入了 进化逆转 操作技术 为保持群体内个体的多样性 采用连续多次对换的变异技术 使可行解有较大顺序排列上的变化 以抑制 进化逆转 的同化作用G若发生变异 则用随机方法产生交换次数K 对所需变异操作的染色体进行K次对换(对换的两码位也是随机产生的)G3.2Ggafca算法Ggafca算法描述如下:/输入群体规模M交叉概率Pc变异概率Pm最大代数Tmax/输入数据集X=X1 X2 . Xn类数c;完全随机产生初始群体含M个个体;fOr( =1; <=Tmax; -)fOr(I=1;I<=M;I-)/逆转变异操作GPCROSSOVER();/佳点集

20、交叉操作保留适应值较大的M个个体 形成下一代群体;适应值最大的个译码得到聚类问题的最优解G在Ggafca算法中合适的c值选择仍然是个比较困难的问题 这通常与问题领域相关 用户可能需要选择若干个c值来试验GGgafcm算法的计算代价可以分解成以下多个部分:计算个体适应值的时间复杂性交叉变异操作的时间复杂性计算总适应值和平均适应值的时间复杂性 而且每一部分与随机数有关 一般计算若干次执行的平均时间复杂性 这一点对聚类方法应用于大规模数据集时尤其重要G混合模糊聚类方法 Ggafca基于GA的模糊聚类比传统的fCM模糊聚类算法通常收敛较慢 但是得到的是更精确的聚类 这表明可以用遗传算法的聚类结果作为f

21、CM聚类的初始聚类中心G这里提出的混合聚类算法gafca有3个步骤:Step1:执行一次(或多次)Ggfca模糊聚类算法GStep2:将适应值最大的个体译码 得到c个初始聚类中心GStep3:执行fCM算法G5比较实验与结果分析为了显示本文提出的遗传模糊聚类算法的有效性及聚类效果 采用fcmGgafcaGgafca及SGA(模糊聚类的标准遗传算法方法3) 选择406合肥工业大学学报(自然科学版)第卷Iris问题测试各自的聚类性能O问题是 Iris(鸢尾属植物)标准数据 10 通常被作为机器学习中分类问题的基准函数测试数据集,每组数据包含Iris花的4个属性,3种不同的花共150个样本O实验中取

22、群体规模n=60交叉概率Pc=0. 5变异概率Pm=0.01及预定进化代数T=100O用4种模糊聚类方法对Iris数据集进行模糊聚类测试,算法收敛性效果比较如图1所示O从图1看出fCM收敛较快,但早熟于一个较大的目标6结论本文改造了佳点集交叉操作,提出了一种基于佳点集GA的模糊聚类算法Ggafca和混合的模糊聚类方法Ggafca算法O比较实验测试表明Ggafca的聚类质量更好,但收敛稍慢,而混合方法具有较好的综合性能O继续用本文讨论的方法MushroomWineBreastCancer和10Automotives等数据进行实验,均可得到类似对函数值,平均分类正确率低;用标准遗传算法聚类SGA能

23、获得更高的分类正确率,但收敛速度慢;而基于佳点集GA的聚类算法Ggafca不仅收敛快,而且效果好;而混合算法Ggafca能够较快地收敛于最小值O1.fCM.Ggafca3.Ggafca4.SGA图1算法收敛性比较4种算法的聚类质量比较,见表1所列O其值是50次运算中目标函数的最小值及其平均误差达到最小值时的平均迭代次数和分类正确率O这表明当用佳点集遗传算法来搜索初始聚类中心后,再用fCM进行模糊聚类的混合算法,其性能有了较全面的改进O表14种算法的聚类质量比较模糊聚类算法目标函数的平均分类正确率最小值代数/(%)fCM9 7.963 0.037195 .47Ggafca61 .136 0.04

24、33191.44Ggafca605.074 0.035599.67SGA64 .16 0.041513.67的结论OGgfcm和Ggfcm方法可广泛应用于不同数据库下的模糊聚类挖掘研究O参考文献1 李雄飞,李军.数据挖掘与知识发现 M .北京 高等教育出版社, 003. 9.张敏,于剑.基于划分的模糊聚类算法 J.软件学报, 004,15(6) 5 6 .3 高新波.模糊聚类分析及其应用 M.西安 西安电子科学技术大学出版社, 004.49 55.4 WuYS,DingXG.AnewclusteringmethodforChinesecharacterrecognitionsystemusin

25、gartificialneuralnetworks J.ChineseJournalofElectronics,1993, (3) 1 . 5MaulikU,BandyopadhyayS.Geneticalgorithm-basedclusteringtechnigue J .Patternrecognition, 000,33(9) 1455 1465.6 WeiC,fahnC.Themultisynapseneuralnetworkanditsapplicationtofuzzyclustering J .IEEETransonneuralnetworks,00 ,13(3) 600 61

26、 . 7 LiJ,GaoXB,JiB.AfeatureweightedfCMclusteringalgorithmbasedonevolutionarystrategy A .IEEErobotics,AutomationSociety.Proceedingsofthe4thWorldCongressonIntelligentControlandAutomation C.Shanghai,China PressofEastChinaUniversityofScienceandTechnolgy,00 .1540 1553. 王小平,曹立明.遗传算法 理论应用与软件实现 M.西安 西安交通大学出版社, 00 . 46 49. 9 张铃,张钹.佳点集遗传算法 J.计算机学报, 001, 4(9) 917 9 . 10fisherrA.IrisData EB/OL .http /www.ics.uci