一种改进的蚁群聚类分析算法

甘　泉, 王　慧

(1.平顶山学院 计算机与科学技术学院,河南 平顶山,467000;

2.平顶山学院 招生就业处,河南 平顶山,467000)



一种改进的蚁群聚类分析算法

甘泉1, 王慧2

(1.平顶山学院 计算机与科学技术学院,河南 平顶山,467000;

2.平顶山学院 招生就业处,河南 平顶山,467000)

摘要：提出了一种改进的蚁群聚类分析算法。该算法改进了经典的LF算法。利用短期记忆和网格信息素的局部分布控制蚂蚁的随机移动,利用信息熵作为蚂蚁运动状态转换规则,通过对信息熵的计算与比较,更改了数据对象拾起和放下的判断规则。设置的参数减少了,不仅每次放下对象时能够减少小块区域的信息熵,拾起时能够增加小块区域的信息熵,还能加快聚类过程,达到好的聚类结果。结果表明,该算法显示出了较高的稳定性和准确率。

关键词：聚类; 蚁群聚类; 信息素; 信息熵

1引言

数据挖掘技术领域中的数据聚类的存在,是对事物进行了解的重要步骤。20世纪90年代,Dario M等人提出了蚁群算法[1],最早被用于解决旅游商问题,还用于二度调度问题[2]。随着蚁群算法的广泛应用[3],人们发现蚁群模型在某些方面更接近实际的聚类问题。在与其他聚类分析模型进行比较时,基于蚁群的聚类分析模型有较多的优点:这种模型一般是独自需要解决相关难题,会自动根据数据对象的特征产生聚类的数量,会更好地处理噪声和异常值[4],会处理不同维度的数据集,能较容易完成数据的可视化。

2蚁群聚类基本原理

Lumer和Faieta[5]对基本模型进行了扩展,在数据分析领域广泛应用,提出了LF算法。该算法先将数据任意散放在单独网格里,在地点蚂蚁能有效的感受到周围的状况。对象Oj在地点r与附近事物的相似度由下面公式计算[6]:

(1)

式中:f(Oi)表示对象Oi和其邻域内的对象Oj之间的相似度的度量[7]。参数α代表了相差异的度量,利用它来确定两个数据对象能否放置在一起。Neighs×s是指以地点r为中心的s×s的区域。 在LF算法中蚂蚁拾起或者放下一个对象Oi的概率分别按照以下公式计算:

(2)

(3)

式中:Pp表示蚂蚁拾起对象Oi的概率,Pd表示蚂蚁放下对象Oi的概率,k+和k-是两个常量。

3改进的蚁群聚类分析算法(ALFBP)

在LF算法中,基本模型被扩展到了数据分析范畴,而且有很大的进展,由于这种算法的参数设置繁琐,并且敏感,同时对于运动的区域进行了限制,即二维网格的圈定,对于某些网格的存在失去了意义,例如没有数据的网格。所以,这种“物以类聚”统计分析情况并不尽如人意。改进算法思想为:首先将有需要的数据对象分布于二维网格,然后具体的具有蚂蚁真实的群体行为进行聚类剖析。采用信息素和短期记忆的思想对控制蚂蚁的随意移动进行控制,把信息熵作为蚂蚁运动状态的转换规则,信息熵的计算与比较来替代LF算法中的群体相似度计算和概率转换函数,对拾起和放下数据对象的判断规则进行修改。实验结果显示证明了改进算法是有效的,算法取得了较好的聚类结果。

3.1蚂蚁空间转移策略

在一个二维的平面网格中,蚂蚁的短期记忆和网格中信息素的分布决定了蚂蚁从一个位置到下一个位置的空间转移.相应的解决方法为:让每一个蚂蚁都能够记住近几次所放下的数据对象和相应的位置,如果新的数据对象被拾起,分析新对象与某个数据对象之间的关系,看是否可以归并,如果不能,可以按照具体的数据分布来确定下一步的移动方向。

假设蚂蚁在平面网格上的具体位置为(γ,θ),在它的走过的痕迹中会留下相应的信息素,在步长时间段内,所留下的信息为η,伴随时间的推移,推移过后的信息就会进行相应的减少,设减少的衰减率为κ。那么蚂蚁从k转移到位置k的空间方面的转移概率pik用以下公式来确定:

(4)

(5)

W(σi)响应函数(response function)是关于i的信息素(pheromones)浓度所表示的,证明膜翅目昆虫在关于信息素(pheromones)浓度为σi的位置i的相对出现率,较高的β取值使膜翅目昆虫顺着信息素的有关方向位移,其中β是决定膜翅目昆虫所有情况的抗噪比相关的参数数据,1/δ证明膜翅目昆虫在具有信息素(pheromones)范围内所能捕捉到信息素改变之能力,j/k表示在k邻域内所有网格单元j的和,集合中的参数β与1/δ二者是形成了信息素(pheromones)痕迹的关键因素。ω(Δi)为到位置i的权值因素,Δi代表在时间为步长的时候的位置i与位置K在方向方面的区别量,依据Δi的值来对ω(Δi)进行确定[8],因为各方格有八个紧挨着的网状式单元组成,也就有8个不同的方向进行移动,产生八个方向,各个方向之间的夹角为45度,那么膜翅目昆虫可事先从此八个方向当中,任意选取1个方向,则膜翅目昆虫迅速的改变方向的概率远远小于缓慢的改变方向的概率,所以,定义相异改变度数之数值与文献[8]相同,分别为:ω(0o)=1,ω(±45o)=0.5,ω(±90o)=0.25,ω(±135o)=0.08,ω(180o)=0.05。

3.2信息熵的计算

信息熵是一个比较抽象的数学概念,我们把信息熵定义为离散型随机事件产生的概率。学者Shannon(香农)对信源符号熵的界定如下:假定随机变数为X,存在取值集是x,就具有一定的可能性,在为x值的情况下,则可能性的函数就为p(x),信源符号熵E(x)的相关公式是:

(6)

针对1个数项变量之矢量x=(x1,x2,…,xn)的信息熵的计算公式为:

(7)

式中:p(x1,x2,…,xn)是多变量可能分布函数,X1,X2,…Xn是相应向量项的可能取值集合。

通过借用信息熵中包含聚类的子空间的信息熵比不包含聚类的信息熵小的特征,在 LF算法中引入信息熵,对数据对象拾起和放下的判断规则进行更改,设置的参数变少了,取得了较好的聚类质量。该策略描述为:单个负重对象oi的膜翅目昆虫位移至网络中空白区,计算附近s×s范围里的对象信源符号熵,试想未放下对象oi前的信源符号熵在与该区域的信源符号熵进行比对时,前者略大于后者,则放下该对象oi单个并未负重的膜翅目昆虫移至对象oi处,计算附近s×s区域中的对象信息熵,试想oi未拾起对象前的信源符号熵与该对象后该范围的信源符号熵,在做出对比时,前者大于后者时,不小于拾起则拾起对象oi。假定所有“数据对象”(Data Object )包含n个属性,且它们之间是独立的关系,A1,A2,…,An,每个属性之取值集为X1,X2,…Xn,就有极大的可能性s×s区域中的对象信息熵E(S2)为:

(8)

3.3算法描述

据上面对基于信息素和信息熵的蚁群聚类算法的讨论,ALFBP算法的过程如图1所示。

在ALFBP算法中,影响蚂蚁运动状态的因素仅有邻域s参数,比LF算法里的设置参数不多,在各次放下对象的时候,可以不增多非大块范围之信源符号熵,拾起的时候,可以不减少非大块范围的信源符号熵,还能加快聚类过程,达到好的聚类结果。通过多次的仿真实验,当形成一些较小的聚类时,负载的蚂蚁会很多次寻找放下的位置,就会多次出现E1

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

(1) 为了测试ALFBP算法的聚类质量和改进算法的有效性,我们分别进行了两组各十次实验,比较了最终聚类结果与LF算法的聚类结果。算法采用JAVA来实现。实验使用UCI公共数据库所提供的两个数据集见表1,这两个数据集都有自己的分类表,能够评价最终的聚类性能,设置算法的参数参见表2。聚类性能评价通过计算F一measure 的值,最大迭代次数都设置为106。

表1　实验数据集表示

第一组实验中,使用Iris数据集来测试算法的聚类质量。在20次实验中,ALFBP算法的F一measure 值有18次超过了LF算法的F一measure 值。就平均F一measure值而言,ALFBP算法达到了0.945,LF算法为0.889。由此可知,聚类质量ALFBP算法要优于LF算法。而且,对比LF算法,ALFBP算法避免产生小块的聚类。

图1　ALFBP算法流程图Fig.1　ALFBP algorithm flow chart

表2　实验参数表

第二组20次实验中,采用了数据集Zoo来测试算法的聚类质量。在20次实验中,ALFBP算法的F一measure值全都超过了LF算法的F一measure值。ALFBP算法平均F一measure 值为0.856,能够保持比较满意的聚类效果,但是LF算法之平均数值约是0.688,聚类之效果并不明显。由此可见ALFBP算法更适合于高纬数据的处理。

(2) 正态分布测试数据集。数据集中的四组数据的属性按照正态分布产生,每组200个数据,各组数据服从均值为μ,方差为σ=2的正态分布。

具体为:类1为(x～N[0,2],y～N[0,2]),类2为{x～N[0,2],y～N[8,2]},类3为{x～N[8,2],y～N[0,2]},类4为{x～N[8,2],y～N[8,2]}。数据集随机的分布在60×60的网格上,蚂蚁速度限制在1到10之间。邻域大小为3,蚁群大小为20,分别用LF算法和ALFBP算法对生成的数据集进行聚类,经过16万次的迭代得到误差函数随迭代次数的变化曲线图如图2所示。

图2　两种算法误差比较Fig.2　Comparison of the two algorithms error

在图2中,横坐标表示为迭代次数×104,纵坐标表示为误差平方和×102。从图2我们可以看出ALFBP算法有较好的收敛性能,而且能够加快聚类,这是因为ALFBP算法设置的参数减少了,使用ILFBP算法中定义的蚂蚁信息素和短期记忆方式校正其随机移动,利用信息熵作为蚂蚁运动状态转换规则,每次对于数据的拾起和放下都会对区域的信息熵有减少或者增加的影响。还能加快聚类过程,使相似度大的数据对象能够较快地聚集在一起能够加快聚类。另外,两种算法经过16万次迭代后的F-measure 值为LF为0.2344,ALFBP算法为0.9822,这些结果都表明该算法可行。

5结束语

本文提出了改进的蚁群聚类分析算法,利用短期记忆和网格信息素的局部分布控制蚂蚁的随机移动,通过使用当前数据对象位置局部区域信息熵的计算和比较作为蚂蚁运动状态转换的策略,来减少设置参数的个数。实验结果显示改进的算法收敛速度快,效果更高,算法的稳定性高。另外,本文各种方法采用的实验数据,均为国内相关文献选用的实验数据,这便于本文方法与相关方法实验结果的比较。在未来的研究工作中,应将本文各方法应用于实际数据处理问题,将其不断完善。

参考文献:

[1]Dorigo M,Bonabeau E,Theraulaz G.Ant algorithms and stigmergy[J].Future Generation Computer Systems.2000,16(8):851-871.

[2]宋佩莉,祁飞,张鹏.混合蚁群蜂群算法在旅行Agent问题中的应用[J].计算机工程与应用,2012,48(36):33-38.

SONG Peili,QI Fei,ZHANG Peng.Application of hybrid ant colony and bee colony algorithm in traveling Agent problem[J].Computer Engineering and Applications,2012,48(36):34-38.

[3]侯超.侯永.一种改进蚁群聚类算法在数据挖掘中的研究[J].微计算机信息,2011,27(12):136-138.

HOU Chao,HOU yong.An Improved Ant Colony Clustering Algorithm in Data Mining[J].Micro Computer Information.2011,27(12):136-138.

[4]周国娟.基于蚁群算法的文本聚类处理的研究[J].通信技术.2010,43(11):74-77.

ZHOU Guojuan.Text Clustering Research based on Ant Colony Algorithm[J].Communications Technology.2010,43(11):74-77.

[5]Lamer E,Fajita B.Diversity and adaptation in populations of clustering ants[C].Proc.of Third International Conference on Simulation of Adaptive Behavior.Cambridge,MA,USA:MIT Press.1994:501-508.

[6]DM Dorigo,L M Gambardella.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66

[7]D R Chialvo,M M Millonas.How swarms build cognitive maps[C].The Biology and Technology of Intelligent Autonomous Agents,Nato ASI Series.1995:(144):439-450.

[8]V Ramos,F Muge,P Pina.Self-Organized Data and Image Retrieval as a Consequence of Inter-Dynamic Synergistic Relationships in Artificial Ant Colonies[C]Hybrid Intelligent Systems,Frontiers of Artificial Intelligence and Applications,Santiago,Chile,2002,12.

甘泉男(1980-),安徽灵璧县人,讲师,研究方向为算法分析等。

王慧女(1982-),河南平顶山人,讲师,研究方向为数据挖掘。

An Improved Ant Clustering Analysis AlgorithmGANQuan1,WANGHui2

(1.College of Computer Science and Technology,Pingdingshan University,Pingdingshan 467000,China;

2.Department of Admission and Employmentl Pingdingshan University,Pingdingshan 467000,China)

Abstract：An improved ant colony clustering algorithm is developed.This algorithm improved classic LF algorithm by employing short-term memory and local distribution grid to control ant pheromone random movement,information entropy state of motion to act as ants’ conversion rules.The judgment rule of picking up and dropping data is changed based on calculating and comparing the information entropy.This reduces the set parameters.Not only the entropy of small area which putting down the object reduces,but also the entropy of small area which picking up the object increases.The method speeds up of process of clustering and achieves good clustering results.These results prove that the algorithm has high stability and accuracy.

Key words：clustering; ant colony clustering; pheromone; information entropy

基金项目：河南省科技厅攻关项目(KJT142102210226)

中图分类号：TP 391

文献标识码：A