基于邻域模型的K-means初始聚类中心选择算法

基于邻域模型的K-means初始聚类中心选择算法1

曹付元1，2，梁吉业1，2，姜广1，2

1

计算智能与中文信息处理省部共建教育部重点实验室，太原 (030006)

2

山西大学计算机与信息技术学院，太原 (030006)

E-mail：cfy@sxu.edu.cn

摘 要：传统的K-means算法由于其方法简单，在模式识别和机器学习中被广泛讨论和应用.但由于K-means算法随机选择初始聚类中心，而初始聚类中心的选择对最终的聚类结果有着直接的影响，因此算法不能保证得到一个唯一的聚类结果. 本文利用邻域模型中对象邻域的上下近似，定义了对象邻域耦合度和分离度的概念，给出了对象在初始聚类中心选择中的重要性，提出了一种初始聚类中心的选择算法. 另外，分析了邻域模型中三种范数对聚类精度的影响，并和随机选择初始聚类中心、CCIA选择初始聚类中心算法进行了比较，实验结果表明，该算法是有效的.

关键词：邻域模型；初始聚类中心；K-means聚类；粗糙集

聚类分析是数据挖掘研究和应用中的一个重要部分，由于聚类算法不对数据作任何统计假设，在模式识别和人工智能等领域，聚类算法常被称为一种无监督的学习.聚类分析是将数据对象分组成多个类或多个簇，在同一个簇中的对象具有较高的相似度，而不同簇中的对象差别较大[1].目前聚类分析已被广泛应用于金融欺诈、医疗诊断、图像处理、信息检索和生物信息学等研究领域.

自20世纪60年代以来，聚类算法被广泛研究并得到了很好的应用[2-5]，其中1967年Q. J. Mac提出的K-means聚类算法[6]，由于其方法简单，已成为当前最流行的聚类算法之一，特别数据分布呈现类内团聚状，该算法能得到很好的聚类结果. 但K-means算法只适用于数值型数据，因此许多研究者对K-means算法进行了扩展，Z. X. Huang提出了K-modes和K-prototypes算法[7]. A. Ahmad 提出了针对混合数据的K-means聚类算法[8]. 但K-means算法是以确定的类别数及选定的初始聚类中心为前提，算法的聚类结果受到取定的类别数及初始聚类中心 1

的影响，聚类结果只能是局部最优，且不能保证得到一个唯一的聚类结果. 针对初始聚类中心的选择，许多学者进行了研究. R. O. Duda和P. E. Hart提出了一种初始平均值的回归方法[9]. P. S. Bradley等提出了一种优化初始点的过程[10]. J. M. Penā等对K-means算法的不同初始方法进行了比较[11]. S. S. Khan和A. Ahmad提出了一种针对K-means算法的聚类中心初始化算法（CCIA）[12]. 实验结果表明这些算法都优于传统的K-means算法，且随机和Kaufman初始化方法优于其它的初始化方法，因为它不依赖于对象的序[11].

T. Y. Lin提出了邻域模型的概念[13]，该模型通过空间点的邻域来粒化论域空间，将邻域理解为基本信息粒子，用来描述空间中的其他概念. Y. Y. Yao和W. Z. Wu分别研究了1-step和k-step邻域信息系统的性质[14，15]. Q. H. Hu等利用拓扑空间中球形邻域的概念，构造了基于邻域粗糙集模型的特征选择算法[16]. 邻域模型作为数值信息粒度的计算模型已经得到了成功的应用.

M. Meila和D. Heckerman认为初始聚

本课题得到国家863计划项目（2007AA01Z165）和高等学校博士学科点专项科研基金（20050108604）的资助。

- 1 -

http://www.paper.edu.cn

类中心的选择没有一种能普遍接受的方法[17]. 邻域的大小与聚类中心选择有着一种必然的联系. 本文在邻域模型的基础上，通过对象邻域的耦合度和分离度描述了对象在选择初始聚类中心过程中的重要性，提出了针对K-means算法的初始聚类中心确定方法. 采用UCI国际标准数据验证了该方法的有效性，分析了邻域模型中三种范数对聚类精度的影响.

D为决策属性；V=∪Va ，V⊂R，Va

a∈A

是属性a的值域；f:U×A→V是一个信息函数，它为每个对象的每个属性赋予一个信息值，即∀a∈A，x∈U，f(x,a)∈Va.

定义4设S=(U,A,V,f)是一个数值型信息系统，P⊆A，则U关于属性集P的距离矩阵MdP=(dP(i,j))是一个

1 邻域粗糙集模型基本概念

定义1

[16]

|U|×|U|的矩阵，其中任一元素为

dP(i,j)=(∑|f(xi,ak)−f(xj,ak)|λ)1/λk=1|P|

给定一个N维的实数空间

R，d:RN×RN→R，我们称d是RN上的一个度量，如果d满足

（1）d(x1,x2)≥0，∀x1,x2∈RN,

其中1≤i,j≤|U|，λ=1,2,∞，在二维实数空间内，基于1范数，2范数和无穷范数的邻域分别对应菱形、圆和正方形区域.

设Dmax=max{dP(i,j)}为距离矩阵

d(x1,x2)=0当且仅当x1=x2；

（2）d(x1,x2)=d(x2,x1)，

MdP中的最大值，将距离矩阵MdP进行归

一化处理，记为

'Md=(dP(i,j))/Dmax， P

∀x1,x2∈RN;

（3）d(x1,x3)≤d(x1,x2)+d(x2,x3)，

∀x1,x2,x3∈RN;

则称为度量空间.

定义2[16] 给定实数空间上的非空有限集合U={x1,x2,󰀢,xn}，对于U上的任意对象xi，定义其ε邻域为

其中dP(ii,j)为矩阵MdP中的任一元素.

定义5 设S=(U,A,V,f)是一个数值型信息系统，P⊆A，ε≥0，则∀xi∈U定义其ε邻域为

εδP(xi)={x|x∈U,dP(x,xi)≤ε}，

''

δε(xi)={x|x∈U,d(x,xi)≤ε}，

其中ε≥0.δε(xi)称为由xi生成的邻域信息粒子，简称为xi的邻域粒子.

根据度量的性质有：

（1）δε(xi)≠∅，因为xi∈δε(xi)； （2）xj∈δε(xi)⇒xi∈δε(xj)； （3）

则U关于属性集P的

P

ε邻域矩阵

εMdε=(dP(i,j))中任一元素为

⎧1ifdP'(i,j)<εdP(i,j)=⎨. '

0ifd(i,j)ε≥P⎩

定义6 设S=(U,A,V,f)是一个数值

ε型信息系统，X⊆U，P⊆A，ε≥0，则X关于属性集P的下近似、上近似和近似精度分别定义为

εPεX={xi|δP(xi)⊆X,xi∈U}，

∪δε(x)=U.

i

i=1

n

定义3 设S=(U,A,V,f)是一个数值型信息系统，其中U：对象的非空有限集合，称为论域；A：属性的非空有限集合，

εPεX={xi|δP(xi)∩X≠∅,xi∈U}，

A=C∪D，C∩D=∅，C为条件属性，

αPε(X)=

|PεX||PεX|

，

- 2 -

http://www.paper.edu.cn

其中0≤αPε(X)≤1.

定义7 设S=(U,A,V,f)是一个数值型信息系统，P⊆A，ε≥0，则U关于属性集P的ε下近似矩阵Mdε=(dP(i,j))中

P

θ为分离度阈值(0≤θ≤1)，如果

εεDiv(δP(xi),δP(xj))≥θ，则认为xi,xj属

于同一个类内，否则属于两个类.

例1 设S=(U,A,V,f)是一个数值型数据的信息系统，U={x1,x2,x3,x4,x5}，

ε任一元素为

εε⎧1ifδP(xi)⊆δP(xj)，

dP(i,j)=⎨

⎩0otherwiseεa∈A，f(x,a)表示对象x在属性a上的

取值，其中f(x1,a)=1.1，f(x2,a)=1.2，

则U关于属性集P的ε上近似矩阵

εMdε=(dP(i,j))中任一元素为

P

f(x3,a)=1.6

，

f(x4,a)=1.8

，

f(x5,a)=1.9，当指定ε=0.2时，则 x1,x2,x3,x4,x5对应的邻域分别为

εε⎧1ifδP(xi)∩δP(xj)≠∅

. dP(i,j)=⎨

⎩0otherwiseεδ{0.2a}{x1}={x1,x2}， δ{0.2a}{x2}={x1,x2}， δ{0.2a}{x3}={x3,x4}， δ{0.2a}{x4}={x3,x4,x5}， δ{0.2a}{x5}={x4,x5}，

则x1,x2,x3,x4,x5邻域对应的下近似和上近似分别为

定义8设S=(U,A,V,f)是一个数值型信息系统，xi∈U，P⊆A，ε≥0，则

εδP(xi)关于属性集P的耦合度定义为

εβP(xi)=εε|Pε(δP(xi))|

|Pε(δP(xi))|

εε，

其中0<βP(xi)≤1，如果βP(xi)越大，则

xi的ε邻域的耦合度越大. 如果ε=0，则

εε∀xi∈U，都有βP(xi)=1，βP(xi)的计算

{a}0.2(x1)={x1,x2}， {a}0.2(x2)={x1,x2}， {a}0.2(x3)={x3}，

表达式也可表示为

ε(xi)=βP

∑dε(i,j)

P

|U|

{a}0.2(x4)={x3,x4,x5}，

.

∑d

j=1

j=1

|U|εP

(i,j)

{a}0.2(x5)={x5}， {a}0.2(x1)={x1,x2}， {a}0.2(x2)={x1,x2}， {a}0.2(x3)={x3,x4,x5}， {a}0.2(x4)={x3,x4,x5}，

，

定义9 设S=(U,A,V,f)是一个数值型信息系统，∀xi,xj∈U,P⊆A，ε≥0，定义δP(xi)和δP(xj)的分离度为

Div(δP(xi),δP(xj))=

εεεεε|δP(xi)∩δP(xj)|

εε|δP(xi)∪δP(xj)|

εε{a}0.2(x5)={x3,x4,x5}，

且有0≤Div(δP(xi),δP(xj))≤1，如果

εx1,x2,x3,x4,x5邻域对应的耦合度分别

为

Div(δP(xi),δP(xj))越小，则xi,xj中邻域

中对象的分离程度越大.如果ε=0，则

εεβ{0.2a}(x1)=1， β{0.2a}(x2)=1，

∀xi∈U，有Div(δP(xi),δP(xj))=0. 设

- 3 -

εεhttp://www.paper.edu.cn

1

β(x3)=，

3

0.2{a}

对∀i,1≤i≤|Centers|，Order[j],2≤j≤|U|，

都有Div(Centers[i],Order[j])<θ成立，则

β{0.2a}(x4)=1，

Order[j]为一个新的初始中心. 循环上述

操作，当|Centers|=k，算法终止. 如果不能选出k个初始中心点，则减小ε的取值，转步骤２.

β{0.2， a}(x5)=

则有

0.20.20.20.2

， β{0.2a}(x1)=β{a}(x2)=β{a}(x3)>β{a}(x4)=β{a}(x5)

1

3

则x1作为第一个初始聚类中心，而

3 评估方法

对于一个给定的聚类，如果数据集中包含C个类，设ai表示正确分到Ci类中的对象数，bi表示错误分到Ci类中的对象数，

Div(δDiv(δ0.2{a}(x1),δ(x1),δ0.2{a}(x2))=1，所以x2不能作(x3))=0，所以x3为第二

为第二个中心，又因为

0.2{a}

0.2{a}

个中心，假设分为2类，则聚类结果为

ci表示排除在Ci类中的对象数，则第i个类

的精度和召回率分别定义为：

{x1,x2}和{x3,x4,x5}.

pi=ai/(ai+bi)1≤i≤C， ri=ai/(ai+ci)1≤i≤C，

聚类算法的精度和误分率分别定义为[18]

2 初始聚类中心选取算法

（Initial Cluster Centers Choice Algorithm即ICCCA）

输入：S=(U,A,V,f)，P⊆A，聚类个数k,范数λ,分离度阈值θ；

输出：k个初始聚类中心Centers. 步骤１：初始化Centers=∅，生成U关于属性集P的距离矩阵MdP=(dP(i,j))和归一化矩阵M

'

dP

⎛C⎞

micro−p=micro−r=⎜∑ai⎟/n，

⎝i=1⎠

⎛C⎞

Error=⎜∑bi⎟/n,

⎝i=1⎠

其中n是数据集的对象数，同时有

=(dP(i,j))/Dmax，并计

∑(a+b)=∑(a+c)=n.

i

i

i

i

i=1

i=1

CC

算所有对象之间距离的平均值u；

步骤２：在[0，u] 之间选择ε，生成邻域矩阵Mdε=(dP(i,j))；

P

4 实验分析

为了验证该方法的有效性，我们从UCI数据集中挑选了3组数据，其中Letter Image

εε步骤3：生成U中所有对象xi的δP(xi)的下近似矩阵Mdε=(d(i,j))和上近似矩

P

Recognition 数据集是从20000条记录中的前16000条中选出字母为A类和字母为D类的对象，其中字母为A类的对象数有7，字母为D类的对象数有805，3组数据描述如表1所示：

表1 数据描述

Data Set 123

Samples I II 类

类

IV 类

εP

阵Mdε=(dP(i,j))，并求出βP(xi)；

P

εε步骤４：并对βP(xi)按照由高到低排序，设排序结果为x'1≥x'2≥󰀢≥x|U'|，记

εOrder={x'1,x'2,󰀢,x|U'|}；

步骤5：x'1即为第一个初始中心，

Centers=Centers∪{x'; 依次取1}

- 4 -

Wine 178 59 71 48 Recognition Fisher’s Iris 150 50 50 50 Letter Image 15 7 805 0 Recognition

http://www.paper.edu.cn

在计算各对象的邻域时，为了减少因各属性量纲不一致对结果的影响，我们将所有对象之间的距离都标准化到[0，1]区间，同时可以得到所有对象之间的平均距离u.邻域ε的取值是一个非常重要的问题，它决定了邻域的大小，如果邻域太小，则没有其他对象包含在邻域内，如果邻域太大，则可能导致对象之间的分离度降低，不利于聚类.在通常情况下，ε取值在[0，u]之间效果比较好.在三种不同的数据集上取

表4 Letter Image Recognition Data在三种不同初始聚类中心选择算法下K-means聚类算法的误分率

ICCCA算

实际类别数目7（A）805（D）

法分类结果

ICCCA误分率

CCIA误分率

随机误分率

A D 690

99

27 778

877

7.90% 8.55% 9.26%

717

由于在二维实数空间内，基于1范数、

ε=0.1,λ=2,θ=0.5，我们分别比较了本

文提出的算法、CCIA[12]算法以及随机算法确定初始聚类中心下的K-means聚类算法的误分率，其中随机误分率是10次随机聚

2范数和无穷范数分别对应菱形、圆和正方形区域，图1、2、3分别展示了在三个不同的数据集上ε在[0，u]且步长为0.05所对应的三种范式对聚类精度的影响：

类结果的平均值，分别如表2、表3和表4：

表2 Wine Recognition Data在三种不同初始聚类中心选择算法下K-means聚类算法的误分率 实际类别数目

ICCCA算法分类结果 I II III

ICCCA误分率

CCIA误分率

随机误分率

59（I） 59 0 0 71（II） 4 3 48（III） 0 0 48

表3 Fisher’s Iris Data在三种不同初始聚类中心选

择算法下K-means聚类算法的误分率

实际类别数目

ICCCA算法 分类结果

ICCCA

CCIA误分率

随机误分率

3.93% 5.05%

5.51%

图1 Fisher’s Iris Data 在ε在[0，0.4]之间，步长为0.05在三种不同范式对应的误分率（其中距离的平

均值为u=0.4757）

63 51

误分率

I II III 50（I） 50 0 0 50（II） 0 48 2

10.67% 11.33%

50（III） 0 14 36

50 62 38

- 5 -

18.13%

图2Wine Recognition Data在ε在[0，0.6]之间，步长为0.05在三种不同范式对应的误分率（其中距离

的平均值为u=0.6194）

http://www.paper.edu.cn

聚类算法. 计算机学报，2007，30（5）：756-762） [4] M. Zhang, J. Yu. Fuzzy Partitional Clustering

Algorithms. Journal of Software，2004，15（6）：858-868

（张敏，于剑. 基于划分的聚类模型. 软件学报，2004，15（6）：858-868）

[5] X. S. Xing，J. Pan，L. C. Jiao. A Novel K-means

Clustering Based on the Immune Programming Algorithm. Chinese Journal of Computers, 2003，

：605-610 26（5）

（行小帅，潘进，焦李成. 基于免疫规划的K-means 聚类算法. 计算机学报，2003，26（5）：605-610）

[6] Q. J. Mac. Some methods for classification and

analysis of multivariate observation, Proceeding 5th Berkley Symposium. On Mathematical Statistics and Probability, 1967，I, 281-297. University of California Press. 1967，Xvii, 666 [7] Z. X. Huang. Extensions to the k-Means algorithm

for clustering large data sets with categorical values. Data Mining and Knowledge Discovery, 1998, 2: 283-304

[8] A. Ahmad, L.Dey. A K-means clustering algorithm

for mixed numeric and categorical data. Data & Knowledge Engineering, 2007, 63:503-527

[9] R. O. Duda, P.E. Hart. Pattern Classification and

Scene Analysis. John Wiley and Sons. NY，1973 [10] P. S. Bradley, O. L. Mangasarian, W. N. Street.

Clustering via concave minimization. In: M. C. Mozer, M. I. Jordan, T. Petsche(Eds.). Advances in Neural Information Processing System, MIT Press, 1997, 9: 368-374

[11] J. M. Penā, J. A. Lozano, P. Larraňaga. An

empirical comparsion of four initalization methods for the K-means algorithm. Pattern Recognition Letter, 1999, (20):1027-1040

[12] S. S. Khan, A. Ahmad. Cluster center

initialization algorithm for K-means clustering. Patter Recognition Letters, 2004, 25: 1293-1302 [13] T. Y. Lin. Granular Computing on binary

relations I: data mining and neighborhood systems. In: rough sets in knowledge discovery, Skoworn A and Pokowshi L(eds) Physica-Verlag, 1998, 107-121

[14] Y. Y. Yao. Relational interpretation of

neighborhood operators and neighborhood systems. Information Sciences, 1998, 111(198):239-259

[15] W. Z. Wu, W. X. Zhang. Neighborhood operator

systems and approximations. Information Sciences, 2002, 144(1-4):201-217

[16] Q. H. Hu, D. R. Yu, Z. X. Xie. Neighborhood

classifiers. Expert Systems with Applications, 2007, (in Press)

[17] M. Meila, D. Heckerman. An experimental

comparison of several clustering methods. Microsoft Research Report MSR-TR-98-06. Redomnd, WA, 1998

[18] Y. M. Yang. An evaluation of statistical

approaches to text categorization. Journal of Information Retrieval, 1999, 1 (1–2):67-88

图3 Letter Image Recognition Data在ε在[0，0.5]之间，步长为0.05在三种不同范式对应的误分率

（其中距离的平均值为u=0.5671）

根据图1、图2和图3我们可以看出，相同的数据集在不同的范数下，聚类精度是不同的，所以我们可以根据数据分布的不同，选择不同的范数，使聚类精度达到最优.同时邻域ε的取值在[0.05，0.1]之间的效果比较好.

5 结论

本文基于度量空间的邻域模型，通过对象邻域的耦合度和分离度描述了对象在选择初始聚类中心过程中的重要性，提出了一种初始聚类中心确定的方法，给出了邻域ε的取值范围，分析了邻域模型中的三种范数和邻域ε对聚类精度的影响. 实验分析表明，基于邻域模型的初始聚类中心选择算法优于随机选择初始聚类中心和CCIA选择初始聚类中心算法，相对而言参数ε较小的时候聚类精度较高，效果较为理想.

参考文献

[1] J. Han，M. Kamber. Data Mining: Concepts and

Techniques. San Francisco, US: Morgan Kaufmann, 2001

[2] J. S. Zhang，Y. Liang，Z. B. Xu. Clustering

Methods by Simulating Visual Systems. Chinese Journal of Computers，2001，24（5）：496-501 （张讲社，梁怡，徐宗本. 基于视觉系统的聚类算法. 计算机学报，2001，24（5）：496-501） [3] Y. Jin, W. L. Zuo. A clustering algorithm using

dynamic nearest neighbors selection model. Chinese Journal of Computers, 2007，30（5）：756-762

（金阳，左万利. 一种基于动态近邻选择模型的

- 6 -

http://www.paper.edu.cn

Nitial cluster centers choice algorithm for K-means based on

neighborhood model

1

Cao Fuyuan1,2，Liang Jiye1,2，Jiang Guang1,2

Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of

Education，Taiyuan (030006)

2

School of Computer and Information Technology，Shanxi University，Taiyuan (030006)

Abstract

The traditional K-means algorithm considered as a simple method has been widely discussed and applied in pattern recognition and machine learning. However, K-means algorithm could not guarantee unique clustering result because initial cluster centers are chosen randomly, moreover, choosing initial cluster centers is extremely important as it has a direct impact on the formation of final clusters. In this paper, concepts of coupling and division are defined by using low approximation and upper approximation of object neighborhood, and importance of objects in the procedure of choosing cluster centers is also given, initial cluster centers choice algorithm for K-means based on neighborhood model is proposed. Compared with choosing initial cluster centers randomly and CCIA algorithms, cluster accuracy affected by three kinds of norm in neighborhood model is analyzed. The experimental results show that the algorithm is effective.

Keywords：neighborhood model，initial cluster centers，K-means clustering，rough set

作者简介：

曹付元，1974年生，讲师，博士研究生，主要研究方向为数据挖掘、机器学习；

梁吉业，1962年生，教授，博士生导师，主要研究方向为粗糙集理论、数据挖掘、人工智能等；

姜广，1984年生，助教，主要研究方向为概念格、数据挖掘。

- 7 -