基于划分的K －means 聚类算法丁丽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 PartitionDING 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.1K －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@ ；孙高峰（1983－），男，安徽亳州人，工程师，学士，主要从事供电公司地区电网调度工作。
簇的质心，通过迭代使每个簇内的对象不再发生变化为止。
这时准则函数达到最优，每个簇内相似度高，簇间相似度低。
其过程描述如下：（1）首先，随机地选择K 个对象，代表要分成的K 个簇的初始均值或中心。
（2）计算其余对象与各个均值的距离，然后把它们分别划分到距离中心最近的簇中。
（3）计算每个簇中所有对象的平均值，作为每个新的簇中心（4）计算所有对象与新的K 个中心的距离，根据“距离中心最近”原则，重新划分所有对象到各个簇中（5）重复（3）、（4），直至所有簇中心不变为止。
2.2K －means 算法划分聚类的三个关键点（1）数据对象的划分①距离度量的选择K －means 算法比较适合处理连续型属性，对离散型属性不适合。
在计算数据对象之间的距离时要选择合适的相似性度量。
比较著名的距离度量是欧几里得距离和曼哈顿距离［3］，其中最常用的是欧几里得距离，其公式如下：d x i ，x ()j =∑dk =1x 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 =∑ki =1∑p ∈Cip －m i2（2－2）E 表示数据库中所有对象的平方误差和，P 表示给定的数据对象，m i 表示簇c i 的均值。
（3）簇中心的计算。
用每一簇的平均值作为计算相似度簇中心的依据，其公式如下：m i =1n i ∑p ∈C ip ，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卷所以，C1=｛2，3｝，C2=｛4，6，10，12，15，20，27，30｝。
（3）开始进行第一次迭代。
重新计算簇中心：m1=2.5，m2=15.5，重新计算各个数据元素与新的簇中心的距离。
对数据元素2：d（2，m1）=d（2，2.5）=0.5，d（2，m2）=d（2，15.5）=13.5，d（2，m1）＜d（2，m2），因此把｛2｝分配给簇C1；对数据元素4：d（4，m1）=d（4，2.5）=1.5，d（4，m2）=d（4，15.5）=11.5，d（4，m1）＜d（4，m2），因此把｛4｝分配给簇C1；对数据元素10：d（10，m1）=d（10，2.5）=7.5，d（10，m2）=d（10，15.5）=5.5，d（10，m1）＞d（10，m2），因此把｛10｝分配给簇C2；对数据元素20：d（20，m1）=d（20，2.5）=17.5，d（20，m2）=d（20，15.5）=4.5，d（20，m1）＞d（20，m2），因此把｛20｝分配给簇C2；对数据元素12：d（12，m1）=d（12，2.5）=9.5，d（12，m2）=d（12，15.5）=3.5，d（12，m1）＞d（12，m2），因此把｛12｝分配给簇C2；对数据元素30：d（30，m1）=d（30，2.5）=27.5，d（30，m2）=d（30，15.5）=14.5，d（30，m1）＞d（30，m2），因此把｛30｝分配给簇C2；对数据元素6：d（6，m1）=d（6，2.5）=3.5，d（6，m2）=d（6，15.5）=9.5，d（6，m1）＜d（6，m2），因此把｛6｝分配给簇C1；对数据元素3：d（3，m1）=d（3，2.5）=0.5，d（3，m2）=d（3，15.5）=12.5，d（3，m1）＜d（3，m2），因此把｛3｝分配给簇C1；对数据元素15：d（15，m1）=d（15，2.5）=12.5，d（15，m2）=d（15，15.5）=0.5，d（15，m1）＞d（15，m2），因此把｛15｝分配给簇C2；对数据元素30：d（27，m1）=d（27，2.5）=24.5，d（27，m2）=d（27，15.5）=11.5，d（27，m1）＞d（27，m2），因此把｛27｝分配给簇C2；所以，第一次迭代后的结果为：C1=｛2，3，4，6｝，C2=｛10，12，15，20，27，30｝。