基于划分的K均值聚类算法

丁

丽1，孙高峰

2(1.亳州职业技术学院信息工程系; 2.安徽电力亳州供电公司电力调度控制中心，安徽亳州236800)

①

摘

要：文中首先介绍了聚类分析的涵义，然后分析K －means 算法的基本思想以及划分聚

类的三个关键点，最后通过具体的实例讲解了K －means 算法的实现。

关键词：聚类分析;K －means 算法;簇中心

中图分类号：TP301文献标识码：A 文章编号：1671－380X （2013）06－0028－03

Ｒesearch of K －means Clustering Algorithm Based on Partition

DING Li 1，SUN Gao －feng 2

（1.Department of Information Engineering ，Bozhou Vocation and Technical College ；

2.Power Dispatching Control Center ，Bozhou Power Supply Company ，Anhui Electric ，Bozhou 236800，China ）Abstract ：This paper firstly introduces the definition of cluster analysis ，then analyzes the general idea of K －means algorithm and the three crucial points of typifying clustering.Finally explains the realization of K －means al-gorithm through a concrete example.

Key words ：Cluster Analysis ；K －means Algorithm ；Cluster Center 随着信息技术的快速发展及广泛推进，数据挖掘成为当今社会研究的一个热点领域，聚类分析是数据挖掘中的一项核心技术，它通过研究数据的分布特征来发现数据背后隐藏的事物内部规律。聚类算法有很多种，每一种算法都有自己的独特之处。K －means 算法是聚类分析的经典算法之一，文中主要对K －means 算法进行阐述。1聚类分析概述

聚类分析是人的一项重要活动，比如，小孩子通过不断学习都能够区分动物和植物，也能够区分鸡和狗。聚类与分类不同，分类是按照一定的标准把数据分成不同的类别，聚类是通过观察数据的特征寻找这个标准。

聚类分析的核心是聚类，即将物理或抽象对象的集合分成相似的对象类的过程。通过聚类把数据分成不同的集合，同一个集合中的数据对象彼此相

似，不同数据集合的对象之间彼此相异［1］

。形成聚类的原则是使类内部的相似性最大，类间的相似性最小。聚类的研究方法有很多，用的比较多的是

K －means （K －平均值）、BIＲCH 算法、clara 算法、eLIQuE 算法、chameleon （变色龙）算法等。聚类可以对迅猛增长的数据加以组织，人们通过聚类可以发现一些数据分布的特征，因此成为比较活跃的研究课题。目前，很多领域已经成功地应用了该项技术，包括市场研究、人工智能和图像处

理、生物学、数据压缩等领域［2］

。例如，在生物学领域，聚类可以自动对物种分类，依据是物种特

征；还可以更好地理解生物学中基因的功能。在商业中，市场分析员通过聚类分析可以很容易发现顾客库中不同的顾客群。聚类还可以应用于客户关系管理，对从接触点收集到的数据进行分析，可以得出有价值的知识，以便用于改进营销方案、制定定价和促销策略。2K －means 算法

2.1

K －means 算法基本思想

K －means 算法，也被称为K －均值，是最常用、最著名的一种聚类算法。K －means 算法是把n 个对象分成K 个簇，用簇中对象的均值表示每个

·

82·第35卷第6期2013年6月宜春学院学报

Journal of Yichun College Vol.35，No.6June.2013

①

收稿日期：2013－02－27

作者简介：丁丽（1983－），女，安徽亳州人，助教，硕士，主要从事数据挖掘及电子商务研究，Email ：dingli0206@126.com ；孙高峰（1983－），男，安徽亳州人，工程师，学士，主要从事供电公司地区电网调度工作。

簇的质心，通过迭代使每个簇内的对象不再发生变化为止。这时准则函数达到最优，每个簇内相似度高，簇间相似度低。其过程描述如下：

（1）首先，随机地选择K 个对象，代表要分成的K 个簇的初始均值或中心。

（2）计算其余对象与各个均值的距离，然后把它们分别划分到距离中心最近的簇中。

（3）计算每个簇中所有对象的平均值，作为每个新的簇中心

（4）计算所有对象与新的K 个中心的距离，根据“距离中心最近”原则，重新划分所有对象到各个簇中

（5）重复（3）、（4），直至所有簇中心不变为止。2.2K －means 算法划分聚类的三个关键点

（1）数据对象的划分

①距离度量的选择

K －means 算法比较适合处理连续型属性，对离散型属性不适合。在计算数据对象之间的距离时要选择合适的相似性度量。比较著名的距离度量是欧几里得距离和曼哈顿距离［3］

，其中最常用的是

欧几里得距离，其公式如下：

d x i ，x ()j =

∑d

k =1

x ik －x ()jk

槡

2

（2－1）

这里x i ，

x j 表示两个d 维数据对象，x i =（x i 1，x i 2，…，x id ），x j =（x j 1，x j 2，…，x jd ），d （x i ，x j ）表示对象x i 和x j 之间的距离，距离越小，二者越相似；距离越大，二者差异就越大。

根据欧几里得距离，计算出每一个数据对象与各个簇中心的距离。

②选择最小距离，即如果d （p ，m i ）=

min ｛d （p ，m 1），d （p ，m 2），…，d （p ，m k ）｝

那么，p ∈c i ；P 表示给定的数据对象；m 1，m 2，…，m k 分别表示簇c 1，c 2，…，c k 的初始均值或中心；（2）准则函数的选择。K －means 算法采用平方误差准则函数来评价聚类性能，其公式如下：

E =

∑k

i =1∑p ∈C

i

p －m i

2

（2－2）

E 表示数据库中所有对象的平方误差和，P 表

示给定的数据对象，

m i 表示簇c i 的均值。（3）簇中心的计算。用每一簇的平均值作为

计算相似度簇中心的依据，其公式如下：

m i =

1

n i ∑p ∈C i

p ，i =1，2，…，k （2－3）

这里假设簇c 1，

c 2，…，c k 中的数据对象个数分别为n 1，

n 2，…，n k 。2.3K －means 算法的实现

（1）划分数据对象。选择k 个数据对象作为初始k 个聚类的中心，根据欧几里得距离公式，依次比较每个数据对象与各个中心的距离，选择距离中心最近的簇，依次把n 个对象划分到k 个簇中

［4］

。完成第一次划分之后，重新计算新的簇的

中心，然后开始重新划分数据对象，直到新的簇中心不再发生变化，停止迭代。

（2）计算簇中心。每次划分数据对象之后，都要重新计算簇中心，直到簇中心不再发生变化为止。

2.4K －means 算法实例

现有一需要聚类的数据集合：｛2，

4，10，20，12，30，6，3，15，27｝；假设需要分成两个簇，即k =2，K －means 算法聚类过程如下：

（1）选择数据集合的前两个元素作为初始簇中心，即m 1=2，m 2=4。

（2）对剩下的数据对象，利用欧几里得距离，分别计算它们与各个簇中心的距离，并分配给最近的簇。

对数据元素10：d （10，

m 1）=d （10，2）=8，d （10，m 2）=d （10，4）=6，d （10，m 1）＞d （10，m 2），因此把｛10｝分配给簇C 2；

对数据元素20：d （20，m 1）=d （20，2）=18，d （20，m 2）=d （20，4）=16，d （20，m 1）＞d （20，m 2），因此把｛20｝分配给簇C 2；

对数据元素12：d （12，m 1）=d （12，2）=10，d （12，m 2）=d （12，4）=8，d （12，m 1）＞d （12，m 2），因

此把｛12｝分配给簇C 2；

对数据元素30：d （30，

m 1）=d （30，2）=28，d （30，m 2）=d （30，4）=26，d （30，m 1）＞d （30，m 2），因此把｛30｝分配给簇C 2；

对数据元素6：d （6，m 1）=d （6，2）=4，d （6，m 2）=d （6，4）=2，d （6，m 1）＞d （6，m 2），因此把｛6｝分配

给簇C 2；

对数据元素3：d （3，

m 1）=d （3，2）=1，d （3，m 2）=d （3，4）=1，d （3，m 1）=d （3，m 2），把｛3｝分配给簇C 1；

对数据元素15：d （15，m 1）=d （15，2）=13，d （15，m 2）=d （15，4）=11，d （15，m 1）＞d （15，m 2），因此把｛15｝分配给簇C 2；

对数据元素27：d （27，m 1）=d （27，2）=25，d （27，m 2）=d （27，4）=23，d （27，m 1）＞d （27，m 2），因此把｛27｝分配给簇C 2；

·

92·第6期丁丽，孙高峰：基于划分的K －means 聚类算法第35卷

（3）开始进行第一次迭代。重新计算簇中心：

m

1=2.5，m

2

=15.5，重新计算各个数据元素与新的

簇中心的距离。

对数据元素2：d（2，m1）=d（2，2.5）=0.5，d

（2，m

2）=d（2，15.5）=13.5，d（2，m

1

）＜d（2，m

2

），

因此把｛2｝分配给簇C1；

对数据元素4：d（4，m1）=d（4，2.5）=1.5，d

（4，m

2）=d（4，15.5）=11.5，d（4，m

1

）＜d（4，m

2

），

因此把｛4｝分配给簇C1；

对数据元素10：d（10，m1）=d（10，2.5）=7.5，

d（10，m

2）=d（10，15.5）=5.5，d（10，m

1

）＞d（10，

m

2），因此把｛10｝分配给簇C

2

；

对数据元素20：d（20，m1）=d（20，2.5）=

17.5，d（20，m

2）=d（20，15.5）=4.5，d（20，m

1

）＞d

（20，m

2），因此把｛20｝分配给簇C

2

；

对数据元素12：d（12，m1）=d（12，2.5）=9.5，

d（12，m

2）=d（12，15.5）=3.5，d（12，m

1

）＞d（12，

m

2），因此把｛12｝分配给簇C

2

；

对数据元素30：d（30，m1）=d（30，2.5）=

27.5，d（30，m

2）=d（30，15.5）=14.5，d（30，m

1

）＞

d（30，m

2），因此把｛30｝分配给簇C

2

；

对数据元素6：d（6，m1）=d（6，2.5）=3.5，d

（6，m

2）=d（6，15.5）=9.5，d（6，m

1

）＜d（6，m

2

），

因此把｛6｝分配给簇C1；

对数据元素3：d（3，m1）=d（3，2.5）=0.5，d

（3，m

2）=d（3，15.5）=12.5，d（3，m

1

）＜d（3，m

2

），

因此把｛3｝分配给簇C1；

对数据元素15：d（15，m1）=d（15，2.5）=

12.5，d（15，m

2

）=d（15，15.5）=0.5，d（15，m

1

）＞d

（15，m

2

），因此把｛15｝分配给簇C

2

；

对数据元素30：d（27，m1）=d（27，2.5）=

24.5，d（27，m

2

）=d（27，15.5）=11.5，d（27，m

1

）＞

d（27，m

2

），因此把｛27｝分配给簇C

2

；

所以，第一次迭代后的结果为：C1=｛2，3，4，

6｝，C

2

=｛10，12，15，20，27，30｝。

（4）进行第二次迭代。重新计算簇中心：m

1

=

3.75，m

2

=19。同理，可依次计算出每一个数据元

素与新的均值3.75和19的距离，并划分到距离较

小的簇中。第二次迭代后的结果为：C1=｛2，3，4，

6，10｝，C

2

=｛12，15，20，27，30｝。

（5）进行第三次迭代。重新计算簇中心：m

1

=

5，m

2

=20.8，同理，可依次计算出每一个数据元素

与新的均值5和20.8的距离，并划分到距离较小的

簇中。第三次迭代后的结果为：C1=｛2，3，4，6，10，

12｝，C

2

=｛15，20，27，30｝。

（6）进行第四次迭代。重新计算簇中心：m

1

=

6.17，m

2

=23，同理，可依次计算出每一个数据元素

与新的均值6.17和23的距离，并划分到距离较小

的簇中。第四次迭代后的结果为：C1=｛2，3，4，6，

10，12｝，C

2

=｛15，20，27，30｝。

由以上可以看出：第三次和第四次迭代后两个

簇C1、C2的数据元素没有发生变化，所以再重新

计算出的新的簇中心不变，即m1=6.17，m2=23，

算法停止。聚类结果如表1所示。

表1聚类结果

迭代次数m1m2C1C2

1 2.515.5｛2，3，4，6｝｛10，12，15，20，27，30｝

2 3.7519｛2，3，4，6，10｝｛12，15，20，27，30｝

3520.8｛2，3，4，6，10，12｝｛15，20，27，30｝

4 6.1723｛2，3，4，6，10，12｝｛15，20，27，30｝

用准则函数计算出每次迭代后的总体平方误差分别是420.5，298.8125，246.36，217.4495依次减小，准则函数是收敛的。

3结束语

聚类分析是一种探索性的分析工具，可用于分析用户的行为。如根据客户的不同属性（年龄、职业等）对客户的购买行为进行分类，从而可以针对不同的客户提供不同的营销方式，提高消费者的满意度；也可以用于对网络日志信息进行分类。聚类分析可以作为数据挖掘中其他算法的一个预处理步骤，其结果也可以用于关联分析［5］。K－means算法是聚类分析中最著名的算法，但它也存在一定的不足之处，还有待于进一步的研究和改进。

参考文献：

［1］罗可，蔡碧野，吴一帆，等.数据挖掘中聚类的研究［J］.

计算机工程与应用，2003，（20）：182－185

［2］（加）Jiawei Han，Micheline Kamber，范明，孟小峰.数据挖掘概念与技术［M］.北京：机械工业出版社，2007：3－155［3］陈衡岳.聚类分析及聚类结果评估算法研究［D］.沈阳：东北大学，2006

［4］陈文伟，黄金才，赵新星.数据挖掘技术［M］.北京：北京工业大学出版社，2002：10－16

［5］梁志荣.数据挖掘中聚类分析的技术方法［J］.电脑开发与应用，2007，20（6）：37－39

·

03

·

第6期宜春学院学报第35卷