2024年4月4日发(作者：段文茵)

K-means 聚类算法研究综述

摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍

了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性

度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means

聚类的进一步研究方向。

关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵

Review of K-means clustering algorithm

Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global

optimal result cannot be reached. The goal， main steps and example of K-means clustering algorithm are introduced. K-means

algorithm requires three user-specified parameters: number of clusters K， cluster initialization， and distance metric.

Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means

clustering algorithm are pointed at last.

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

K-means聚类算法是由Steinhaus 1955年、Lloyed 1957

年、Ball & Hall 1965年、McQueen 1967年分别在各自的

不同的科学研究领域独立的提出。K-means聚类算法被提出

来后，在不同的学科领域被广泛研究和应用，并发展出大量

不同的改进算法。虽然K-means聚类算法被提出已经超过

50年了，但目前仍然是应用最广泛的划分聚类算法之一

1

。

容易实施、简单、高效、成功的应用案例和经验是其仍然流

行的主要原因。

文中总结评述了K-means聚类算法的研究现状，指出

K-means聚类算法是一个NP难优化问题，无法获得全局最

优。介绍了K-means聚类算法的目标函数、算法流程，并

列举了一个实例，指出了数据子集的数目 K、初始聚类中

心选取、相似性度量和距离矩阵为K-means聚类算法的3

个基本参数。总结了K-means聚类算法存在的问题及其改

进算法，指出了K-means聚类的进一步研究方向。

法和拉格朗日原理，聚类中心



k

应该取为类别

c

k

类各数

据点的平均值。

K-means聚类算法从一个初始的K类别划分开始 ，然

后将各数据点指派到各个类别中，以减小总的距离平方和。

因为K-means聚类算法中总的距离平方和随着类别个数K

的增加而趋向于减小（当

Kn

时，

J(C)0

）

。因此，

总的距离平方和只能在某个确定的类别个数K下，取得最

小值。

1.2 K-means算法的算法流程

K-means算法是一个反复迭代过程,目的是使聚类域中

所有的样品到聚类中心距离的平方和

J(C)

最小，算法流程

其中，

d

ki

[]

距离判断准则，计算该类内各点到聚类中心



i

的距离平方

和

J(c

k

)

x

i

C

i



x

i





k

2

（1）

聚类目标是使各类总的距离平方和

J(C)

小。



J(c

k1

K

k

)

最

J(C)



J(c

k

)



x

i





k

k1k1x

i

C

i

KK

2





d

ki

x

i





k

k1i1

Kn

2

（2）



1若x

i

c

i

，

显然，根据最小二乘







0若x

i

c

i

1经典K-means聚类算法简介

1.1 K-means聚类算法的目标函数

对于给定的一个包含n个 d维数据点的数据集

X{x

1

,x

2

,,x

i

,,x

n

}

，其中

x

i

R

d

，以及要生成

的数据子集的数目K，K-means聚类算法将数据对象组织为

K个划分

C{c

k

,i1,2,K}

。每个划分代表一个类

c

k

，

每个类

c

k

有一个类别中心



i

。选取欧氏距离作为相似性和

包括 4个步骤

[

1

]

，具体流程图如图1所示。

1)选定数据空间中K个对象作为初始聚类

中心，每个对象代表一个类别的中心

2)对于样品中的数据对象，

则根据它们与这

些聚类中心的欧氏距离，按距离最近的准则

分别将它们分配给与其最相似的聚类中心

3)计算每个类别中所有对象的均值作为该类

别的新聚类中心，计算所有样本到其所在类

是

4)聚类中心和

J(C)

值

否

聚类结束

图1 K-means 聚类算法流程图

Fig.1 Steps of K-means clustering algorithm

1.3 K-means聚类算法实例

图2显示的是K-means算法将一个2维数据集聚成3

类的过程示意图。

2 K-means聚类算法是一个NP难优化问题

K-means聚类算法是一个NP难优化问题吗？在某个确

(a)将被分成3类的2维原始输入数据 (

(a) two-dimensional input data with three clusters

定的类别个数K下，在多项式时间内，最小的总距离平方

和

J(C)

值和对应的聚类划分能否得到？目前，不同的学者有

不同的答案。

Aristidis Likas等人

[

2

]

认为在多项式时间内最小的值和

对应的聚类划分能够得到，并于2002年提出了全局最优的

K-means聚类算法。但给出的“The global K-means clustering

algorithm”只有初始聚类中心选取的算法步骤，而缺乏理论

证明。很快，pierre Hansen等人

[

3

]

就提出“The global K-means

clustering algorithm” 不过是一个启发式增量算法，并不能

保证得到全局最优，文章最后还给出了反例。

很多学者指出，如果数据点的维数

d1

，最小的总距

离平方和

J(C)

值和对应的聚类划分能够在

O(Kn)

2

时间内

使用动态规划获得，例如Bellman and Dreyfus

[

4

]

。Pierre

Hansen等人

[

3

]

认为,K-means聚类算法时间复杂度未知。

但是，更多的学者认为，对于一般的数据维数d和类别

个数K，K-means聚类算法是一个NP难优化问题

[

5

]

。Sanjoy

Dasgupta等人认为即使在类别个数K=2的情况下，K-means

聚类算法也是一个NP难优化问题。Meena Mahajan等人

[

6

]

认为即使在数据点的维数

d2

下，对于平面的K-means

聚类问题，也是NP难的。本研究也认为，对于一般的数据

维数d 和类别个数K，K-means聚类算法是一个NP难优化

问题。K-means聚类算法是一个贪心算法，在多项式时间内，

仅能获得局部最优，而不可能获得全局最优。

b) 选择3个种子数据点作为3个类的初始聚类中心

(b) Three seed points selected as cluster centers and initial assignment

of the data points to clusters

(c)更新聚类类别和类别中心的第二次迭代过程 (d)更新聚类类别和类别中心的第3次的迭代过程 (e)K-means聚类算法收敛所获得的最终聚类结果

(c) step two of intermediate literations updating (d)Step three of intermediate iterations updating (e)final clustering obtained by K-means algorithm

cluster labels and their centers cluster labels and their centers at convergence

图2 K-means 算法示意图

Fig.2 Illustration of K-means algorithm

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

K-means聚类算法需要用户指定 3个参数：类别个数

K，初始聚类中心、相似性和距离度量。针对这3个参数，

K-means聚类算法出现了不同的改进和变种。

3.1类别个数K

K-means聚类算法最被人所诟病的是类别个数K的选

择。因为缺少严格的数学准则，学者们提出了大量的启发式

和贪婪准则来选择类别个数K。最有代表性的是，令K逐

渐增加，如

K1,2,

，因为 K-means 聚类算法中总的距

离平方和J随着类别个数 K的增加而单调减少。最初由于

K较小，类型的分裂（增加）会使J值迅速减小，但当K

增加到一定数值时，J值减小速度会减慢，直到当K等于总

样本数N时，

J0

，这时意味着每类样本自成一类，每个

样本就是聚类中心 。如图3所示，曲线的拐点A对应着接

近最优的K值，最优K值是对J值减小量、计算量以及分

类效果等进行权衡得出的结果。而在实际应用中，经常对同

一数据集，取不同的K值，独立运行K-means聚类算法，

然后由领域专家选取最有意义的聚类划分结果。

并非所有的情况都容易找到J-K关系曲线的拐点，此

时K值将无法确定。对类别个数K的选择改进的算法是Ball

& Hall

7

于1965年提出的迭代自组织的数据分析算法

（Iterative Self-organizing Data Analysis Technique

Algorithm, ISODATA），该算法在运算的过程中聚类中心的

数目不是固定不变的，而是反复进行修改，以得到较合理的

类别数K，这种修改通过模式类的合并和分裂来实现，合并

与分裂在一组预先选定的参数指导下进行。

3.2初始聚类中心的选取

越来越多的学者倾向于认为最小化总距离平方和

[]

J(C)

值和对应的聚类划分是一个ＮＰ难优化问题。因此，

K-means聚类算法是一个贪心算法，在多项式时间内，仅能

获得局部最优。 而不同的初始聚类中心选取方法得到的最

终局部最优结果不同。 因此，大量的初始聚类中心选取方

案被提出。

经典的K-means聚类算法的初始聚类中心是随机选取

的。Selim S Z, Al-Sultan K S于1991年提出的随机重启

动K-means聚类算法是目前工程中应用最广泛的初始聚类

中心选取方法，其过程如图4所示。王成等人提出使用最大

最小原则来选取初始聚类中心

8

，与其它方法不同的是，该

过程是一个确定性过程。模拟退火、生物遗传等优化搜索算

法也被用于K-means聚类算法初始聚类中心的选取。四种

初始聚类中心选取方法的比较可见文献

9

。自从 Aristidis

Likas 等人

2

提出“The global K-means clustering algorithm”，

[]

[]

[]

图3 J-K关系曲线

Fig.3 Relationship curve between J and K

对其的批评

3

、讨论和改进就没有停止过

10

。

[][]

用户指定重启动次数N，初始化计数

随机选择初始聚类中心

K-means聚类

计数次数加1

ii1

是

iN?

否

选择J值最小的聚类方案

聚类结束

图4 多次重启动K-means聚类算法流程图

Fig.4 Steps of multiple restarts K-means clustering algorithm

3.3相似性度量和距离矩阵

K-means聚类算法使用欧式距离作为相似性度量

和距离矩阵，计算各数据点到其类别中心的距离平方和。

因此，K-means聚类算法划分出来的类别店铺是类球形

的。实际上，欧式距离是Minkowski距离在

m2

时

的特例，即

L

2

距离。在采用

L

m

距离进行K-means聚

类时，最终类中心应是每一类的m中心向量。Kashima

等人于2008年使用

L

1

距离，最终聚类中心使每一类的

中位向量。对于一维数据

X{x

1

,x

2,

,x

i

,,x

n

}

而言，中位数M比均值x对异常数据有较强的抗干扰

性，聚类结果受数据中异常值的影响较小。Mao & Jain

[

11

]

于1996年提出使用Mahalanobis距离，但计算代价

太大。在应用中，Linde等。于1980年提出使用

Itakura-Saito距离。Banerjee等人2004年提出，如果使

用Bregman差异作为距离度量，有许多突出优点，如

克服局部最优、类别之间的线性分离、线性时间复杂度

等。

4 K-means聚类算法的其他改进

在K-means聚类算法中，每个数据点都被唯一的划分

到一个类别中，这被称为硬聚类算法，它不易处理聚类不是

致密而是壳形的情形。模糊聚类算法能摆脱这些限制，这些

方法是过去20年间集中研究的课题。在模糊方法中，数据

点可以同时属于多个聚类，Dunn 等人

[

12

]

于1973年提出了

模糊K-means聚类算法。

5 结束语

笔者也相信K-means聚类是一个NP难优化问题，但这

需要更加严格的数学理论证明。因此K-means聚类算法是

一个贪心算法，在多项式时间内，仅能获得局部最优，对

K-means聚类算法的研究也将继续。但是对K-means 聚类

算法的研究和改进应注意以下几点：

1）笔者感兴趣的是现实世界问题的实际解决方案，模

式分析算法必须能处理非常大的数据集。所以，只在小规模

的例子上运行良好是不够的；我们要求他的性能按比例延伸

到大的数据集上，也就是高效算法（efficient algorithm）。

2）在现实生活应用中数据里经常混有由于人为误差而

引起的噪声。 我们要求算法能够处理混有噪声的数据，并

识别近似模式。只要噪声不过多地影响输出，这些算法应能

容忍少量的噪声，称为算法的健壮性

（

robust）。相对于

L

2

距离，

L

1

距离有较强的健壮性。但相似性度量和距离矩阵

的选取，不是一个理论问题，而是一个应用问题，需要根据

问题和应用需要需求，假定合适的模型。例如，采用不同

L

m

的距离，K-means聚类的结果一般是不同的。

3）统计稳定性即算法识别的模式确实是数据源的真实

模式，而不只是出现在有限训练集内的偶然关系。如果我们

在来自同一数据源的新样本上重新运行算法，它应该识别出

相似的模式，从这个意义上讲，可以把这个性质看作输出在

统计上的健壮性。样本读入次序不同，一些聚类算法获得的

模式完全不同，而另一些聚类算法对样本读入次序不敏感。

从这个角度来讲，最大最小原则比随机重启动、模拟退火、

生物遗传在初始聚类中心选取上要好。

4）K-means聚类算法的很多变种引入了许多由用户指定

的新参数，对这些参数又如何自动寻优确定，是一个不断深

入和发展的过程。

5）K-means还存在一个类别自动合并问题

[

1

]

，在聚类过

程中产生某一类中无对象的情况，使得得到的类别数少于用

户指定的类别数，从而产生错误，能影响分类结果。其原因

需要在理论上深入探讨,但这方面的论文和研究很少。聚类

的意义，这也是所有的聚类算法都面临的问题，需要在数学

理论和应用两方面开展研究。

参考文献：

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

Recognition Letters, 2010, 31(8): 651-666.

[2] Likas A, Vlassis M, Verbeek J. The global K-means clustering algorithm

[J]. Pattern Recognition,2003, 36(2): 451-461.

[3] Selim S Z，Al-Sultan K S. Analysis of global K -means，an incremental

heuristic for minimum sum-of-squares clustering [J]. Journal of

Classification，2005(2): 287-310.

[4] Bellman R, Dreyfus S. Applied dynamic programming [M]. New Jersey:

Princeton University Press, 1962.

[5] Aloise D, Deshpande A, Hansen P, et al. NP-hardness of euclidean

sum-of-squares clustering [J]. Machine Learning, 2009, 75(2): 245-248.

[6] Mahajan M, Nimbor P, Varadarajan K. The planar K-means problem is

NP-hard [J]. Lecture Notes in Computer Science, 2009(5431): 274-285.

[7] Ball G, Hall D. ISODATA, a novel method of data analysis and pattern

classification[M]. California: Technical rept. NTIS AD 699616. Stanford

Research Institute, 1965.

[8] WANG Cheng, LI Jiao-jiao, BAI Jun-qing, et al. Max-Min K- means

Clustering Algorithm and Application in Post-processing of Scientific

Computing[C]//Napoli: ISEM, 2011: 7-9.

[9] Pena J M, Lozano J A, Larranaga P. An empirical comparison of four

initialization methods for the K -means algorithm [J]. Pattern

Recognition Letters, 1999(20): 1027-1040.

[10] Lai J Z C, Tsung-Jen H. Fast global K -means clustering using cluster

membership and inequality[J]. Pattern Recognition, 2010(43):

1954-1963

[11] Mao J, Jain A K. A self-organizing network for hyper- ellipsoidal

clustering（hec）[J]. IEEE Transactions on neural net- works, 1996(7):

16-29.

[12] Dunn J C. A fuzzy relative of the isodata process and its use in

detecting compact well-separated clusters[J]. Journal of Cybernetics,

1973(3):32-57

2024年4月4日发(作者：段文茵)

K-means 聚类算法研究综述

摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍

了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性

度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means

聚类的进一步研究方向。

关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵

Review of K-means clustering algorithm

Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global

optimal result cannot be reached. The goal， main steps and example of K-means clustering algorithm are introduced. K-means

algorithm requires three user-specified parameters: number of clusters K， cluster initialization， and distance metric.

Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means

clustering algorithm are pointed at last.

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

K-means聚类算法是由Steinhaus 1955年、Lloyed 1957

年、Ball & Hall 1965年、McQueen 1967年分别在各自的

不同的科学研究领域独立的提出。K-means聚类算法被提出

来后，在不同的学科领域被广泛研究和应用，并发展出大量

不同的改进算法。虽然K-means聚类算法被提出已经超过

50年了，但目前仍然是应用最广泛的划分聚类算法之一

1

。

容易实施、简单、高效、成功的应用案例和经验是其仍然流

行的主要原因。

文中总结评述了K-means聚类算法的研究现状，指出

K-means聚类算法是一个NP难优化问题，无法获得全局最

优。介绍了K-means聚类算法的目标函数、算法流程，并

列举了一个实例，指出了数据子集的数目 K、初始聚类中

心选取、相似性度量和距离矩阵为K-means聚类算法的3

个基本参数。总结了K-means聚类算法存在的问题及其改

进算法，指出了K-means聚类的进一步研究方向。

法和拉格朗日原理，聚类中心



k

应该取为类别

c

k

类各数

据点的平均值。

K-means聚类算法从一个初始的K类别划分开始 ，然

后将各数据点指派到各个类别中，以减小总的距离平方和。

因为K-means聚类算法中总的距离平方和随着类别个数K

的增加而趋向于减小（当

Kn

时，

J(C)0

）

。因此，

总的距离平方和只能在某个确定的类别个数K下，取得最

小值。

1.2 K-means算法的算法流程

K-means算法是一个反复迭代过程,目的是使聚类域中

所有的样品到聚类中心距离的平方和

J(C)

最小，算法流程

其中，

d

ki

[]

距离判断准则，计算该类内各点到聚类中心



i

的距离平方

和

J(c

k

)

x

i

C

i



x

i





k

2

（1）

聚类目标是使各类总的距离平方和

J(C)

小。



J(c

k1

K

k

)

最

J(C)



J(c

k

)



x

i





k

k1k1x

i

C

i

KK

2





d

ki

x

i





k

k1i1

Kn

2

（2）



1若x

i

c

i

，

显然，根据最小二乘







0若x

i

c

i

1经典K-means聚类算法简介

1.1 K-means聚类算法的目标函数

对于给定的一个包含n个 d维数据点的数据集

X{x

1

,x

2

,,x

i

,,x

n

}

，其中

x

i

R

d

，以及要生成

的数据子集的数目K，K-means聚类算法将数据对象组织为

K个划分

C{c

k

,i1,2,K}

。每个划分代表一个类

c

k

，

每个类

c

k

有一个类别中心



i

。选取欧氏距离作为相似性和

包括 4个步骤

[

1

]

，具体流程图如图1所示。

1)选定数据空间中K个对象作为初始聚类

中心，每个对象代表一个类别的中心

2)对于样品中的数据对象，

则根据它们与这

些聚类中心的欧氏距离，按距离最近的准则

分别将它们分配给与其最相似的聚类中心

3)计算每个类别中所有对象的均值作为该类

别的新聚类中心，计算所有样本到其所在类

是

4)聚类中心和

J(C)

值

否

聚类结束

图1 K-means 聚类算法流程图

Fig.1 Steps of K-means clustering algorithm

1.3 K-means聚类算法实例

图2显示的是K-means算法将一个2维数据集聚成3

类的过程示意图。

2 K-means聚类算法是一个NP难优化问题

K-means聚类算法是一个NP难优化问题吗？在某个确

(a)将被分成3类的2维原始输入数据 (

(a) two-dimensional input data with three clusters

定的类别个数K下，在多项式时间内，最小的总距离平方

和

J(C)

值和对应的聚类划分能否得到？目前，不同的学者有

不同的答案。

Aristidis Likas等人

[

2

]

认为在多项式时间内最小的值和

对应的聚类划分能够得到，并于2002年提出了全局最优的

K-means聚类算法。但给出的“The global K-means clustering

algorithm”只有初始聚类中心选取的算法步骤，而缺乏理论

证明。很快，pierre Hansen等人

[

3

]

就提出“The global K-means

clustering algorithm” 不过是一个启发式增量算法，并不能

保证得到全局最优，文章最后还给出了反例。

很多学者指出，如果数据点的维数

d1

，最小的总距

离平方和

J(C)

值和对应的聚类划分能够在

O(Kn)

2

时间内

使用动态规划获得，例如Bellman and Dreyfus

[

4

]

。Pierre

Hansen等人

[

3

]

认为,K-means聚类算法时间复杂度未知。

但是，更多的学者认为，对于一般的数据维数d和类别

个数K，K-means聚类算法是一个NP难优化问题

[

5

]

。Sanjoy

Dasgupta等人认为即使在类别个数K=2的情况下，K-means

聚类算法也是一个NP难优化问题。Meena Mahajan等人

[

6

]

认为即使在数据点的维数

d2

下，对于平面的K-means

聚类问题，也是NP难的。本研究也认为，对于一般的数据

维数d 和类别个数K，K-means聚类算法是一个NP难优化

问题。K-means聚类算法是一个贪心算法，在多项式时间内，

仅能获得局部最优，而不可能获得全局最优。

b) 选择3个种子数据点作为3个类的初始聚类中心

(b) Three seed points selected as cluster centers and initial assignment

of the data points to clusters

(c)更新聚类类别和类别中心的第二次迭代过程 (d)更新聚类类别和类别中心的第3次的迭代过程 (e)K-means聚类算法收敛所获得的最终聚类结果

(c) step two of intermediate literations updating (d)Step three of intermediate iterations updating (e)final clustering obtained by K-means algorithm

cluster labels and their centers cluster labels and their centers at convergence

图2 K-means 算法示意图

Fig.2 Illustration of K-means algorithm

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

K-means聚类算法需要用户指定 3个参数：类别个数

K，初始聚类中心、相似性和距离度量。针对这3个参数，

K-means聚类算法出现了不同的改进和变种。

3.1类别个数K

K-means聚类算法最被人所诟病的是类别个数K的选

择。因为缺少严格的数学准则，学者们提出了大量的启发式

和贪婪准则来选择类别个数K。最有代表性的是，令K逐

渐增加，如

K1,2,

，因为 K-means 聚类算法中总的距

离平方和J随着类别个数 K的增加而单调减少。最初由于

K较小，类型的分裂（增加）会使J值迅速减小，但当K

增加到一定数值时，J值减小速度会减慢，直到当K等于总

样本数N时，

J0

，这时意味着每类样本自成一类，每个

样本就是聚类中心 。如图3所示，曲线的拐点A对应着接

近最优的K值，最优K值是对J值减小量、计算量以及分

类效果等进行权衡得出的结果。而在实际应用中，经常对同

一数据集，取不同的K值，独立运行K-means聚类算法，

然后由领域专家选取最有意义的聚类划分结果。

并非所有的情况都容易找到J-K关系曲线的拐点，此

时K值将无法确定。对类别个数K的选择改进的算法是Ball

& Hall

7

于1965年提出的迭代自组织的数据分析算法

（Iterative Self-organizing Data Analysis Technique

Algorithm, ISODATA），该算法在运算的过程中聚类中心的

数目不是固定不变的，而是反复进行修改，以得到较合理的

类别数K，这种修改通过模式类的合并和分裂来实现，合并

与分裂在一组预先选定的参数指导下进行。

3.2初始聚类中心的选取

越来越多的学者倾向于认为最小化总距离平方和

[]

J(C)

值和对应的聚类划分是一个ＮＰ难优化问题。因此，

K-means聚类算法是一个贪心算法，在多项式时间内，仅能

获得局部最优。 而不同的初始聚类中心选取方法得到的最

终局部最优结果不同。 因此，大量的初始聚类中心选取方

案被提出。

经典的K-means聚类算法的初始聚类中心是随机选取

的。Selim S Z, Al-Sultan K S于1991年提出的随机重启

动K-means聚类算法是目前工程中应用最广泛的初始聚类

中心选取方法，其过程如图4所示。王成等人提出使用最大

最小原则来选取初始聚类中心

8

，与其它方法不同的是，该

过程是一个确定性过程。模拟退火、生物遗传等优化搜索算

法也被用于K-means聚类算法初始聚类中心的选取。四种

初始聚类中心选取方法的比较可见文献

9

。自从 Aristidis

Likas 等人

2

提出“The global K-means clustering algorithm”，

[]

[]

[]

图3 J-K关系曲线

Fig.3 Relationship curve between J and K

对其的批评

3

、讨论和改进就没有停止过

10

。

[][]

用户指定重启动次数N，初始化计数

随机选择初始聚类中心

K-means聚类

计数次数加1

ii1

是

iN?

否

选择J值最小的聚类方案

聚类结束

图4 多次重启动K-means聚类算法流程图

Fig.4 Steps of multiple restarts K-means clustering algorithm

3.3相似性度量和距离矩阵

K-means聚类算法使用欧式距离作为相似性度量

和距离矩阵，计算各数据点到其类别中心的距离平方和。

因此，K-means聚类算法划分出来的类别店铺是类球形

的。实际上，欧式距离是Minkowski距离在

m2

时

的特例，即

L

2

距离。在采用

L

m

距离进行K-means聚

类时，最终类中心应是每一类的m中心向量。Kashima

等人于2008年使用

L

1

距离，最终聚类中心使每一类的

中位向量。对于一维数据

X{x

1

,x

2,

,x

i

,,x

n

}

而言，中位数M比均值x对异常数据有较强的抗干扰

性，聚类结果受数据中异常值的影响较小。Mao & Jain

[

11

]

于1996年提出使用Mahalanobis距离，但计算代价

太大。在应用中，Linde等。于1980年提出使用

Itakura-Saito距离。Banerjee等人2004年提出，如果使

用Bregman差异作为距离度量，有许多突出优点，如

克服局部最优、类别之间的线性分离、线性时间复杂度

等。

4 K-means聚类算法的其他改进

在K-means聚类算法中，每个数据点都被唯一的划分

到一个类别中，这被称为硬聚类算法，它不易处理聚类不是

致密而是壳形的情形。模糊聚类算法能摆脱这些限制，这些

方法是过去20年间集中研究的课题。在模糊方法中，数据

点可以同时属于多个聚类，Dunn 等人

[

12

]

于1973年提出了

模糊K-means聚类算法。

5 结束语

笔者也相信K-means聚类是一个NP难优化问题，但这

需要更加严格的数学理论证明。因此K-means聚类算法是

一个贪心算法，在多项式时间内，仅能获得局部最优，对

K-means聚类算法的研究也将继续。但是对K-means 聚类

算法的研究和改进应注意以下几点：

1）笔者感兴趣的是现实世界问题的实际解决方案，模

式分析算法必须能处理非常大的数据集。所以，只在小规模

的例子上运行良好是不够的；我们要求他的性能按比例延伸

到大的数据集上，也就是高效算法（efficient algorithm）。

2）在现实生活应用中数据里经常混有由于人为误差而

引起的噪声。 我们要求算法能够处理混有噪声的数据，并

识别近似模式。只要噪声不过多地影响输出，这些算法应能

容忍少量的噪声，称为算法的健壮性

（

robust）。相对于

L

2

距离，

L

1

距离有较强的健壮性。但相似性度量和距离矩阵

的选取，不是一个理论问题，而是一个应用问题，需要根据

问题和应用需要需求，假定合适的模型。例如，采用不同

L

m

的距离，K-means聚类的结果一般是不同的。

3）统计稳定性即算法识别的模式确实是数据源的真实

模式，而不只是出现在有限训练集内的偶然关系。如果我们

在来自同一数据源的新样本上重新运行算法，它应该识别出

相似的模式，从这个意义上讲，可以把这个性质看作输出在

统计上的健壮性。样本读入次序不同，一些聚类算法获得的

模式完全不同，而另一些聚类算法对样本读入次序不敏感。

从这个角度来讲，最大最小原则比随机重启动、模拟退火、

生物遗传在初始聚类中心选取上要好。

4）K-means聚类算法的很多变种引入了许多由用户指定

的新参数，对这些参数又如何自动寻优确定，是一个不断深

入和发展的过程。

5）K-means还存在一个类别自动合并问题

[

1

]

，在聚类过

程中产生某一类中无对象的情况，使得得到的类别数少于用

户指定的类别数，从而产生错误，能影响分类结果。其原因

需要在理论上深入探讨,但这方面的论文和研究很少。聚类

的意义，这也是所有的聚类算法都面临的问题，需要在数学

理论和应用两方面开展研究。

参考文献：

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

Recognition Letters, 2010, 31(8): 651-666.

[2] Likas A, Vlassis M, Verbeek J. The global K-means clustering algorithm

[J]. Pattern Recognition,2003, 36(2): 451-461.

[3] Selim S Z，Al-Sultan K S. Analysis of global K -means，an incremental

heuristic for minimum sum-of-squares clustering [J]. Journal of

Classification，2005(2): 287-310.

[4] Bellman R, Dreyfus S. Applied dynamic programming [M]. New Jersey:

Princeton University Press, 1962.

[5] Aloise D, Deshpande A, Hansen P, et al. NP-hardness of euclidean

sum-of-squares clustering [J]. Machine Learning, 2009, 75(2): 245-248.

[6] Mahajan M, Nimbor P, Varadarajan K. The planar K-means problem is

NP-hard [J]. Lecture Notes in Computer Science, 2009(5431): 274-285.

[7] Ball G, Hall D. ISODATA, a novel method of data analysis and pattern

classification[M]. California: Technical rept. NTIS AD 699616. Stanford

Research Institute, 1965.

[8] WANG Cheng, LI Jiao-jiao, BAI Jun-qing, et al. Max-Min K- means

Clustering Algorithm and Application in Post-processing of Scientific

Computing[C]//Napoli: ISEM, 2011: 7-9.

[9] Pena J M, Lozano J A, Larranaga P. An empirical comparison of four

initialization methods for the K -means algorithm [J]. Pattern

Recognition Letters, 1999(20): 1027-1040.

[10] Lai J Z C, Tsung-Jen H. Fast global K -means clustering using cluster

membership and inequality[J]. Pattern Recognition, 2010(43):

1954-1963

[11] Mao J, Jain A K. A self-organizing network for hyper- ellipsoidal

clustering（hec）[J]. IEEE Transactions on neural net- works, 1996(7):

16-29.

[12] Dunn J C. A fuzzy relative of the isodata process and its use in

detecting compact well-separated clusters[J]. Journal of Cybernetics,

1973(3):32-57