一种利用信息熵的群体智能聚类算法

1、一种利用信息熵的群体智能聚类算法!#$%计算机工程与应用前言数据挖掘是一个多学科交叉的研究 领域，涉及数据库技术、 人工智能、 机器学习、统计学、知识 获取、生物计算等学科。这些学科的发展为数据挖掘的研究提供了新的机遇与挑战。聚类是数据挖掘的重要任务之一，目前主要的聚类算法可以划分为如下几类()：划分方法， 层次方法，基于密度的方法，基于网格的方法和基于模型的方法等。这些方法大多数需要一些参数限制，设定聚的数目，而且聚类结果对初始状态及参数非常敏感。近年来，一些学者开始应用 群体智 能(*+,-./01233452062)(!)的思想研究聚类问题。因为群体智能源于对简单个体组成的群落社会系统的

2、模拟，如蚁群、蜂群，在没有任何先验知识和无统一指挥的分布环境下，它们具有自 我组织、合作、通信等特点。在文献(%)中，720289:8-5等首次模拟幼蚁自 动分类(即较小 的幼虫在中心， 较大的幼虫在外围)及蚁尸聚积现象， 提出了聚 类基本模型。随后;8.2- 和,421,在文献(#)中改进了 720289:8-5 的基本 模型，提出了 ；算法并应用于数据分析中虽然以上方法可以获得较好的聚类结果，但是需较长的计算时 间，还需设置较多的参数。文献（,=）采用 群体智能与 均值算法相结合的方法加快聚类速 度。论文在；算法中利用信息熵来控制蚂蚁拾起和放下对象动作， 既可以减少参数的个数，又可以加快聚

3、类的进程。!蚁群聚类的基本模型和；算法在自 然界中， 一些蚂蚁可以将 蚁尸 聚成 公墓，也可将幼虫按大小分类。720289:8-5 等根据这两种现象提出 了两种模型（），两者的 原理是一致的，即一群蚂蚁在一个二维区域内任意移动，允许按 规则拾起和放下物体。一个任意移动的未载物体的蚂蚁拾起一个物体的可能性！按公式（）计算；一个任意移动的载有物体的蚂蚁放下一个物体的可 能性!#按公式（！）计算，其中$是蚂蚁周围物体的个数，唏口 %! 均为常数。!?%$!（）#?$%!$!（!）;8.2- 和,421, 在文献（#）中，基 于720289:8-5的 基本 模型，提出了以下算法：A B/0414,34

4、C,14:0 B A:- 2D2-E 412. F:G3,62 -,0F:.3E :05-4FH0F :-:- ,33 ,5201I F:G3,62 ,5201 ,1 -,0F:.3E I232612FI412H0F :-A B J,40 3:G B A:- （? 1: （.,K F:- ,33 ,52011 F:/L（,5201 803,F20）,0F（ I412 :668G42F 9E 412. ）1M20N:.G812$（）,0F（）7-,+ -,0F:. -2,3 08.92- ） 921+220 ,0F /L（）!()1M20 AA 拾起规则 O46P 8G 412. HOF /LH

5、3I2 /L (,52016,-E405 412.) ,0F(I412 2.G1E ) 1M20N:.G812 $() ,0F #()7-,+ -,0F:. -2,3 08.92- ) 921+220 ,0F /L()!# () 1M20AA放下规则7-:G 412. 一种利用信息熵的群体智能聚类算法刘波(暨南大学计算机科学系，广州二!) HQ.,43 :39K3FFRI:M8$6:.摘要论文采用群体智能(*+,-. /01233452062)的思想研究聚类问题。在;8.2- 和,421,基于蚁群的聚类算法中， 通过信息熵的计 算与比较，改变了拾起和放下对象的规则， 增加了两区域对象的 合并操

6、作，从而加快了 聚类速度并减少了 参数设置数目。该方法能够有效地聚集数据库的记录对象，具有一定的实际应用价值。关键词信息熵群体智能聚类文章编号！QS%Q (!# ) %QSQ%献标 识码 T 中 图分类号 UO%!#$%()*+ !#+,()-. /%)*+ 0*(,12 3*4 563(. 7*#)+*89)$:,( 72G,-1.201:L N:.G812-*642062，V40,0W04D2-I41E, X8,05CM:8 =%!) UM2 G,G2- 6,-42I-2I2,-6M:0638I12-405 8I405 I+,-.401233452062$/1 ,.20FIG46P405

7、,0FF-:GG405 -832I 40!;%(38:,01 Y9,I2F 638I12-405 ,35:-41M.G-:G:I2F 9E ;8.2- ,0F ,421,1M-:85M 6:.G81405,0F6:.G,-40540L:-.,14:0201-:GE$TI,-2I831 ， 41 IG22FI 8G 638I12-405,0F -2F862I08.92-:LG,-,.212-I$UM2.21M:F6,0638112-26:-FI40,F,1,9,I22LL2614D23E,0F 4I :L G-,6146,3,GG346,14:0D,382$26,(4% :40L:-.,14:0

8、201-:GE , I+,-.401233452062, 638I12-作者简介：刘波，女，副教授，主要研究方向：数据挖掘，数据仓库，智能信息处理。S 计算机工程与应用!#$%() *+() ,+-./0 1.23().456 7050810)(0*9:;.2*(97*10 (.1 .88=*0);6.1:02390(1() .2() .2?2*(15.831*.( .+ *1047以上算法考虑的是：在一个!的网格中，蚂蚁在地点#可以观察到周围$的区域中的物体(下面称对象)。对象在地点2与周 围对象的相似度按公式 (% 计算，其 中！是一个衡量相异度的参数，(% %0是两个对象%和 %(的距离

9、。)(%A$!%(! *+,-( $)(#)AB( % %0 !# *+ ) ( %C%.-+#/$%+(% 00( % 1A1AD)(% (*)!(#)0( % !) (% *+ )( %E1!A*+ )(% 1!$()在F算法中，蚂蚁拾起和放下一个对象的可能性按公式(#)和公式()计算。拾起或放下的规则是：将一个随机数与计算所得的拾起或放下可能性值比较，若随机数小则执行拾起或放下操作。这种规则会导致一个对象多次被拾起或放下，从而聚类较慢。%基于信息熵的蚁群聚类方法（12.=6GH（1GI57102）在文献JKL中，阐 述了 M:3（.（ 提出 的 信息 熵定义：假设2是一个随机变量，3是其

10、可能的取值集合（连续型数据需离散化），0 （2）是取2值的可能性函数，信息熵4（2）定义为公式（N）:4（ 2）B23! 0 （2）5.90 （ 2）（ N） 个多变量向 量 2O2A2!，25P的 信息熵按公式 （K）计算，其中：0（ 2）60 （2A，2!，25） 是多变量可能分布函数，3A，3!，35是相应向 量项的可能取值集合（连续型数据需离散化）。4（2）B2A!3A25!35! 0 （2A，2!， ，25）5.90 （2A，2!，25）（ K）文献JK，QL已提出了基于信息熵的聚类算法，这些方法均依据这样一个事实：包含聚的子空间的信息熵比不包含聚的信息熵小。借鉴这一思想，下面在（1

11、2.=6GH（1GI57102算法中，将信息熵引 入F算法中，改变了拾起和放下判断规则。R S 初始化S R.2每一对象% ）.将%随机地放在一网格中；（）.2.2每一蚂蚁）.随机地选择网格中一地方；（）.2R S主循环SR.2 .A1. .43T ）.2 每一蚂蚁）.,+ （蚂蚁未负载）3（）（在 % 之处）1:0（计算信息熵4A和4! ；，+（4AC4!） 1:0（拾起% RR拾起规则（）,+570，+ （蚂蚁负载%）3（）（所在之处为空）1:0（计 算信息熵4A和4! ； ，+（ 4AC4!）1:0（放下% RR放下规则（）*+（），+蚂蚁随机移到某地方；（）.2（） .2一个未负载的蚂

12、蚁移到对象之处，计算周围$的区域中的对象信息熵，假设未拾起对象前的信息熵为4A，拾起对象后该区域的信息熵变为4!，拾 起规则为：，+ 4AC4!，则拾起对象。一个负载对象的蚂蚁移到空白 之处，计算周围$的区域中 的对象信息熵，假设未放下对象前的信息熵为4A，放下对象% 后该区域的信息熵变为4!，放下规则为：，+ 4AC4!，则放下对象。假设每一对象包括5个互为独立的 属性7A ,7!75,各属性的 可能取值集合为3A ,3!，35 , #区域中的对象信息熵可按公式 （Q 计算，0 （2）按公式 （U）计算， 其中589:+#;%）;2 是$区 域中满足762的对象个数，589:+#;%）;=$

13、+是$区域中的对象总 数。4（ $!）B5 6 A!2! 35! 0（ 2）5.90（ 2）（ Q） 0（ 2）589:+#;%）;2589:+#;%）;=$+ （ U #两种方法的比较分析蚁群聚类方 法最大的特点是：不需设定最终产生的聚的数目，聚中心是动态变化的，可以发现任意形状的聚。以上两种方法均以 390（1的任意选择的地方作为变化的聚中 心，并考察周围一小块区域中的对象，通过拾起或放下操作改变此一小块区域的对象相似度。在F算法中，影响拾起或放下动作的因素有对象间的距离、1A、 1!、！、$等参数，还有随机数，因此，每次放下的对象不一定 与小块区域中存在的对象相似；每次拾起的对象不一定与

14、小块区域中存在的对象不相似，聚类过程很慢。在(12.=6GH(1GI57102的方法中， 影响拾起或放下动作的因素 只有$参数，每次放下对象能减少小块区域的信息熵；每次拾起能增加小块区域的信息熵。根据文献JK, QL 包含聚的子空间的信息熵比不包含聚的信息 熵小，因此同类型的对象能够较快地聚集在一起，但产生的结果是局部最优。通过调整观察区域的大小$，可减少小块聚的产生。两种方法的时间复杂度均为？(.43T*=5. ), *=5.为蚂蚁个数，但 实验结果表明(12.=6GH(1GI57102算法经过较少次循环就能达到较 好的聚类结果。实验结果从VI,J#L公共数据库中选取一组数据集 (W*8G1

15、38G1.Q)9340)，该数据集包括UQ个对象， 可分为两类。分别用F算法和(12.=6GH(1GI57102方法对这一数据集进行 聚类。在F算法中，设置N个参数：1A$A，1!$A !$, $!NXN .43T% =,+5.;589:+# (蚂蚁数 目)； 在(12.=6GH(1GI57102AQA!#$%算机工程与应用(上接56/-78456/-7839;*8,878; ,-./0=;后面输出 所有的拓扑序列，即存放在二维数组 严 中的元素，略去；$?AB算 法的实例用ABC算法，可以求出 一个可行的CDE网的所有可行 的拓扑序列，该算法的调用是以判断CDE网不存在有向环为前提的 + 1

16、。对于图 所示的CDE网，调用ABC算法可求得！个并行拓扑 序列如下：（）! % # ； （!） ! % # ； （% ! # % ；（#） % !# ；（）% ! #；（?）!%#；（F）!% # ；（G）!# % ；（H）% ! #；（） % !# ；（） %! #；（!）% !#。而用非并行算法只能求得一种拓扑序列：% ! # 。两种结果相 比，ABC算法的优势是很显然的。因为一个实际活动很有可能不能按%!#这样的唯一顺序安排，那么有了 ABC的结果，则还有 种可能的串行安排选择。更为重要的是，从所有的拓扑序列中， 可以得到并行信息，如 上例，可按（）！ （! %）! （ #）的顺序安排

17、子工程，若每个 子工程耗费一个单位时间，则并行安排只需三个单位时间，而串行安排却需六个单位的时间。可见，AB（算法提升了拓扑排序算法的实用价值。F结束语若一个CDE网有！个顶点，最多有!#个拓扑序列,则AB（算法的 时间 复杂度和空间 复杂度均为$（!#%!）,算法效率较高，但仍需要进一步优化。拓扑排序算法在工程的计划管理、系统的统筹调度、工艺决策过程+#1、生产流程控制及软件开发+1等领域得到了 广泛的应用， 但是以往用程序只能求得一种拓扑序列使得算法实用性下降。ABC算法根据拓扑排序思想， 引 入层次的概念，并基于一种 以十字队列为主的混合数据结构，采用分层求解的方法得到了一个CDE中顶点

18、的所有可行拓扑序列。该算法的并行性就体现在：ABC算法在求解过程中是分层的，同一层次的子序列均求出以 后才能求下一层次的子序列， 即并行地向前推进； 同时，从多个 拓扑序列中能得到同一时刻可并行执行的子工程名 。结合工程安排的实际情况及一些特定的约束条件，利 用ABC算法可以得到真正可行的串 行或并行子工程安排表， 从而真正做到 管理统筹的自 动化、高效化，因 此ABC算法具有非常高的实用 价值。（收稿日期：!# 年 月）参考文献$陈慧南$数据结构（使用1=语言描述）+J1$南京：东南大学出版社，！!$王晓瑛，魏正军$关于拓扑排序算法的讨 论+K1$西北大学学报 （自 然科学版），！!3# :

19、%#L%#?%王顺凤$种有向权图的拓扑排序算法及其应用 +K1晡京气象学院学报（自 然科学版），！!3#$赵学军，乔红兵等$IC系 统工艺决策过程的CDE3网表示法及拓扑排序分析+K1$机电一体化， HHG3#丁明亮，陈仁全$用有限自 动机和拓扑排序理论提高JMB开 发效率+K1$微计算机信息，！3F方法中，仅设置三个参数：!4N ，:）04%, （）*!+!#,*-（蚂蚁数目）4!。在实验中， 首先使AP,Q0）,Q0-8 R/7S）:8 数据集的对象均匀分 布在N的区域中， 不同类型的对象分别用不同符号表示。可以得出以下结论：（）TU算法在4%时，不能将同一类型的对象聚在一起， 不同 类型

20、的对象混合集中分布在几个区域中； （!）R/0*-;VQC/0QIW.X08* 方法在4%时，基本上可以将不同类型的对象分开， 并且同一类型 的对象集中分布在几个区域范围内 。显然，R/0*-;VQC/0QIW.X08*方法与TU算法相比， 聚类速度较 快，而且准确率高。?结论群体智能是人工智能领域一个新颖的研究分支，其模拟一些自然界中具有自 治、合作、通信等特点社会群体的行为， 已 解决旅行推销员， 作业调度， 路由 选择等优化问题。Y8/8.Z-.*S、T.:8* 和U）P80）等在文献+% #1中，借鉴蚁群可以将蚁尸聚成公墓以及可将幼虫按大小分类的行为，提出了聚类模型和算法，但是存在聚类

21、速度慢并且需要设置较多参数等 问题。论文利用 信息熵修改了 TU算法中的拾起和放下对象规则，减少了参数数目，力口 DO6-*7 d/Pe8*XP0V*8XX HHH%$Y8/8.Z-.*S K T, B a-XX，b U*)/2X 80 )W$A8 YV/):P,X -6 l-WW8,0Pe8B-*0P/S: f-Z-03TP28 C/0 )/7 C/03TP28 f-Z-0+l1$M/K C J8V8*，B ggPWX-/ 87X$*-,887P/SX UP*X0 I-/68*8/,8 -/BP:.W)0P-/ -6 C7);0Pe8_8)eP-*U*-: C/P:)WX 0- C/P:)0

22、X，I):Z*P7S8，JC：JMA *8XX，HH%?L%?#$T.:8* R， _ U)P80)$YPe8*XP0V )/7C7);0)0P-/ P/-;.W)0P-/X -6 ,W.X308*P/S )/0X+I1$M/:*-,887P/SX AP*7 M/08*/)0P-/)W I-/68*8/,8 -/ BP:.3W)0P-/-6 C7);0Pe8 _8)eP-*:P，HHH3?吴斌，傅伟鹏，郑毅等$种基于群体智能的g8Z文 档聚类算法+K1$计算机研究与发展，! ； %H():#!HL#%F$Y)/P8W _)*Z)*i，K.WP) I-.0- ，cP TP$IDDTICAC/8/0*-;V3Z)X87)WS-3*P0:6-* ,)08S-*P,)W ,W.X08*P/S+I1$M/:;*-,887P/SX-6088W8e8/0P/308*/)0P-/)W ,-/68*8/,8，-e8*V )/77)0) :P/P/S，HHHG