基于蚁群觅食原理的聚类算法的研究及改进

张梦佳，李 秦，王菲菲

(兰州交通大学 数理学院，甘肃 兰州730070)

基于蚁群觅食原理的聚类算法的研究及改进

张梦佳，李 秦，王菲菲

(兰州交通大学 数理学院，甘肃 兰州730070)

针对基于蚁群觅食原理的聚类算法初期收敛速度较慢的问题，以及未区分各维特征主次的缺陷，本文提出了一种两阶段蚁群聚类算法，以解决上述问题。第一阶段引入各只蚂蚁的实时信息素更新规则改善算法初期收敛速度较慢问题，并为第二阶段提供合理的初始隶属度矩阵；第二阶段利用隶属度矩阵自适应地赋予各维特征不同的权重，再用信息素强度和加权欧氏距离共同指导各只蚂蚁构造解。经过人工数据集和UCI数据集的测试，结果表明两阶段蚁群聚类算法可以加快算法初期收敛速度，同时提高聚类的准确率。

蚁群聚类；两阶段；收敛速度；自适应权重

聚类作为数据分析领域中人们认识和探索事物内在分布结构的一种有效手段，被广泛应用于许多领域，如：信息检索、客户细分、机器学习、图像压缩、生物学等。聚类为无监督学习，其根据数据样本之间的相关性将数据样本集划分为不同的类，使得相同类内的数据之间相似度较高，而不同类之间的相异度较高。

蚁群算法[1]是1991年由意大利学者Dorigo M提出的一种模仿蚂蚁群体行为的仿生优化算法，2004年Shelokar将蚁群算法运用于聚类分析中，提出基于蚁群觅食原理的聚类算法[2](Ant Colony Clustering Algorithm，ACCA)。基于蚁群觅食原理的聚类算法具有蚁群算法的随机搜索、自组织聚类、优良的分布式计算等优点，但是该算法初期受蚁群随机搜索、信息素更新缓慢的影响收敛速度较慢，聚类过程中信息素的高度集中导致算法后期易陷入局部最优。目前对基于蚁群觅食原理的聚类算法的改进多是与其他算法相结合,取得了较好的聚类结果，但是还存在一些不足：文献[3]使用初始化敏感的K-Means算法快速、粗略地确定蚁群聚类算法的聚类中心，聚类结果容易受初始聚类中心的影响；文献[4-5]结合遗传算法的交叉、变异操作避免蚁群聚类算法陷入局部最优，但混合算法的运行时间较长；文献[2-5]未区分样本各维特征的主次。为了加快算法初期收敛速度，又避免聚类结果受到初始聚类中心的影响，同时考虑样本各维特征的贡献率，本文提出一种两阶段蚁群聚类算法。

1 基于蚁群觅食原理的聚类算法

蚂蚁在寻找食物源的过程中会在其走过的路径上留下一种特殊的分泌物信息素来标记路径，蚂蚁释放出来的信息素的量与路径长度成反比，而蚂蚁选择路径的概率与信息素的量成正比，随着时间推移该物质也会逐渐挥发。当一条路径上走过的蚂蚁数量越多，这条路径被后来蚂蚁选择的概率越高，从而就增强了该路径上信息素的强度，因此会吸引更多的蚂蚁，这一过程称为正反馈[6]。通过正反馈机制，蚂蚁最终可以找到从蚁穴到食物源的最短路径。

设X={Xi|i=1,2,…,N}为N个数据样本集，其中Xi=(xi1,xi2,…,xiz) 为z维向量。基于蚁群觅食原理的聚类算法ACCA就是把X划分为K个类M1,M2,…,MK，使聚类目标函数F最小。设mk=(mk1,mk2,…,mkz)为类Mk的聚类中心，目标函数F定义如下：

(1)

设τik(t)表示t时刻样本Xi到聚类中心mk路径上残留的信息素量，该算法仅对蚂蚁找到的全局最优解路径上的信息素更新，更新方式为：

(2)

基于蚂蚁觅食原理的聚类算法如下：

步骤2：构造每只蚂蚁的解，对每只蚂蚁随机生成一个随机数q。若q≤q0，则蚂蚁根据信息素矩阵选中拥有最大信息素强度的类，将样本Xi分配到类Mk中；否则，将样本Xi随机分配到类Mk中。

步骤3：根据蚂蚁构造的解计算式(1)目标函数值和新的聚类中心(即类内样本特征的平均值)。

步骤4：若所有蚂蚁均完成解的构造，则对A个目标函数值从小到大进行排序，找出最小的F值记为此次迭代的最优值；然后将此次迭代的最优解与全局最优解进行比较，取二者之中目标函数值较小者为全局最优解，再按式(2)进行全局信息素的更新；否则，返回步骤2。

步骤5：若满足结束条件t>t_max，则输出全局最优解；否则迭代次数t=t+1，转至步骤2。

基于蚁群觅食原理的聚类算法初期收敛速度较慢，聚类过程中未考虑各维特征的贡献率，导致聚类结果不理想。为了改善聚类的效率和质量，本文第一阶段采用基于各只蚂蚁实时信息素更新规则改进的蚁群聚类算法进行初始化，加快算法初期收敛速度，使蚁群尽快搜索到近似解附近，为下一阶段提供合理的初始隶属度矩阵；第二阶段引入自适应特征加权，在每次迭代中利用隶属度矩阵自适应赋予各维特征不同的权重，进而由信息素强度和加权欧氏距离共同指导蚂蚁构造解，最终得到较理想的聚类。

2 两阶段蚁群聚类算法

2.1 第一阶段蚁群聚类算法

基于蚁群觅食原理的聚类算法式(2)中信息素的更新仅仅增强了全局最优解路径上的信息素强度，其他路径上的信息素强度没有更新，这就造成了算法初期收敛速度较慢。为了改善这一问题，本阶段在每只蚂蚁搜索完成之后进行全部路径上的信息素更新，新信息素矩阵作为下一只蚂蚁构造解的依据，再结合每次迭代完成后全局最优解路径上信息素的更新，有效提高了算法的初期收敛速度。

第R只蚂蚁实时信息素更新规则：

τik(R)=(1-ρ)τik(R-1)+Q/(dik+0.01)。

(3)

式中：Q为一个正常数，ρ为随机挥发因子[7](当ρ取大时有利于全局搜索，ρ取小时加快收敛速度)。

2.2 第二阶段蚁群聚类算法

(4)

由于t时刻聚类中心计算公式为：

(5)

将mkj(t)带入式(4)得：

(6)

将式(5)带入式(6)得到不计算聚类中心点的各维权重系数：

(7)

上式中t时刻各维权重系数是根据t-1时刻得到的隶属度矩阵和数据样本计算得到。进而能够得到t时刻样本Xi到聚类中心mk的加权欧氏距离：

(8)

经过第一阶段的预处理之后可以粗略地得到聚类中心，则在此阶段改变蚂蚁构造解的方式为：

(9)

用信息素强度和加权欧氏距离指导蚂蚁构造解，以降低算法仅仅依赖信息素构造解的错误率。

2.3 两阶段蚁群聚类算法步骤

步骤1：初始化。设定各参数Q、L,聚类数K，蚂蚁个数A，最大迭代次数t_max，第一阶段迭代次数t_1，初始信息素矩阵τik(0)=C。

步骤2：迭代次数t≤t_1，则每只蚂蚁按ACCA中蚂蚁搜索解的方式确定各样本所属的类；每只蚂蚁经过所有样本点后，按式(3)更新全部路径上的信息素。

步骤3：所有蚂蚁全部完成一次遍历后,按式(2)取ρ∈rand更新全局信息素，直到满足终止条件。

步骤4：利用隶属度矩阵、数据样本确定各维特征的权重系数，由信息素矩阵和按式(8)计算所得的距离矩阵确定Pik。

步骤7：若满足结束条件t>t_max，则输出全局最优解；否则迭代次数t=t+1，转至步骤4。

3 实验结果与分析

本文采用人工数据集和UCI机器学习数据集中的iris、wine数据集，分别对ACCA和两阶段蚁群聚类算法进行测试。其中，人工数据集由服从以下4类高斯分布的数据构成：类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)}，每类各50个数据。3种数据集具体描述如表1所示。

实验运行环境：AMD A8-6410,2.0 GHzCPU,4 GB RAM,Matlab2010。实验参数设定：ρ=0.1，q0=0.9，Q=100 ,L=2,初始化τik(0)=0.01，蚂蚁个数A=50。

表1 数据集

对以上3个数据集运用ACCA和两阶段蚁群聚类算法分别运行50次，结果如表2、表3、表4所示。从表2、表3和表4中可以看出：

(1)单用两阶段蚁群聚类算法中第一阶段蚁群聚类算法比ACCA的收敛速度快，正确率也有小幅提高，说明该阶段提供的隶属度矩阵较为合理，能用于下一阶段特征权重系数的计算。但是该阶段仅仅依靠信息素选择样本所属的类,正确率还有待提高。

(2)在人工数据集、iris数据集和wine数据集上，两阶段蚁群聚类算法的平均正确率比ACCA分别提高17.27%、7.16%、27.27%，聚类的正确率显著提高，这是由于特征权重系数消除了数据间的冗余，使得蚂蚁依靠信息素强度和加权欧式距离选择样本所属的类更精确。

(3)相比ACCA，两阶段蚁群聚类算法的平均运行时间有大幅提高，说明该算法有效保留了第一阶段蚁群聚类算法收敛速度快的优点。

表2 人工数据集聚类结果对比

表3 iris数据集聚类结果对比

表4 wine数据集聚类结果对比

注：*表示无此阶段

4 结 语

本文对基于蚁群觅食原理的聚类算法进行改进，第一阶段引入实时信息素更新规则加快算法初期收敛速度，第二阶段自适应赋予各维特征不同的权重系数，消除数据间的冗杂，使蚂蚁更有效地构造解,提高聚类的准确率。经人工数据集和UCI数据集的测试，进一步验证了两阶段蚁群聚类算法的可行性及有效性。

[1] Dorigo M,Maniezzo V,Colorni A.The ant system:Optimization by a colony of cooperation agents[J].IEEE Trans on SMC,1996,26(1):28-41.

[2] Shelokar P S,Jayaraman V K,Kulkarni B D.An ant colony approach for clustering[J].Analytica Chimica Acta,2004(509):187-195.

[3] 李振,贾瑞玉.基一种改进的k-means蚁群聚类算法[J].计算机技术与发展,2015,25(12):28-31.

[4] 戴皇冠,石跃祥,李聘婷.基于混合交叉因子的蚁群聚类优化[J].计算机工程与设计,2011,32:3840-3843.

[5] 王智,张自力.一种新的混合蚁群聚类算法[J].西南师范大学学报(自然科学版),2009,34(3):88-92.

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

[7] 张永强,王晓东.基于信息素更新和挥发因子调整改进蚁群算法[J].西安工程大学学报,2016,30(3):400-404.

[8] 陈新泉.聚类算法中的优化方法应用[M].四川:电子科技大学出版社,2014:65-81.

[9] 林金灼,叶东毅.基于蚁群聚类算法的优化与改进[J].计算机系统应用,2013,22(12):93-99.

[10] Monmarche N,Slimane M,Venturini G.On improving clustering in numerical databases with artificial ants[C].Lecture notes in Artificial Intelligence,1999,9:13-17.

[11] Huang J Z,Michael K N,Hongqiang R,et al.Automated Variable Weighting in k-Means Type Clustering[J].IEEE Transaction on pattern analysis and machine intelligence,2005,27(5):657-668.

[12] 熊文,晋耀红.使用蚁群优化和凝聚层次的混合聚类[J].北京邮电大学学报,2013(36):60-63.

[13] 肖林云,陈秀宏,林喜兰.特征加权和优化划分的模糊C均值聚类算法[J].微电子学与计算机,2016,33(10):143-150.

[14] 龚燕.一种新的全局收敛的混合聚类算法[D].辽宁:大连理工大学,2016:20-26.

Research and Improvement of Clustering Algorithm Based on Ant Colony Foraging Principle

ZHANG Mengjia, LI Qin, WANG Feifei

(Lanzhou Jiaotong University, Lanzhou 730070, China)

Focusing on the problem, which the clustering algorithm based on ant colony foraging principle of convergence may be slow in the initial stage, and the defects not distinguishing the various features of primary and secondary, this paper presents a two-stage ant colony clustering algorithm to solve the problems mentioned above. The first stage of algorithm which introduces the ant real-time initial pheromone update rule to improve the problem of low convergence speed in early algorithm. the second stage of algorithm, guiding the ants structural solution by the membership matrix to adaptively endow the reasonable feature weight of each dimension, as well as the pheromone intensity and weighted Euclidean distance .Through the test on artificial data set and UCI data sets, the results show that the two-stage ant colony clustering algorithm can improve the convergence speed in early algorithm, mean while, improve the accuracy of clustering.

ant colony clustering; two stages; the rate of convergence; adaptive feature weight

10.3969/j.issn.1674-5403.2017.04.014

TP301.6

A

1674-5403(2017)04-0060-05

2017-04-25

张梦佳(1993-)，女，河南新乡人，在读硕士研究生，主要从事智能计算方面的研究.