一种改进的基于K-Means的蚁群聚类算法

尚玉新

( 山东商业职业技术学院，山东 济南 250103 )

一种改进的基于K-Means的蚁群聚类算法

尚玉新

( 山东商业职业技术学院，山东 济南 250103 )

聚类分析被广泛用于数据挖掘等领域，基于蚁群算法的聚类算法也得以应用。针对K-Means算法和蚁群聚类算法出现的缺点，利用了K-Means算法快速确定聚类中心和精英适应保留值的策略，提出了一种改进的基于K-Means的蚁群聚类算法。仿真实验表明，改进算法的性能得到有效提高。

聚类分析；K-Means算法；蚁群算法；信息素

1 引言

聚类是根据数据间的相似程度将数据进行合理的分类，使得类间的相似性尽量小，而类内的相似性尽量大。[1,2]聚类是一种无监督的学习，因为它没有关于分类的先验知识。在实际应用中，聚类分析的研究成果已经广泛应用到数据挖掘、图像处理、模式识别、金融投资、地理信息系统、卫星图像和信息检索等领域。[3,4]蚁群算法是由意大利学者根据生物仿生学原理提出的一种智能算法，因其具有并行性、鲁棒性等优良性质得到了广泛的应用。[5]蚁群聚类算法最早是由Deneubourg提出的基于蚂蚁觅食行为的聚类方法[6]，Lumer 和Faieta提出改进算法，并应用到数据分析中[7]。但基本蚁群聚类算法参数对性能影响较大且设置有一定难度，而且需要花费较长的时间[8]，因此利用K-Means算法先在较短时间内做出快速分类[9,10]，确定聚类中心，再利用蚁群算法根据现有的聚类结果来聚类，这样可以相互弥补缺陷，得到更好的效果。

2 改进的基于K-Means的蚁群聚类算法

2.1 K-means算法

K-means算法是最常用的聚类算法之一，其优点是简单有效，而且可以用于多种数据类型。[11]

算法描述如下：

(1)随机选择K个对象作为初始聚类中心；

(2)根据聚类中心将每个样本分配给K个中心，形成相似的簇；

(3)重新计算每个簇的平均值，用均值点作为新的聚类种子。

(4)重复执行(2)和(3)直至各个簇不再发生变化，即各个聚类中心不发生变化。

该算法对包含异常点的数据进行聚类时，常常会收敛于局部最优解，而不是全局最优解。当簇密集且区别明显时，用此方法效果较好，区别不明显时效果不好。

2.2 蚁群聚类算法

聚类问题的蚁群算法思路描述如下[12]：模式样本分配给第j个聚类中心Zj(j=1,2,…，K)，蚂蚁就在模式样本i到聚类中心Zj的路径上留下信息素τij，蚂蚁选择聚类中心Zj的转移概率为

(1)

信息素更新方程为

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

蚁群算法存在的问题：

(1)该算法收敛过程比较缓慢，在迭代初期，由于系统参数改变很慢，使得整个运行过程耗时较长。为简化操作，初始时一般都赋予相等的常数，这样各条路径上的信息素要明显区别开就需要较长的时间。

(2)该算法初值的选取对聚类结果影响很大，如果选择不当将影响算法的执行效率和结果。

精英蚁群聚类算法是在蚁群算法的基础上引入了精英蚂蚁的策略[13]，就是在每次迭代的过程中，保留固定量的具有最优值的解进入下一次迭代循环中，这样可以把迭代中优良的解保留下来加入到下一次循环中，起到提高算法性能的作用。

2.3 改进的基于K-Means的蚁群聚类算法

通过上述内容可知，为了实现优势互补，可以将K-Means算法和精英蚁群聚类算法进行融合，做出改进，将K-Means做过预处理的数据用精英蚁群算法进一步聚类，从而得到理想结果。算法描述如下：

(1)任选K个初始聚类中心：Z1,Z2,Z3,…，Zk；

(2)分别将样本集X中的各个模式样本按照欧氏距离的平方和最小的原则分配给K个聚类中心中的某一个Zj；

(4)若Zj′≠Zj(j=1,2,…，K)且没有快速分类到指定阈值则转(2)；

(5)Nc←0(Nc为迭代次数)，由K-Means算法的分类结果计算出聚类中心Zj(j=1,2,…，K)，计算每个样本数据相对应的到不同聚类中心Zj的初值τij(0)(i=1,2,…,n;=1,2,…,K)，初始化蚂蚁数n，信息素挥发系数ρ，精英蚂蚁数r，随机给出分配方案；

(6)对每只蚂蚁按转移概率pij选择下一个节点，利用信息素矩阵构造解；

(7)计算本次迭代中蚂蚁找到的聚类中心和每个样本到新的聚类中心的距离，记录下本次迭代最优解和全局最优解；

(8)进行信息素更新得到τ(t)，并保留前最优的个解进入下一次迭代中；

(9)若超过最大迭代次数且无退化行为，则输出找到的最好解，计算停止，否则转(6)。

3 数值实验

为了验证改进算法的有效性，采用蝶形数据集和Iris数据集[14]利用matlab7.0编程分别对K-Means算法、蚁群聚类算法、本文改进算法进行比较。在实验中，改进算法参数设置如下：ρ=0.01，Q=100，K=3，计算蝶形数据时蚂蚁个数为20，计算Iris数据集，蚂蚁个数为40，Nc_max=500，每种方法进行30次仿真，结果如表

从以上实验数据可以看出，本文算法利用了K-Means算法快速确定聚类中心和精英适应保留值的策略，在性能上有所改进。3种算法中改进算法略高于基本蚁群算法，均优于K-Means算法。但是由于前期K-Means算法限制了聚类的个数，因而只适应于数目确定的聚类分析问题，对于聚类数目不确定的问题没有能很好解决，值得进一步探索。

4 结束语

本文提出了在基于K-Means基础上的改进的蚁群聚类算法，引入了精英保留机制，将K-Means算法和精英蚁群聚类算法进行融合。通过对两个数据集进行仿真实验，发现新算法能有效提高算法的性能，从而为聚类问题提供了一种思路。今后还应该着力于深入研究参数对算法的影响，以进一步提高效率。

[1]Chen M S. Data mining :An overview from a database perspective[J].IEEE Transaction on Knowledge and Data Engineering,1996,8(6):833-866.

[2]刘念涛，刘希玉.基于改进的启发式蚁群算法的聚类问题的研究[J].计算机技术与发展,2007,17(8):37-39.

[3]Handl J,Knowles J,Dorigo M. On the performance of ant-based clustering[C]//Proc of the 3rd Int Conf on Hybrid Intelligent Systems. Australia: IOS Press,2003,12.

[4]王慧.改进的蚁群聚类分析算法的研究[D].河南大学硕士学位论文，2009.

[5]Colorni A,Dorigo M,Manierzzo V,et al. Distributed optimization by ant coloies[C]//Proc of European Conf on Artificial Life. Paris, France: Elsevier Publishing,1991:134-142.

[6]Deneubourg J L,Goss S, Franks N,et al. The Dynamics of Collectivesorting:Robot-Like Ants and Ant-Like Robots[C]//Proc of the 1st Int’l Conf on Simulation of Adaptive Haviour, 1991:356-365.

[7]Lumer E,Faieta B.Diversity and Adaption in Populations of Clustering Ants[C]//Proc of the 3rd Int’l Conf on Simulation of Adaptive Behavior,1994: 501-508.

[8]Monmarche N,Slimane M,Venturini G.AntClass: discovery of clusters in numeric data by a hybridization of an ant Colony with the K means algorithm[R].Internal Report, Switzerland: [s.n.],1999.

[9]高尚,汤可宗,杨静宇.一种新的基于混合蚁群算法的聚类方法[J].微电子学与计算机,2006,23(12):38-40.

[10]韩强,邢洁清.蚁群聚类组合方法参数M的研究[J].计算机工程应用技术,2009,5(36):10469-10470.

[11]高尚,杨静宇,吴小俊.聚类问题的蚁群算法[J].计算机工程与应用,2004,(8):90-91,232.

[12]邢洁清,朱庆生,郭平.蚁群聚类组合方法的研究[J].计算机工程与应用,2009,45(18):146-148.

[13]基于最优适值保留的蚁群文本聚类算法[J].计算机工程与科学，2010，32(5)：79-81.

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

(责任编辑：孙强)

An Improved Ant Colony Clustering Algorithm Based on K-Means

SHANG Yu-xin

( Shandong Institute of Commerce and Technology, JiNan，ShangDong 250103, China )

Clustering analysis is mainly used for dada mining, so does the ant colony clustering algorithm. In this paper, an improved ant colony algorithm is presented based on K-Means algorithm and a mechanism of the best solution kept. It can definite culster center fastly in the beginning and make the best solution kept for the next time. The simulated results show that the improved algorithm has better performance.

clustering analysis; K-Means algorithm; ant colony algorithm; pheromone

2014-09-20

尚玉新，(1986-)，男，山东利津人，硕士，电子信息学院助教，主要研究领域为数据挖掘。

TP274

A

1671-4385(2015)01-0093-03