蚁群聚类算法研究及应用Word文件下载.docx

1、裴振奎（1962），男，山东东营人，博士研究生，副教授，硕士生导师，研究方向为机器学习与计算智能；李华（1977），女，山东滨州人，硕士研究生，研究方向为数据挖掘、自然计算；宋建伟（1982），女，河北廊坊人，硕士研究生，研究方向为网络安全、计算智能；韩锦峰（1981），女，山西大同人，硕士研究生，研究方向为计算智能、数据库系统理论。裴振奎，李华，宋建伟，韩锦峰（中国石油大学（华东）计算机与通信工程学院，山东东营257061）摘要：聚类作为数据挖掘技术的重要组成部分，在很多领域有着广泛应用。蚁群算法是近几年研究的一种新算法，该算法采用分布式并行计算和正反馈机制，具有易于与其它方法相结合的优点。

2、根据蚁群算法在聚类中的应用及改进型式的不同，文章主要介绍了几种基本的流行的蚁群聚类算法，分析了它们的不同之处，并对蚁群聚类算法今后的研究方向作了展望。关键词：聚类;蚁群算法;信息素;正反馈机制;蚁群聚类算法中图法分类号：TP301文献标识码：A文章编号：1000-7024（2008）19-5009-05Investigation and application of ant colony clustering algorithmsPEI Zhen-kui,LI Hua,SONG Jian-wei,HAN Jin-feng（College of Computer and Communicatio

3、n Engineering,China University of Petroleum（East China）,Dongying 257061,China）Abstract：Clustering is widely used in some fields as a part of important data mining.Ant colony algorithms are novel algorithms in re-cently years.These methods have several virtues such as distributed parallel computing,p

4、ositive feedback mechanism and combinationwith certain heuristics.Some kinds of basic and popular ant colony clustering algorithms are introduced,the differences of them areanalyzed and the direction for study of ant colony algorithms based on application and improving modality in clustering.Key wor

5、ds：clustering;ant colony algorithm;pheromone;positive feedback mechanism;ant colony clustering algorithm计算机工程与设计2008年10月Oct.2008第29卷第19期Vol.29 No.19 Computer Engineering and Design5010蚁行为特征的聚类算法，如：蚂蚁觅食原理为基础的聚类、受蚂蚁堆积尸体启发的聚类等。这类算法大多是根据具体情况对系数、参数及公式等的改进。多种群的蚁群聚类算法，这类算法主要是将上述的单种群扩大为多种群，以完善聚类效果、提高速度。与其它方

6、法结合，通过优势互补来改善聚类效果、提高聚类质量、缩短聚类时间，如与K-Means算法结合1，与遗传算法结合的算法等。蚁群聚类算法应用很广，从Deneubourg发现蚂蚁能将分散在蚁穴各处的蚂蚁尸体按一定规律垒堆起来，并依此提出了基于蚂蚁的聚类基本模型开始。之后，Lumer和Faieta在此基础上提出了用于聚类分析的LF算法2，并将其应用到数据分析当中。Monmarch引入AntClass系统，交替使用蚁群聚类和k均值算法修正误差，获到“高质量”的聚类。Ramos等人3、Handl等人4将LF算法用于文本聚类。Kuntz和Snye则对每对图像节点的非相似度值函数做了修改，将之用于图像的分割，韩

7、彦芳等人5从模糊角度出发结合蚁群特点提出了用于图像分割的蚁群聚类算法。吴斌等人6将基于蚁群的聚类算法用于客户关系管理中的客户行为分析以及Web文档聚类。翁怀荣等人7引入随机扰动和感觉知觉特征以指导信息素的更新，并将改进后的蚁群聚类算法用到企业人力资源管理中。总之，随着蚁群聚类算法研究的深入，其应用领域也在不断扩大。3算法分析3.1基于蚂蚁行为特征的聚类算法3.1.1基于蚂蚁觅食原理蚂蚁觅食主要分搜索和搬运食物两步。蚂蚁移动时在所经路径留下信息素，通过感知信息素的强弱进行非直接通信，形成正反馈加强搜索。在该算法中，一般将数据视为具有不同属性的蚂蚁，聚类中心即蚂蚁所要寻找的“食物源”，数据聚类过程

8、被看作是蚂蚁寻找食物源的过程。基本思想8：假设待聚类对象为=|=（,）,=1,2,，算法首先进行初始化，将设置各个路径的信息素0=0，半径，统计误差，代表对象等参数。计算对象到之间的加权欧氏距离=及各路径上的信息素1,0,，将对象合并到的概率为=（1）式中：=,=1,2,+1,，、控制参数的常量，权值。如果阈值常数，则将合并到的领域。该方法的优缺点：不需要预先设置聚类数，但由于簇半径已经给出所以聚类规模受到了限制；代表对象对运行效率及聚类结果影响较大，选择不当将陷入局部最优解；若待聚类数据大时，算法的执行速度慢。为了缩短算法时间，文献9改进了算法，使蚂蚁在空载时搜索数据对象，负载时搜索簇相结合

9、，既能扫描所有数据元素，又能利用信息素痕迹引导蚂蚁快速返回到簇，加速算法收敛。但这种方法也存在问题：不再将数据都视为蚂蚁，这就需要确定蚂蚁数。蚂蚁数目的大小影响聚类的性能和收敛速度：太少，收敛速度变慢；太多则使聚类性能变坏。其次，蚂蚁转移以信息素的大小作为依据，因此算法容易陷入局部最优解。目前，基于蚂蚁觅食原理的聚类算法是用的较多的蚁群聚类算法，但仍然存在如上所述的问题，因此还有待进一步改进。3.1.2蚁堆形成原理生物学研究显示，蚂蚁能将群体中死亡的蚂蚁聚集成堆。工蚁对不同的蚂蚁尸体分别放置，小的蚁堆通过吸引工蚁将更多的尸体放置其中。待聚类的个体逐个被拾起，并根据周围的环境将个体再逐一放下。基

10、本思想：假设所有的数据对象都随机地分布在二维的与数据集成比例伸缩的网格中，处于网格中的两个对象和之间的距离（又叫相异度）,=0，反之则为1，得到一个二进制相异度矩阵。设若干个蚂蚁在此二维网格上移动，反复执行拾起或放下对象的操作。如果蚂蚁某一时刻在位置处发现了对象，则在处与相似的对象的局部密度为=max0,11+1max（2）对象领域中出现其它对象时的平均相似度。参数为相异度比例，位置的领域的面积为。蚂蚁速度均匀分布于1,，其中是一个蚂蚁在一个时间单元内沿给定的网格轴线行走的网格单元数。每次循环蚂蚁拾起和放下对象的原则：如果蚂蚁没有负载，即没有搬运对象，则随机从邻近的单元拾起一个对象，拾起概率为

11、+（3）如果蚂蚁有负载，则它随机的选择邻近的空单元放下该对象，或者如果负载对象与邻近对象相似也放下该对象，放下概率为2,（4）其中都为一个阈值常数。蚂蚁拾起或放下负载对象受局部相似密度影响，局部相似度大，则拾起概率就小、放下概率大，负载对象不易被移走；反之亦然。同时，蚂蚁的移动速度也将影响拾起或放下对象。该算法是基于网格和密度的聚类方法，高维数据空间首先映射到某一低维网格空间，映射要确保簇间距离不小于簇内距离。算法优点：不需要预先设定聚类的簇数，同时由于是基于密度的聚类方法，还可以发现任意形状的簇。缺点：随机的拾起、移动和放下对象，因此算法的收敛速度很慢；网格的精细度影响聚类结果的精细度，且存

12、在能否搜索到所有对象的问题。3.1.3蚂蚁自我聚集行为的聚类蚂蚁通过自我聚集行为构建的树状结构，称为蚂蚁树（AntTree）10树中的节点是蚂蚁表示的数据，蚂蚁能够达到树的任何地方并能粘在任何位置上。起初，蚂蚁被放在一个相当于树根的固定点上，蚂蚁在这棵树上或已经固定在树上的蚂蚁身上移动，来寻找适合的位置，由于受到对象间的作用，5011蚂蚁更趋于固定在树枝的末端。树的结构和蚂蚁表示的数据之间的相似性引导它的移动，当所有蚂蚁都在树上固定后，就获得了数据集的划分。规定每只蚂蚁只有一个父亲节点，最多有个孩子结点。对每只蚂蚁都定义一个相似度阈值（）和相异度阈值（），并由进行局部更新，用来判断蚂蚁表示的数

13、据与其它蚂蚁表示的数据的相似或相异程度。蚂蚁的局部行为：第一个蚂蚁直接连接到上，对后来的蚂蚁分两种情况：（1）在支点上。设为支点上且与最相似的蚂蚁，若和足够相似，即,，则它就连接在支点上，意味创建了一棵新子树，该子树上的蚂蚁将尽可能的与以为根的其它子树上的蚂蚁不同，其中,=11表示相似度尺度；若已经有孩子结点，则向移动。假如和既不足够相似也不足够相异，则用式（5）,（6）更新阈值*（5）+（6）增加下次连接的概率（，为调解因子）。（2）在蚂蚁上移动。若的孩子结点少于且与足够相似（即，），与上其它蚂蚁足够相异（即，,（8）蚂蚁相遇规则：两只均没巢的蚂蚁相遇并彼此接受时将创建一个新巢，作为“种子”

14、聚集相似蚂蚁以产生最终的簇；没巢的蚂蚁遇到有巢的蚂蚁并且可以别接受时，没巢的蚂蚁加入；属于同一个巢的蚂蚁在彼此接受的情况下增加评价因子和，蚂蚁依感知其巢的大小，根据感知与巢中其它蚂蚁的接受度；同巢的两只蚂蚁相遇且不能彼此接受，减少，当小于一定程度该蚂蚁的标签和重新被置为0，此时被当作“异类”从巢中被驱逐出去；不同巢的蚂蚁相遇且彼此接受则合并巢。该算法无需给定聚类数就能自动实现数据集的聚类；适用于数字向量、字符串以及多媒体等多种类型的数据。大量采用随机策略使蚂蚁达到平衡的效率不高；时间复杂度难以估计。文献12受蚂蚁化学识别系统的聚类算法启发，在给出有效的聚类评判标准的基础上设计出无参化的聚类算法

15、。3.1.5受蚂蚁分巢居住行为启发的聚类该算法13中，将蚂蚁看成一个行为简单的Agent，代表一个数据对象。蚂蚁有睡眠和活跃两种状态，并定义了适应度函数来衡量蚂蚁与其领域的相似度，通过适应度和激活概率函数决定蚂蚁所处的状态。整个蚂蚁动态地、自适应地、自组织地形成多个独立的子群体，使不同类别的蚂蚁之间互相分离，同类蚂蚁紧密排列，从而形成聚类。蚂蚁在0101的二维网格空间中活动，=0.5（为上取整函数），网格上、下边界相连，左、右相连。将的状态记为，=（，）1，这里为数据个数，和为所在位置的坐标，表示它所在类的类号，反映它当前是出于活跃还是睡眠状态。采用Moore型领域使蚂蚁在网格的任何一个位置的

16、周围都有8个邻居，并记为为的邻域。定义当前位置的适应度函数为为9（1,）（9）,Agent代表的数据对象和之间的距离，即相异度。参数的值可由以下公式确定=,（10）蚂蚁在环境中转为活跃态的激活概率=（11）参数，称为激活阈值，并作自适应的调整，其增量依据式（12）调整=（12）常数，第代Agent的平均适应度。蚂蚁移动中，用表示聚类规则的集合。的类别信息通过中以下的规则更新：到达一个合适的位置变为睡眠态，其类号改变，取邻域中与其相异度最小的Agent的类号；由睡眠态变为活跃态，其类号也改变，以它的标号作为其在移动期间的类号；继续保持睡眠态不变，则其类号保持不变。该算法通过活跃和睡眠两种状态，克

17、服了蚂蚁数目难确5012定的问题，同时又不会遗漏待聚类对象；自适应的修改参数，所以对参数的限制也少，算法参数少。虽然就聚类质量来说它有了很大的提高，但仍然存在执行时间长的问题。3.2多种群蚂蚁聚类受种群之间相互协作的启发，多种群聚类算法通过信息交换来发现优化结果多种群聚类是在单种群聚类的基础上，将单种群扩大到多种群的算法，而各种群可采用相同14或不同的蚁群聚类算法进行聚类。在文献14中，需要预先设置聚类数M，通过选择M个对象确定初始的聚类中心，采用最近邻法进一步修改聚类中心，并根据聚类中心确定种群数。在修改后的聚类中心及规定的搜索周期内，再进一步对待聚类对象进行划分。采用不同种群聚类主要分两部

18、：一是相异蚁群的各自聚类；二是将来自不同蚁群的聚类柔和。这里各种群中的蚂蚁可以不同步速移动，也可以将转化公式中的参数设置为不同值。每次各种群聚类行为后将各自的结果，通过超图模型合并，得到新的相似矩阵。同时，将新的相似矩阵作为信息返回到各蚁群当中，以指导下此的聚类行为。信息交换策略也可以采用：种群各自传递各自的信息策略、循环交叉传递信息策略和选择上次循环中聚类质量最好时的信息策略。图1给出了多种群聚类算法的一种结构15图的底层为3种速度不同的蚁群模块进行聚类，得到初步结果；上层为聚类组合模块，并将初步聚类结果组合成一个超图；再上层为图划分模块，采用基于蚁群算法的图划分算法对超图进行二次划分，得到

19、最终结果。虽然采用多种群的蚁群聚类算法往往比单种群的算法在聚类结果上要好，但这一方法与单种群聚类算法相比需要花更多的时间，各蚁群数量也不好选择，各种群聚类不好控制，同时需要设置多个参数。3.3混合的蚂蚁聚类算法3.3.1与K-Means算法的混合考虑到K-Means算法有快速收敛的优点，以此改进蚁群聚类算法，达到缩短算法时间的目的。等人提出的AntClass算法是在蚁堆聚类的基础上，交替使用蚁群聚类和K-Means算法修正误差以获到“高质量”的聚类。高尚等人14,16则先利用K-Means算法对数据进行快速分类，根据分类结果更新信息素，来指导其它蚂蚁选择。该类算法中，蚁群聚类部分多采用单种群的

20、聚类算法。先采用K-Means算法进行初步聚类的最大缺点是对聚类数预先设置。结合密度思想的蚁群聚类算法17在使用K-Means算法之前使用蚂蚁聚类，得到初始的聚类中心，以求避免传统聚类算法对初始分割的要求。3.3.2与遗传算法的混合该聚类算法18主要利用了遗传算法的快速全局搜索能力和蚁群算法的正反馈收敛机制。算法第一步利用遗传算法对数据进行初步聚类，形成初始聚类中心；第二步利用蚁群算法完善聚类结构。该算法的基本框架如图2所示。这类算法中的蚁群聚类算法也主要基于单蚁群的聚类算法。虽然两算法结合一定程度地相互弥补了对方的不足，但算法的合点仍是一个问题，同时算法的复杂度和效率也不是那么理想。与其它算

21、法结合的蚁群聚类算法，主要也是为了克服原蚁群聚类算法的效率低及易陷入局部最优的缺点，是今后蚁群聚类算法改进和研究的主要方向。4结束语蚁群聚类算法具有很多特性：并行性、自组织性、鲁棒性和灵活性，对算法稍作修改就可以应用到很多领域，因此其研究价值不言而喻。本文主要总结了现今存在的部份蚁群聚类算法，针对每种基于蚁群的聚类算法分别论述了它们的基本思想、聚类原理以及主要步骤。在指出了蚁群聚类算法各自所具有的优点同时，也分析了各自存在的缺点，如：一部分算法的聚类数仍需预先设置的缺陷、参数过多的问题、算法仍存在易陷入局部最优的问题及算法执行时间过长的问题等，这对算法的改进方向提供了依据。参考文献:1Monm

22、archN,Slimane M,Venturini G.On improving clusteringin numerical databases with artificial antsC.Lecture notes inArtificial Intelligence,1999:13-17.2Yang Yan,Mohamed S Kamelb.An aggregated clustering ap-proach using multi-ant colonies algorithmsJ.Pattern Recogni-tion,2006,39:1278-1289.3Vitorino R,Jua

23、n J M.Self-organized stigmergic document maps:图1多蚁群聚类算法结构最终聚类结果图划分聚类组合蚁群1常数蚁群2随机数蚁群3递减随机数图2与遗传算法结合的蚁群聚类算法框架生成若干组合优化解解码YN满足条件群体t+2依次运算：选择、交叉、变异计算适应度函数群体t个体编码定义目标函数和适应度函数问题描述随机将蚂蚁及初始聚类均匀分布在平面内，初始化所有参数对每只蚂蚁根据公式计算对象的平均相似度及对象间的距离对每只蚂蚁计算拾起、放下概率对所有对象标识聚类序列号输出聚类结果5013Environment as a mechanism for context l

24、earningC.Alba E,Herrera F,Merelo J J,et al.Proc of the 1st Intl Conf On Meta-heuristics,Evolutionary and Bio-Inspired Algorithms,2002:284-293.4Handl J,Meyer B.Improved ant-based clustering and sorting in adocument retrieval interfaceC.LNCS 2439,2002:913-923.5韩彦芳,施鹏飞.基于蚁群算法的图像分割方法J.计算机工程与应用,2004,40（18）:5-7.6吴斌,郑毅,傅伟鹏,等.一种基于群体智能的客户行为分