基于随机扰动的K-M eans聚类中心优化方法∗

孙利雷，秦 进

(贵州大学计算机科学与技术学院，贵州贵阳550025)

基于随机扰动的K-M eans聚类中心优化方法∗

孙利雷，秦 进∗

(贵州大学计算机科学与技术学院，贵州贵阳550025)

针对K-Means算法对初值敏感和容易陷入局部最优的缺点，本文提出一种基于概率的随机扰动聚类中心优化算法。首先，每次迭代后重新计算聚类中心，以聚类中心为圆心向外搜索一定邻域内的点，将聚类中心以概率随机定位到邻域内的某个点上，称该点为物理中心点;之后，选定的物理中心点以一定速率向聚类中心方向移动一定距离，计算出的位置即为新的聚类中心;最后，根据欧氏距离重新划分数据集。该算法通过概率扰动方式使聚类中心不再固定为某一点，而将其中心扩大到一定区域，搜索该区域内的最优解，从而极大地避免了K-Means算法陷入局部最优的可能;并且，即使计算进程已经陷入局部最优，优化后的算法也可以通过最优区域搜索，以一定概率的机会跳出局部最优。

概率;随机扰动;聚类中心;K-Means

近十几年来，随着信息技术的迅猛发展，大型数据库、数据仓库被用于商业、政府、科学研究和工程开发等领域，每个领域都积累了海量的、各种类型的数据资料和基础数据信息。拥有海量基础数据之后，我们又面临新的问题:如何从海量的基础数据信息中发现有用的知识，最大化的发现基础数据中的隐藏知识，提高知识信息的利用率，使其能发挥更大的作用。

聚类分析是数据挖掘中应用最为广泛的算法之一。聚类分析又称群分析，它是研究分类问题的一种统计分析方法，已被广泛应用到许多领域，包括模式识别、图像分析、自然语言处理、数据分析等。如，在植物学分类中，通过植物的不同叶片尺寸、颜色、花瓣半径等特征，使用聚类方法能够推导出不同物种的分类，根据相似特性对其进行分类，获得对物种中固有结构的认识。

聚类是数据挖掘中应用极为广泛的重要技术之一，至今已提出很多聚类算法。聚类是根据数据集的一个或多个特征信息来动态将数据集划分为多个聚类簇，使各个聚类簇内部数据点的相似性高，聚类簇间各个数据点之间的相似性低。目前，数据挖掘领域常用的聚类算法主要有K-Means、层次聚类算法、模糊聚类算法等。K-Means算法因其简单、高效的特性被广泛应用在各个聚类领域[1]。

本文首先介绍K-Means聚类算法及其特征，并由此引出K-Means算法存在的不足之处；之后，分析阐述改进的思想，并引出新的算法；最后是实验部分，通过实验验证新算法的有效性和正确性。

1 K-M eans算法

K-Means算法是一个典型的基于距离的聚类算法，采用距离作为其相似性的评价指标，即认为两个对象的距离越近，其相似度就越大，两个对象的距离越远，其相似度就越小。

K-Means算法输入参数为K(聚类个数)和待聚类的数据集，输出为把数据集分成的K个簇，使得簇内的数据点的相似度高，而各个簇间的相似性低[2]。

通常，使用误差平方函数来评估聚类结果的优劣，误差平方函数定义如下:

E:在数据集中，所有数据点到所属聚类的聚类中心的误差平方和；

n:待聚类的数据集中数据点的个数；

K:聚类中心个数；

ck:第k个聚类中心位置；

Ck:第k个聚类簇；

xi:待聚类数据集中第i个数据点。

1.1 聚类中心计算方法

对于K-Means算法，聚类中心计算可以说是整个算法中最为重要的一环，聚类中心的位置的好坏直接影响到聚类算法的收敛速度和聚类结果的好坏。一个好的聚类中心计算方法可以使算法快速有效的收敛到全局最优解，而不好的聚类中心算法很可能会使聚类算法经过多次迭代后，收敛到次优解或局部最优解。

聚类中心为该簇内所有数据点的均值，计算方式如下:

ck:第k个聚类中心位置；

Ck:第k个聚类簇；

xi:本簇内第i个数据点；

nk:聚类簇Ck中元素的个数。

1.2 聚类划分计算方法

聚类划分计算方法将每个数据点划归到离它最近的聚类中心所属的聚类簇中。

首先，计算出离待聚类数据点x最近的聚类中心，计算方式如下:

x:待聚类的数据点；

ck:离数据点x最近的聚类中心；

ci:第i个聚类簇的聚类中心；

K:聚类簇个数。

得到离数据点x最近的聚类中心后，将数据点x划分到满足聚类中心为ck的聚类簇中。

1.3 K-M eans算法

K-Means算法处理流程:首先，随机选择K个不同的数据点作为每个聚类簇的初始聚类中心；第二步，将数据集中所有数据点，按其到每个聚类中心的距离的远近，划分到距离最近的一个聚类簇中；第三步，计算每个聚类簇内所有数据点的均值，作为该聚类簇新的聚类中心，重新评估聚类中心的优劣。重复第二步和第三步，直至聚类中心不再变化或者达到预先设定的最大迭代次数时停止，输出聚类结果[3]。

K-Means算法描述如下:

输入:聚类中心个数，K；

待聚类的数据集:

n:待聚类数据的个数，

m:待聚类数据的维数；

输出:聚类结果

其中:

初始化:随机选择K个数据点作为K个初始聚类簇中心:{c1，c2，…，cK}。

Repeat Begin

Step1:计算每个待聚类的数据点到每个聚类中心的欧氏距离；

Step2:根据数据点到聚类中心的欧氏距离，将数据点划分到离它最近的一个聚类中心所在的聚类簇中；

Step3:重新计算聚类中心

Step4:计算误差平方和

Step5:误差平方和E小于设定的阈值或聚类分布不再变化，或者达到预先设定的迭代次数时退出，否则跳转到Step1。

Repeat End

1.4 K-M eans算法的缺点

K-Means聚类算法在误差函数为单峰函数情况下能够取得非常好的聚类效果，但在误差函数为多峰函数的情况下就难于取得好的结果。因为KMeans算法初始聚类中心为随机生成，如果随机生成的聚类中心所在的区域为局部最优，K-Means算法又是在局部最优区域内向着局部最优解移动，那么K-Means算法就无法从该局部最优区域跳出，从而无法找出全局最优解。

2 基于随机扰动的K-Means改进算法

传统K-Means中心计算方法，因其为直接通过本聚类簇内所有数据点的均值计算的中心位置，所以不具有向外搜索能力，容易陷入局部最优解，并且当计算进程陷入局部最优解的情况下，没有自行跳出局部最优解的能力。

针对K-Means算法对聚类中心初值敏感，容易陷入局部最优的缺点，引入基于概率的随机扰动的思想到K-Means算法中。基于概率的随机扰动的思想使得算法并不是一直朝着最优(或局部最优)的方向行进，而在行进过程中，以一定的随机条件向邻近区域内的最优解或次优解靠拢，这样就扩大了搜索半径，更容易跳出局部最优的限制而找到全局最优解。

2.1 概念定义

定义一 理论聚类中心

理论聚类中心计算方法是对本聚类簇内所有数据点求均值，得到的均值即为理论聚类中心。理论聚类中心是K-Means算法的聚类中心，用cT表示。

定义二 物理聚类中心

在本聚类簇内，由理论中心位置cT为圆心，按算法开始时设定的搜索半径长度向外搜索，得到搜索半径内的一个数据点的集合，用S表示；在数据集S内，按概率随机指定一个数据点，该数据点的坐标定义为物理聚类中心，用cP表示。

定义三 实际聚类中心

实际聚类中心，是数据点划分的直接依据，是由物理聚类中心cP和理论聚类中心cT相计算得出。其计算方式为物理聚类中心cP向理论聚类中心cT方向按一定距离移动后的坐标位置，用cR表示。

2.2 概率随机定位聚类中心计算方法

2.2.1 理论聚类中心计算方法

理论聚类中心为该聚类簇内所有数据点的均值，其计算方式如下:k

ck:理论聚类中心位置；

Ck:第k个聚类簇；

xi:本簇内第i个数据点；

nk:聚类Ck中元素个数。

2.2.2 本簇内每个数据点的权重计算

数据点的权重，表示本聚类簇内数据点与理论聚类中心的关联度，数据点离理论聚类中心越近，表示该点与理论聚类中心的关联度越高，权重越大；反之该点与理论聚类中心的关联度就低，权重就小。权重计算公式如下:

wi:本簇内第i个点的权重；

xi:本簇中第i个数据点；

nk:本簇中数据点的个数；

Ck:第k个聚类簇。

2.2.3 物理聚类中心计算

依数据点的权重信息，使用轮盘赌算法[4-5]，随机定位到聚类半径内的一个点上[6-7]，则该点的位置即为该簇的物理中心cP。

计算方法如下:

领域集:

s:聚类半径；

使用轮盘赌算法，随机得到领域集Neighbor(ck)中一个数据的索引I；

将领域集Neighbor(ck)中第I个数据作为物理聚类中心:cP＝Neighbor[I]。

2.2.4 实际聚类中心计算

实际聚类中心以物理聚类中心为基准，向理论聚类中心移动一定距离得到。实际聚类中心结合了理论聚类中心和物理聚类中心两个数据的信息，该聚类中心即以物理聚类中心为基点，具有随机性，又参考了理论聚类中心信息，具有稳定性并保证了正确的收敛方向。

计算公式为:

cR:实际聚类中心；

cT:物理聚类中心；

cT:理论聚类中心；

ρ:为步长因子，控制由物理聚类中心cP向理论聚类中心cT移动的速率，取值为0～1之间的实数。当ρ越大时，cP与cT的差值对cT的影响越大。

2.3 基于随机扰动的K-M eans聚类中心优化算法

通过以上分析，整理出可以避免算法落入局部最优，或者当算法已经落到局部最优区域时，通过随机扰动处理使K-Means算法到达全局最优的新算法，基于随机扰动的K-Means聚类中心优化算法，其具体步骤为:

输入:聚类中心个数，K；

聚类数据集:

n:待聚类数据的个数，

m:待聚类数据的维数；

输出:聚类结果

其中:

初始化K个数据点作为K个理论聚类簇中心:{c1，c2，…，cK}

Repeat Begin

Step1:计算理论聚类中心cT、物理聚类中心cP、实际聚类中心cR；

Step2:根据实际聚类中心信息，将数据点按照欧氏距离划分到最近的一个聚类中；

Step3:计算误差平方和

Step4:误差平方和E小于预先设定的阈值或聚类中心和各个簇内数据点不再变化，或者达到预先设定的最大迭代次数时算法结束，否则跳转到Step1。

Repeat End

3 实验结果及分析

本实验共使用了两个数据集，分别是Iris数据集和Yeast数据集。Iris数据集以鸢尾花的特征作为数据来源，数据集包含150个数据；Yeast数据集包含1484个数据。

3.1 实验1.邻域半径大小对基于随机扰动的KM eans聚类中心优化算法收敛速度的影响

聚类个数为K＝2，初始聚类中心随机生成，迭代次数:最大100次。图1是优化算法在Iris和Yeast两个数据集上的表现:

图1 聚类半径大小对聚类速度影响走势图

由测试结果可以看出，邻域半径的大小对算法的收敛速度有较大的影响，该值的选取直接影响到算法的收敛速度。两个数据集在聚类半径在4到12左右时，经过较少的迭代次数就可以收敛到最优。通过对Iris数据集(包含150个数据)和Yeast数据集(包含1484个数据)聚类半径影响趋势图可以看出，当聚类数据量较大时，其聚类半径变化对收敛速度影响越不明显，即数据量越小，算法对聚类半径越敏感。

3.2 实验2.K-M eans算法和基于随机扰动的KM eans聚类中心优化算法在两个数据集上的表现比较

聚类个数K＝2，初始聚类中心随机生成，迭代次数:最大100次。

在Yeast数据集测试结果:K-Means算法和改进后的K-Means算法在Yeast数据集上聚类误差一样，经过多次计算都得到同样的误差值264413，说明该数据集的误差函数很可能是一个单峰值函数，所以两个算法都达到了全局最优解。

在Isir数据集测试结果:由表1可以看出，改进后的K-Means算法在Iris数据集上获得了比KMeans误差更小的聚类结果，说明Iris数据集的误差函数是一个多峰值函数，并且，由于K-Means算法对初始值敏感和易于陷入局部最优，从表1中可以看出，在Iris数据集上，K-Means算法已经陷入了局部最优，没有得到全局最优解。而改进后的KMeans算法避开了K-Means算法所陷入的局部最优，得到了更好的聚类结果。

表1 在Isir数据集上聚类效果的比较

从算法在两个数据集上的测试结果可以看出，在Yeast数据集上，K-Means和基于随机扰动的K-Means聚类中心优化算法误差结果一样；在Iris数据集上，基于随机扰动的K-Means聚类中心优化算法误差小于K-Means算法得到的误差，得到比K-Means更好的结果。

4 结语

基于随机扰动的K-Means聚类中心优化算法在公用数据集Yeast上的测试结果与K-Means算法效果一样，在 Iris数据集上聚类结果优于K-Means算法。由实验结果可以看出，改进后的算法在聚类误差函数为单峰值或较少局部最优的场景下的测试效果与K-Means算法一样；而在误差函数为多峰值函数的数据集场景下，优化后的K-Means算法的测试结果优于标准K-Means算法，更容易得到较K-Means算法更好的聚类结果。所以，基于随机扰动的K-Means聚类中心优化算法相比K-Means算法具有避免和跳出局部最优的能力。

[1]李正兵，罗斌，翟素兰，等.基于关联图划分的 Kmeans算法[J].Computer Engineering and Applications，2013，49(21):1-3.

[2]车丽美，肖洋，王甦易，等.Kmeans聚类分析在形音字表音度中的应用[J].计算机技术与发展，2011，21(2):223-225.

[3]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19(1):48-61.

[4]淦艳，魏延，杨有，等.基于改进随机移动算子的人工鱼群算法[J].Computer Engineering and Applications，2014，50(13):1 -3.

[5]刘坤，葛俊锋，罗予频，等.概率引导的随机采样一致性算法[J].计算机辅助设计与图形学学报，2009(5):657-662.

[6]Geman S，Geman D.Stochastic relaxation，Gibbs distributions，and the Bayesian restoration of images[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，1984(6):721-741.

[7]Geman S，Geman D.Stochastic relaxation，Gibbs distributions，and the Bayesian restoration of images[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，1984(6):721-741.

[8]Fahim A M，Salem AM，Torkey F A，etal.An efficientenhanced k-means clustering algorithm[J].Journal of Zhejiang University SCIENCE A，2006，7(10):1626-1633.

(责任编辑:周晓南)

K-M eans Clustering Center Optim ization M ethod Based on Random Perturbation

SUN Lilei，QIN Jin∗

(College of Computer Science＆Technology，Guizhou University，Guiyang 550025，China)

For the shortcomings of K-Means algorithm that it is sensitive to initial value and easily plunge into local optimum，a randomized clustering center optimization algorithm was proposed.First of all，recalculating the clustering center after each iteration，searching pointswithin a certain neighborhood area outward of the center，choosing the clustering centerwith probability from the points found in neighborhood area，this point is called the physical center.Then，the selected physical centermoving to the cluster center with a certain distance at a certain speed，the calculating location is the new clustering center；Finally，dividing the data set according to the Euclidean distance.The improved algorithm changes the clustering center by probability perturbation method，and enlarges its center to a certain area to search the optimal solution，so the improved algorithm can greatly avoids the K-Means algorithm falling into local optimum；and even if the calculation process is trapped in local optimum，the optimized algorithm can also jump outwith a certain probability through searching the optimal region.

probability；stochastic perturbation；clustering center；K-Means

TP301

A

1000-5269(2016)04-0090-05

10.15958/j.cnki.gdxbzrb.2016.04.18

2015-09-16

贵州大学引进人才科研项目资助(2012028)

孙利雷(1983-)，男，在读硕士，研究方向:模式识别，Email:sunlileisun＠163.com.

∗通讯作者:秦进，Email:56505138＠qq.com.