一种改进的蚁群聚类算法

俞 辉, 裴振奎, 陈继东

(中国石油大学(华东)计算机与通信工程学院 山东东营257061)

一种改进的蚁群聚类算法

俞 辉, 裴振奎, 陈继东

(中国石油大学(华东)计算机与通信工程学院 山东东营257061)

针对现有蚁群聚类中将带聚类样本放于网格进行聚类的算法存在随机移动而延长聚类时间,及大数据集进行蚁群聚类时收敛速度慢的缺点,在蚁群进行聚类前增加数据预处理.利用两元素越相似属于同一类簇的可能性越大的思想,将样本集中的样本量缩小.研究了通过信息素进行聚类的蚁群聚类算法,使算法中的“蚂蚁”在一定指导下进行聚类,达到缩短时间的目的.最后通过实验验证了所提出算法的有效性和优越性.

蚁群算法;聚类分析;数据挖掘;群体智能

0 引言

蚁群算法是一种新型的模拟进化算法,用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的困难问题.蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法,该算法采用了正反馈并行自催化机制,具有较强的鲁棒性、优良的分布式计算机制及易于与其他方法相结合等优点,在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力[1-2].聚类分析也称聚类,是多元统计分析的一种,同时也是数据挖掘中的重要研究领域,是数据分组和划分处理的重要手段.聚类的目标是在没有任何先验知识的前提下,根据样本自身的相似性划分成若干个子集,使相似的样本尽可能归为一类,而不相似的尽量划分到不同的类中.因此,聚类又称无监督分类,在图像分割、医学诊断、天气预报、矿藏识别及商务领域等有着广泛的应用[3].蚁群聚类算法研究力求对大数据集进行聚类时能够在保证聚类质量的情况下,缩短聚类的执行时间,降低算法对经验知识的弱依赖性.但是由于目前存在的一些聚类算法在聚类参数设置、聚类结果及算法执行时间上都不够理想,一直没能够自动控制聚类簇数目和在保证聚类结果较好的情况下得到更理想的运行时间.

考虑到提出的蚁群聚类算法聚类时所存在的缺陷[4],根据遗传算法的机理、工作过程,将遗传算法思想引入蚁群聚类算法中,提出了混合遗传算法思想的蚁群聚类算法,研究了通过信息素进行聚类的蚁群聚类算法,并通过实验验证了所提出算法的有效性和优越性.

1 一种改进的蚁群聚类算法

1.1 蚁群聚类算法的优缺点

与聚类分析的典型要求对照,可以看出采用蚁群算法进行聚类的优缺点.蚁群聚类算法的优势:首先,蚁群聚类算法的聚类中心的个数是由样本集中数据本身的特点产生的,因此极大克服了传统聚类算法聚类簇数预先设定的缺陷,这体现了对先验知识的弱依赖性[5].其次,算法在预处理阶段就将数据对象随机地分布在一个二维的网格空间中,数据对象属性个数的增加对算法的性能没有太大影响,即算法具有很好的伸缩性;预处理同时也降低了算法对输入样本顺序的敏感程度.由于采用了基于密度的算法,因此能够得到不同形状的聚类结果,满足了对发现任意形状聚类的要求.

蚁群聚类算法最明显的缺陷就是若要得到高质量的聚类结果,算法的计算效率不高,尤其是对大样本集进行聚类时[6].另一方面,蚁群聚类算法需要预先设定“蚂蚁”的数目以及环境参数,而蚂蚁数目及环境参数的确定是由具体聚类样本集的大小决定,因此也影响了算法的可伸缩性.经分析可知,蚁群聚类算法的突出问题就是算法的计算效率低,以及对大样本集的适应能力差[7].由于蚁群聚类算法具有分布式计算、自组织、可扩展性、健壮性等特点,因此可以采用控制策略决定蚂蚁的移动,从而提高算法效率.

1.2 改进的蚁群聚类算法分析

提出的基于信息素的蚁群聚类算法,考虑到聚类对象的数量过大,而蚂蚁的数量又会对聚类的速度有所影响,因此,进行蚁群算法聚类时先对样本进行数据预处理.利用越相似的样本属于同一类的可能性越大的思想,在算法的预处理阶段采用基于最近邻优先的聚类算法进行聚类.将待聚类样本集随机分布在一个二维网格中,对每个样本周围领域相似的样本进行合并,缩小样本个数,减少下一步的数据处理量.为避免在传统的蚁群聚类算法中的蚂蚁没有走过路径上的数据一直没有被选择的机会,将经过预处理后的待聚类样本视为一个一个的蚂蚁,根据蚂蚁的环境决定蚂蚁的活动,控制蚂蚁活动的数量[8].通过信息素量以及相似度决定蚂蚁移动的位置和方向,算法执行中调整这两个参数在不同阶段的侧重点,由算法起始主要依靠信息素浓度来选择移动位置到经过一段时间的迭代后调整到依靠聚类的相似度来决定的方法,指导蚂蚁的运动,提高算法的运行效率.

2 算法的基本原理

改进的蚁群聚类算法是基于具有睡眠与活跃两种状态相结合的一种蚁群聚类算法,通过蚂蚁所处的环境决定蚂蚁的活动.这不仅动态地决定了蚂蚁的数量,也解决了蚂蚁随机移动而浪费大量时间进行无用移动的缺陷,使算法在更快的时间内达到聚集成簇的活动.

2.1 适应度函数

改进的蚁群聚类算法中将数据视为一个一个的蚂蚁,蚂蚁根据周围环境的适应度函数值来决定自身的状态,即是继续呆在原地还是移动.由蚂蚁所处的环境决定其行动,可以避免遗漏待聚类样本,一定程度地提高聚类质量.

每个蚂蚁即待聚类样本,被视为一个agenti,它的状态记为qi,qi=(xi,yi,ci),1≤i≤N,其中xi,yi为agenti的横坐标与纵坐标,ci为类号.这里使用Moo re型领域,每个agenti邻居为其3×3区域的其他agent,并记为N(agenti).

定义agenti当前位置的适应度函数值f(agenti)为:

其中,d(agenti,agentj)表示agenti与agentj的相似距离,也叫相异度函数.在本文中算法都采用欧氏距离作为相似距离.通常,d(agenti,agentj)越大表示越不相似,当d(agenti,agentj)接近于零或等于零时表示agenti与agentj相似或相等.适应函数f(agenti)越大,表明agenti与周围的agent越不相似,需要跳离这个环境;当f(agenti)越小时,则表明与周围环境相似,继续停留在此处;当f(agenti)=0时,表明agenti周围没有邻居.

2.2 移动策略

改进的蚁群聚类算法移动策略:根据蚂蚁周围的环境情况f(agenti)决定蚂蚁是移动还是留在原地,有策略性的指导蚂蚁的活动,提高算法的运行效率.若f(agenti)>1,则蚂蚁准备跳出当前环境,选择蚂蚁所处的Moo re领域外最相似的蚂蚁,若此处将合并的蚂蚁周围领域有空位,移动到此位置;若0

2.3 算法步骤

1)初始化参数设置,将样本随机放置于网格中;

2)进行数据预处理;

for(i=0;i≤n;i++)//n为样本集中的样本个数,

每个待聚类样本在各自的Moore领域内比较领域中样本相似度;

if两样本相似度≤最小阈值d,则两样本合并成一个,合并位置为较小者的位置,并视为一个agent;对每个agent标号,类号设为标号;

3)While(not termination);

4)for each agent do,计算agent的适应度函数值;

5)if f(agenti)>1 then蚂蚁agenti待移动,选择除agenti的3×3区域d(agenti,agentj)最小的agent,若此处的agent周围领域有空位,移动到此位置合并类号(选择类号最小的为新的类号);

else if 0

else agenti蚂蚁不移动,类号不变;

6)end for;

7)end w hile;

8)输出所有agent的聚类信息.

2.4 算法测试与分析

改进的蚁群聚类算法的有效性测试采用经典的聚类算法K-means算法[9]与之比较,测试数据为13个二维数据.K-means算法参数设定聚类簇数k=3,ε=0.1.改进的蚁群聚类算法的网格数设为ceil(sqrt(n))×ceil(sqrt(n))=16个,n=13;初始数据预处理阶段,最小阈值d=1;循环次数为10次.图1是测试数据的平面分布图.

表1是K-means算法与改进的蚁群聚类算法对测试数据的聚类结果.

由表1可以看出,改进的蚁群聚类算法在聚类簇数及正确率上与K-means算法的正确率一致,因此可以验证算法的有效性,同时,在得到最终结果的循环次数上相比,改进的蚁群聚类算法要比K-means算法更好.

图1 测试数据的平面分布图Fig.1 Plane distribution of test data

表1 2种算法的聚类结果Tab.1 Clustering resultsof two algo rithm s

该算法的数据预处理很重要,算法数据预处理环节中的最小阈值设的好则能有效减少样本,降低循环阶段的样本处理量,一定程度地提高算法的执行效率.若最小阈值设的过小则达不到数据预处理的效果,还浪费时间,若最小阈值设的过大则很有可能把一些距离较近的孤立点合并进去,失去了蚁群聚类算法的优势[10].同时,由于算法在网格设置上是根据待聚类的数据量来决定网格的多少,使得样本的分布很集中,因此可视化效果方面不够理想,若样本分布在正好的网格中,在预处理环节的最小阈值设置不合理,则算法聚类结果也不够理想.若在一个大的网格上进行聚类,则算法又对孤立点处理不理想,尤其是当样本分布很散的情况下.

3 结论

改进的蚁群聚类算法充分利用最近邻优先吸收的思想,在数据预处理阶段降低样本集中的样本量,使算法执行的处理量数据减少,本文在解决大样本集聚类问题具有较大的实用价值.基于蚁群的聚类算法研究目前仍然是一个十分活跃的研究领域,尽管作者的研究工作取得了一些有意义的成果,但还不是最优的聚类方法,同时聚类的结果还有待进一步提高,执行时间也需要进一步缩短.对算法进行预处理的同时也增加了经验阈值的设置,违背了对先验知识弱依赖性的初衷,而且经验阈值的大小将直接关系到数据预处理后的待聚类数据量.今后应力求通过改进预处理部分减少数据量,降低蚁群聚类部分的处理时间,以及蚁群算法与遗传算法的结合部分,使蚁群聚类算法在更迅速地进行聚类的同时,又避免陷入局部最优以达到更理想的聚类结果及效率.

[1] 段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005.

[2] 曹军民,裴红星,王长松.基于蚁群算法的连铸二冷优化[J].郑州大学学报:理学版,2009,41(4):112-115.

[3] 高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2004.

[4] 李士勇,陈永强,李妍,等.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004:14-18.

[5] 焦李成,刘芳,缑水平,等.智能数据挖掘与知识发现[M].西安:西安电子科技大学出版社,2006.

[6] 束建华,倪志伟,杨善林.基于蚁群优化的分类规则挖掘方法[J].广西师范大学学报:自然科学版,2007,25(4):230-233.

[7] 胡建军,唐常杰,李川,等.基于最近邻优先的高效聚类算法[J].四川大学学报:工程科学版,2004,36(6):93-99.

[8] 徐晓华,陈崚.一种自适应的蚂蚁聚类算法[J].软件学报,2006,17(9):1884-1889.

[9] 行小帅,潘进,焦李成.基于免疫规划的K-means聚类算法[J].计算机学报,2003,26(5):605-609.

[10] 洪孙焱,陆正福,申时凯,等.基于蚁群优化的应用层多播路由算法[J].广西师范大学学报:自然科学版,2008,26(3): 230-233.

An Improved Ant Colony Clustering Algorithm

YU Hui, PEIZhen-kui, CHEN Ji-dong
(College of Com puter&Comm unication Engineering,China University of Petroleum,Dongying 257061,China)

To shorten clustering time in ant colony algo rithm(ACA)and speed up convergence rate of large data sets,data p rep rocessing is adop ted before ant colony clustering algorithm (ACCA).M eanw hile,clustering speed is studied through the pheromone of ACCA,and ants in the algorithm should be guided by certain information.In order to test the validity of the algorithm s,K-means and the basic ant colony clustering are compared at the same time.The experimental results show the effectiveness of the p roposed app roach.

ant colony algorithm;clustering analysis;data mining;swarm intelligence

TP 181

A

1671-6841(2010)03-0059-04

2010-05-26

俞辉(1974-),男,讲师,硕士,主要从事数据挖掘、智能算法及嵌入式系统研究,E-mail:huiyu@upc.edu.cn.