基于孤立点和初始质心选择的k均值改进算法

顾洪博 (大庆石油学院计算机与信息技术学院，黑龙江 大庆 163318)

张继怀 (大庆市让胡路区政府，黑龙江 大庆 163712)

顾洪博 (大庆石油学院计算机与信息技术学院，黑龙江 大庆 163318)

张继怀 (大庆市让胡路区政府，黑龙江 大庆 163712)

介绍了在聚类中广泛应用的经典k-均值算法，针对其随机选择初始质心和易受孤立点的影响的不足，给出了一种改进的k-均值算法。首先使用距离法移除孤立点，然后采用邻近吸收法对初始质心的选择上进行了改进，并做了改进前后的对比试验。试验结果表明，改进后的算法比较稳定、准确，受孤立点和随机选择质心的影响也有所降低。

k-均值算法；孤立点；初始质心；距离

聚类(Clustering)是按照某个特定标准将数据集划分成不同个簇(Cluster)或类(Class)的过程，同一组内的数据对象具有较高的相似度而不同组之间的数据对象相似度较低[1]。聚类的应用越来越广泛，在经济学、生物学、医药学、信息工程等许多领域都有着十分重要的应用[2]。因此，对聚类的要求也越来越高，提出准确且又高效的聚类算法刻不容缓。对于一个给定的n个数据对象的数据集，采用目标函数最小化的策略，通过把数据分成k个组，每个组为一个簇，这就是划分方法。最著名与最常用的划分聚类算法是经典k-均值(k-menas)算法[3]，其基本思想描述如下：

1)随机指定k个聚类中心(C1,C2,…,Ck)；

2)对每一个样本Xi,找到离它最近的聚类中心Ci,并将其分配到Ci所标明类；

3)将每一个Cw移动到其标明的类的中心；

4)计算偏差D；

5)如果D值收敛，则返回(C1,C2,…,Ck)并终止算法；否则,返回步骤2)。

k-均值算法能对大型数据集进行高效分类[4]，其计算复杂性为O(tkmn)，其中，t为迭代次数，k为聚类数，m为特征属性数，n为待分类的对象数，通常k、m、t均小于n。但其也存在如下不足：通常会在获得一个局部最优值时终止；仅适合对数值型数据聚类，且算法的效果受孤立点和初始质心的影响很大[5]。为此，笔者给出了一种改进的k-均值算法。

1 对孤立点的改进——基于距离法

经典k-均值算法中没有考虑孤立点。所谓孤立点都是基于距离的，是数据U集中到U中最近邻居的距离最大的对象[6]，换言之，数据集中与其最近邻居的平均距离最大的对象。

针对经典k-均值算法易受孤立点的影响这一问题，笔者基于距离法移除孤立点，具体过程如下：首先扫描一次数据集，计算每一个数据对象与其临近对象的距离，累加求其距离和，并计算出距离和均值。如果某个数据对象的距离和大于距离和均值，则视该点为孤立点。把这个对象从数据集中移除到孤立点集合中，重复直到所有孤立点都找到。最后得到新的数据集就是聚类的初始集合。

2 对随机选取初始聚类中心的改进

经典k-均值算法随机选取k个点作为初始聚类中心进行操作。由于是随机选取，则变化较大，初始点选取不同，获得聚类的结果也不同[7]。并且聚类分析得到的聚类的准确率也不一样。对k-均值算法的初始聚类中心选择方法——随机法进行改进，其依据是聚类过程中相同聚类中的对象是相似的，相异聚类中的对象是不相似的。因此提出了一种基于数据对象两两间的距离来动态寻找并确定初始聚类中心的思路[8]，具体过程如下：

首先整理移除孤立点后的数据集U，记录数据个数y，令m=1。比较数据集中所有数据对象两两之间的距离。找出距离最近的2个数据对象形成集合Am；比较Am中每一个数据对象与数据对象集合U中每一个对象的距离，在U中找出与Am中最近的数据对象，优先吸收到Am中，直到Am中的数据对象个数到达一定数值，然后令m=m+1。再从U中找到对象两两间距离最近的2个数据对象构成Am，重复上面的过程，直到形成k个对象集合。这些集合内部的数据是相似的，而集合间是相异的。

可以看出，这种聚类方法同时满足以下2个条件：①每个组至少包含一个数据对象；②每个数据对象必须属于且仅属于一个组。即数据对象Xi∈Ai，且U={{A1∪A2∪…∪Ak}∪A0}，且Ai∩Aj=Φ。最后对k个对象集合分别进行算术平均，形成k个初始聚类中心。

3 改进算法

假设数据对象集合U有n个数据对象，要将其分为k类，|ε|≤1E-6。改进算法的步骤如下：

输入：聚类个数k，包含n个数据对象p个属性的数据样本集(1≤klt;n)；

输出：k个聚类和t个孤立点。

1)初始化。t=0，A0=Φ(0≤tlt;n)；其中A0存放孤立点的集合；t为孤立点的个数；y为移除孤立点后的数据对象个数；

2)计算U内所有数据对象Xi和Xj之间的距离d(Xi,Xj)(1≤i,j≤n)，并计算U中每个数据对象的距离和Si与距离和均值H；

3)扫描U，比较每个数据点Xi的距离和Si与H的大小，如Sigt;H则Xi为孤立点，t增1，并把Xi加入到A0，并从U中移除Xi；直到所有孤立点都找完，得到t，y=n-t；最后得到新的数据集U′=U-A0。循环t次，输出孤立点；

4)把U′作为新的数据中心，有y个数据对象，其中(1≤y≤n)，m=1；

5)计算U中所有数据对象两两之间的距离d(Xi,Xj)，找出满足dmin(Xi,Xj)的2个数据对象Xi和Xj，令Am={Xi,Xj}，Um=U-Am；

6)计算Am中每一个数据对象与U1中每一个样本的距离，找出在Um中与Am中最近的数据对象Xa((1≤a≤y)，令集合Am={Am,Xa}，Um+1=Um-Am，重复此过程直到Am中的数据对象个数大于等于δ*n/k，(0lt;δ≤1)，δ是经验值；

7)若mlt;k，则m=m+1。再从U2中找到样本两两间距离最近的2个数据对象构成Am，重复5)～7)，直到形成k个对象集合；

8)对k个对象集合分别进行算术平均，形成k个初始聚类中心Ci(1≤i≤k)，计算ε；

9)进行聚类分析，得到U={{A1∪A2∪…∪Ak}∪A0}。4试验分析

试验采用Iris数据集[8]。该数据集共有150条记录，每个记录有4个属性：sepal length、sepal width、petal length和petal width。为了方便，只选取Iris (petal length、petal width) 作为试验对象，并随机加入10个孤立点：(1.5,61)、(21,0.21)、(0,0)、(48,0)、(0.4,91) 、(0,11)、(121,0.01)、(10,0)、(4.8,0)、(0.4,9.1)。从而U中n=150，k=3，t=10，p=2。试验在VC++6.0下进行，试验结果见表1。

从上面的试验中可以看出，k1到k4的结果表明原始的k-均值算法可以比较准确的分类。Iris数据集中数据是均匀分布，但有2类数据有交叉，所以分类效果有所下降。更主要的是因为随机选取的初始质心，也会影响分类效果。4次试验4次初始质心都不一样，自然分类结果也就不同。另外，人为加入的孤立点，明显影响了原始的k-均值算法的执行效果。对于把这些孤立点加到那一个类中，都会使这类的质心有所偏移。因为每个质心的选取都是经过计算平均距离得到的，孤立点的加入会影响其所在类的质心的确定。

表2 改进前后的聚类结果

k5到k6是使用移除孤立点后使用原始k-均值算法得到的数据。可以看出，分类效果好于有孤立点的。k7到k8是改进初始质心后使用原始的k-均值算法获得的数据。试验表明，采用距离法寻找初始聚类中心，分类效果明显好于原始的k-均值算法。去除了质心的随机性，分类结果大大提高。但此时还有孤立点存在的，所以类的稳定性较差。

k9到k10是改进算法得到的结果，分类的准确率有所提高。这说明改进后的算法先移除影响试验结果的孤立点，然后根据计算后的初始质心来寻找数据，因而产生的初始聚类中心比较符合数据实际分布，也就更适用于对实际数据的聚类。

5 结 语

介绍了在聚类中广泛应用的经典k-均值算法，针对其随机选择初始质心和易受孤立点的影响的不足，给出了一种改进的k-均值算法。试验表明，与传统随机选取初始聚类中心的方法相比，改进后的方法可得到更好的划分效果，寻找较为准确的k个聚类中心。

[1]杨小兵.聚类分析中若干关键技术的研究[D].杭州:浙江大学,2005.

[2]连凤娜,吴锦林,唐琦.一种改进的k-means聚类算法[J].电脑与信息技术,2008,16(1):38～40.

[3]Marques J P,Written,Wu Y F.Trans Pattern Recognition Concepts,Methods and Applications[M]. 2nd ed.Beijing:Tsinghua University Press,2002.51～74.

[4]Huang Z.A fast clustering algorithm to cluster very large categorical data sets in data mining[EB/OL]. http://www.ece.northwestern.edu/～harsha/Clustering/sigmodfn.ps，2008-12-15.

[5]Sambasivam S,Theodosopoulos N.Advanced data clustering methods of mining Web documents[J].Issues in Informing Science and Information Technology,2006,(3):563～579.

[6]Sanjay Chawla,Pei Sun. SLOM: a new measure for local spatial outliers[J].Knowledge and Information Systems, 2006, (4) :412～429.

[7]尹珧人,王德广.一种改进的k-means聚类算法在入侵检测中的应用[J].科学技术与工程,2008,8(16):4701～4705.

[8]Sudipto G,Rajeev R,Kyuseok S.Cure:an effieient Elustering algorithm forlarge databases[J]. Information Systems，2001,261:35～58.

[编辑] 洪云飞

TP301.6

A

1673-1409(2009)01-N060-03

2009-01-07

黑龙江省教育厅科学技术研究项目(11521008)；黑龙江省自然科学基金资助项目(F200603)。

顾洪博(1976-)，女，1988年大学毕业，硕士，讲师，现主要从事数据库应用及数据挖掘方面的教学与研究工作。