聚类分析中K-means算法综述

攻读硕士学位研究生试卷（作业）封面

（ 2015 至 2016 学年度第一学期）

题 目 论文选读

科 目 聚类分析中K-means算法综述

姓 名 王苑茹

专 业 计算机技术

入学年月 2015年8月

聚类分析中K-means算法综述

摘要:聚类分析是数据挖掘中一个极其重要的研究方向，是一个将数据划分成簇的方法或手段。聚类分析可广泛利用在商务智能，Web搜索，生物学以及图像模式识别等众多方面。本文主要叙述聚类分析中的K-means聚类算法，总结了K-means聚类算法的研究现状，并针对K-means算法的相关改进做了综述。

关键词：K-means聚类算法；数据子集；聚类中心；相似性度量和距离矩阵 Overview of K-means algorithm in

clustering analysis

Abstract:Clustering is major field in data mining which also is an important method of data partition or grouping. Clustering now has been applied into various ways in business intelligence,Web classification,biology,market and so on.In this paper, we introduce the spatial clustering rules,At the same time, the classical K-means algorithm is describe,And some related improvements to K-means algorithm are summarized.

Key words: K-means clustering algorithm; number of clusters K; cluster initialization; distance metric

1、引言

K-means聚类算法是1955年由Steinhaus 、1957年 Lloyed、1965年 Ball & Hall、1967年 McQueen分别在他们各自研究的不同的科学领域独立提出的。空间聚类分析方法是空间数据挖掘理论中一个重要的领域，是从海量数据中发现知识的一个重要手段。k-means算法是空间聚类算法中应用非常广泛的算法，同时它也在聚类分析中起着重要作用。日益丰富的空间和非空间数据收集存储于空间数据库中，随着空间数据的不断膨胀，海量的空间数据的大小、复杂性都在快速增长，远远超出了人们的解译能力，从这些空间数据中发现邻域知识迫切需求产生一个多学科、多邻域综合交叉的新兴研究邻域，空间数据挖掘技术应运而生。虽然k-means聚类算法被提出已经快60年了，但是目前仍然是应用最为广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。

本文主要叙述聚类分析中的K-means聚类算法，总结了K-means聚类算法的研究现状，并针对K-means算法的相关改进做了综述。

2、经典K-means算法

2.1 K-means算法

k-means 聚类算法是一种基于形心的划分技术，是数据挖掘领域最为常用的聚类方法之一，最初起源于信号处理领域。它的目标是划分整个样本空间为若干个子空间，每个子空间中的样本点距离该空间中心点平均距离最小。因此，k-means是划分聚类的一种。

k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

大体上说，k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度，分别将它们分配给与其最相似的聚类；然后再计算每个所获新聚类的聚类中心；不断重复这一过程直到标准测度函数开始收敛为止。一般都采

用均方差作为标准测度函数。 k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

假设数据集D包含n个欧氏空间中的对象。划分方法把D中的对象分配到K个簇C1,...,Cj中，使得对象1≦i，j≤k,Ci⊂D且Ci⋂Cj=Ø，一个目标函数用来评估划分的质量，使得簇内对象相互相似，而与其他簇中的对象相异。也就是说，该目标函数以簇内高相似性和簇间低相似性为目标。

基于形心的划分Ci技术使用簇的形心代表该簇。对象s∈Ci与该簇的代表ci之差用dist（s，ci）度量，其中dist（x，y）=sqrt( ∑(xi1-yi2)^2 ) 这里i=1,2..n。

簇Ci的质量可以用簇内变差度量，它是Ci中所有对象和形心ci之间的误差的平

方和，

α=∑∑dist(s,ci)2 （1） i=1p∈cik

其中，α是数据集中所有对象的误差的平方和；s是空间中的点，表示给定的数据对象；ci是簇Ci的形心[2]。

2.2 k-means算法流程

k-means算法流程，首先，随机的选择k个对象，每个对象初始地代表了一个聚类的平均值或中心，对剩下的各个对象，根据其与每个聚类中心的欧氏距离，将它派发给最相似的聚类。之后，应用更新之后的均值作为新的聚类中心，再重新分配全部对象。继续迭代，一直到分配趋于稳定，也就是本轮迭代所形成聚类与前一轮形成的聚类相同。

3、K-means聚类算法的参数及其改进

k-means聚类算法需要用户指定 3个参数：类别个数K，初始聚类中心、相似性和距离度量。针对这3个参数，k-means聚类算法出现了不同的改进和变种。

3.1 基于K值的改进

在 k-means 算法中 k 是事先给定的，这个 k 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 k-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。

1) 解决方法-聚类有效性函数

根据聚类有效性函数的方法是非常简单的一种解决方法，从［2，N］的区间内逐一选取k值，并利用该函数评价聚类的效果，最终得到最优的k值。

中外有许多学者也是按照这种思想提出了一系列的解决方法。

李永森等[3]提出的距离代价函数综合了类际距离和类内距离两项距离函数，类际距离为所有聚类中心到全域数据中心的距离之和。类内距离即所有类中对象到其聚类中心的距离之和。作者证明了当距离代价函数达到最小值时，空间聚类结果为最优，此时对应的k 值为最佳聚类数。

杨善林[4]提出的距离代价函数作为空间聚类的有效性检验函数, 就是当距离代价函数达到最小值时侯, 以距离代价最小准则实现了k 值优化算法，空间聚类结果为最优.根据经验规则计算和确定最优解的上界, 给出了求k值最优解kopt及其上界kmax的条件, 并在理论上证明了经验规则kmax≤n的合理性.

吴艳文等[5]提出的通过提供相对较易得到的k 初值( 大于kopt) ,得k 个初始聚类。分析聚类之间相互关系,判断那些聚类应是同一类,从而得到对k 值的优化。

王朔等[6]提出基于非模糊型集群评估指标（DBI）的概念。该指标主要利用几何原理进行运算，分别以聚类间离散程度及位于同一类内数据对象的紧密程度为依据。即不同聚类间的相异性高而同一类内数据对象的相似性高，并以此来进行聚类结果的评估。当类内各数据对象间距离越小而类间距离越大时指标值则越小，代表各聚类内的数据对象越紧密且聚类间的差异大。指标值越小，表明此聚类数目下聚类结果越佳。DBI 值越小代表各聚类内数据相似度越大而类间的相似度越小，由此得到最佳聚类数目。

2）解决方案-遗传算法

Bandyopadhyay 等[7]提出了GCUK 算法是基于遗传算法的。此算法的染色体是运用字符串方式来编码的，也就是将每个初始的聚类中心坐标按照顺序来进行编码，符号“#”来表示没有作为初始聚类中心的数据点，编码完成以后在逐代交叉运算中最后得到了最优k值。

张月琴等[8]提出了优化值参数是基于遗传算法的。在遗传算法中, 通过编码来实现染色体。依据k-means算法要找到最佳的k值, 染色体的编码既是对k值的编码。在一般情况下，对于某类问题,总是有一聚类的最大类数MaxClassnum, 这个值即可由用户来进行输入，也可以是给定的聚类样本个数。k是介于1和MaxClassnum之间的整数，可以使用二进制串既染色体来表示。

胡彧等[9]提出了由遗传操作中的变异操作来控制k值的大小。变异操作的本质是挖掘群体中个体的多样性，同时提高算法的局部随机搜索能力，防止出现未成熟收敛通过对个体适应度函数的求解，决定聚类数k值的变化方向。由于最初所给的聚类数k值并非是最佳聚类数，因此将最初所给种群中具有最大适应度值的个体做为最佳聚类数的榜样个体，其它个体的长度(即k值)向榜样个体的长度靠扰。

3）其他方法

孙雪等[10]提出了一种基于半监督k-means 的k 值全局寻优算法。

设初始少量数据集带标记的为监督信息, 数据集无标记的,监督信息数据集的标记为i和j.设k =2为初值, 在完整的数据集上来进行const rained-k-means 聚类.当k取不同值时, 计算监督信息中被错误标记的数据总数N，公式如下：

N=∑min(nic,njc) （1）

其中c 表示聚类后各簇的标号;nic,njc 表示在第c簇中标记的数据所占的比例为i , j .出现空簇的频率取决于K值上限, 当出现空簇的频率大于50 %时, 则此时k被认为已取得最大值.在k值优化的整个过程中, 如果某一簇内的监督信息满足以下条件, 即 c=1k

max(nic,njc)

nic njc

则该次聚类结果被认为是无效,保留有效的簇中心值,再开始新一轮聚类,在中心点选择上采取了半增量的迭代方式,提高了算法性能。上式阈值选取可采取重复实验的方法,一般当nic与njc的数量相差较少时,类标记为c的簇就为无效的簇.使N取得最小值的k取值就为k-means聚类算法的最佳初值。

田森平等[10]提出了根据所需聚类数据的分布的属性，来计算他们间的距离，经过这一系列变换，得到最终的聚类参数k值。从需要聚类的数据之中抽取出一部分样本数据，来获取聚类参数的抽样数据；再计算抽样数据间的距离来得到一沿对角线对称的距离矩阵，从这一距离矩阵之中找出一个大于零的最小距离即为mind(xi,xj) , 作为高密度半径和簇划分半径的一个项，来保证这两个半径不会太小；对距离矩阵按列求平均值，再对这些平均值求Ri求平均值得到R，根据|Ri-R| / R的误差来去掉噪声点，在噪声点去除完全后，重新计算R，根据R和min d(xi,xj), 求得了高密度半径R。再找出min Ri，依据, d(xi,xj)

的关系来得到高密度个数的参数Z；最终根据R和min d(xi,xj), 获得簇划分的半径r，合并簇的中心点之间距离m，合并簇的边界点之间距离h。

综上所述的研究可发现，学术界已经提出了许多种K值的选取方法，并且分别基于不同的解决方法。

3.2 初始聚类中心的选择

k-means算法是贪心算法，在多项式时间内，只能得到局部最优。初始聚类中心的选择是随机选取的，不同的初始聚类中心选取方法得到的最终局部最优结果也不同。所以可能造成在同一类别的样本被强制当作两个类的初始聚类中心，使得聚类结果最终只能收敛于局部最优解，k-means 算法的聚类效果在很大的程度上依赖于初始聚类中心的选择，因此，大量的初始聚类中心选取方案被提出。 袁方等[11]提出了基于密度的优化初始聚类中心的方法，找到一组能反映数据分布特征的数据对象作为初始聚类中心

首先计算数据对象xi所处区域的密度，来定义一个密度参数：以xi为中心，包含了常数Minpts 个数据对象的半径称为对象xi的密度参数，用ε表示。ε越大，则说明数据对象所处区域的数据密度就越低。反之，ε越小，说明数据对象所处区域的数据密度越高。通过计算每个数据对象的密度参数，就可以发现处于高密度区域的点，从而得到一个高密度点集合D。在D中取处于最高密度区域的数据对象作为第1 个聚类中心z1；取距离z1最远的一个高密度点作第2个聚

类中心z2 ；计算D 中各数据对象xi到z1,z2的距离 d( xi,z1 )，d( xi,z2 )，z3为满足

max(min(d( xi,z1 ), d( xi,z2 )) i =1, 2,…,n

的数据对象xi ；zm为满足

max(min(d( xi,z1 ), d( xi,z2 ),...,d(xi,zm 1)) i =1,2,…,n

的数据对象xi ,xi∈D。依此得到k个初始聚类中心。

秦钰等[12]提出了探测数据集中的相对密集区域, 再利用这些密集区域生成初始类中心点。该方法能够很好地排除类边缘点和噪声点的影响, 并且能够适应数据集中各个实际类别密度分布不平衡的情况, 最终获得较好的聚类效果。

利用UPGMA 层次聚类算法初期汇聚效果好的优势, 发现数据集中的密集区域, 避免类边缘点或噪声点成为初始类中心点, 同时, 着重于考虑区域的相对密集程度, 改变UGPMA 算法的停止条件, 使子树的生成停止在不同的聚类层次上, 以适应各个实际类别密度不平衡的数据集。

赖玉霞等[13]提出了根据数据的自然分布来选取初始聚类中心, 找出对象中分布比较密集的区域, 这正是聚类的目的, 从而摆脱了随机选取聚类中心对聚类结果产生的不稳定性, 以及用质心代表一个簇所带来的“噪声”和孤立点数据对聚类结果的影响。

黄敏等[14]提出了在基于高密度点分布的算法基础上，解决了当高密度点分布不只一个时如何选取聚类中心的问题。找到最大者作为聚类中心点，并将与聚类中心的距离小于样本平均距离的点的密度参数从密度参数集合中删除。

周爱武等[15]提出了的算法的改进建立在没有离群点的数据集上,通过求次小距离的样本点的中心， 然后求出此中心与一个聚类中心之间的距离， 与样本点之间的平均距离进行判断。如果小于样本点之间的平均距离， 则将此样本点加入初始化集合中， 再求第三距离小的样本点，如果大于样本点之间的平均距离， 则求出此中心存入二维数据样本点中心 。集合二维数据样本点中心中的个数等于k， 初始聚类中心全部找到。

周炜奔等[16]提出了基于密度、中心点的初始化中心算法，首先算出样本数据集之中每个样本密度，得到一个以密度为标准的样本集合。然后在标准样本集合基础上进行初始聚类中心的选取和簇的划分。每划分出一个簇，就从标准样本集合中删除该簇所包括的数据点。

郑丹等[17]提出了基于k-means聚类算法对初始聚类中心敏感的这一特点的改进算法。k-means聚类算法中，数据对象间的相似性是根据欧氏距离衡量的，距离越小则说明越相似。用DK图对k-dist图进行分析，找出对应密度水平的平缓曲线。在不同的密度水平上分别选择一个k-dist值最小即密度相对最大的点作为初始聚类中心。根据上述原理，在总数为k的数据集之中找出q`个密度相对与其它点最大的点来作为初始聚类中心。

相比确定k值，优化算法应用于初始聚类中心的选择更加合适，目前已经提出了许多比较成熟的算法，并且已经有相关的专著问世[18]。

3.3 相似性度量和距离矩阵

k-means聚类算法使用欧式距离作为相似性度量和距离矩阵，计算各数据点到其类别中心的距离平方和。因此，k-means聚类算法划分出来的类别店铺是类球形的。实际上，欧式距离是Minkowski距离在m 2时的特例，即L2距离。在采用Lm距离进行K-means聚类时，最终类中心应是每一类的m中心向量。Kashima等人于2008年使用L1距离，最终聚类中心使每一类的中位向量。对于一维数据

X={x1,x2,⋅⋅⋅,xi,⋅⋅⋅,xn}而言，中位数M比均值x对异常数据有较强的抗干扰性，聚类结果受数据中异常值的影响较小。Mao&Jain于1996年提出使用Mahalanobis距离，但计算代价太大。在应用中，Linde等。于1980年提出使用Itakura-Saito距离。Banerjee等人2004年提出，如果使用Bregman差异作为距离度量，有许多突出优点，如克服局部最优、类别之间的线性分离、线性时间复杂度等。

4、结束语

k-means聚类算法是一种非常优秀的算法，以其简单的算法思想、较快的聚类速度和良好的聚类效果得到了广泛的应用。对于该算法在聚类过程中暴露出的若干问题，本文对其中k值确定、初始聚类中心选择等主要问题进行了综述。因此k-means聚类算法是一个贪心算法，在多项式时间内，仅能获得局部最优，对 k-means聚类算法的研究也将继续。

参考文献 ：

[1] Anil K J. Data clustering: 50 years beyond K-Means [J]. Pattern Recognition Letters, 2010,

31(8): 651-666.

[2]Jiawei han;Micheline Kamber;Jian Pei.Data Mining:Concepts and Techniques,Third

Edition[J].2015.7

[3]李永森，杨善林，马溪骏等． 空间聚类算法中的K 值优化问题研究［J］．系统仿真学报，

2006,18( 3) : 573 － 576．

[4]杨善林, 李永森, 胡笑旋, 等.k-means算法中的k值优化问题研究[ J] .系统工程理论与实

践, 2006,(2):97 -101.

[5]吴艳文,胡学钢.一种K_means算法的k值优化方案[J].巢湖学院学报.2007,9(6):21-14.

[6]王朔顾,进广.基于K 值改进的K－means 算法在入侵检测中的应用[J].工业控制计算

机,2014,27(7):93-97.

[7]Bandyopadhyay S,Maulik U.Genetic Clustering for Automatic Evolution of Clusters and

Application to Image Classification［J］．Pattern Recognition，2002，35( 6) : 1197 － 1208．

[8]张月琴, 刘静.一种改进的聚类算法在入侵检测中的应用[ J] .太原理工大学学报, 2008,

39(专辑):74 -76.

[9]孙雪,李昆仑,胡夕坤,赵 瑞.基于半监督K -means 的K 值全局寻优算法.北京交通大学学

报,2009,33(6):106-109.

[10]田森平,吴文亮.自动获取k-means 聚类参数k值的算法[J].计算机工程与设

计.2011,32(1):274-276.

[11]袁方,周志勇,宋鑫.初始聚类中心优化的 k-means 算法.计算机工程.2007,33(3):65-66.

[12]秦钰,荆继武,向继,张爱华.基于优化初始类中心点的K-means 改进算法.中国科学院研究

生院学报,2007,24(6):771-777.

[13]赖玉霞,刘建平.K- means 算法的初始聚类中心的优化.计算机工程与应用,2008,

44( 10):147-149.

[14]黄敏,何中市,邢欣来,陈英.一种新的K-means聚类中心选取算法.计算机工程与应

用,2011,47(35):132-134.

[15]周爱武,崔丹丹,潘勇.一种优化初始聚类中心的K- means聚类算法.微型机与应用，

2011,30(13):1-4.

[16]周炜奔,石跃祥.基于密度的K-means 聚类中心选取的优化算法.计算机应用研究，

2012,29(5):1726-1727.

[17]郑丹,王潜平.K-means初始聚类中心的选择算法.计算机应用，2012,32( 8) :

2186-2188,2192.

[18]戴文华.基于遗传算法的文本分类及聚类研究［M］．北京: 科学出版社，2008. 11