基于最近邻思想的K-均值算法

李金广 刘家磊 安阳工学院

基于最近邻思想的K-均值算法

李金广 刘家磊 安阳工学院

K-均值聚类算法是一种基于划分方法的聚类算法，本文通过对传统的K-均值聚类算法的分析，提出了一种改进的K-均值算法，并对该算法的时间复杂度和空间复杂度进行了分析。该算法在计算聚类中心点时采用了一种最近邻的思想，可以有效地去除“噪声”和“孤立点”对簇中平均值（聚类中心）的影响，从而使聚类结果更加合理。最后通过实验表明该算法的有效性和正确性。

数据挖掘；聚类；K-均值。

1 当前主要的聚类算法

数据聚类是数据挖掘的一个非常活跃的研究方向。聚类在文献[1]中定义为：将数据对象进行分组，成为多个类或簇。在聚类过程中无须用户提供先验的分类知识，而是根据数据实际的分布情况得到自然的聚集结果。当前主要的聚类算法可以划分为如下几类：

1）基于划分的方法，如k-means(K-均值)文献[2]，k-medoids(K-中心点)文献[3]；

2）基于层次的方法，如BIRCH文献[4]，CURE文献[5], ROCK文献[6]，Chameleon文献[7]；

3）基于密度的方法，如DBSCAN文献[8]；

4）基于网格的方法，如STING；

5）基于模型的方法。

全文内容安排如下：第二节介绍传统K-均值算法的基本思想，并进行特性分析；第三节介绍改进的K-均值算法；第四节实验；第五节结束语。

2 传统的K-均值算法

2.1 基本思想

K-均值算法是一种重要的聚类算法，它是目前应用最广的基于划分的聚类算法，K-均值算法以K为参数，把N个对象分为K个簇，使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中的对象的平均值来进行。

K-均值算法的处理流程如下：首先从N个数据对象任意选择K个对象作为初始聚类中心，而对于所剩下的其他对象则根据它们与这些聚类中心的相似度量（距离）分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）。不断重复这一过程直到标准函数开始收敛为止。

2.2 K-均值算法的基本过程

输入：聚类个数K,以及包含N个数据对象的数据库。

输出：K 个簇。

处理流程：

（1）从N个数据对象任意选择K个对象作为初始聚类中心。

（2）循环下述流程（3）到（4）直到每聚类不再发生变化。

（3）根据每个聚类对象的均值（聚类中心对象），计算与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。

（4）重新计算每个有变化聚类的均值（中心对象）。

2.3 K-均值算法的优缺点

优点：K-均值算法实现起来比较简单其计算复杂度为(nkt),其中,n为对象个数,k为聚类个数,t为循环次数,它具有可扩展性。

缺点：K-均值算法有以下四个缺点：

（1）K-均值算法只适用于聚类均值有意义的情况。

（2）用户必须事先指定聚类个数K。

（3）K-均值算法还不适合发现非凸状的聚类。

（4）K-均值算法对噪声和异常数据非常敏感。因为这类数据可能会影响到各聚类的均值。

要想使一种聚类算法能克服以上所有缺点几乎不可能。针对K-均值算法对异常点和噪声敏感的这一缺点，Kaufman和Rousseeuw在文献中提出了一种K-中心点算法,K-中心点算法不采用簇中对象的平均值作为参照点,而是选用簇中位置最中心的点（中心点）作为聚类的中心点。剩余的对象根据其与代表点的距离分配给最近的一个簇。然后反复地用非代表对象代替代表对象，以改进聚类的质量。

K-中心点聚类算法虽然比K-均值算法更健壮，但K-中心点聚类算法的执行代价要比K-均值算法要高得多。

3 基于最近邻思想的K-均值算法

3.1 基本思想

在传统K-均值算法中存在的一个主要缺点是对噪声和异常点敏感，其原因是在K-均值算法的每一次迭代中，簇中的所有对象都参与计算平均值，再将新的平均值作为新的聚类中心进行计算，这样噪声和异常点都会参与平均值的计算。因而对平均值（聚类中心）有较大的影响。为了避免该情况发生，我们可以选择参与平均值（聚类中心）计算的对象，不是全部的对象都参与计算平均值，而是选择与上次聚类中心最近邻的i（i

下面分析聚类初始点对该算法的影响。如果所选初始点为正常对象（不是异常）点，则其近邻数一般都会大于i这种情况该中心点形成的簇不会被删除。如果某一初始点选中了异常点，由于异常点与正常对象之间的距离较远，则其近邻对象一般都会小于i，这样就可以将该中心点所形成的簇删除，从而使聚类结果更加合理。不会受到异常点的影响。

在聚类过程中，如果某一聚类中心所形成的簇中包含有异常点，如果该簇中包含的对象个数小于i个，则该簇被删除；如果该簇中对象的个数大于i个则在计算新的聚类中心时，异常点必定不会参与计算；如果该簇中对象的个数刚好是i个，则异常点参与计算。但经过数次迭代之后，该情况出现的概率很小。

综上所述，该算法可以有效地去除噪声（异常点）对传统K-均值算法中平均值（聚类中心点）的影响，从而使聚类结果更加合理。

3.2 基本过程

输入：簇的数K，包含n个对象的数据库，i簇中参与计算平均值的对象数目。

输出：K个或小于K个簇。

处理流程：

（1）任意选择K个对象作为初始的簇中心。

（2）循环下述流程（3）（4）直到每个聚类不再发生变化。

（3）根据簇中前i个对象的平均值，将每个对象重新赋给最类似的簇。

（4）更新簇中聚类中心的值。（计算每个簇中与前一次聚类中心最邻近的前i个对象平均值。）

3.3 时间复杂度分析

改进后的K-均值算法与传统K-均值算法的最大区别就是取每个簇中与聚类中心最邻近的i个对象作为计算平均值（下一次聚类中心）的对象。而不是计算簇中所有对象的平均值作为下一次聚类的中心。这样就需要在计算平均值之前进行一次排序。排序的时间复杂度为km2(其中k为簇的个数，m为最大簇中对象的个数)。因此改进后的K均值算法的时间复杂度为k(m2+n)t（其中k为簇的数目，m为最大簇中对象的个数，n为全体数对象个数，t为迭代次数。影响m值的因素很多，如果则改进后的K均值算法与传统的K_均值算法时间复杂性相同，但通常m2>n所以改进后的K平均算法要比传统的K_均值算法时间复杂度要高。

4 实验

我们将本算法应用到学生成绩信息分析中，学生成绩信息分析的目的是研究学生成绩的分布情况，找出异常信息，为教务部门进行教学督查提供决策信息。

1）实验环境

计算机配置：CPU Athlon 64 3000+，1GHz内存，160GB 硬盘

操作系统：Microsoft Windows XP

开发平台：Microsoft Visual Studio 2005

开发语言：C#

数据库：Microsoft SQL Server 2005

2）数据集

近两年来收集的学生公修课学生成绩信息，数据中含学生学号、姓名、高等数学成绩、大学英语成绩。

实验比较了改进后的K-均值算法与传统K-均值算法。实验前首先将指定数据全部读入内存，并完成相应的预处理工作。

3）实验结果分析

通过实验表明改进后的K-均值算法和传统的K-均值算法用时基本相当，并没有显著增加用时，但聚类效果却明显改善。

5 结束语

在本文中，我们提出了一种基于最近邻思想的K-均值算法，该算法在计算聚类中心点时，采用了一种最近邻思想有效克服了‘噪声’对平均值的影响，从而使聚类结果更加合理，并通过实际数据的实验验证明这种算法是有效的。如何将该算法应用到更多的实际数据的聚类是下一步的研究。

[1] Jiawei Han，Micheline Kamber 著；范明，孟小峰，等译.数据挖掘概念与技术.机械工业出版社

[2] J.MacQueen. Some methods for classification and analysis of multivariate observations.Journal of the American Statistical Association, 83:715----728, 1967

[3] L.Kaufman and P.J.Rousseeuw. Finding Groups in Data:An Introduction to Cluster Analysis. New York:John Wiley&Sons,1990

[4] T.Zhang,R.Ramakrishnan, and M.Livny. BIRCH:An efficient data clustering method for very large databases.In Proc.1996 ACMSIGMOD Int.Conf.Management of data (SIGMOD’96),oages 103----114, Mibtreak,Cabada,June 1996

[5] S.Guha,R.Rastogi,and K.Shim. Cure:An efficient clustering algorithm for large databases.In Proc.1998 ACM-SIGMOD Int. Conf.Management of Data(SIGMOD’98), pages73—84, seattle,WA,June 1998

[6] S.Guha,R.Rastogi,and K.Shim. Rock:An Robust clustering algorithm for categorical attributes.In Proc.1999 Int.Conf.Data Engineering(ICDE’99), page512—521, Stdebet,Australia,Mar.1999

[7] G..Karypis,E.-H.Han, and V.Ku- mar. CHANELEON:A hierarchical clustering algorithm using dynamic modeling.COMPUTER,32:68—75,1999

[8] M.Ester,H.-P.Kriegel,J.sander, a nd X. Xu. Adensity-based algorithm for dircorvering clusters in large spatial databases. In Proc. 1996 Int.Conf. Knowledge Discovery and Data Mining (KDD’97),pages226—231,Portland, OR, Aug. 1996

10.3969/j.issn.1001-8972.2011.17.012

李金广（1980-），男，硕士，河南息县人，主要研究方向为数据挖掘、智能信息处理等。