基于改进粒子群的K—means聚类算法

吴涤单

摘要：针对传统的k-means算法处理离散型数据的不足以及选取初始聚类中心的随机性等缺点，提出了一种基于改进的粒子群优化k-means算法，根据文中提供的优化算法寻找初始聚类中心后，在阀值范围内进行数据样本间的迭代更新，直至聚类中心稳定。经过实验结果验证分析表明，经过改进的粒子群优化k-means算法与传统的k-means算法相比，更具有良好的聚类收敛效果，聚类效果也相对稳定。

关键词：k-means；改进粒子群算法；聚类

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）06-1238-04

Improved K-means Clustering Algorithm Based on Particle Swarm Optimization

WU Di-dan

（Nanjing College of Information Technology， Nanjing 210023， China）

Abstract： Random defects in the traditional K-means algorithm to process the discrete data insufficiency as well as the selection of initial clustering center， put forward an improved particle swarm optimization based on K-means algorithm， to find the initial cluster center according to the optimization algorithm is provided in this paper， are updated iteratively between data samples in the threshold range， until the clustering center. Through the experimental results verify the analysis shows that， by K-means algorithm， the improved particle swarm optimization k-means algorithm compared with the traditional clustering， has a good convergence effect， cluster effect is also relatively stable.

Key words： K-means； improved particle swarm algorithm； clustering

聚类起源于分类学，在原始的分类中，人们大都根据积累以往的知识、经验把信息进行分类。随着信息技术的快速发展和人们对分类信息所提的要求的越来越高，根据以往的经验和知识难以满足目前日益增长的各种分类需求，这就需要我们把数学工具和多元分析引入到分类学当中来，随之产生了目前的多种聚类分析方法，如模糊聚类法、系统聚类法、动态聚类法、图论聚类法、聚类预报法、序样品聚类法等。聚类分析的算法可以分为划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法[1]。目前聚类分析算法已经广泛的应用于税务、教育、商业、计算机科学、人工智能、数据挖掘、人工神经网络等多个不同的应用领域[2]。

1 k-means聚类算法

随着科学技术的日新月异的发展，人们对k-means算法的研究也日益深入，许多的学者也做不少研究、探索、改进，如文献[3]提出一种基于密度敏感相似性度量来确定聚类中心， 文献[4-7]根据聚类样本密度来初始化聚类中心，文献[8]提出了K-means的谱算法，文献[9]提出了一种基于影响因子的K-means算法。

k-means算法也称为k-均值算法，是一种基于划分法的聚类算法，同时也是一种应用十分广泛的聚类算法。它将聚类数据集内的所有数据样本的均值作为该聚类的中心点，该算法的主要流程是通过迭代过程把数据集划分为不同的种类，从而使评价聚类性能的准则函数达到最优，这样就使生成的每个聚类内数据样本紧凑，各个类之间相互独立。这种划分方法开始时将所有的对象都分配至暂定的K集群，然后随机选取数据集中心后，形成聚类中心点，寻找远离中心的数据点，把每个数据点都分配到与之最为接近的聚类中心点，把每个聚类样本中的数据均值作为新的聚类中心，继续选择新的聚类中心和更新迭代直至聚类中心不再变化为止， K-means算法具体描述如下：

第一步：从数据集S中，随机选取k个初始聚类中心（M1， M2， M3，… MI，…， MK）

第二步：计算各个数据点到初始聚类中心（Mi）的距离，根据两者之间距离把各个数据点划分到相应的数据簇

第三步：通过计算更新后的数据簇平均值，找出更加合适的聚类中心Mi

第四步：调整每个数据簇的中心点Mi，判断数据簇的中心点是否变化，若变化跳转到步骤2；否则，结束迭代

2 基于改进的粒子群优化的k-means聚类算法

聚类通常可以定义为对分组的数据集进行分类的方法，通过聚类使同一组中的数据样本具有高度相似性，不同组中的数据样本具有高度的相异性。K-means聚类的主要缺点在于初始聚类中心的选择是完全随机的。正因为这种随机选取初始聚类中心的方式，由此产生的聚类收敛质量难以确定。可以采取的唯一措施是将尽量选择集群中心点作为初始聚类中心。但这只是一种预防措施，从根本上解决不了的问题。正因为传统的k-means算法的这些缺陷，该文在k-means聚类算法的基础上引入改进的粒子群算法，对k-means算法进行优化，使之能达到较好的聚类效果。

2.1 相关定义

定义1 欧氏距离，数据集中空间数据点X和数据点Y之间的距离

D[X，Y]=[i=1n（xi-yi）2] （1）

定义2 切比雪夫距离，两个二维向量之间的最大距离

D[X，Y]max=max[xi-yi] （2）

定义3 数据点与数据集合之间的平均距离

D[X，N]avg= Average（D[X，n]），n∈N （3）

2.2 粒子群算法

粒子群优化算法（PSO）是由美国的Kennedy和Eberhart博士受到鸟群觅食行为的启发于1995年提出的。它属于一种进化算法，与遗传算法有一定的相似性，都是通过随机选定初始解，通过迭代更新，来寻找最优解。但它与遗传算法相比操作实现简单，收敛速度也较快，故在应用领域上也比遗传算法较为广泛，在现实世界中解决问题也具有较大的优越性。

PSO初始化每个问题的解都可以看成一个粒子，然后通过迭代更新来查找问题的答案（最优解）。所有的粒子都有一个经过规则优化的适应值，单个的粒子都有一个决定方向和距离的速度。在寻找最优解的过程其实就是一个粒子迭代更新的过程，在每次迭代过程当中，粒子通过两个极值来更新自我，第一个就是粒子自己所检索到的最优解（个体极值pBest），第二个就是目前整个种群所找到的最优解（种群极值gBest），在粒子群优化算法当中，粒子的位置用W[tij] （W[ti1]， W[ti2]， W[ti3]， ……， W[tix]），在寻找问题最优解的过程当中取决于合适的优化规则和粒子的飞行速度。

V[i+1ij]= w*V[tij]+c1*r*（pBest[tij]- W[tij]）+c2*r*（gBest[tij]- W[tij]） （4）

W[t+1ij] = W[tij] + V[i+1ij] （5）

V[i+1ij] 是粒子的速度， w是惯性权重， W[tij]是当前粒子的位置r 是介于（0， 1）之间的随机数，c1，c2 是学习因子。

2.3改进的粒子群算法

因为粒子的运行速度决定了粒子运行的方向和距离，在公式（4）中，存在w、r、c1、c2等随机数，每次循环更新搜索最优解时也存在一定的随机性。粒子具有可记忆性，为了提高粒子的可遗传性，提高集群的收敛效率，对公式（4）进行一些必要的改进[10]。

c1*r=w1=[pBesttijWtij]，c2*r=w2=[gBesttijWtij]

V[i+1ij]= w*V[tij]+w1*（pBest[tij]- W[tij]）+w2（gBest[tij]- W[tij]） （6）

通过对粒子运行速度计算的改进，增强了粒子局部的搜索能力，提高了聚类的效果。

2.4基于改进粒子群优化的k-means算法

假定我们要把一个含有n个数据样本空间的数据集（S）聚类为k个数据簇（M1 ， M2，… ，Mk）。首先对数据集内的数据样本根据公式（1）进行预先处理，根据公式（1）计算出来的欧式距离来分析各个样本的归属性，降低聚类的复杂性。在粒子群优化算法当中，粒子具有可记忆性，粒子能记住自己搜索到的最优解。粒子的当前位置根据公式（5）由粒子的速度和粒子前一次位置所决定。使用改进了的粒子群优化算法在初始聚类中心时，我们通过计算粒子间的欧式距离选出k个最小平方差的数据点作为聚类的初始中心。然后通过粒子的迭代更新，直至满足聚类的终止条件为止，找到最优的聚类中心。改进的粒子群算法优化k-means聚类算法的具体步骤如下：

输入：给定的数据集S（含有n个数据样本，n1，n2，…nd）

输出：k个聚类

第一步：结合公式（6）计算数据集S中所有样本之间的距离，根据公式（1），选定k个初始聚类中心

第二步：根据公式（2），计算出一个最大阀值f

第三步：根据公式（3）提供的数据点到集合之间的平均距离，把各个数据样本归到k个初始聚类中心，形成k个初始数据簇（V[0i]={V[0i1]， V[0i2]，……， V[0in]}）

第四步：利用改进了粒子群位置计算公式，重新计算各个数据点之间的距离（距离均应小于最大阀值f），根据公式（6），更新聚类中心 V[ti]={V[ti1]，V[ti2]，……V[tik]}

第五步：如果达到规定的收敛效果或者最大的迭代次数就终止更新聚类中心，结束优化，输出k个数据簇。

3 实验验证

为了验证本文经过改进的粒子群优化k-means算法的聚类效果，选用操作系统为 Windows7专业版，内存4G ，处理器为Intel（R） Xeon（R）CPU e31225 @3.10G Hz，在常用的标准测试数据集uci中使用Iris、Balance-scal两种数据集，采用传统的k-means算法、粒子群优化k-means算法、改进的粒子群优化k-means算法，分别测试8次并对其聚类效果进行分析。如下所示。

表1 传统的k-means在Iris、Balance-scal两种数据集上的测试

根据三种不同算法（传统的k-means算法、粒子群优化k-means算法、经过改进的粒子群优化k-means算法）在两个不同的通用数据集（Iris、Balance-scal）上的测试结果可以看出，在Iris数据集上使用三种不同的算法得到的平均准确率依次分别为63.98%，64.83%，77.61%，在Balance-scal数据集上使用三种不同的算法得到的平均准确率依次分别为63.64%，64.19%，77.33%，算法迭代次数都是8次，实验结果表明基于改进的粒子群优化k-means聚类算法，收敛程度高，取得了较好的聚类效果。

4 结束语

k-means算法是一种基于划分的应用十分广泛的进化聚类算法，该文提出根据改进了的粒子群算法来优化k-means，弥补了传统k-means算法随机选取初始聚类中心的不足，经过实验验证取得了良好的收敛效果，聚类质量稳定。

参考文献：

[1] Xu Song，He Yan，Sun Xiuxia，et a1.New visual localization algorithm for targets with different heights[J].Chinese Journal of Scientific Instrument，2010，31（3）：546-551.

[2] Rui Xu，Wunsch D.Survey of clustering algorithms[J].IEEE Trans on Neural Network，2005，16（3）：645-678.

[3] 王玲，薄列峰，焦李成.密度敏感的普聚类[J].电子学报，2007，35（8）：1577-1578.

[4] LAI Yuxia，LIU Jianping.Optimization study on initial center of K-means algorithm[J].Computer Engineering and Applications，2008，44（10）：147-149.

[5] HAN Lingbo，WANG Qiang，JIANG Zhengfeng.Improved K-means initial clustering center selection algorithm[J].Computer Engineering and Applications，2010，46（17）：150-152.

[6] YUAN Fang，ZHOU Zhiyong，SONG Xin.K-means clustering algorithm with meliorated initial center[J].Computer Engineering，2007，33（3）：65-66.

[7] 汪中，刘贵全，陈恩红.一种优化初始中心点的K-means算法[J].模式识别与人工智能，2009，22（2）：299-304.

[8] 钱线，黄萱菁，吴立德.初始化K-means谱算法[J].自动化学报，2007，33（4）：342-346.

[9] Leng Mingwei，Tang Haitao，Chen Xiaoyun.An efficient K-means clustering algorithm based on influence factors[C].Eighth ACIS International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing，2007：815-820.

[10] 陈东辉，刘志镜，王纵虎.一种基于粒子群优化的可能性C均值聚类改进方法[J].计算机科学，2012，39（11）：123-124.