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

1、.一种基于群体智能的聚类算法摘要：作者：吴斌 - 相关文章关键词：类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！;13一种基于群体智能的聚类算法CSI吴斌 史忠植（中科院计算技术研究所智能信息处理开放实验室 北京 100080）摘要：群居性生物的群体行为涌现的群体智能正在成为人工智能的研究热点。本文对基于群体智能的聚类算法进

2、行了研究，在蚁群打扫巢穴的基本解释模型基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法；本文还提出了一种简化的概率转换函数，减小了概率转换函数参数选取的难度；接着本文分析了群体相似系数对聚类算法的重要性。实验结果表明这种基于群体智能的聚类算法具有较好的聚类性能。关键字：群体智能自组织聚类群体相似度概率转换函数1 引言科学家从丰富多彩的自然界获得了无数启迪。群居性生物的群体行为涌现的群体智能正在成为人工智能的研究热点。启发于群居性生物的寻食、打扫巢穴等行为而设计的解决实际问题的算法获得了令人惊奇的成功。这些算法在组合优化、通信网络和机器人领域的

3、应用实例的数量正成指数地增长1,2,3。如果一个团队的生存能力对于个体的生存能力是必需的则称这个团队提供了集体智能。Bonabeau等人认为群体智能是任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置4,5。群体智能的特点是最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，并具有自组织、可扩展性、健壮性等特性。蚁群算法是群体智能具有代表性的解决组合优化问题的算法。Marco Dorigo等人将蚁群算法先后应用于TSP问题、资源二次分配问题等经典优化问题，得到了较好的效果3。蚁群算法在电信路由控制方面的应用被认为是目前较好的一种算法6。蚁群

4、算法启发于蚁群合作获取食物的模型，它通过信息素的发布和蒸发调节蚂蚁个体寻食行为，由此找到最短路径。解决组合优化问题的蚁群算法来源于蚁群寻食行为，而启发于蚁群合作蚁巢分类的相关技术因为没有系统的性能评价，目前还处于初步研究和概念证实的阶段1 。观察群居蚂蚁的昆虫学家发现：蚂蚁的幼虫和食物不是随机地分散在蚁巢内，而是按类别分别堆放。Deneubourg 等人提出了一种行为解释的基本模型7，巢的空间结构产生于简单的局部的相互作用而不需要任何集中控制或者全局环境的表示。Beckers等人将这个模型应用于机器人技术，证明了使用几个简单机器人而不是一个复杂的机器人快速完成复杂任务的可能性8,9。Lumer

5、 和 Faieta将这个模型扩展到对可以依据相似性测量比较的对象处理，证实了基本模型在数据分析中的应用10。Kuntz等人则将模型扩展应用于图的分割问题及VLSI设计11,12。本文对基于群体智能的聚类算法进行了研究，在基本解释模型的基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法,并提出了一种简化的概率转换函数。与Lumer 和 Faieta的模拟实验数据不同，本文选用了三个标准的机器学习数据库作为测试数据库。算法的基本思路是：将待聚类的对象随机放置一个两维网格的环境中，每一个对象有一个随机初始位置，每一只蚂蚁能够在网格上移动，并测量当前对

6、象在局部环境的群体相似度，通过概率转换函数将群体相似度转换成移动对象的概率，以这个概率拾起或放下对象。蚁群联合行动导致属于同一等价类的对象在同一个空间区域能聚积在一起。与经典的分级聚类算法和K均值动态聚类算法相比，基于群体智能的聚类算法CSI具有群体智能算法的共同特点，它利用个体与个体和个体与环境的交互作用，不必预设聚类中心的数目，实现自组织聚类过程，具有健壮性、可视化等特点。自组织是指具有耗散结构、具有自催化和定向涨落机制的开放式系统在演变过程中呈现出来的全局有序现象，如生命现象、热对流现象等。基于群体智能的聚类算法CSI同样具备自组织计算的主要特征：（1）问题结构组成的不明确性，结构的形成

7、是系统在对环境信息的不断处理中自发生成的；（2）结构变化没有明确的方向，其知识的积累完全取决于所处理的环境信息中存在的规律性；（3）它强调大量个体的协调作用，是一个高度自主协同的过程，它通过大量的局部相互作用可以产生全局的整体效应。通过设计局部的个体的交互规则，可以实现全局自组织的功能14。本文组织如下：第2节介绍Deneubourg 提出的基本模型和相关的数据分析算法；第3节说明基于群体智能的聚类算法的基本概念和思路及算法描述；第4节介绍实验结果和分析；最后是结论。2 基本模型Chretien用Lasius niger蚂蚁做了大量实验研究的巢穴组织。工蚁能在几小时内将大小不同的尸体聚成几类。

8、在这种聚集现象之上的基本机制是工蚁搬动不同对象之间的吸引度：小的对象聚类中心通过吸引工蚁存放更多的同类对象变大。这是一个正反馈导致形成更大的聚类中心。在这种情况下，在环境中聚类中心的分布起到了非直接通信（stigmergy）的作用。Deneubourg等人提出蚁群聚类现象解释模型。这个模型以下称基本模型（BM）依靠的一般思想是单独的对象将被拾起并放到其它有更多这种类型对象的地方。假设环境中只有一种类型的对象，由一个当前没有负载对象的随机移动的蚂蚁拾起一个对象的概率是： (1)其中f 是在蚂蚁附近对象观察分数(perceived fraction)，k1是门限常数：若f< <k1，p

9、p接近1，（即当周围没有多少对象时，拾起一个对象的概率很大），若k1< <f ，pp接近0，（即在一个稠密的聚类中，一个对象不大可能被移动）。一个随机移动的负载蚂蚁放下一个对象的概率是： (2)其中k2是另一个门限常数：若f< <k2，pd接近1，若k2< <f ，pd接近0。拾起和放下行为大致遵守相反的规则。Lumer 和 Faieta 将Deneubourg 等人的BM 推广应用到数据分析。主导思想是定义一个在对象属性空间里的对象之间的“不相似”d（或者距离）：例如，在BM中，两个对象Oi和Oj不是相似就是不同，所以可以定义一个二进制矩阵， d（Oi,O

10、j）=0，如果Oi和Oj是不同的对象，d（Oi,Oj）=1，如果Oi和Oj是相同的对象。很明显，相同的思想可以扩展到有更多复杂对象的情况，即对象有更多的属性，且或者更复杂的距离。在数据分析中，必须处理能够由有限n个实数值属性描述的对象的情况是常见的，所以对象可看做在空间的点和d（Oi,Oj）可属于欧氏距离。Lumer和Faietar的 算法（LF）将属性空间投影到一些低维空间，以便使得聚类出现以下特性：聚内距离必须相应小于聚间距离。Lumer 和Faieta的实验数据是在平面四个象限上随机产生的四组正态分布的各200个点。而拾起Pp和放下Pd概率计算公式分别为公式（3）和（4）：（3） (4)

11、为了改进原有模型的性能，他们在系统上增加了三个特性：（1）蚂蚁具有不同的移动速度，设定蚂蚁的速度v均匀分布在1,vmax之间，这个速度v 通过函数f(oi)（公式（5）所示）影响蚂蚁是拾起一个对象还是放下一个对象；（2）蚂蚁具有一个短时间的记忆；（3）行为转换，如果在一个设定的时间步长内在上面没有进行任何拾起或者放下行动，蚂蚁能够消除这些聚类中心。这些特性在减少相同的聚类中心、避免局部非优化结构等方面改进了原模型。 (5)公式（5）中，f(oi)是对象Oi 与出现在它邻近范围内的其它对象Oj 的平均相似度，对应模型中的f。s表示邻近范围的半径，d（Oi,Oj）为两对象的距离，参数定义了距离的规

12、模，它是一个非常重要的参数。在后面我们将定义它为群体相似度系数。3. 基于群体智能的聚类算法CSI1、基本概念基于群体智能的聚类算法CSI的主要思想仍是Deneubourg提出的基本模型，同时结合Lumer 和 Faieta的LF算法，明确提出一种聚类算法CSI。首先是将待测对象随机分布在一个环境中（一般是一个两维网格），简单个体如蚂蚁测量当前对象在局部环境的群体相似度，并通过概率转换函数得到拾起或放下对象的概率，以这个概率行动，经过群体大量的相互作用，最终得到若干聚类中心。定义1群体相似度是一个待聚类模式（对象）与其所在一定的局部环境中所有其它模式的综合相似度。群体相似度的基本测量公式是公式

13、（6）（6）其中NeighSXS(r)表示局部环境，在两维网格环境中通常表示以r 为半径的圆形区域。表示对象属性空间里的对象与 之间的距离，常用方法是欧式距离和街市距离等。定义为群体相似系数。它是群体相似度测量的关键系数，它直接影响聚类中心的个数，同时也影响聚类算法的收敛速度。它最终影响聚类的质量，若群体相似系数过大，不相似的对象可能会聚为一类，若群体相似系数过小，相似的对象可能分散为不同的类。另外，关于公式（5）中的面积因素，由于在多数情况下，它只是一种常数，所以可以将它综合在概率转换函数中考虑。在本文实验中，采用了渐变的群体相似系数，群体相似系数随着循环次数的增加以较小步长地由大变小，从而

14、减小算法对群体相似系数取值范围的依赖性。定义2概率转换函数是将群体相似度转换为简单个体移动待聚类模式（对象）概率的函数。它是以群体相似度为变量的函数，此函数的值域是0,1。同时概率转换函数也可称为概率转换曲线。它通常是两条相对的曲线，分别对应模式拾起转换概率和模式放下转换概率。在CSI聚类算法中，概率转换函数也是一个重要元素。在Deneubourg提出的基本模型与Lumer 和 Faieta的LF算法中，采用了相似的概率转换函数，分别由公式（14）表示。在本文的实验中，采用了一种简单曲线，斜率为k的直线，如公式（7）和（8）所示：（7）（8）概率转换函数简化后，关于概率转换函数的参数只有k，而

15、在原模型中，概率转换函数的参数包括两个门限常数k1 和k2，而且在本文实验中，k没有根据实验数据变化而变化，而原模型门限常数k1 和k2的选取与实验数据相关密切，因此概率转换函数的简化减轻了算法参数选取的复杂度。为了进一步说明CSI聚类算法，下面将基于蚁群算法的聚类算法CSI与另一种成熟的自组织聚类算法自组织特征映射SOM13进行一个简单比较，如表1所示。从表1可以看出，两种算法在一些方面有一定的相似性。例如SOM和CSI的聚类过程都是权值矢量的形成过程，前者是直接由输入模式通过竞争学习形成固定数目的权值矢量，而后者通过群体的作用隐藏地形成不定数目的权值矢量。此外，两者的实验结果（本文未列出）

16、的对比也可发现一些大的聚类中心模式基本相同。表1：基于蚁群算法的聚类算法与SOM聚类算法的比较自组织特征映射SOM基于蚁群算法的聚类算法Clustering based on Swarm Intelligence初始化：将待聚类模式的维设为输入层，在平面上随机设定NxN的输出权值矢量，直接将待聚类模式随机分散在平面上。聚类过程：待聚类模式与权值矢量比较，得到获胜矢量，修改获胜矢量及周围局部矢量，使它们移向输入模式。循环执行上述过程到满足停止条件。观察周围局部环境（相似模式的多少），以相关的概率在平面上搬起或放下待聚类模式，隐藏实现权值矢量的生成和修改。循环执行上述过程到满足停止条件。停止条件：

17、计算权值矢量的误差，小于一定域值则停止，或直接确定循环次数。中间包括有权值矢量有序化阶段和收敛阶段。蚁群不再（或很少）搬起待聚类模式（达到收敛条件）或直接确定循环次数。输出：形成明确的权值矢量，NxN个（或小于NxN）聚类中心。形成平面直观的聚类中心，中心个数不确定，受概率影响，聚类结果有一定的不确定性。重要参数：获胜神经元邻近区域函数L(n)、学习率h(n)，参数在迭代过程中变化。 群体相似系数、概率转换函数观察区域半径d。参数可为变量。（基本模型：搬起常数Kp，放下常数Kd，相似度归一常数a，参数为常数）特点：神经网络、自组织、竞争学习、墨西哥草帽函数建立反馈模型基于蚁群打扫蚁巢行为的解释

18、模型，自适应、无集中控制、适合分布式环境。 2、算法描述算法的基本过程描述如下：步骤1、参数初始化，,cycle_counter, ant_number, r ,k，MAXCYCLENUMBER；步骤2、将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x,y）坐标；步骤3、给一组蚂蚁赋初始模式值，初始状态为无负载；步骤4、循环次数cycle_counter加1；步骤5、此组蚂蚁开始聚类循环；步骤6、以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用公式（6）计算此模式在观察半径范围内的群体相似度；步骤7、若本只蚂蚁无负载，则用公式（7）计算拾起概率Pp；步骤8、 与一随机概率Pr

19、相比较，若PpPr则蚂蚁不拾起此模式，再随机赋给蚂蚁一个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标。步骤9、若本只蚂蚁有负载，则用公式（8）计算放下概率Pd；步骤10、与一随机概率Pr相比较，若Pd>Pr则蚂蚁放下此模式，将蚂蚁的坐标赋给此模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值，否则蚂蚁继续携带此模式，蚂蚁状态仍为有负载，再次随机给蚂蚁一个新坐标。；步骤11、若此组所有蚂蚁完成循环，则继续，否则选取下一只未循环蚂蚁转向步骤5；步骤12、以一定的步长调整；步骤13、 若循环次数小于最大循环次数MAXCYCLENUMBER，转向步骤4，否则程序结束。算法

20、的结束条件可以是直接设定最大循环次数，也可用各聚类中心不再有模式移动为标准即算法已收敛。其中步骤12调整的方法可以是连续微调，也可以每循环一个固定次数后再调整，本文采用了后一种方式，此外在这一步还可调整其它参数如观察半径等。4. 实验结果及分析本文测试数据都来自于UCI的(/mlearn/MLRepository.html) 机器学习数据库。本文选取了三组测试数据。它们分别是动物（zoo）、鸢草（iris）和图像(image) 数据库。其中动物数据库为101个记录，16个条件属性，1个决策属性，7 个类别分别是哺乳动物、鸟类、爬行动物、两栖动物、鱼类、

21、昆虫和节肢动物。鸢草是经典聚类测试数据库，有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实验结果图，其中红色表示哺乳动物；兰色表示鸟类；绿色表示爬行动物；品红色表示两栖动物；青色表示鱼类；黄色表示昆虫；灰色表示节肢动物。表2是ZOO实验结果表。从实验

22、结果可知，CSI聚类算法不仅基本能将7种类型的动物分开，而且还得到了一些细分的结果，如红色表示的哺乳动物被分为了三个部分，其中最大的一个类别是陆生哺乳动物共有36种动物，第二类别是4个是水生哺乳动物有4种动物，哺乳动物中很特别的卵生哺乳动物鸭嘴兽被单独归成第三类。表2ZOO实验结果表原类别 新类别动物名称1哺乳动物1陆生哺乳动物aardvark, antelope, bear, boar, buffalo, calf, cavy, cheetah, deer, elephant,fruitbat, giraffe, girl, goat, gorilla, hamster, hare, leo

23、pard, 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,octopus,seawasp,starfish 6昆虫，7、节肢动物5昆虫、素食节肢动物(2)Flea， gnat， h

24、oneybee， 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， （3）tortoise4鱼类，7鱼类bass ，carp ，catfish，chub，dogfish，haddock，

25、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=1000X600；ant_number=10, r= 25,k=0.1， size=750X480实验结果为图2所

26、示：图中红色表示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模式，绿色表示类别Iris-virginica模式，实验结果如下：聚类后只有编号为107、120、134、135的共4个Iris-

27、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个聚类中心，但是三种类别的模式相互混在同一个聚类中心内。0.4-0.3200X300形成24个聚类中心，类别混淆个数不大

28、于10。0.2200X3600形成10个左右聚类中心，类别为Iris-virginicat 和Iris-versicolor的模式分散生成多个聚类中心，类别混淆个数更少。0.1未出现收敛，实验次数为200X10000无聚类中心，模式仍随机分散分布。表3是IRIS实验群体相似系数与聚类结果对照表。从表中可看出群体相似系数对聚类结果影响很大。它不仅影响算法的收敛速度，而且影响聚类的结果，包括聚类中心的数目和聚类的质量。一般情况下，群体相似系数越小，算法收敛越慢，聚类中心个数增多，而群体相似系数越大，算法收敛越快，聚类中心个数减少，但是不适当的群体相似系数值可能导致算法太慢或不收敛和聚类结果无效即距

29、离相差很大的模式聚在一起。5. 结论本文对基于群体智能的聚类算法进行了研究，在基本解释模型的基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成一种基于群体智能的聚类算法，并提出了一种相关的简化概率转换函数。实验证明这一基于群体智能的聚类算法是一种自组织聚类算法，具备健壮性、可视化等特点，并能生成一些新的有意义的聚类模式。本文还通过实验分析了群体相似系数对聚类算法的影响，实验证明群体相似系数是聚类算法的一个关键参数。此算法是一种基于简单个体与局部环境相互作用的无集中控制的聚类算法，适应分布式环境，虽然目前在时间复杂性和空间复杂性方面与经典的聚类算法相比并不具备优势，但是作为

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

31、6,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; 4/Courses/EE150/dungeon5 Bonabeau,E.,Dorigo,

32、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., Goss S

33、.,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 Books, Ca

34、mbridge, 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 robot

35、ics, 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 Books,

36、 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 technology,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