基于k-means算法改进的蚁群聚类算法

秦福高，王文琴

(常州工学院计算机信息工程学院，江苏 常州 213002)

0 引言

k-means算法是一种经典的聚类分析方法，如果簇与簇之间区别明显、簇内部是密集的，它的聚类效果较好。但是该算法对初始聚类中心敏感，对于“噪声”和孤立点数据敏感，容易陷入局部最优。现在许多研究人员尝试将启发式算法引入聚类分析，借助随机搜索算法找到全局最优解。

蚁群算法是一种有效的随机搜索算法，蚁群在问题空间多点同时进行独立的解搜索，增强了算法的全局搜索能力。Dorigo M 等［1］根据蚁群觅食原理提出了蚁群优化算法。基于觅食行为的蚁群聚类算法中，蚂蚁通过在所经路径移动时留下的信息素进行非直接通信。［2］基于信息素的kmeans聚类方法［3］中，初始中心点虽然不是任选样本，但“噪声”和孤立点仍有可能成为初始聚类中心，而且收敛速度相对较慢。如果能够优化初始中心点，引入精英机制及优生优育机制加强正反馈，则能提高聚类的准确率，加快收敛，于是本文提出了基于k-means算法的改进的蚁群聚类算法。

1 k-means算法及其缺点

1.1 k-means算法思想

k-means算法以k为参数，把n个对象分为k个簇，以使类内具有较高的相似度，而类间的相似度最低。相似度的计算根据一个簇中对象的平均值(被看作簇的重心)来进行。收敛一般采用平方误差准则，其中，E 是数据集中所有对象到中心点的距离平方误差和，p是数据集中的对象，mi是簇 Ci的均值(即中心点)。［3］

1.2 k-means算法缺点

k-means算法是基于距离的经典的聚类算法，其优点是简单、易懂、快速，对于密集型数据，聚类效果好，处理大数据集时，具有相对可伸缩性和高效性。但是该算法对于“噪音”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。如果初始中心点选择不当，容易使算法陷入局部最优状态，不同的初始中心点，可能会导致不同的聚类结果。

2 一种基于信息素的k-means聚类方法

2.1 蚁群算法

蚂蚁的食物源总是随机散布于蚁巢周围，经过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。蚂蚁运动时是通过路径上释放出的一种特殊的分泌物——信息素来寻找路径。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。

由于现实的蚁群运动过程接近于实际的聚类问题，所以近年来涌现出大量的蚁群聚类算法。基于觅食行为的蚁群聚类算法，将数据视为具有不同属性的蚂蚁，聚类中心即是蚂蚁所要寻找的“食物源”，数据聚类过程则被看作是蚂蚁寻找食物源的过程，蚂蚁通过其移动时在所经路径留下的信息素进行非直接通信，形成正反馈加强搜索。［2］

2.2 蚁群算法与k-means算法的结合

传统k-means算法的初始中心点是任选的样本，如果初始中心点选在“噪音”和孤立点数据周围，即使是少量的该类数据也能够对平均值产生极大的影响，容易使算法陷入局部最优状态。基本蚁群算法可看做是一个分布式的多智能体系统，该算法在问题空间的多个点同时独立地进行解搜索，不仅使算法具有较强的全局搜索能力，也增加了算法的可靠性。Sara Saatchi等人［3］将蚁群算法与k-means算法结合成基于信息素的k-means聚类方法，利用蚁群算法的全局搜索能力来弥补k-means算法容易陷入局部最优的不足。

基于信息素的k-means聚类方法处理过程:开始时将所有对象随机归并到k个类中，然后计算出初始类中心并更新信息素，数据对象的归属根据转移概率的大小来决定，在下一轮循环中，引入聚类偏差的衡量标准，更新聚类中心，计算偏差，再次判断，直到偏差没有变化或在一定误差范围内，算法结束。

该算法的初始中心点虽然不是任选的样本，但仍是随机分成k类后各类样本的重心，分类的随机性比较大，“噪声”和孤立点仍有可能成为初始聚类中心，陷入局部最优，影响聚类的准确率。另外，该算法在聚类过程中只是采用基本蚁群算法中的信息素更新方式，收敛速度相对较慢。所以此算法有待进一步改进。

3 改进的聚类算法

3.1 基于距离和密度优化初始凝聚点

通常，聚类时希望选择数据集中、分布范围较大的点作为凝聚点。初始凝聚点如果仅基于距离因素，往往会取到“噪声”或孤立点。如果仅基于密度选择初始凝聚点，选出的k个类中心中有多个距离相近同属于一个类的可能性将非常大，这无疑会增加迭代的次数。

因此本文提出基于距离和密度优化初始凝聚点。算法取相距最远的k个均处于高密度区域的样本作为聚类中心，这些中心点基本上是确定的，从而避免了初始中心选择的随机性，尽可能降低了“噪声”和孤立点的干扰，保证了聚类结果较好的稳定性，同时也能防止多个类中心同处一类导致寻优迭代次数的增加。

首先定义样本点x所在区域的密度:

其中，Distance(x，p)为某种距离度量，r为半径，X代表样本点集，p是以x为中心、以r为半径的球体内的样本。式(1)表明数据对象的密度是以x为中心点、r为半径组成的球体所包含的样本数。半径r的确定方法如下:首先计算两两数据对象间距离的平均值averdis，然后根据经验，给定一个常数 θ，密度半径:r=θ*averdis。

计算出每个数据对象的密度后，找到处于高密度区域的样本组成高密度样本集合hdsample，在hdsample中取密度最大样本点作为第—个聚类中心center1，然后取距离center1最远的一个高密度样本点作为第二个聚类中心center2，接着取满足 max(min(d(x1，center1)，d(xi，center2)))i=1，2，…，n 的样本 xi作为 center3，以此类推，取满足 max(min(d(x1，center1)，d(xi，center2)，…，d(xi，centerq-1)))i=1，2，…，n 的样本 xi作为centerq。按照此方法，计算出k个初始聚类中心。

3.2 精英机制及优生优育机制

蚁群聚类过程中如果只是采用基本蚁群算法中的信息素更新方式，收敛速度相对较慢。因此，本文提出引入精英机制及优生优育机制加强正反馈进行蚁群聚类:根据信息素及蚂蚁的随机性确定每只蚂蚁行走路径，并做好相应的标识;根据标识的类别计算各聚类中心，并计算每只蚂蚁的旅程F;根据F值升序排序，前3只蚂蚁作为精英，并只对这3只精英蚂蚁的旅程进行变异实现优生优育，再计算F，找出父代和子代中旅程最短的精英蚂蚁，保留该精英，进行后续处理。

聚类过程中采取精英保留机制，并在精英中进行变异优生优育，利用若干精英的信息来更新信息素。这种聚类方法不仅可以进一步避免“噪声”和孤立点的干扰，还能够利用信息素的正反馈作用加快收敛速度，求得最优解。

3.3 算法的处理过程

改进的算法处理过程如下:

把基于距离和密度优化的聚类中心作为初始中心点，依据欧氏距离进行第一次聚类;依据式(2)根据第一次聚类结果更新路径上的信息素;依据式(3)计算转移概率Pij，数据样本Xi是否归并到聚类中心Cj由转移概率Pij决定，若Pij(t)＞P0(P0为一设定值)，则Xi归并到Cj，否则，不归并;根据类内距计算适应度值，找出前3只精英蚂蚁并进行变异，从所有蚂蚁中找出精英蚂蚁及其路径，更新各条路径上的信息素，对此次最优路径进行正反馈;下一代蚂蚁根据信息素寻找目的地;当精英蚂蚁不再变化时，停止聚类，输出结果。

其中，ρ为信息素挥发系数;τij(t)为t时刻样本Xi到聚类中心Cj路径上的信息量;Q为信息素强度;L为当前蚂蚁本次循环所走路径的总长度;α为信息启发式因子，反映了蚂蚁在运动过程中积累的信息在蚂蚁状态转移时所起的作用，其值越大，蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强;β为期望启发式因子，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，状态转移概率越接近于贪心规则;ηij(t)为启发函数，一般 ηij(t)=1/dij，dij是样本 Xi到聚类中心Cj的距离。

4 实验结果及分析

4.1 实验结果

实验环境是Matlab 7.0，实验数据集有8个，见表1，其中Ant1和Ant2是类与类之间区别明显的人工数据集，Iris、Glass、Blance、Image、Wine 和Zoo是来自UCI机器学习库中的数据集。通过8个数据集测试k-means算法、基于信息素的kmeans聚类方法及本文提出的改进算法的F-measure和运行时间平均值，测试结果见表2。

表1 数据集描述

表2 三种算法的测试结果

4.2 实验分析

测试结果采用常用的外部评价方法F-measure来进行聚类准确率的评估。F-measure组合了信息检索中查准率与查全率的思想，查准率即正确预测的百分比，查全率即捕捉到正确分类的百分比。

根据表2的实验数据，在测试数据集相同的情况下，k-means算法的F-measure值最低，主要因为初始凝聚点是随意选择的样本，常常受到“噪声”或孤立点的干扰，陷入局部最优;基于信息素的 k-means聚类方法的 F-measure值比k-means算法有所提高，因为初始凝聚点是随机分类后的样本的重心，一定程度上可以减少“噪声”或孤立点的干扰;本文提出的基于k-means算法的改进的蚁群聚类算法的F-measure值最高，说明基于距离和密度优化初始凝聚点，再利用蚁群的多点同时独立搜索这一分布式特点，可以有效避免噪声或孤立点的影响，提高聚类准确率。

从运行时间上看，k-means算法最快，因为算法简单，只要根据欧氏距离即可进行聚类;基于信息素的k-means聚类方法最慢，主要是为了防止陷入局部最优，蚂蚁的转移受到随机概率的影响;本文提出的基于k-means算法的改进的蚁群聚类算法，因为初始时对优化的凝聚点进行了正反馈，聚类过程中又采取了精英保留机制和优生优育策略加强正反馈，所以加快了收敛，能更快地找到最优解。

5 结语

本文提出了一种基于k-means算法的改进的蚁群聚类算法，从实验结果看，较好地解决了“噪声”或孤立点的干扰，在实现全局搜索提高聚类准确率的同时，加快了收敛速度，该算法是可行的、有效的。

［1］Dorigo M，Di Caro G.The ant colony optimization meta-heuristic［C］//Corne D，Dorigo M，Glover F.New Ideas in Optimization.London:McGraw-Hill，1999:11-32.

［2］李士勇，陈永强，李妍.蚁群算法及其应用［M］.哈尔滨:哈尔滨工业大学出版社，2004:14-18.

［3］Saatchi S，Hung C C.Hybridization of the Ant Colony Optimization with the K-Means Algorithm for Clustering［C］//Kalviainen H，Parkkinen J，Kaarna A.SCIA 2005.Berlin:Springer-Verlag，2005:511-520.