史彦丽,金 欢

(1.吉林化工学院 理学院,吉林 吉林 132022；2.吉林化工学院 信息与控制工程学院,吉林 吉林 132022)

聚类属于无监督学习算法,依据某个或者多个相似度准则,使处于同一类的数据具有更高相似性,处于不同类的数据具有更大的差异性.聚类算法在大数据[1]、数据挖掘[2]、社交网络[3]、离群值检测[4]、计算机视觉[5]、模式识别[6]、图像处理[7-8]以及生物信息学[9]等领域应用广泛.近年来，学者们提出了大量聚类算法.均值漂移[10](Meanshift)算法作为一种爬山算法,算法核心为顺着密度增加的方向找到聚簇点.DBSCAN[11]算法是一种基于密度的聚类算法,善于处理多种形状分布的数据集.AP[12]聚类算法的核心思想是将所有的目标数据作为潜在聚类中心,通过计算所有数据点之间的相似度关系来构建矩阵,进而获得各样本的聚类中心.

K-means聚类算法是一种基于划分的聚类算法,通过设置初始中心点和类簇个数k,反复迭代寻优,直到迭代结果不发生改变,确定最终聚类中心点,算法结束.但算法未能考虑数据点的密度分布,对非凸形分布的数据集聚类效果差.另外,K-means聚类算法的k值选取需先验知识,如何选取最优k值成为K-means聚类算法的重难点.与K-means聚类算法不同,进化聚类算法[13]不仅可以反映当前时刻各数据特征之间的关系,还能为后期即将输入的新数据做好聚类准备.当输入新数据时,该点将分配给距离相似度最大的类或以该点为中心自建新类,可以观察每个数据对最终聚类结果所产生的影响,通过反复迭代更新,中心点和类簇数目将自适应选取.

基于上述分析,本文提出基于进化思想的类簇融合聚类算法及其类簇融合算法(Clustering lgorithm based on evolutionary thought and its cluster fusion algorithm,EF-means).针对K-means聚类算法k值选取需要先验知识的问题,EF-means聚类算法将K-means聚类算法与进化聚类算法进行合并,通过设定距离倍参α,逐渐将数据划分,在此过程中自动确定类簇数目k.

针对K-means聚类算法处理非凸形分布的数据集时聚类效果差,提出基于最近距离的中间圆密度簇融合算法与基于代表类的中间圆密度簇融合算法两种类簇融合算法,可大幅降低聚类算法在k值选取上的复杂度及时间成本,通过度量类簇体间的密度相似度及类簇间部分点集的密度相似度,将相似度大的类簇进行融合,可处理凹形分布的数据集,并使k值逐渐减小,直到类簇融合过程结束,达到合理的聚类结果.

1 预备知识

1.1 K-means聚类算法

K-means算法对数据集聚类前,需先设定类簇数目k及对应的初始聚类中心点,接着以欧式距离为相似度准则,将剩余数据点划分到相似度大的中心点所代表的类簇中,形成k个类簇.然后,更新各类簇中心坐标,并重新将数据划分给新的聚类中心点.最后,迭代以上过程,当连续两次的聚类结果不发生改变,则所有数据完成划分,聚类完成.

对于给定数据集ZN×M=[z1,z2,…,zN]T,其中zi=[zi1,zi2,…,ziM],N为样本数,M为样本维数,K-means聚类算法将数据集ZN×M划分为k个类簇S=[s1,s2,…,sk],对应的类簇中心点为O=[o1,o2,…,ok].计算各类簇内的点与中心点的距离平方和为

(1)

其中,si表示第i个类簇；k为类簇数目；oi表示第i个类簇的质心；z表示Si中的样本点.最终目标是使各类簇内的点与中心点的距离平方和L(S)最小,聚类结束.

1.2 K-means聚类算法缺陷分析

K-means聚类算法也存在缺陷,综合多方面分析,表现为以下3方面：

(1)k值及初始聚类中心点的选取需凭借先验知识.聚类前,K-means聚类算法需设定参数k，对拥有庞大数据量或维度高的数据集需要反复尝试调整参数k,时间成本高,且聚类结果不理想.对于同一数据集,K-means聚类算法选取不同的k值所对应聚类结果的可视化，如图1所示.

(2)若各类簇的体积差异大且类簇间距离近,则聚类效果不佳.K-means聚类算法仅用欧式距离作为相似度,当各类簇的样本点数分配不均匀导致各类簇的体积差异大时,聚类效果不理想.对于Aggregation数据集,使用K-means聚类算法聚类的可视化结果如图2所示.

(3)对非凸形分布的数据集聚类效果差.K-means聚类算法处理非凸形分布的数据集时,没有考虑到各数据之间的密度相似度和余弦相似度等相似性,各数据的相似性和差异性无法合理度量,使聚类结果不理想.使用K-means聚类算法对Twomoon数据集聚类的可视化结果如图3所示.

为解决上述问题,近些年学者们对K-means聚类算法进行了改进.Arthur[14]提出了K-means++聚类算法,在K-means聚类算法的基础上使初始中心点的距离尽可能的远,聚类中心点将更准确,但k值选取仍需人为确定.Memarsadeghi[15]提出了ISODATA聚类算法,对于聚类结果中的每一个类簇,当类簇内的样本数过少或者两类簇间的距离相似度大时进行合并,当类簇内的数据点过于离散时,则将该类簇分裂为多个类簇,通过反复迭代,k值逐步被确定,但算法需要调整的参数多,参数选取难度大,且各参数相互影响.Fahim[16]提出了NOK-means聚类算法,NOK-means聚类算法将DBSCAN聚类算法与K-means聚类算法合并,利用DBSCAN聚类算法确定类簇的数目并计算各类簇的中心点,从而确定K-means聚类算法的参数,使得类簇数k以及聚类中心点自适应选取,但NOK-means聚类算法无法对非凸形分布的数据集正确聚类.Sinaga[17]等人提出了U-K-means聚类算法,相比于K-means聚类算法,U-K-means聚类算法不需要任何初始化和参数选择仍可自动确定最优类簇的数量,但算法仍无法精准处理非凸形分布的数据集.

2 EF-means算法

针对K-means聚类算法的k值选取需要靠先验知识,以及K-means聚类算法处理非凸形分布的数据集时聚类效果较差,本文提出基于进化思想的聚类算法及其类簇融合算法.EF-means算法将K-means聚类算法与进化聚类框架进行合并,可将数据划分为多个体积小的凸形分布的类簇,此时类簇数k自适应选取,但实际类簇数目大于真实类簇数目.提出基于最近距离的中间圆密度簇融合算法,算法寻求距离相似度最大的类簇,将凸形分布、体积小且密度相似度大的类簇融合为一个类簇.k值逐渐接近真实值,但该类簇融合算法无法融合相似度大且形状为非凸形分布的类簇.为解决此问题,本文提出基于代表类的中间圆密度簇融合算法,算法将各个类簇内的一部分数据作为代表类,用各自代表类代替原始类簇判断类簇之间融合,可将非凸形分布的且密度相似度大的类簇融合,k值将逐渐减小,直到类簇融合过程结束,聚类完成.

2.1 基于进化聚类的K-means聚类算法

将K-means聚类算法与进化聚类框架合并,类簇数目k将自适应确定,可大幅降低聚类算法在k值选取上的复杂度及时间成本.对于数据集ZN×M=[z1,z2,…,zN]T,其中zi=[zi1,zi2,…,ziM],N为样本数,M为样本维数.首先,将ZN×M中任意两个数据点z1与z2设为初始聚类中心点.当新数据点zi输入时,计算zi与聚类中心点的欧氏距离,并求得所有聚类中心点之间距离的均值,公式如下：

(2)

(3)

nj=nj+1,

(4)

(5)

k=k+1,

(6)

uk=zk,

(7)

其中,α为待调参数(距离倍数参数),nj代表第j个类的数据点的个数,ej=zt-ui.

如图4所示,因算法采用欧氏距离来度量各数据点及类簇之间的相似度,聚类结果均为凸形分布的类簇,实际类簇数大于真实类簇数,各类簇间存在重叠冗余特征.

2.2 类簇融合算法

在使用基于进化聚类的K-means聚类算法进行聚类过程中,各类簇之间存在间隙,随着数据样本点的逐步加入,各类簇之间的间隙将被逐渐填充,使原本空间上不相交的两个类簇紧密相交,增加了各类簇间的相似性,为此，本文提出两种类簇融合算法.类簇的融合算法可以很好地解决各类簇之间关系,设定对应相似度来量化类簇间关系,将相似度大的类簇进行融合,可以消除类簇间重叠和冗余的信息,使实际类簇数目逐渐趋近真实值,得到更加精准的聚类结果.

2.2.1 基于最近距离的中间圆密度簇融合算法

使用基于进化思想的K-means聚类算法进行聚类后,实际类簇数大于真实类簇数.为解决此问题,提出基于最近距离的中间圆密度簇融合算法,算法具体流程如下.

上述聚类中心点为OK×M=[o1,o2,…,oK]T,其中oi=[oi1,oi2,…,oiM],K为类簇数,M为样本维度.首先,计算所有簇与簇之间中心点的欧氏距离x(oi，oj),找到中心点相距最近的两个类的中心点oi和oj,计算公式如下：

(8)

然后,设上述中心点oi与oj为圆A与圆B的圆心,两圆半径分别用rA与rB表示,oi与oj连线中点为中间圆圆心,r表示中间圆半径,且满足下式：

(9)

最后,比较中间圆中A类点和B类点的总数m(A,B)、圆A中点的数量mA与圆B中点的数量mB三者的大小,若m(A,B)>mA或m(A,B)>mB,则将A类与B类融合,并更新相应参数,公式如下：

ni=ni+nj,

(10)

(11)

否则不融合.不难看出m(A,B)可反映类簇A和类簇B的密度相似度,通过与类簇A、类簇B的点密度对比来判断融合,可将密度相似度大的类簇合理合并,消除类簇间重叠和冗余信息,达到准确聚类目的.

如图5所示,在K-means聚类算法基础上使用基于最近距离的中间圆密度簇融合算法的可视化结果,最终得到的结果为多个凹形分布的类簇,此时各类簇中心点之间的中点均分布于凹形类簇外,此时中间圆内无数据点分布,中间圆的点密度无法正确量化两个凹形类簇的相似性.

2.2.2 基于代表类的中间圆密度簇融合算法

凹形类簇之间的中间圆内无数据点分布,因此中间圆的点密度无法正确量化两个凹形类簇的相似性.为此,本文提出基于代表类的中间圆密度簇融合算法,该算法将各类簇之间相似度最大的l组点作为代表类,并将代表类代替原始类簇进行类簇融合分析.具体过程如下：

对于聚类中心点集合OK×M,首先计算簇与簇之间所有点之间的相互距离,选取最近的2l个点作为代表点,这些点组成的类称为代表类,以2个代表类的中心点，及其连线中点o(k1,k2),这3点分别为圆心,调整半径参数,计算3个圆内点的密度.计算如下：

(12)

(13)

其中vi是第i个代表点；o(k1,k2)k为代表类的中心点；ρki代表第i个圆的点密度；nki表示该类数据点在该圆内的个数.比较ρk1、ρk2与ρk3的大小.如果ρk3>ρk1或ρk3>ρk2,则合并聚类,更新相应参数；否则不合并.重复以上,直到结果不发生改变,算法结束.

如图6所示,在基于最近距离中间圆密度簇融合算法的基础上使用基于代表类的中间圆密度簇融合算法的可视化结果.相似度大的非球形类簇发生了融合,得到类簇数为真实值,聚类完成.

2.3 算法步骤

输入：数据集data,距离倍参α,密度倍参ρk.

输出：聚类结果C.

step 1：将数据集中任意两个数据点作为初始中心点.

step 2：当有新数据点zi加入时,根据式(2)计算与其最近的聚类中心点的距离rt.

step 4：重复step 2和step 3,直到无新的数据点加入时,执行step 5.

step 5：根据公式(8)找出相距最近的两个类簇,根据公式(9)设定各圆的半径,比较3个圆内点的个数m(A，B),mA,mB,若m(A，B)>mA或m(A，B)>mB,则将两类融合,并根据公式(10)、(11)更新相应参数.

step 6：重复step 5,直到m(A，B)

step 7：若ρk3>ρk1或ρk3>ρk2,则合并相应的两个类簇,并根据公式(10)、(11)更新相应参数,并重复上述步骤,直到ρk3<ρk1且ρk3<ρk2时,聚类算法结束.

3 实验结果与分析

实验使用合成数据集对EF-Means算法进行测试与评估.将EF-means聚类算法与DBSCAN[11]、OPTICS[18]、AP[19]与K-mean等聚类算法进行比较.其中K-means、DBSCAN、OPTICS和AP均参照文献[20]的实验结果.

3.1 评价指标

本实验使用3个常用的聚类评价指标评估最终聚类结果,分别为：AMI、ARI、FMI.以上3个指标的值上界均为1,且当值为1时,聚类结果最优.

对于数据集,假设有U和V两种不同的标签,其中U和V分别代表数据集的真实类别和聚类结果,则调整互信息AMI(U,V)的值为

(14)

其中：

H(U)与H(V)为对应的香农熵；MI(U,V)为U与V的互信息；E{MI(U,V)}为MI(U,V)的期望值.

调整兰德系数ARI定义为

(15)

Fowlkes-Mallows指数为

(16)

其中：TP表示数据样本对的真实类别和聚类结果一致；TN表示数据样本对的真实类别和聚类结果均不一致；FP表示数据样本对的聚类结果一致,但真实类别不一致；FN表示数据样本对的真实类别一致,但是聚类结果不一致.

3.2 数据集

实验用到的合成数据集共6个,各项参数如表1所示.

表1 合成数据集

为保证算法有效性验证的客观性,选取不同类型数据集进行测试说明.其中Aggregation数据集由7个样本点数分配不均匀的类簇组成,且各类簇的体积差异较大；Flame数据集由1个球形分布的类簇和1个非球形分布的类簇组成,且两个类簇相距较近；Jain数据集由2个非凸形分布的类簇组成,且各类簇内的样本点分布不均匀；Pathbased数据集由1个环形类簇和2个球形类簇组成,且球形类簇被环形类簇包围；Spiral数据集由两个相互环绕的环形类簇组成；D31数据集由31个球形类簇构成，数据集的类簇数目多，且各类簇间的距离较近.

3.3 算法参数选择

3.4 合成数据集实验结果分析

表2为5种聚类算法在6个数据集上的聚类结果及其对应的参数值.图7～9分别展示了EF-means聚类算法、DBSCAN聚类算法与K-means聚类算法对Jain、Flame和Pathbased数据集的聚类结果,“红星”代表EF-means聚类算法与K-means聚类算法的类簇中心点,DBSCAN算法的可视化图中的黑色点代表算法识别出的噪声点.

表2的实验结果表明,本文所提出EF-means聚类算法整体性能优于其他算法.处理表1的数据集时,EF-means聚类算法显著优于其他4种聚类算法.处理Spiral与Jain数据集时,EF-means聚类算法可以达到100%准确的水平.处理D31数据集时,EF-means聚类算法优于除K-means算法之外的其他算法.

表2 5种聚类算法在6个合成数据集上的聚类性能

图7的可视化结果可看出,Jain数据集由2个非球形分布的类簇组成,且各类簇内的样本点分布不均匀,稀疏度差异较大.EF-means聚类算法可正确发现数据集的形状及类簇数.由于数据点的密集程度相差较大,DBSCAN聚类算法将其中一个类簇的多个点划分为了噪声点,导致最终的聚类结果差.由于数据集由2个非球形分布的类簇组成,K-means聚类算法无法进行准确聚类.

图8的可视化结果可看出,Flame数据集主要由一个凸形分布的类簇和一个非凸形分布的类簇组成,两类簇紧密相接,且左上角有两个噪音点.对于含有凸形分布和非凸形分布类簇的数据集,EF-means聚类算法都能进行准确聚类.由于Flame数据集两类簇边缘紧密相接,且DBSCAN聚类算法易将均匀分布且相距较近的数据点聚为一类,导致DBSCAN聚类算法将Flame数据集两类簇边缘的数据点错误地聚为一类.因数据集中含有非凸形分布的类簇,且K-means聚类算法无法排除噪声点,使得聚类结果差.

图9的可视化结果可看出,Pathbased数据集由1个环形类簇和2个球形类簇组成,且球形类簇被环形类簇包围.从图9可以看出,EF-means聚类算法不仅能成功发现类簇数,还能进行精准聚类.由于数据集内的球形类簇的点分布密集,环形类簇的点分布稀疏,DBSCAN聚类算法成功识别出中间的两个类簇,并将环形类簇识别为噪声点.因数据集中包含2个球形类簇和1个非球形类簇,所以K-means聚类算法仅正确识别中间的2个类簇,而环形类簇被错误地划分为3个类,使得K-means聚类算法最终的准确度很低.

4 结 论

针对K-means聚类算法的不足,本文提出了EF-means聚类算法.将K-means聚类算法与进化聚类算法合并,数据点将分为多个凸形分布的类簇,再使用基于最近距离的中间圆密度簇融合算法和基于代表类的中间圆密度簇融合算法对凸形分布的类簇进行融合,得到最终的聚类结果.K-means聚类算法对k值的选取十分敏感,而且在处理数据量大和类簇类别多的数据集时,k值的选取及初始聚类中心点的选择难度将大幅度增加,且无法处理非凸形分布的数据集,而EF-means聚类算法的距离倍数参数α和密度阈值参数ρk的取范围较为固定,选取难度和时间成本低,有效地解决了K-means聚类算法的难题,使得k值被自适应选取,不再需要初始聚类中心点,并且可以识别任意形状的类簇.通过对多个合成数据集的实验结果分析及可视化观察可知,使用EF-means聚类算法可正确发现数据集的形状及类簇数,并且处理非凸形分布的数据集有较好的聚类效果,提高了算法的可行性与实用性.