K-最近邻聚类算法（精选4篇）
K-最近邻聚类算法 篇1
聚类是一种无监督的机器学习模式,是数据挖掘、机器学习以及模式识别领域重要的研究内容,在识别数据集的内在结构方面具有极其重要的地位。聚类算法通常在语音识别、图像处理、数据挖掘、生物学、心理学、考古学等诸多领域和学科中被广泛地应用[1]。
聚类算法主要包括划分方法、层次的方法、基于密度的方法、基于网格的方法以及基于模型的算法。宏观上来看,以上算法大致可分为两类:从整体出发聚类如,K-MEANS、CURE算法等,以及从个体出发聚类如DBSCAN、CHAMELEON算法等。从整体出发的聚类很难考虑到个体之间特定的联系和差异,因此很难发现对象之间固有的联系。与此相反,从个体出发的聚类可以掌握对象之间的关联关系,在聚类过程中能够保持关联的有效性。然而对于个体出发的聚类又难以给出具体的参数对簇的大小和数量加以界定。
为了解决以上问题,优化聚类效果,提出一种基于K近邻团的聚类算法。该算法同时引用了K近邻与逆K近邻[5]的概念,构造K近邻邻接矩阵和逆K近邻邻接矩阵,通过矩阵“与”操作构造K近邻团邻接矩阵,在此邻接矩阵上挖掘K近邻团,从而发现对象之间的固有聚类。K近邻团中的任意两个对象之间互为K近邻,保证了彼此之间的相似性,避免对象被错误地划分到其他簇中。同时选择不同的K值可以形成大小不等的团,通过数据自身的关联来决定簇的数量。
1 K近邻图、逆K近邻图、K近邻团和极大K近邻团
在介绍K近邻团聚类算法之前,先引入K近邻图、逆K近邻图、K近邻团和极大K近邻团的概念。
1.1 K近邻图和逆K近邻图
K近邻(KNN)是由Cover 和Hart 于1968年提出的,定义K近邻图如下:
定义1K近邻图是指有向图GKNN=(V,E),其中结点集V={V1,V2,…,Vn},边集E={e1,e2,…,em}且ek=<Vi,Vj>,Vi,Vj∈V; i=1,2,…,m,当且仅当Vi是Vj的K近邻时ek不为零,且邻接矩阵MKNN(n*n)[ij]不为零。
K近邻图表示对象之间的相似关系,根据K的取值不同邻接矩阵可以是稀疏矩阵,也可以是稠密矩阵,其元素个数为kn个。
定义2 逆K近邻图是指有向图GRKNN=(V,E),其中结点集V={V1,V2,…,Vn},边集E={e1,e2,…,em}且ek=<Vi,Vj>,Vi,Vj∈V; i=1,2,…,m,当且仅当Vi是Vj的逆K近邻时ek不为零,且邻接矩阵MRKNN(n*n)[ij]不为零。
由定义1及定义2可知逆K近邻图是在K近邻图的基础上将所有弧的起始点和终止点对调得到的,反映在邻接矩阵上有MRKNN(n*n)=MKNN(n*n)T,即逆K近邻的邻接矩阵是K近邻邻接矩阵的转置。
1.2 K近邻团和极大K近邻团
定义3K近邻有向图GKNN=(V,E)的子图G′=(V′,E′),V′⊆V,E′⊆E满足∀Vi,Vj∈V′同时存在ek=<Vi,Vj>和ek=<Vj,Vi>,则点集E′称为K近邻团(K-nearest Clique,KNC)。
例如对图1含有5个点的数据集当k=3时我们可以分别计算出K近邻、逆K近邻及K近邻团:
由定义3可知,G是一个有向完全图,由于K近邻团中任意两个点都互为K近邻,因此K近邻团是图GKNN上的一个等价关系。
定义4 若一个K近邻团满足任何以其作为真子集的集合都不能构成K近邻团,则我们称该K近邻团为极大K近邻团(Max K-nearest Clique,MKNC)。
由定义可知图GKNN中可能存在多个MKNC,这些MKNC有可能彼此相交,也有可能彼此无任何联系,但是每个MKNC中的对象都满足彼此相似的特性,因而可以代表一个具有特定意义的簇。由此可见如何发现数据集中的极大K近邻团成为研究的首要目标。
2 K近邻团聚类算法
以图1所示数据为例,若采用KNN聚类算法则点V1和V5具有最大的相似度(相似度为1),这显然是不正确的;若采用RKNN算法,则点V1、V5各为一类,V2、 V3 、V4为一类,这显然也不是理想的结果,而采用KNC作为聚类标准则能够达到期望的聚类效果。K近邻团聚类算法就是利用极大K近邻团作为聚类的依据,将每个极大K近邻团看做一个类别簇,从而实现根据对象本身特性的自然聚类。该算法主要步骤如图2。
2.1 构造K近邻图
挖掘极大K近邻团首先要构造K近邻图GKNN,其中K近邻的度量可以采用多种方法,例如欧式距离、余弦值或内积[2]。求K近邻可以采用R-tree、SS-tree、SR-tree和Voronoi图等计算方法。算法可将距离的度量作为一个参数,根据数据集自身的特点选择不同的距离公式。本文采用欧几里得距离作为K近邻的度量,并使用了一种基于kd-tree的近邻搜索算法ANN[4]来计算K近邻并构造K近邻图。为了提高计算效率和压缩存储空间,对K近邻图的邻接矩阵还采用了一种基于比特的存储方式[3],该方式对0—1矩阵的压缩比达到32∶1,降低了大型数据集计算的内存消耗。
2.2 构造K近邻团无向图
由于K近邻团是图GKNN上的等价关系,因此用来表示K近邻团的图G′的邻接矩阵是一个对称矩阵。又由定义3可知G′即是图GKNN的子图,所以对于任意的K近邻团邻接矩阵都可以通过对GKNN进行初等变换得到。因此,所有的K近邻团构成的集合也必然是GKNN的子集,且刚好覆盖了GKNN中所有的相反弧对。
通过以上分析可知,所有K近邻团构成的集合可以用GKNN与GRKNN的与操作集GKNC来表示;其中点集E保持不变,若GKNN中存在弧<ei,ej>且GRKNN中也存在弧<ei,ej>,则GKNC中存在弧<ei,ej>。用邻接矩阵MKNC表示为:
即MKNC[i,j]=MKNC[i,j]=
MKNN[i,j]&MRKNN[i,j]=
MKNN[i,j]&MKNNT[i,j]=
MKNN[i,j]&MKNN[j,i]。
因此K近邻团集合构成的图可以用对称的无向图来表示,通过图GKNN与图GRKNN的邻接矩阵进行与操作可得K近邻团无向图的邻接矩阵。同时该操作又可以去除有向图中的单边弧,减少了下一步计算的计算量。
2.3 挖掘极大K近邻团
最后利用图GKNC的邻接矩阵MKNC进行极大K近邻团的挖掘。GKNC的构造方式不但提高了计算效率,而且将对极大K近邻团的挖掘转化为GKNC上极大团的挖掘。极大团的挖掘是一个NP完全问题[6],可以利用分治策略、蚁群算法、并行交叉熵等算法来解决。本文借鉴了文献[7]描述的一种快速挖掘并枚举所有极大团的算法,该算法利用枚举树和矩阵乘法在O[M(n)]的时间延迟内完成极大团的挖掘,其中M(n)为n×n矩阵相乘的时间复杂度。算法描述如图3[7]。
2.4 算法的迭代
通过2.3节的计算,可以得到K近邻无向图中所有的极大团集合S。由于图G的复杂性,所得到的极大团集合往往是含有较多的数据集,导致结果呈现为多种类别并存,这对于聚类来说并不是一个很好的结果。根据之前分析可知,虽然数据集是零碎的,但其内聚性却相当高,也即相同极大团中的对象彼此相似度是非常大的,实验表明同一个极大团中的对象有很高的比率是属于同一个类别的。
基于以上分析,利用算法的迭代,将每个极大团看作一个新的对象重复上述算法直到得到较少的簇集。迭代过程中任意两个极大团Ci和Cj之间的距离做如式(2)定义。
选择适当的k值可以保证算法的收敛性。根据后续实验,通常迭代1—2次即可得到较好结果,从而实现具有一定簇数量的聚类划分。
2.5 算法效率分析
该算法主要包括构造K近邻图、构造K近邻团无向图、挖掘K近邻极大团以及迭代四个步骤,其中迭代算法可以看作是前三个步骤的多次执行。不难得出构造K近邻图及K近邻团无向图的时间复杂度均为O(n2),而理论上极大团挖掘算法作为一个NPC问题的时间复杂度为O(2n),采用文献[7]所述算法可将时间复杂度缩减为O(Δ4),其中Δ为K近邻团无向图的度。因此,整体算法的时间复杂度为O(n2)+O(Δ4)。
3 实验及评价
为了验证算法的有效性,首先我们构造了几种不同簇分布的二维数据集,并利用该算法进行聚类测试,对其性能及效果做出相应分析;然后我们以鸢尾花数据集作为真实数据对算法的分析结果进行验证。
在Matlab中构造了如图2所示的四个数据集对算法进行测试。其中图(a)为两个边界清晰的正态分布向量集;图(b)为两个边界较为模糊的正态分布向量集;图(c)中间为正态分布周围为均匀分布的向量集;图(d)为互相咬合的均匀分布向量集。
我们以数据集(a)为例,取不同的k值对数据进行聚类,得到结果如图5。
从图5可以看出,当k值取值较小时,会形成较多基数较小的极大团集合,从而导致数据集被割裂开来,这并不是我们所希望的,但从另一方面来看,每个极大团所包含的元素应具有较高的相似度,通过合并算法的迭代,最终可以得到基数较大、数量较少的簇构成的聚类结果。
根据以上分析,取k=50对数据集(b)、(c)进行聚类,得到结果如图6。
从图6可以看出,对于边界较为模糊的数据集该算法也具有较好的适应性,即对数据集的核心部分可以有效加以分离,对于具有类别二义性的交叉部分也可以进行有效提取,该部分的划分算法可以采用差集的方式加以提取;对于分布范围较大的数据集可以表示为若干较小的聚类簇,我们可以通过算法的迭代将其表示为一个大的聚类簇。
取k=50,图7为数据集(c)、(d)的二次迭代的划分结果。
4 总结
本文提出了一种基于K近邻团的聚类方法。该算法利用了数据集自身数据之间的关联特性构造出K近邻团矩阵,利用团结构的高内聚性保证每个近邻团内的对象之间具有较高的相似度,进而通过挖掘K近邻团对目标数据集进行聚类。算法最终可以通过迭代实现满足要求的聚类划分。
摘要：在K近邻和逆K近邻理论基础上提出了K近邻团的概念。通过度量对象间的相似度,任意两个元素都互为K近邻和逆K近邻的对象集合构成一个K近邻团。利用同一个K近邻团中的对象彼此都具有较高相似性的特点,选取不同的K值对目标集合进行聚类。通过实验证明了该方法的有效性。
关键词：K近邻,逆K近邻,K近邻团,聚类算法
参考文献
[1]孙吉贵,刘杰,赵连宇.聚类算法研究.软件学报,2008;19(1):48—61
[2]桑应宾,基于K近邻的分类算法研究.重庆:重庆大学硕士学位论文,2009
[3]魏小锐,袁瑞芬,曲超.0—1矩阵的比特存储类.东莞理工学院学报,2010;3:44—47
[4]Arya S,Mount D M,Netanyahu N S,et al.An optimal algorithm for approximate nearest neighbor searching fixed dimensions.ACM,1998;45(6):891—923
[5]Achtert E,Bohm C,Kroger P,et al.Skyline and similarity search:Efficient reverse k-nearest neighbor search in arbitrary metric spaces.ACM SIGMOD International Conference on Management of Data,2006:515—526
[6]Karp R.Reducibility among combinatorial problems.Complexity of Computer Computations1972
[7]Makino K,Uno T.New algorithms for enumerating all maximal cliques.Lecture Notes in Computer Science,2004;3111:260—272
[8]曲超,潘晓衡,朱君,等.基于单词超团的文本聚类方法.计算机工程,2011;37(11):86—88
K-最近邻聚类算法 篇2
聚类的基本任务是为对象集合中所有存在特征相似或接近的对象个体进行类别标记。目前,比较流行的聚类方法有划分法、层次法、密度法、网格法等。在众多的聚类方法中,K-means聚类算法是一种应用广泛的无监督聚类划分方法。K-means聚类算法具有算法简单、时间复杂度低等优点,在数据呈球状分布的领域有着较好的聚类效果。但是,由于K-means聚类算法通过随机的方式来确定初始聚类中心,所以其聚类结果呈现出一定的不稳定性,并容易陷入局部最优解。为了提高K-means聚类稳定性,人们对初始聚类中心进行了各种优化。汪中等[1]提出了通过采用密度敏感的相似性度量来计算对象的密度,以此来启发式地生成样本初始中心的方法。赖玉霞等[2]提出了采取聚类对象分布密度方法来确定初始聚类中心,然后选择相互距离最远的k个处于高密度区域的点作为初始聚类中心的方法。张斌等[3]提出了基于距离估计优化初始聚类中心的K-Means算法。上述三种算法分别从密度分布和距离角度来选择聚类初始中心点,但没有考虑类蔟的规模对聚类结果的影响。曹付元等[4]提出了利用邻域模型中对象邻域耦合度和分离度实现初始聚类中心选择的K-Means算法。Fouad Khan[5]提出了在具有最大对象间隔的特征基础上生成初始聚类中心的K-means算法。上述两种算法直接在对象几何参数上进行选择初始聚类中心,当干扰较大时其聚类效果受影响的概率较大。Juanying Xie等[6]提出了通过全局搜索稳定的对象位置来生成初始聚类中心的K-means算法。该算法在对象规模较大时时间复杂度也较大。Yan Zhu等[7]提出了通过AP算法来生成初始聚类中心的CAK-means算法,该算法在AP生成的所有聚类中心基础上进行K-means聚类,并通过比较最终的聚类效果以选出最佳的初始聚类中心,其聚类效果较好但时间复杂度较高。本文提出了通过近邻传播聚类算法生成若干个初始聚类,然后通过考察初始聚类的规模来确定K-means的初始聚类中心的K-means算法(APK-means)。该算法充分发挥了近邻传播聚类(AP)算法能够快速进行大规模数据聚类的优点,同时规避了其无法确定聚类数量的缺陷,有效提高了聚类的稳定性和有效性。本文第1节分别简述了K-means算法和AP算法,第2节详细介绍了APK-means算法,第3节通过实验验证了APK-means算法的有效性和稳定性。
1 K-means聚类算法和AP算法
1.1 K-means聚类算法
设某对象集对象之间的距离为该对象集的k个类别,k个类别的聚类中心
K-means聚类算法通过迭代计算距离逐渐把对象划分成k个类蔟,使得目标函数最小化。
K-means算法描述如下:
输入:聚类的数目k和包含n个对象的数据集。
输出:满足目标函数值最小的k个类蔟。
step 1:从n个数据对象中任意选择k个对象作为初始聚类中心;
step 2:循环step 3和step 4,直到目标函数E的值在某范围内不再发生变化为止或者迭代次数超过上限;
step 3:计算每个对象与聚类中心的距离,并且根据最小距离重新划分对象到相应的类蔟中;
step 4:重新计算每个类蔟的聚类中心。
1.2 AP算法
AP算法定义了以下几个概念:
(1)相似度
对象间的相似度s(i,j)反映了对象xi,xj之间的相似程度,其定义为1式和2式:
(2)吸引度和吸引度矩阵
对象间的吸引度r(i,j)反映了对象xi以对象xj为聚类中心的可能性,其定义为3式:
吸引度矩阵
(3)归属度和归属度矩阵
对象间的归属度a(i,j)反映了以对象xj为聚类中心的类蔟包含对象xi的可能性,其定义为4式和5式:
吸引度矩阵
AP算法描述如下:
输入:n个对象的数据集。
输出:若干个类蔟。
step 1:计算数据集的相似度矩阵;
step 2:计算吸引度矩阵和归属度矩阵,其中a(i,j)=0;
step 3:循环step 4,直到类蔟不再发生变化或者迭代次数超过上限;
step 4:根据式6、7更新吸引度矩阵和归属度矩阵:
step 5:由式8得到以对象xj为聚类中心的类蔟包含对象xi的聚类结果。
2 APK-means聚类算法
若K-means聚类算法所选择的初始聚类中心远离实际的聚类中心,或者是偏远的噪声干扰点等,则聚类的结果会呈现出不确定的现象,从而不能保证较高质量的聚类效果。因此,通过提高初始聚类中心的选取质量来优化K-means算法的聚类效果是可行的方法之一。
2.1 APK-means聚类思想
AP算法在对象间相似度的基础上定义了吸引度和归属度概念,通过迭代不断更新吸引度和归属度矩阵,逐渐将对象集中相似的对象划分到相同的类蔟中,以最终形成若干个类蔟并获得每个类蔟的聚类中心。本文提出在AP算法聚类结果基础上进行K-means聚类的思想。该思想以AP算法聚类生成的类蔟中心为K-means算法的初始聚类中心,充分利用AP算法快速、稳定的聚类效果,有效提高了K-means算法的初始聚类中心的质量。但是,AP算法的聚类数目受每个对象自身成为聚类中心可能性大小(该值称为偏置参数p,一般采用3式估计其值)的影响,且两者之间的映射关系是不明确的。因此AP算法在进行聚类前无法获知最终的聚类数目。而K-means聚类算法是在已知聚类数目的前提下进行聚类。当AP算法聚类生成的类蔟数目等于K-means算法要求的聚类数目时,直接以AP算法聚类结果为当前聚类结果。当AP算法聚类生成的类蔟数目小于K-means算法要求的聚类数目时,通过调整偏置参数p来增加类蔟数目,使其大于K-means算法要求的聚类数目。
当AP算法聚类生成的类蔟数目大于K-means算法要求的聚类数目时,本文提出选择类蔟中规模较大的类蔟的聚类中心作为K-means算法的初始聚类中心。K-means算法在聚类过程中,规模大的类蔟会不断和规模小的类蔟进行合并,直到完成指定的k个聚类。APK-means聚类从以下两个方面优化了K-means聚类效果:
(1)规模较大的类蔟聚类分布对对象集总体聚类分布的影响意义比规模较小的类蔟相对大些,所以规模较大的类蔟的聚类中心在距离上比随机选择的聚类中心更加接近全局最优类蔟分布的聚类中心,使得APK-means算法的聚类效果会比普通K-means算法好。
(2)由于对象间的相似度在AP算法聚类时是不会变动的,所以AP算法聚类生成的类蔟聚类分布是固定的,使得K-means算法最终的聚类结果会保持稳定。
APK-means算法建立对象相似度、吸引度和归属度共三个规模为N*N的矩阵,其时间复杂度为O(AP)+O(K-means),其空间和时间代价大于一次K-means算法的代价。但是APK-means算法只需运行一次即可获得较好的聚类效果。而K-means算法往往需要运行多次才能获取较好的聚类效果。
2.2 APK-means聚类算法
APK-means算法描述如下:
输入:聚类的数目k和包含n个对象的数据集。
输出:满足目标函数值最小的k个类蔟。
step1:运行AP算法
step2:如果AP算法生成的类蔟数等于k,返回;
step3:如果AP算法生成的类蔟数小于k,偏置参数p增加0.01p,跳转至step 2;
step4:计算所有AP算法生成的聚类类蔟的规模(既类蔟中所包含的对象数量);
step5:选取前k个规模最大类蔟的中心为初始聚类中心;
step6:运行K-means聚类算法;
3 实验结果
3.1 聚类效果指标
本文采用聚类密集性指标对K-means算法和APK-means算法的聚类效果进行评估。聚类密集性指标通过测量聚类内的方差来反映聚类数据同一性的程度,其值越小表明同一性越高,即聚类密集性效果越好。聚类密集性指标定义如下:
设对象集其方差其中为对象之间的距离,为对象集X的均值。设对象集X的k个聚类类蔟为则X的密集性指标为
3.2 仿真数据实验
仿真数据实验采用随机生成的100个分为3类的数据对象集合,分别采用K-means算法和APK-means算法进行聚类。表1所示的是运行5次K-means算法和5次APK-means算法的的聚类密集性指标值。
表2所示的是上述5次K-means算法和5次APK-means算法聚类类蔟的聚类中心坐标。
图(1)和图(2)分别是运行5次K-means算法和1次APK-means算法的聚类效果图,图中使用符号“*”、“+”和“^”分别对三个类蔟中的对象进行标记。
图2(a)中三个红色“+”大符号标记了APK-means生成的三个聚类中心。
该仿真实验结果显示K-means算法聚类结果受到了随机选取的聚类中心的影响,而APK-means算法的5次聚类结果都相同,这表明APK-means算法具有更好的聚类稳定性。K-means算法5次聚类结果的密集性指标普遍低于APK-means算法,表明APK-means算法具有更有更好的聚类有效性。
3.3 UCI数据实验
本文采用UCI数据库中的Iris数据集。该数据集包含150个具有4个属性值的对象,共分为3类。由于该数据集已经提供了分类标签,且按照同分类同组的方式顺序编排,所以聚类效果可以通过计算对象正确分类的正确率进行评估。其实验算法描述如下:
step 1:使用聚类算法进行聚类;
step 2:根据数据集的分类标签统计聚类结果中每个对象所属分类一致的数量;
step 3:将分类一致的对象总数除以数据集中对象的总数,得到聚类正确率。
表3所示的是运行5次K-means算法和5次APK-means算法的的聚类密集性指标值。
该实验结果同样表明APK-means算法比K-means算法具有更好的聚类有效性和稳定性。
4 结束语
本文基于K-means聚类算法和AP算法提出了一种APK-means聚类算法。该算法首先由AP算法生成若干类蔟,当类蔟数量小于聚类数k时,通过调整偏置参数p来提高聚类数k;当类蔟数量大于聚类数k时,以此按类蔟规模大小降序选择其对应的聚类中心为K-means聚类算法的初始聚类中心点,接着进行K-means聚类。APK-means聚类算法充分利用了AP算法能够快速稳定生成类蔟的优点,同时也避免了对所有类蔟聚类中心进行全局搜索,优化了K-means聚类算法的聚类稳定性和有效性,获得了较好的聚类效果。但是APK-means算法的空间复杂度和时间复杂度比K-means聚类算法有了一定的上升,在对象集规模较大时其计算代价较大。
摘要：K-means聚类算法在随机选择的初始聚类中心的基础上进行聚类,其聚类效果会因为初始聚类中心的不确定性而不稳定。为了优化其聚类效果,提出了基于近邻传播算法(AP算法)的K-means聚类优化算法(APK-means)。该算法首先通过近邻传播算法生成若干个初始聚类,然后依序选择k个聚类规模最大的聚类中心作为K-means聚类算法的初始聚类中心,接着运行K-means聚类。算法有效性分析和实验结果验证了该算法有效优化了K-mean算法的聚类稳定性和有效性。
基于最近邻思想的K-均值算法 篇3
数据聚类是数据挖掘的一个非常活跃的研究方向。聚类在文献[1]中定义为:将数据对象进行分组, 成为多个类或簇。在聚类过程中无须用户提供先验的分类知识, 而是根据数据实际的分布情况得到自然的聚集结果。当前主要的聚类算法可以划分为如下几类:
1) 基于划分的方法, 如k-means (K-均值) 文献[2], k-medoids (K-中心点) 文献[3];
2) 基于层次的方法, 如BIRCH文献[4], C U R E文献[5], R O C K文献[6], Chameleon文献[7];
3) 基于密度的方法, 如D B S C A N文献[8];
4) 基于网格的方法, 如S T I N G;
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<n/k) 个数据对象参与计算平均值。如果某个簇中对象个数不足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个对象作为计算平均值 (下一次聚类中心) 的对象。而不是计算簇中所有对象的平均值作为下一次聚类的中心。这样就需要在计算平均值之前进行一次排序。排序的时间复杂度为k m 2 (其中k为簇的个数, m为最大簇中对象的个数) 。因此改进后的K均值算法的时间复杂度为k (m 2+n) t (其中k为簇的数目, m为最大簇中对象的个数, n为全体数对象个数, t为迭代次数。影响m值的因素很多, 如果则改进后的K均值算法与传统的K_均值算法时间复杂性相同, 但通常m 2>n所以改进后的K平均算法要比传统的K_均值算法时间复杂度要高。
4 实验
我们将本算法应用到学生成绩信息分析中, 学生成绩信息分析的目的是研究学生成绩的分布情况, 找出异常信息, 为教务部门进行教学督查提供决策信息。
1) 实验环境
计算机配置:C P U A t h l o n 6 43 0 0 0+, 1 G H z内存, 1 6 0 G B硬盘
操作系统:Microsoft Windows XP
开发平台:Microsoft Visual Studio2005
开发语言:C#
数据库:Microsoft SQL Server 2005
2) 数据集
近两年来收集的学生公修课学生成绩信息, 数据中含学生学号、姓名、高等数学成绩、大学英语成绩。
实验比较了改进后的K-均值算法与传统K-均值算法。实验前首先将指定数据全部读入内存, 并完成相应的预处理工作。
3) 实验结果分析
通过实验表明改进后的K-均值算法和传统的K-均值算法用时基本相当, 并没有显著增加用时, 但聚类效果却明显改善。
5 结束语
在本文中, 我们提出了一种基于最近邻思想的K-均值算法, 该算法在计算聚类中心点时, 采用了一种最近邻思想有效克服了‘噪声’对平均值的影响, 从而使聚类结果更加合理, 并通过实际数据的实验验证明这种算法是有效的。如何将该算法应用到更多的实际数据的聚类是下一步的研究。
摘要：K-均值聚类算法是一种基于划分方法的聚类算法, 本文通过对传统的K-均值聚类算法的分析, 提出了一种改进的K-均值算法, 并对该算法的时间复杂度和空间复杂度进行了分析。该算法在计算聚类中心点时采用了一种最近邻的思想, 可以有效地去除“噪声”和“孤立点”对簇中平均值 (聚类中心) 的影响, 从而使聚类结果更加合理。最后通过实验表明该算法的有效性和正确性。
关键词：数据挖掘,聚类,K-均值
参考文献
[1]Jiawei Han, Micheline Kamber著;范明, 孟小峰, 等译.数据挖掘概念与技术.机械工业出版社
[2]J.MacQueen.Some methods for classificationand analysis of multivariate observations.Journal of the American Statistical Association, 83:715----728, 1967
[3]L.Kaufman and P.J.Rousseeuw.FindingGroups in Data:An Introduction to ClusterAnalysis.New York:John Wiley&Sons, 1990
[4]T.Zhang, R.Ramakrishnan, and M.Livny.BIRCH:An efficient data clustering method forvery large databases.In Proc.1996 ACM-SIGMOD Int.Conf.Management of data (SIGMOD’96) , oages 103----114, Mibtreak, Cabada, June 1996
[5]S.Guha, R.Rastogi, and K.Shim.Cure:Anefficient clustering algorithm for largedatabases.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:AnRobust clustering algorithm for categoricalattributes.In Proc.1999 Int.Conf.DataEngineering (ICDE’99) , page512—521, Stdebet, Australia, Mar.1999
[7]G..Karypis, E.-H.Han, and V.Ku-mar.CHANELEON:A hierarchical clustering algorithmusing dynamic modeling.COMPUTER, 32:68—75, 1999
K-最近邻聚类算法 篇4
层次聚类是基于分层思想的聚类算法, 他的优点是可以在不同维度水平上对数据进行探测, 容易实现相似度量或距离度量。但单纯的层次聚类算法终止条件含糊, 且执行合并或分裂的操作后不可修正, 容易导致聚类结果质量下降。通常, 层次聚类算法一般与其他方法相结合来解决实际的聚类问题。目前主要的层次聚类算法有BIRCH算法、CURE算法、ROCK算法等。[1]算法利用层次方法进行平衡迭代归约和聚类。它引入了聚类特征 (CF) 和聚类特征树 (CF树) , 用于概括聚类描述, 提高了聚类算法对于大型数据库的高效性和可扩展性。
该算法首先将数据对象划分成树形结构, 然后采用其他算法对聚类结果求精。聚类特征是一个三元组, 它给出了一个子簇的信息的汇总描述。假设某个子簇中有n个d维的点或对象Xi (i=1, 2, …, n) , 则该子簇的聚类特征CF定义如下:
CF= (n, LS, SS)
式中:n——子簇中点的数目;LS——n个点的线性和;SS——n个数据点的平方和。LS反映簇的质心位置, SS反映簇的大小, 即凝聚程度。
CF树是一种高度平衡的树, 它存储了层次聚类的聚类特征。包含两个参数:分支因子B和阀值T。分支因子B定义了每个非叶子节点孩子的最大数目, 而阀值参数T决定了CF树的规模。
BIRCH算法一般包括两个阶段: (1) 扫描数据库, 建立一个初始存放于内存的CF树, 它可以被看作数据的多层压缩, 试图保留数据内在的聚类结果; (2) 采用任意的聚类算法对CF树的叶子节点进行聚类。当插入新数据对象时, CF树可以动态构造, CF树的重建类似于B+树构建中的节点插入和分裂, 因此BIRCH支持增量聚类。由于CF树的每个节点的大小的限制, 可能导致节点并不总是对应于用户所认为的一个自然簇, 而且, 如果簇不是球形的, BIRCH算法不能很好地工作, 因为它采用了直径的概念来控制聚类的边界。
1.2 CURE算法
CURE采用了一种新颖的自底向上的层次聚类算法, 它把层次算法和划分算法结合在一起解决了偏好球形和相似大小的问题, 在处理孤立点上也更加健壮。该算法在计算簇间的距离时, 采用了基于质心和基于代表对象之间的中间策略。它不用单个质心或对象来代表一个簇, 而是选择数据空间中固定数目的具有代表性的点。它从一个簇中选择一定数目散布很好的点来代表该簇, 这些点用于确定该簇的形状和大小。然后根据一个特定的分数或收缩因子向簇中心“收缩”或移动它们。在算法的每一步, 有最近距离的代表点的两个簇合并, 重复合并过程, 直至得到期望的聚类数目。
CURE算法克服了利用单个代表点或基于质心的方法的缺陷, 可以发现非球形及大小差异较大的簇。簇或离散点的收缩降低了CURE算法对孤立点的敏感性。
1.3 ROCK算法
ROCK算法[2]是在CURE算法的基础之上提出的, 它适用于枚举数据的凝聚的层次聚类算法。通过把两个簇的聚集的互连性与用户定义的静态互连性模型相比较, 从而度量两个簇之间的相似度。其中, 两个簇的互连性是指两个簇之间的交叉的数目, 而连接是指两点之间的共同邻居数, 也就是簇间相似度是用不同簇中共同邻居的点的数目来确定的。
其它有代表性的层次聚类算法还有Chameleon算法, 李侃等[3]提出的基于SVM的空间数据库的层次聚类分析, 淦文燕等[4,5]学者提出的基于核密度的层次聚类算法和基于数据场的层次聚类方法, 沈洁等学者提出的基于划分的层次聚类算法等。
2 基于区域最近邻生长的层次聚类算法
本文在分析现有层次聚类算法的基础上, 采用递归四等划分的方式对数据集进行划分, 根据区域 (叶子节点) 的最近邻距离将叶子节点进行合并, 提出了基于区域最近邻生长的层次聚类算法。
2.1 数据集的划分与初始叶子节点的生成
本节采用递归的方式对数据集进行划分。设数据集
数据集进行划分后, 遍历数据集, 将数据集中的点划分到相对应的数据区域中, 形成初始的聚类数据区域。划分形成的数据区域的个数因数据集的规模和数据集的维度的不同而不同。数据集的划分是本文提出算法的第一步, 数据集的划分不当, 聚类结果很难保证。在分析大量数据集的基础上, 在实验经验和查阅其它的数据集划分的情况下, 本算法中采取如下约定, 每个数据区域中的平均点数小于等于10, 即:
式 (1) 是一个经验公式, 划分的区域数越多, 聚类的结果越精确, 但划分的区域的个数越多, 算法花费的时间越多。
对数据集进行划分后, 统计每个数据区域中的点数, 去除点数为零的数据区域, 并计算每个数据区域的质心, 计算公式如下 (其中k为数据区域中数据的点数) :
经过计算, 生成了具有质心和数据点数的初始聚类区域, 即初始叶子节点。
2.2 相关定义
定义1:叶子节点。根据划分规则和后面的合并规则, 定义叶子节点为:
L= (Pi, Num) (1≤i≤m) (3)
式中:Pi——初始划分后形成的数据区域的中心, 每个叶子节点均有一个初始中心。随着叶子节点的合并, i值不断增加;Num——叶子节点及其子节点一共包含的数据点数目。
定义2:叶子节点间距离。设L1为包括六个数据点的叶子节点, 其质心为P1, L2为包括五个数据点的叶子节点, 其质心为P2。定义叶子节点L1、L2之间的距离d (L1, L2) 为质心P1和P2之间的距离, 如图2所示。若叶子节点包含子节点, 则依次计算每个子节点之间的距离, 两个叶子节点的所有子节点之间的最小距离为叶子节点之间的距离。
定义3:叶子节点的最近邻距离。设Ln (n=0, 1, …, k) 为所有叶子节点的总和, 则叶子节点Li的最近邻距离为:
dmin (Li, Lj) =min d (Li, Lj) (1<j≠i<k) (4)
如图2所示, 叶子节点L1的最近邻距离为L1与L2之间的距离d (L1, L2) 。
定义4:叶子节点的最近邻节点。与叶子节点具有最近邻距离的节点定义为叶子节点的最近邻节点, 如图2所示, 叶子节点L2为叶子节点L1的最近邻节点。
定义5:生长节点。初始形成的叶子节点, 每一个都具有寻找其最近邻叶子节点的权利, 具有较小的最近邻距离的节点定义为生长节点。
定义6:生长节点的最近邻节点。与生长节点的所有子节点具有最小的最近邻距离的节点定义为生长节点的最近邻节点。
2.3 生长节点的生长
叶子节点按照定义1、定义5寻找自己的最近邻节点, 具有最小的最近邻距离的节点即生长节点与其对应的最近邻节点进行合并, 被合并的叶子节点的数据点并入生长节点内, 同时该叶子节点的质心变为生长节点的子质心, 从而完成一次生长节点的生长。计算所有叶子节点及其子节点的最近邻距离并根据最近邻距离的大小选出新的生长节点, 进入新一轮的生长过程。
图3演示了具有一个类别的簇的生长过程。为简单起见, 图中的每一个大的黑点表示被划分成的叶子节点, 空心的圈点表示生长节点。通过该生长过程我们可以看出, 具有最近邻距离的叶子节点被定义为生长节点, 在图中用空心圈表示, 该生长节点与自己的最近邻节点合并, 被合并的节点仍保持其质心, 且具有寻找自己最近邻节点的权利, 但在归属上属于合并他的叶子节点。
3 实 验
3.1 步 骤
输入:聚类数目K, 包含N个数据样本的数据集;输出:K个子集及聚类后生成图像;
Step1:根据数据集规模和划分方法确定数据集的划分个数;
Step2:生成初始的叶子节点;
Step3:计算叶子节点的最近邻距离, 并找出生长节点的最近邻节点;
Step4:将生长节点的最近邻节点合并, 生成新的叶子节点;
Step5:检查叶子节点的数目是否等于聚类数目K, 若是, 转向Step6, 反之, 返回Step3, 继续进行;
Step6:算法结束, 输出结果。
3.2 验 证
为了验证新算法的有效性, 采用如下四组数据集对算法进行验证。仿真平台采用VC++6.0, 代码由C语言编码实现 (图中不同灰度图案图形表示不同的类别) 。
数据集1:包括二维平面内45 000个数据点, 由三个直径大小不一的圆和两个大小不一的椭圆构成, 二维平面内点的坐标表示数据点的特征, 如图4所示 (该图像宽度为400, 高度为300) 。
数据集2:包括二维平面内40 000个数据点, 由四个大小不同的矩形和两个U形构成。二维平面内点的坐标表示数据点的特征, 如图5所示 (该图像宽度为430, 高度为300) 。
数据集3:包括二维平面内41 000个数据点, 由空心椭圆形、矩形、椭圆形和被截断的椭圆形等特殊形状构成。二维平面内点的坐标表示数据点的特征, 如图6所示 (该图像宽度为300, 高度为300) 。
数据集4:包括二维平面内30 000个数据点, 由大写字母BSOL一个圆形、一个椭圆、一个矩形和一个圆角矩形构成。二维平面内点的坐标表示数据点的特征, 如图7所示 (该图像宽度为420, 高度为240) 。
4 小 结
通过数据集1～4的聚类结果我们可以看出, 对于球形和其它特殊形状的数据集, 在没有孤立点影响的情况下本文提出的算法均取得了理想的效果, 证明了算法对于球形和其它特殊形状数据集的适用性。在对如上四个数据集的划分上, 遵循了前面的经验公式, 取得了理想的效果。
本文提出了基于区域最近邻生长的层次聚类算法, 在理想数据集下, 通过数据集划分方式的描述, 初始叶子节点的生成, 合并规则的定义, 对算法进行了全面的介绍。最后通过实验的方式对算法进行了验证, 通过不同规模、不同形状数据集对算法的测试, 表明了算法对于球形和其它特殊形状的密度分布均匀的数据集的适用性。算法采用对数据集进行划分的方式, 将大量的数据集划分成独立的不重合的区域, 节省了算法的运行时间。但针对有大量孤立点存在的情况, 需要进一步分析。
摘要：对于非球形和其它特殊形状的非凸数据集的聚类, 基于划分的聚类算法很难取得理想的聚类结果。层次聚类算法根据数据的特征将距离近的数据进行合并, 对于球形数据集和其它具有特殊形状的数据集有很好的聚类效果。在分析现有层次聚类算法的基础上, 根据层次聚类的合并思想和最近邻距离的计算提出了基于区域最近邻生长的层次聚类算法。
关键词：聚类算法,层次聚类算法,区域最近邻生长
参考文献
[1]李修亮, 苏宏业, 褚健.基于在线聚类和关联向量机的多模型软测量建模[J].化工自动化及仪表, 2008, 35 (3) :11-13.
[2]GEORGE K, HAN E H, KUMAR V.CHAMELEON:A Hierar-chical Clustering Algorithm Using Dynamic Modeling[J].IEEEComputer, 1999, 27 (3) :329-341.
[3]李侃, 高春晓, 刘玉树.基于SVM的空间数据库的层次聚类分析[J].北京理工大学学报, 2002, 22 (4) :485-488.
[4]淦文燕, 李德毅.基于核密度估计的层次聚类算法[J].系统仿真学报, 2004, 16 (2) :320-309.
【K-最近邻聚类算法】推荐阅读：
K近邻算法06-07
改进K近邻算法06-24
K近邻方法06-23
K近邻团11-03
动态K-均值聚类算法09-03
k-mean聚类算法论文10-03
最近邻查询11-06
K-匿名算法07-07
聚类算法11-06
近邻传播07-23