一种基于群体智能的聚类算法CSI

1、一种基于群体智能的聚类算法CSI吴斌 史忠植（中科院计算技术研究所智能信息处理开放实验室 北京 100080）摘要：群居性生物的群体行为涌现的群体智能正在成为人工智能的研究热点。本文对基于群体智能的聚类算法进行了研究，在蚁群打扫巢穴的基本解释模型基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法；本文还提出了一种简化的概率转换函数，减小了概率转换函数参数选取的难度；接着本文分析了群体相似系数对聚类算法的重要性。实验结果表明这种基于群体智能的聚类算法具有较好的聚类性能。关键字：群体智能自组织聚类群体相似度概率转换函数1 引言科学家从丰富多彩的自然

2、界获得了无数启迪。群居性生物的群体行为涌现的群体智能正在成为人工智能的研究热点。启发于群居性生物的寻食、打扫巢穴等行为而设计的解决实际问题的算法获得了令人惊奇的成功。这些算法在组合优化、通信网络和机器人领域的应用实例的数量正成指数地增长1,2,3。如果一个团队的生存能力对于个体的生存能力是必需的则称这个团队提供了集体智能。Bonabeau等人认为群体智能是任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置4,5。群体智能的特点是最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，并具有自组织、可扩展性、健壮性等特性。蚁群算法是群体智能具有代

3、表性的解决组合优化问题的算法。Marco Dorigo等人将蚁群算法先后应用于TSP问题、资源二次分配问题等经典优化问题，得到了较好的效果3。蚁群算法在电信路由控制方面的应用被认为是目前较好的一种算法6。蚁群算法启发于蚁群合作获取食物的模型，它通过信息素的发布和蒸发调节蚂蚁个体寻食行为，由此找到最短路径。解决组合优化问题的蚁群算法来源于蚁群寻食行为，而启发于蚁群合作蚁巢分类的相关技术因为没有系统的性能评价，目前还处于初步研究和概念证实的阶段1 。观察群居蚂蚁的昆虫学家发现：蚂蚁的幼虫和食物不是随机地分散在蚁巢内，而是按类别分别堆放。Deneubourg 等人提出了一种行为解释的基本模型7，巢的

4、空间结构产生于简单的局部的相互作用而不需要任何集中控制或者全局环境的表示。Beckers等人将这个模型应用于机器人技术，证明了使用几个简单机器人而不是一个复杂的机器人快速完成复杂任务的可能性8,9。Lumer 和 Faieta将这个模型扩展到对可以依据相似性测量比较的对象处理，证实了基本模型在数据分析中的应用10。Kuntz等人则将模型扩展应用于图的分割问题及VLSI设计11,12。本文对基于群体智能的聚类算法进行了研究，在基本解释模型的基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法,并提出了一种简化的概率转换函数。与Lumer 和 Fai

5、eta的模拟实验数据不同，本文选用了三个标准的机器学习数据库作为测试数据库。算法的基本思路是：将待聚类的对象随机放置一个两维网格的环境中，每一个对象有一个随机初始位置，每一只蚂蚁能够在网格上移动，并测量当前对象在局部环境的群体相似度，通过概率转换函数将群体相似度转换成移动对象的概率，以这个概率拾起或放下对象。蚁群联合行动导致属于同一等价类的对象在同一个空间区域能聚积在一起。与经典的分级聚类算法和K均值动态聚类算法相比，基于群体智能的聚类算法CSI具有群体智能算法的共同特点，它利用个体与个体和个体与环境的交互作用，不必预设聚类中心的数目，实现自组织聚类过程，具有健壮性、可视化等特点。自组织是指具

6、有耗散结构、具有自催化和定向涨落机制的开放式系统在演变过程中呈现出来的全局有序现象，如生命现象、热对流现象等。基于群体智能的聚类算法CSI同样具备自组织计算的主要特征：（1）问题结构组成的不明确性，结构的形成是系统在对环境信息的不断处理中自发生成的；（2）结构变化没有明确的方向，其知识的积累完全取决于所处理的环境信息中存在的规律性；（3）它强调大量个体的协调作用，是一个高度自主协同的过程，它通过大量的局部相互作用可以产生全局的整体效应。通过设计局部的个体的交互规则，可以实现全局自组织的功能14。本文组织如下：第2节介绍Deneubourg 提出的基本模型和相关的数据分析算法；第3节说明基于群体

7、智能的聚类算法的基本概念和思路及算法描述；第4节介绍实验结果和分析；最后是结论。2 基本模型Chretien用Lasius niger蚂蚁做了大量实验研究的巢穴组织。工蚁能在几小时内将大小不同的尸体聚成几类。在这种聚集现象之上的基本机制是工蚁搬动不同对象之间的吸引度：小的对象聚类中心通过吸引工蚁存放更多的同类对象变大。这是一个正反馈导致形成更大的聚类中心。在这种情况下，在环境中聚类中心的分布起到了非直接通信（stigmergy）的作用。Deneubourg等人提出蚁群聚类现象解释模型。这个模型以下称基本模型（BM）依靠的一般思想是单独的对象将被拾起并放到其它有更多这种类型对象的地方。假设环境中

8、只有一种类型的对象，由一个当前没有负载对象的随机移动的蚂蚁拾起一个对象的概率是： (1)其中f 是在蚂蚁附近对象观察分数(perceived fraction)，k1是门限常数：若f k1，pp接近1，（即当周围没有多少对象时，拾起一个对象的概率很大），若k1 f ，pp接近0，（即在一个稠密的聚类中，一个对象不大可能被移动）。一个随机移动的负载蚂蚁放下一个对象的概率是： (2)其中k2是另一个门限常数：若f k2，pd接近1，若k2 Pr则蚂蚁放下此模式，将蚂蚁的坐标赋给此模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值，否则蚂蚁继续携带此模式，蚂蚁状态仍为有负载，再次随机给蚂蚁一个新坐标

9、。；步骤11、若此组所有蚂蚁完成循环，则继续，否则选取下一只未循环蚂蚁转向步骤5；步骤12、以一定的步长调整；步骤13、 若循环次数小于最大循环次数MAXCYCLENUMBER，转向步骤4，否则程序结束。算法的结束条件可以是直接设定最大循环次数，也可用各聚类中心不再有模式移动为标准即算法已收敛。其中步骤12调整的方法可以是连续微调，也可以每循环一个固定次数后再调整，本文采用了后一种方式，此外在这一步还可调整其它参数如观察半径等。4. 实验结果及分析本文测试数据都来自于UCI的() 机器学习数据库。本文选取了三组测试数据。它们分别是动物（zoo）、鸢草（iris）和图像(image) 数据库。其

10、中动物数据库为101个记录，16个条件属性，1个决策属性，7 个类别分别是哺乳动物、鸟类、爬行动物、两栖动物、鱼类、昆虫和节肢动物。鸢草是经典聚类测试数据库，有150个记录，4个条件属性，1个决策属性，3个类别。在图像数据库选取了BRICKFACE、SKY和PATH共3类990个记录，19个条件属性，1个决策属性。a) CSI聚类算法有效性实验实验1 测试数据库ZOO记录数101参数：=6-4, ant_number=6, r= 15,k=0.1，MAXCYCLENUMBER=200X900；size=350X350图1ZOO实验结果图图1是ZOO实验结果图，其中红色表示哺乳动物；兰色表示鸟类

11、；绿色表示爬行动物；品红色表示两栖动物；青色表示鱼类；黄色表示昆虫；灰色表示节肢动物。表2是ZOO实验结果表。从实验结果可知，CSI聚类算法不仅基本能将7种类型的动物分开，而且还得到了一些细分的结果，如红色表示的哺乳动物被分为了三个部分，其中最大的一个类别是陆生哺乳动物共有36种动物，第二类别是4个是水生哺乳动物有4种动物，哺乳动物中很特别的卵生哺乳动物鸭嘴兽被单独归成第三类。表2ZOO实验结果表原类别 新类别动物名称1哺乳动物1陆生哺乳动物aardvark, antelope, bear, boar, buffalo, calf, cavy, cheetah, deer, elephant,

12、fruitbat, giraffe, girl, goat, gorilla, hamster, hare, leopard, lion, lynx, mink, mole, mongoose, opossum, oryx, polecat, pony, puma, pussycat, raccoon, reindeer, squirrel, vampire, vole, wallaby,wolf12水生哺乳动物porpoise, dolphin, seal,sealion,13卵生哺乳动物Platypus,7节肢动物4卵生节肢动物Clam,crab ,crayfish,lobster,oct

13、opus,seawasp,starfish 6昆虫，7、节肢动物5昆虫、素食节肢动物(2)Flea， gnat， honeybee， housefly， ladybird， moth ， termite， wasp， （7） worm ，（7）slug 2鸟类，3爬行动物6鸟类、素食爬行动物(2)chicken, crow, dove, duck, flamingo, gull, hawk, kiwi, lark, ostrich, parakeet, penguin, pheasant, rhea, skimmer, skua, sparrow, swan, vulture, wren， （

14、3）tortoise4鱼类，7鱼类bass ，carp ，catfish，chub，dogfish，haddock，seahorse,sole, tuna， herring, pike, piranha, stingray5两栖动物，3爬行动物8两栖动物, 卵生食肉爬行动物（5）frog ，frog，newt ，toad（3）pitviper slowworm tuatara 7节肢动物9非卵生节肢动物scorpion (7)3爬行动物10 非卵生爬行动物seasnake (3) 图2IMAGE实验结果图实验2测试数据库IMAGE记录数990参数：=2.5-1.5 MAXCYCLENUMBER

15、=1000X600；ant_number=10, r= 25,k=0.1， size=750X480实验结果为图2所示：图中红色表示BRICKFACE图像模式，黄色表示SKY图像模式，兰色表示PATH图像模式。从图中可看出，CSI聚类算法具有聚类能力，能将相似模式聚积在一起。实验3 测试数据库iris记录数150参数：=0.4-0.3, MAXCYCLENUMBER=200X300；size=480X450, r=20,k=0.1，ant_number=6图3为=0.4-0.3时IRIS实验结果图，红色表示类别Iris-setosa模式，兰色表示类别Iris-versicolor模式，绿色表示

16、类别Iris-virginica模式，实验结果如下：聚类后只有编号为107、120、134、135的共4个Iris-virginica模式与兰色类别Iris-versicolor模式属于在一个聚类中心。结果证明CSI聚类算法有较好的聚类性能。图3IRIS 实验结果图 =0.4-0.3 b) CSI聚类算法群体相似系数实验选用测试数据库为iris，记录数为150，不变参数为 size=480X450, r=20,k=0.1，ant_number=6，改变群体相似系数值，研究群体相似系数对聚类结果的影响。 表3IRIS实验群体相似系数与聚类结果对照表 收敛次数聚类结果1200X30虽然形成23个聚

17、类中心，但是三种类别的模式相互混在同一个聚类中心内。0.4-0.3200X300形成24个聚类中心，类别混淆个数不大于10。0.2200X3600形成10个左右聚类中心，类别为Iris-virginicat 和Iris-versicolor的模式分散生成多个聚类中心，类别混淆个数更少。0.1未出现收敛，实验次数为200X10000无聚类中心，模式仍随机分散分布。表3是IRIS实验群体相似系数与聚类结果对照表。从表中可看出群体相似系数对聚类结果影响很大。它不仅影响算法的收敛速度，而且影响聚类的结果，包括聚类中心的数目和聚类的质量。一般情况下，群体相似系数越小，算法收敛越慢，聚类中心个数增多，而群

18、体相似系数越大，算法收敛越快，聚类中心个数减少，但是不适当的群体相似系数值可能导致算法太慢或不收敛和聚类结果无效即距离相差很大的模式聚在一起。5. 结论本文对基于群体智能的聚类算法进行了研究，在基本解释模型的基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成一种基于群体智能的聚类算法，并提出了一种相关的简化概率转换函数。实验证明这一基于群体智能的聚类算法是一种自组织聚类算法，具备健壮性、可视化等特点，并能生成一些新的有意义的聚类模式。本文还通过实验分析了群体相似系数对聚类算法的影响，实验证明群体相似系数是聚类算法的一个关键参数。此算法是一种基于简单个体与局部环境相互作用的

19、无集中控制的聚类算法，适应分布式环境，虽然目前在时间复杂性和空间复杂性方面与经典的聚类算法相比并不具备优势，但是作为一种自组织聚类算法，它将提供一种分析复杂群体现象的方法，如客户行为分析等。而算法本身也有许多值得研究的领域，如蚂蚁添加记忆功能，群体相似系数的自适应生成，概率转换函数的制定及局部环境等参数的影响分析等；在总体方面，算法还可增加后续的聚类中心模式生成及模式分类算法，并且算法目前还缺乏扎实的数学理论分析，同时怎样充分利用群体智能中正反馈特性提高算法的效率也是一个值得探索的问题。 参考文献1 .Bonabeau, M.Dorigo,G.Theraulaz, Inspiration fo

20、r optimization from social insect behaviour, Nature,vol 406,6 July 2000. 2 M.Dorigo, E.Bonabeau, G.Theralulaz, Ant Algorithms and stigmergy, Future Generation Computer Systems 16(2000) 851-871;3 T.Stutzle,H.Hoos, MAX-MIN Ant systems, Future Generation Computer Systems 16(2000) 889-914; 45 Bonabeau,E

21、.,Dorigo,M.& Theraulaz,G. Swarm Intelligence: From Natural to Artificial Systems ,Oxford Univ. Press, New York,1999;6Gianni Di Caro and Marco Dorigo, AntNet: Distributed Stigmergetic Control for Communications Networks, Journal of Artificial Intelligence Research 9(1998) 317-355;7 Deneubourg.J.L., G

22、oss S.,Frank,N., Sendova-hanks, A.,Detrain C.,Chrerien L., The dynamics of collective sorting: robot-like ants and ant-like robots, in: Meyer J., Wilson S.W. (Eds.), Proceedings of the First International Conference on Simulation of Adaptive Behavior: From Animals to Animats, MIT Press/Bradford Book

23、s, Cambridge, MA, 1991, pp.356-363;8 Becker R., Holland O.E. and Deneubourg J.L. From local actions to global tasks: Stigmergy and collective robotics, in Brooks R. and Maes P. Artificial Life IV, MIT Press, 1994;9 Holland O.E. and Melhuish C. Stigmergy, self-organisation, and sorting in collective

24、robotics, Artificial Life 5,1999,pp.173-202;10 E.Lumer, B.Faieta. Diversity and adaptation in populations of clustering ants . in J.-A.Meyer, S.W. Wilson(Eds.), Proceedings of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animats, Vol.3, MIT Press/ Bradford B

25、ooks, Cambridge, MA, 1994, pp 501-508;11 P.Kuntz,D.Snyers,P,Layzell, A stochastic heuristic for visualizing graph clusters in a bi-dimensional space prior to partitioning,Journal of Heuristics,5,1999,327-351;12P.Kuntz,P.Layzell, D.Snyers, A colony of ant-like agents for partitioning in VLSI technolo

26、gy,in: P.Husbans, I. Harvey(Eds.), Proceeding of the Fourth European Conference on Artificial Life, MIT Press,Cambridge, MA, 1997, pp.417-424;13T.Kohonen, Solf-Organizing Maps, 3.ed. ,Berlin , Springer,2001;14胡建军，汪叔淳，现代智能制造中的关键智能技术研究综述，中国机械工程，第11卷第7期，2000年7月，pp.828-835;(HU jian-jun,WANG shu-chun, Survey of the Key Intelligent Methods in Modern Intelligent ManufacturingState-of-the-art of Learning, evolution and Self-organizing, CHINA MECHANICAL ENGINEERING,Vol.11,No.7,2000.7. pp.828-835;)AN CLUSTERING ALGORITHM BASED ON SWARM INTELLIGENCEWu bin Shi zhongzhiThe key lab. of