蚁群聚类算法研究及应用Word文件下载.docx
《蚁群聚类算法研究及应用Word文件下载.docx》由会员分享，可在线阅读，更多相关《蚁群聚类算法研究及应用Word文件下载.docx（24页珍藏版）》请在冰点文库上搜索。
裴振奎（1962－），男，山东东营人，博士研究生，副教授，硕士生导师，研究方向为机器学习与计算智能；
李华（1977－），女，山
东滨州人，硕士研究生，研究方向为数据挖掘、自然计算；
宋建伟（1982－），女，河北廊坊人，硕士研究生，研究方向为网络安全、计算智能；
韩锦峰（1981－），女，山西大同人，硕士研究生，研究方向为计算智能、数据库系统理论。
裴振奎，李华，宋建伟，韩锦峰
（中国石油大学（华东）计算机与通信工程学院，山东东营257061）
摘要：
聚类作为数据挖掘技术的重要组成部分，在很多领域有着广泛应用。
蚁群算法是近几年研究的一种新算法，该算法
采用分布式并行计算和正反馈机制，具有易于与其它方法相结合的优点。
根据蚁群算法在聚类中的应用及改进型式的不同，
文章主要介绍了几种基本的流行的蚁群聚类算法，分析了它们的不同之处，并对蚁群聚类算法今后的研究方向作了展望。
关键词：
聚类;
蚁群算法;
信息素;
正反馈机制;
蚁群聚类算法
中图法分类号：
TP301文献标识码：
A文章编号：
1000-7024（2008）19-5009-05
Investigationandapplicationofantcolonyclusteringalgorithms
PEIZhen-kui,LIHua,SONGJian-wei,HANJin-feng
（CollegeofComputerandCommunicationEngineering,ChinaUniversityofPetroleum（EastChina）,
Dongying257061,China）
Abstract：
Clusteringiswidelyusedinsomefieldsasapartofimportantdatamining.Antcolonyalgorithmsarenovelalgorithmsinre-
centlyyears.Thesemethodshaveseveralvirtuessuchasdistributedparallelcomputing,positivefeedbackmechanismandcombination
withcertainheuristics.Somekindsofbasicandpopularantcolonyclusteringalgorithmsareintroduced,thedifferencesofthemare
analyzedandthedirectionforstudyofantcolonyalgorithmsbasedonapplicationandimprovingmodalityinclustering.
Keywords：
clustering;
antcolonyalgorithm;
pheromone;
positivefeedbackmechanism;
antcolonyclusteringalgorithm
计算机工程与设计2008年10月
Oct.2008
第29卷第19期
Vol.29No.19ComputerEngineeringandDesign－5010－
蚁行为特征的聚类算法，如：
蚂蚁觅食原理为基础的聚类、受
蚂蚁堆积尸体启发的聚类等。
这类算法大多是根据具体情况
对系数、参数及公式等的改进。
②多种群的蚁群聚类算法，这
类算法主要是将上述的单种群扩大为多种群，以完善聚类效
果、提高速度。
③与其它方法结合，通过优势互补来改善聚类
效果、提高聚类质量、缩短聚类时间，如与K-Means算法结合
[1]
，
与遗传算法结合的算法等。
蚁群聚类算法应用很广，从Deneubourg发现蚂蚁能将分
散在蚁穴各处的蚂蚁尸体按一定规律垒堆起来，并依此提出
了基于蚂蚁的聚类基本模型开始。
之后，Lumer和Faieta在此
基础上提出了用于聚类分析的LF算法
[2]
，并将其应用到数据
分析当中。
Monmarché
引入AntClass系统，交替使用蚁群聚类
和k均值算法修正误差，获到“高质量”的聚类。
Ramos等人
[3]
、
Handl等人
[4]
将LF算法用于文本聚类。
Kuntz和Snye则对每
对图像节点的非相似度值函数做了修改，将之用于图像的分
割，韩彦芳等人
[5]
从模糊角度出发结合蚁群特点提出了用于图
像分割的蚁群聚类算法。
吴斌等人
[6]
将基于蚁群的聚类算法
用于客户关系管理中的客户行为分析以及Web文档聚类。
翁
怀荣等人
[7]
引入随机扰动和感觉知觉特征以指导信息素的更
新，并将改进后的蚁群聚类算法用到企业人力资源管理中。
总
之，随着蚁群聚类算法研究的深入，其应用领域也在不断扩大。
3算法分析
3.1基于蚂蚁行为特征的聚类算法
3.1.1基于蚂蚁觅食原理
蚂蚁觅食主要分搜索和搬运食物两步。
蚂蚁移动时在所
经路径留下信息素，通过感知信息素的强弱进行非直接通信，
形成正反馈加强搜索。
在该算法中，一般将数据视为具有不
同属性的蚂蚁，聚类中心即蚂蚁所要寻找的“食物源”，数据聚
类过程被看作是蚂蚁寻找食物源的过程。
基本思想
[8]
：
假设待聚类对象为={|=（
…,）,=
1,2,…,}，算法首先进行初始化，将设置各个路径的信息素
0=0，半径，统计误差，代表对象等参数。
计算对象到
之间的加权欧氏距离
=
及各路径上的信息素
｛
1,
0,>
，将对象合并到的概率为
=
（1）
式中：
={≤,=1,2,…,,+1,…,}，、——控制参数的
常量，——权值。
如果>
——阈值常数，则将合
并到的领域。
该方法的优缺点：
不需要预先设置聚类数，但由于簇半径
已经给出所以聚类规模受到了限制；
代表对象对运行效率
及聚类结果影响较大，选择不当将陷入局部最优解；
若待聚类
数据大时，算法的执行速度慢。
为了缩短算法时间，文献[9]改
进了算法，使蚂蚁在空载时搜索数据对象，负载时搜索簇相结
合，既能扫描所有数据元素，又能利用信息素痕迹引导蚂蚁快
速返回到簇，加速算法收敛。
但这种方法也存在问题：
不再将
数据都视为蚂蚁，这就需要确定蚂蚁数。
蚂蚁数目的大小影
响聚类的性能和收敛速度：
太少，收敛速度变慢；
太多则使聚
类性能变坏。
其次，蚂蚁转移以信息素的大小作为依据，因此
算法容易陷入局部最优解。
目前，基于蚂蚁觅食原理的聚类
算法是用的较多的蚁群聚类算法，但仍然存在如上所述的问
题，因此还有待进一步改进。
3.1.2蚁堆形成原理
生物学研究显示，蚂蚁能将群体中死亡的蚂蚁聚集成堆。
工蚁对不同的蚂蚁尸体分别放置，小的蚁堆通过吸引工蚁将
更多的尸体放置其中。
待聚类的个体逐个被拾起，并根据周
围的环境将个体再逐一放下。
基本思想：
假设所有的数据对象都随机地分布在二维的
与数据集成比例伸缩的网格中，处于网格中的两个对象和
之间的距离（又叫相异度）,=0，反之则为1，得到一个二
进制相异度矩阵。
设若干个蚂蚁在此二维网格上移动，反复
执行拾起或放下对象的操作。
如果蚂蚁某一时刻在位置处
发现了对象，则在处与相似的对象的局部密度为
=max{0,
[1
1+1
max
]}
（2）
——对象领域中出现其它对象时的平均相似
度。
参数为相异度比例，位置的领域
×
的面积为×
。
蚂蚁速度均匀分布于[1,
]，其中是一个蚂蚁在一个时间单
元内沿给定的网格轴线行走的网格单元数。
每次循环蚂蚁拾起和放下对象的原则：
如果蚂蚁没有负
载，即没有搬运对象，则随机从邻近的单元拾起一个对象，拾
起概率为
+
（3）
如果蚂蚁有负载，则它随机的选择邻近的空单元放下该
对象，或者如果负载对象与邻近对象相似也放下该对象，放下
概率为
2,<
（4）
其中
都为一个阈值常数。
蚂蚁拾起或放下负载对象受局
部相似密度影响，局部相似度大，则拾起概率就小、放下概
率大，负载对象不易被移走；
反之亦然。
同时，蚂蚁的移动速
度也将影响拾起或放下对象。
该算法是基于网格和密度的聚类方法
，高维数据空间首
先映射到某一低维网格空间，映射要确保簇间距离不小于簇
内距离。
算法优点：
不需要预先设定聚类的簇数，同时由于是
基于密度的聚类方法，还可以发现任意形状的簇。
缺点：
随机
的拾起、移动和放下对象，因此算法的收敛速度很慢；
网格的
精细度影响聚类结果的精细度，且存在能否搜索到所有对象
的问题。
3.1.3蚂蚁自我聚集行为的聚类
蚂蚁通过自我聚集行为构建的树状结构，称为蚂蚁树
（AntTree）
[10]
树中的节点是蚂蚁表示的数据，蚂蚁能够达到树
的任何地方并能粘在任何位置上。
起初，蚂蚁被放在一个相
当于树根的固定点上，蚂蚁在这棵树上或已经固定在树上的
蚂蚁身上移动，来寻找适合的位置，由于受到对象间的作用，－5011－
蚂蚁更趋于固定在树枝的末端。
树的结构和蚂蚁表示的数据
之间的相似性引导它的移动，当所有蚂蚁都在树上固定后，就
获得了数据集的划分。
规定每只蚂蚁只有一个父亲节点，最多有
个孩子结点。
对每只蚂蚁都定义一个相似度阈值（）和相
异度阈值（），并由进行局部更新，用来判断蚂蚁表示
的数据与其它蚂蚁表示的数据的相似或相异程度。
蚂蚁的局部行为：
第一个蚂蚁直接连接到上，对后来的蚂
蚁分两种情况：
（1）在支点上。
设
为支点上且与最相似的蚂蚁，若
和
足够相似，即,
≥，则它就连接在支点上，意
味创建了一棵新子树，该子树上的蚂蚁将尽可能的与以
为根
的其它子树上的蚂蚁不同，其中,=11
表示相似度尺度；
若
已经有
孩子结点，则向
移动。
假
如和
既不足够相似也不足够相异，则用式（5）,（6）更新阈值
*（5）
+（6）
增加下次连接的概率（，为调解因子）。
（2）在蚂蚁上移动。
若的孩子结点少于且与
足够相似（即，≥），与上其它蚂蚁足够相
异（即，
<
），则连接到上，否则蚂蚁随机地
向的邻居移动，其中
表示上与最相似的蚂蚁。
根据
需要更新阈值，寻找合适的位置，当所有蚂蚁都连接好时算法
结束。
这种算法连接后就不再移动，因此算法执行时间相对较
短，但树状结构体一旦形成就不好再调整，因此初始值
的选
取至关重要，、调解因子的大小不好掌握也对聚类结果造成
一定的影响。
3.1.4基于化学识别的聚类（AntClust）
对蚂蚁来说，每天都面临相遇时进行识别的问题，因为是
否属于同一个巢关乎巢的安全。
蚂蚁幼时由群体中的成年蚂
蚁喂养，通过身体接触接受了其气味并依此建立早期的识别
模板，随着蚂蚁的成长它们自身的化学气味逐渐增强，并因此
影响到与之接触的其它蚂蚁，这样同巢蚂蚁就建立起它们所
共享的气味。
[11]
每只蚂蚁定义如下参数：
蚂蚁巢穴属性决
定的标签，用来代表巢。
起初蚂蚁不受任何巢穴的影响，
所以=0，随后标签不断变换直到蚂蚁找到最好的巢为
止。
模版由蚂蚁的基因和接受阈值组成，前
者对应数据集的对象且在算法过程中不断变化，后者在初始
化阶段获得的，它是蚂蚁与其它蚂蚁相遇期间观察到的最大
相似度,.和平均相似度,.的函数，是动态的，蚂
蚁每次和其它蚂蚁相遇后按式（7）进行修改
←
.+,.
（7）
评价因子反映蚂蚁之间的相遇情况。
相同标签的蚂蚁
相遇时增加，反之减少。
开始时=0，反映蚂蚁所在巢穴
的规模。
表示蚂蚁被接受程度，若具有相同标签的蚂蚁相
遇或两只蚂蚁彼此接受对方，
增加，否则不接受时减少。
蚂
蚁可根据下面公式判断接受与否，设，分别表示两只蚂蚁，则
,>
>
（8）
蚂蚁相遇规则：
①两只均没巢的蚂蚁相遇并彼此接受时
将创建一个新巢，作为“种子”聚集相似蚂蚁以产生最终的
簇；
②没巢的蚂蚁遇到有巢的蚂蚁并且可以别接受时，没巢的
蚂蚁加入；
③属于同一个巢的蚂蚁在彼此接受的情况下增加
评价因子和
，蚂蚁依感知其巢的大小，根据
感知与巢
中其它蚂蚁的接受度；
④同巢的两只蚂蚁相遇且不能彼此接
受，减少
，当
小于一定程度该蚂蚁的标签和重新
被置为0，此时被当作“异类”从巢中被驱逐出去；
⑤不同巢的
蚂蚁相遇且彼此接受则合并巢。
该算法无需给定聚类数就能自动实现数据集的聚类；
适
用于数字向量、字符串以及多媒体等多种类型的数据。
大量采用随机策略使蚂蚁达到平衡的效率不高；
时间复杂度
难以估计。
文献[12]受蚂蚁化学识别系统的聚类算法启发，在
给出有效的聚类评判标准的基础上设计出无参化的聚类算法。
3.1.5受蚂蚁分巢居住行为启发的聚类
该算法
[13]
中，将蚂蚁看成一个行为简单的Agent，代表一
个数据对象。
蚂蚁有睡眠和活跃两种状态，并定义了适应度
函数来衡量蚂蚁与其领域的相似度，通过适应度和激活概率
函数决定蚂蚁所处的状态。
整个蚂蚁动态地、自适应地、自组
织地形成多个独立的子群体，使不同类别的蚂蚁之间互相分
离，同类蚂蚁紧密排列，从而形成聚类。
蚂蚁在[0…1]×
[0…1]的二维网格空
间中活动，==
0.5
（为上取整函数），网格上、下
边界相连，左、右相连。
将的状态记为，=（，，，）1≤
≤，这里为数据个数，和为所在位置的坐标，表示
它所在类的类号，反映它当前是出于活跃还是睡眠状态。
采
用Moore型领域使蚂蚁在网格的任何一个位置的周围都有8
个邻居，并记为为的邻域。
定义当前位置
的适应度函数为为
9
（1
,
）}（9）
——Agent代表的数据对象和之间的距
离，即相异度。
参数的值可由以下公式确定
=[
][
]（10）
蚂蚁在环境中转为活跃态的激活概率
=（11）
参数
，称为激活阈值，并作自适应的调整，其增量依
据式（12）调整
=（12）
——常数，——第代Agent的平均适应度。
蚂蚁
移动中，用表示聚类规则的集合。
的类别信息通过
中以下的规则更新：
①到达一个合适的位置变为睡眠
态，其类号改变，取邻域中与其相异度最小的Agent的类号；
②由睡眠态变为活跃态，其类号也改变，以它的标号作
为其在移动期间的类号；
③继续保持睡眠态不变，则其类
号保持不变。
该算法通过活跃和睡眠两种状态，克服了蚂蚁数目难确－5012－
定的问题，同时又不会遗漏待聚类对象；
自适应的修改参数，
所以对参数的限制也少，算法参数少。
虽然就聚类质量来说
它有了很大的提高，但仍然存在执行时间长的问题。
3.2多种群蚂蚁聚类
受种群之间相互协作的启发，多种群聚类算法通过信息
交换来发现优化结果
多种群聚类是在单种群聚类的基础
上，将单种群扩大到多种群的算法，而各种群可采用相同
[14]
或
不同的蚁群聚类算法
进行聚类。
在文献[14]中，需要预先设置聚类数M，通过选择M个对
象确定初始的聚类中心，采用最近邻法进一步修改聚类中心，
并根据聚类中心确定种群数。
在修改后的聚类中心及规定的
搜索周期内，再进一步对待聚类对象进行划分。
采用不同种群聚类主要分两部：
一是相异蚁群的各自聚
类；
二是将来自不同蚁群的聚类柔和。
这里各种群中的蚂蚁
可以不同步速移动，也可以将转化公式中的参数设置为不同
值。
每次各种群聚类行为后将各自的结果，通过超图模型合
并，得到新的相似矩阵。
同时，将新的相似矩阵作为信息返回
到各蚁群当中，以指导下此的聚类行为。
信息交换策略也可
以采用：
种群各自传递各自的信息策略、循环交叉传递信息策
略和选择上次循环中聚类质量最好时的信息策略。
图1给出了多种群聚类算法的一种结构
[15]
图的底层为
3种速度不同的蚁群模块进行聚类，得到初步结果；
上层为聚
类组合模块，并将初步聚类结果组合成一个超图；
再上层为图
划分模块，采用基于蚁群算法的图划分算法对超图进行二次
划分，得到最终结果。
虽然采用多种群的蚁群聚类算法往往比单种群的算法在
聚类结果上要好，但这一方法与单种群聚类算法相比需要花
更多的时间，各蚁群数量也不好选择，各种群聚类不好控制，
同时需要设置多个参数。
3.3混合的蚂蚁聚类算法
3.3.1与K-Means算法的混合
考虑到K-Means算法有快速收敛的优点，以此改进蚁群
聚类算法，达到缩短算法时间的目的。
等人提出的
AntClass算法是在蚁堆聚类的基础上，交替使用蚁群聚类和
K-Means算法修正误差以获到“高质量”的聚类。
高尚等人
[14,16]
则先利用K-Means算法对数据进行快速分类，根据分类结果
更新信息素，来指导其它蚂蚁选择。
该类算法中，蚁群聚类部
分多采用单种群的聚类算法。
先采用K-Means算法进行初步
聚类的最大缺点是对聚类数预先设置。
结合密度思想的蚁群
聚类算法
[17]
在使用K-Means算法之前使用蚂蚁聚类，得到初始
的聚类中心，以求避免传统聚类算法对初始分割的要求。
3.3.2与遗传算法的混合
该聚类算法
[18]
主要利用了遗传算法的快速全局搜索能力
和蚁群算法的正反馈收敛机制。
算法第一步利用遗传算法对
数据进行初步聚类，形成初始聚类中心；
第二步利用蚁群算法
完善聚类结构。
该算法的基本框架如图2所示。
这类算法中的蚁群聚类算法也主要基于单蚁群的聚类算
法。
虽然两算法结合一定程度地相互弥补了对方的不足，但
算法的合点仍是一个问题，同时算法的复杂度和效率也不是
那么理想。
与其它算法结合的蚁群聚类算法，主要也是为了克服原
蚁群聚类算法的效率低及易陷入局部最优的缺点，是今后蚁
群聚类算法改进和研究的主要方向。
4结束语
蚁群聚类算法具有很多特性：
并行性、自组织性、鲁棒性
和灵活性，对算法稍作修改就可以应用到很多领域，因此其研
究价值不言而喻。
本文主要总结了现今存在的部份蚁群聚类
算法，针对每种基于蚁群的聚类算法分别论述了它们的基本
思想、聚类原理以及主要步骤。
在指出了蚁群聚类算法各自
所具有的优点同时，也分析了各自存在的缺点，如：
一部分算
法的聚类数仍需预先设置的缺陷、参数过多的问题、算法仍存
在易陷入局部最优的问题及算法执行时间过长的问题等，这
对算法的改进方向提供了依据。
参考文献:
[1]Monmarché
N,SlimaneM,VenturiniG.Onimprovingclustering
innumericaldatabaseswithartificialants[C].Lecturenotesin
ArtificialIntelligence,1999:
13-17.
[2]YangYan,MohamedSKamelb.Anaggregatedclusteringap-
proachusingmulti-antcoloniesalgorithms[J].PatternRecogni-
tion,2006,39:
1278-1289.
[3]VitorinoR,JuanJM.Self-organizedstigmergicdocumentmaps:
图1多蚁群聚类算法结构
最终聚类结果
图划分
聚类组合
蚁群1
常数
蚁群2
随机数
蚁群3
递减随机数
图2与遗传算法结合的蚁群聚类算法框架
生成若干组合优化解
解码
Y
N
满足条件
群体t+2
依次运算：
选择、交叉、变异
计算适应度函数
群体t
个体编码
定义目标函数和适应度函数
问题描述
随机将蚂蚁及初始聚类均匀分布在
平面内，初始化所有参数
对每只蚂蚁根据公式计算对象的平
均相似度及对象间的距离
对每只蚂蚁计算拾起、放下概率
对所有对象标识聚类序列号
输出聚类结果－5013－
Environmentasamechanismforcontextlearning[C].AlbaE,
HerreraF,MereloJJ,etal.Procofthe1stInt'
lConfOnMeta-
heuristics,EvolutionaryandBio-InspiredAlgorithms,2002:
284-
293.
[4]HandlJ,MeyerB.Improvedant-basedclusteringandsortingina
documentretrievalinterface[C].LNCS2439,2002:
913-923.
[5]韩彦芳,施鹏飞.基于蚁群算法的图像分割方法[J].计算机工程
与应用,2004,40（18）:
5-7.
[6]吴斌,郑毅,傅伟鹏,等.一种基于群体智能的客户行为分
升级会员 