融合可拓关联函数的密度峰值聚类算法

赵燕伟,朱 芬,桂方志,任设东,谢智伟,徐 晨

1(浙江工业大学 特种装备制造与先进加工技术教育部 浙江省重点实验室,杭州 310014)2(浙江工业大学 计算机科学与技术学院,杭州 310014)

1 引 言

聚类是数据分析的重要手段,将数据集分为若干类,使得簇内紧密且相似性大,簇与簇之间有明显区别,使得相似性最小[1],在模式识别、图像处理和风险管理等领域被广泛应用[2-5].大数据背景下的海量和多样数据的存在,使得聚类算法的研究对这些数据背后隐藏的模式和规律的发现具有重要意义.

聚类算法有划分式、密度式,网格式等[6,7],其中划分式聚类算法主要以K-means算法为代表,密度式聚类算法主要以DBSCAN[8,9]算法为代表,网格式主要以CLIQUE[10]算法为代表.尽管许多聚类算法被提出,但对聚类的研究仍在不断地探索中.2014年Alex Rodriguez 和 Alessandro Laio等[11]提出了一种密度峰值聚类算法CFSFDP,凭借其能自动发现数据集样本的类簇中心,实现任意形状的样本高效聚类等优势,引起了大量学者的关注,但是该算法存在明显缺陷:当数据集中存在多个密度峰值或者某一个非中心样本点分配错误就会出现连续分错现象[12].对此学者提出了不同的改进方法:贾培灵等[13]针对某个类存在多个密度峰值导致聚类不理想问题,提出一种基于簇边界划分的DPC算法;薛小娜等[14]提出了一种结合k近邻的改进密度峰值聚类算法,结合k邻域思想设计了全局搜索分配策略;Wang S L等[15]提出了一种利用原始数据集中数据场的潜在熵自动提取阈值最优值的新方法;MehmoodR等[16]提出了一种自适应选择聚类中心的模糊CFSFDP方法,具有较好的鲁棒性和有效性;谢娟英等[17]提出一种基于k近邻的快速密度峰值搜索并高效分配样本的聚类算法,对噪声数据具有非常好的鲁棒性;Mehmood R等[18]提出了一种通过热扩散密度峰值算法,用于采用非参数估计给定数据集的概率分布,对截止距离的选择和核密度估计进行校正;Zhou Y等[19]提出了一种基于密度比的方法来聚类,通过使用密度估计器计算密度比,修改基于密度的聚类算法以进行基于密度比的聚类;Du M等[20]提出了一种基于k个最近邻点的密度峰聚类,并将主成分分析(PCA)引入到DPC-KNN模型中,进一步提出了基于PCA的方法,该方法对高维数据有更好的聚类效果;刘如辉等[21]提出半监督约束集成的快速密度峰值聚类算法,自动选择候选中心点提高聚类性能具有更高的聚类精度.Chen等[22]摒弃对单个初始中心点的寻找,通过用一半高密度的点生成初始聚类轮廓,完成聚类.

现有的研究虽取得了一定的成效,但簇心选取及未分配点分配准确率仍然不高,一方面原因是簇心质量不佳,另一方面是由于其所采取的最近邻原则分配策略本质上都是基于欧式距离计算而来的密度值,并没有从本质上挖掘出样本点间的相关性,造成样本分配错误.因此本文提出一种融合可拓关联函数的密度峰值聚类算法,引入基于平均差异度的密度度量方式,并提出一种基于可拓关联函数和k邻域思想的分配策略,实现对未分配点进行准确分类.通过对比实验验证,该方法具有更好的聚类效果和聚类准确率.

2 相关知识介绍

2.1 可拓关联函数相关知识介绍

为刻画论域中的元素具有某种性质的程度,蔡文[23]等提出了可拓关联函数的概念,通过建立实域上可拓集的关联函数基本公式,定量客观的描述元素具有某种性质的程度及其量变与质变的过程.该概念在分类检索和故障预警等方面广泛应用,赵燕伟等[24]提出一种基于可拓距的多维关联函数产品低碳设计分类方法,解决了低碳设计中因需求变化所引起的分类跳跃性问题;任设东等[25]提出一种基于关联函数多属性相似实例检索方法,克服了欧式距离检索的不准确性;洪欢欢等[26]提出了一种多维关联函数建模及其检索应用方法,解决多维度实例检索建模及其降维计算的问题.可见,可拓关联函数在描述事物相似度具有较大优势,将其与聚类算法结合,充分发挥其优势是目前研究的重要方向.

在建立关联函数前,为了描述类内事物的区别,引入可拓距和位值等概念:

实轴上任意一点x与区间X0=之距为:

(1)

设X0=,X=,且X0⊂X则称:

D(x,X0,X)=

(2)

为点x关于区间X0和X组成的区间套的位值.

设X0=,X=,且X0⊂X,则:

(3)

称k(x)为点x关于区间X0和X的关联函数.通过关联函数描述事物具有某种性质的程度,即将“具有某性质”的事物从定性描述扩展到“具有该性质的程度”的定量描述.k(x)≥0表明x属于区间X0,k(x)<0表明x不属于区间X0.

(4)

称K(O)为对象O的综合关联函数,vi为对象O第i个属性对应的值.

2.2 CFSFDP算法介绍

CFSFDP算法以其决策图思想和一步分配策略思想,引起很多学者的关注,即提出决策图概念自动发现数据集中样本的类簇中心,并快速分配非中心点,实现任意形状的高效聚类[12].

该算法认为理想的类簇中心应具备两个基本特征:

1)该点局部密度大于围绕它的样本点的局部密度;

2)不同簇心间距离相对较远.为找到满足上述要求的点,对于每个数据i都引入了局部密度ρi和相对距离δi两个概念:

(5)

(6)

其中dc为截断误差,dij是数据i和j之间的欧式距离.

(7)

可知当数据i的局部密度ρi不是最大值时,其相对距离δi为在所有的局部密度大于数据对象i的数据对象中,与数据对象i的距离最小的数据与数据i间的距离;当数据i的局部密度ρi最大时,δi为数据集中与数据i距离最大的距离.

CFSFDP算法认为簇心往往是δ异常大的样本点,同时这些样本点的局部密度ρ也相对较高.通过构造样本相对距离δ和局部密度ρ的决策图选择簇心;获取簇心后,将剩余样本点采用最近原则将其分配到更高密度的最近邻类簇中,一步分配,快速简洁.

但CFSFDP算法具有如下缺陷:

1)该算法采用小于截断距离样本的个数作为样本点密度,对于拥有相同密度即具有相同小于截断距离的样本个数的节点而言,无法更加细致地区分2个节点谁更加稠密,从而对后期结合决策图选取簇心造成一定干扰;

2)对于其高效的一步分配策略,会出现“多米诺骨牌效应”,即:一旦某个数据点分配错误,会影响剩余数据点的分配,现有的研究所提出的分配策略本质上都是基于欧式距离计算而来的密度值进行最近邻原则分配虽然取得一定的效果,但并没有从本质上挖掘出样本点间的相关性,造成样本分配错误,出现“多米诺骨牌效应”.

3 可拓关联函数改进的密度峰值聚类算法

为有效处理CFSFDP算法中存在的两个缺陷,本文将从密度度量方式和分配策略对其进行改进.

1)引入节点平均差异度[27]概念衡量样本密度,对各样本点的密度更加细致的进行区分,便于更加准确的对簇心进行选择;

2)引入可拓关联函数充分考虑样本点与簇心之间相关性,用以揭示样本点的类属关系,提高样本点分配的正确率,从而解决CFSFDP算法的“多米诺骨牌效应”问题.在阐述本文算法之前,需先对节点局部平均差异度、可拓关联函数的节域和经典域进行相关定义.

3.1 相关定义

为便于表述,首先定义样本物元模型、簇心ζ的k距离、簇心ζ的k距离邻域、样本集节域和簇心ζ的k距离邻域的经典域等概念.对于样本集O={O1,O2,…,On},其中Oi为m维向量(i=1,2,…,n),有如下定义:

定义1.节点局部平均差异度,即密度:

(8)

定义2.样本物元模型:样本Oi表示为:

(9)

其中C为样本Oi的属性特征,C=[c1,c2,…,cn],V为样本Oi属性特征所对应的值,V=[v1,v2,…,vn].

定义3.簇心ξ的k距离:

簇心点ξ的k距离是ξ到它的k最近邻的最大距离,记为k_dist(ζ).

(10)

其中Q(ζ)为簇心点ζ到它k最近邻样本点的集合,k的值不能过大,影响聚类正确率,也不能过小,增加算法运行时间,一般取值为簇心个数的2～4倍.

定义4.簇心ζ的k距离邻域:与簇心ζ距离小于k_dist(ζ)的样本点集合,记为N(ζ)

定义5.样本集节域:

(11)

为该样本集O第j维属性值的取值范围,即为各属性的节域.

定义6.簇心ζ的k距离邻域的经典域:

(12)

为第i个簇心ζi的k距离邻域N(ζi)第j维属性的取值范围,即为各属性的经典域.

3.2 算法基本思想

本文提出的算法首先基于各节点平均局部差异度及距离绘制决策图快速找到簇心,之后基于RDCA算法[12]中k距离邻域思想,提出基于簇心点的k距离邻域,得到各簇心的雏形簇心类;最后融合可拓关联函数对各雏形簇心类不断外扩,从而完成最终的聚类.

图1 密度展示结构图Fig.1 Picture of density display

如图1所示,以样本点14,4,16为例,分别画出以该点为圆心,以截断距离dc为半径的圆,可看出在圆内,样本数都为4个,传统的CFSFDP算法将其个数作为样本点密度,即样本点14,4,16密度相等,但图中可看出,虽然样本数相等,但各圆内样本与圆心的疏密程度是有所区别的,故本文提出的算法引入节点平均局部差异度概念描述样本点的密度,对样本点密度进行更细致的描述;进而利用决策图找出簇心.

图2 分配策略思想结构图Fig.2 Figure of distribution strategy

获取簇心后,进行样本的分配,本文采用的分配策略实际是在聚类算法中引入分类的思想,基于可拓关联函数对样本点类簇归属情况给出相应的分配策略如图2所示,提高样本点聚类的准确性,从而降低CFSFDP算法“多米诺骨牌效应”对聚类效果的不利影响.

根据改进后的决策图选出簇心,如图2(a)中所示,点14,16,4为决策图选出的3个簇心,将除簇心外的其他点都标记为未分配点;根据簇心的k距离邻域,得到各雏形簇心类,如图2(b)中虚线圆所示,并将样本点1,6,12,5,18,20,2,7,11标记为已分配点;如图2(c)中,在未分配点中随机挑出一个样本点13分别计算样本点13与各雏形簇心类的关联函数值,即相关度值,根据相关度值将样本13分配到相关度大的簇类中,并将其标记为已分配点;依次判断剩余未分配点,如图2(d)所示,直至完成所有未分配点的分配,即样本点聚类完成.

3.3 算法的实施步骤

Step 1.根据公式(8)和公式(7)计算各样本的局部平均差异度ρ和相对距离δ;

Step 2.根据ρ和δ值,绘制出样本点的决策图,从而确定簇心ζ;

Step 3.根据定义3中的公式(10)与定义4分别计算出各簇心ζi的k距离k_dist(ζi)及k距离邻域N(ζi);

Step 4.将k距离领域N(ζi)默认分配到各自的对应的ζi簇心类cluster(i)中,并将其标记为已分配点,剩余点标记为未分配点;根据定义5中公式(11)计算出样本集各属性的节域vcj;

第三，某些选修课程设置的初期忽视了学生的呼声和意见。某些选修课程的设置不但要围绕某种理念进行，对学生的兴趣也要加以兼顾，以利于提高学生的学习兴趣。

Step 5.从簇心集ζ中随机取出一个未被访问的簇心ζi,并将标ζi记为已访问点.

图3 算法流程结构图Fig.3 Algorithm flowchart

Step 6.根据定义6中公式(12)计算出雏形ζi簇心类cluster(i)样本各属性的经典域vq,j,并根据公式(1-3)建立未分配点各属性的关联函数,获得对应相关度值.

Step 7.根据信息熵[28]计算出各属性权值,由公式(3)和公式(4)建立未分配点综合关联函数,获得各未分配点关于雏形ζi簇心类cluster(i)的综合相关度值;

Step 8.若ζ中仍存在未访问簇心点,则返回到Step 5,直至ζ中所有簇心被访问,则进入下一步;

Step 9.将未分配点分配到综合相关度值大的簇心类,完成未分配样本点的聚类.

该算法流程如图3所示.

3.4 算法复杂度分析

4 实验验证与分析

4.1 实验数据集和评价指标

本文改进的算法,通过Python语言编写,用Spyder工具对实验结果进行显示.为了验证算法的有效性,本文选取4组人造数据和7组不同UCI数据库数据集进行实验,通过与CFSFDP算法、文献[14]改进过的IDPCA算法、DBSCAN算法和K-means算法进行对比,以验证本文算法的性能.各数据的特征如表1所示,其中,Aggregation、Jain和Three cluster是人造数据;Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC是UCI数据库中的真实数据.

聚类效果的衡量标准,分为可视化衡量和定量衡量两种,其中可视化衡量方法可以清晰明了的体现聚类结果和样本的分布;定量衡量指标采用聚类准确率[29]指标(Accuracy,ACC)作为聚类算法性能度量标准.ACC取值范围为[0,1],指标值越大,表明聚类质量越高.

表1 各数据集的基本特征
Table 1 Characteristics of the data set

数据集样本个数样本维数分类数Aggregation78827Jain37323Three cluster60023Data1150023Iris15043Wine179133Seeds21073Ionosphere351342WDBC569302Waveform35000213CMC147393

4.2 改进的密度峰值聚类算法性能分析

4.2.1 可视化数据集实验结果分析

实验采用4组数据集做可视化展示:Aggregation、Jain、Three cluster和Data1,其中Aggregation数据集簇间密度相对均匀,形状多样且簇与簇之间有连接;Jain数据集非线性分布,密度差异较大;Three cluster数据集形状相似,各簇样本密度相对均匀,簇间无交集;Data1数据集线性分布,疏密差异不大.

图4-图7是4组数据集分别基于这5种算法聚类得到的结果:图4,图5分别是基于Aggregation数据集与Three cluster数据集聚类的结果,其中图4(d)IDPCA算法聚类效果最好,其次是图4(b)本文算法,聚类效果最差的是图4(f)K-means算法,而在图5中聚类效果最好的是图5(f)K-means算法,主要原因在于K-means算法对簇型数据集且各簇间彼此不相连的数据集聚类效果较好,其次是图5(b)本文算法聚类效,表明本文算法对簇型且各簇有相连的数据集聚类效果较好.

图6,图7分别是基于Jain数据集与Data1数据集聚类的结果,图6中图6(b)本文算法聚类效果最好,其次是图6(d)IDPCA算法和图6(e)DBSCAN算法,最差的是图6(c)CFSFDP算法与图6(f)K-means算法,原因在于CFSFDP算法对样本疏密度较为敏感,K-means算法对非簇型聚类效果不好;图7中图7(d)IDPCA算法聚类效果最好,其次是图7(b)本文算法和图7(e)DBSCA算法,最差的是图7(f)K-means算法,表明本文算法对不同疏密与非线性数据集具有较好的聚类效果.

图4 Aggregation数据集聚类Fig.4 Aggregation dataset cluster

图5 Three cluster数据集聚类Fig.5 Three cluster dataset cluster

图6 Jain数据集聚类Fig.6 Jain dataset cluster

图7 Data1数据集聚类Fig.7 Data1 dataset cluster

其中,图(a)为实际聚类结果,图(b)为本文算法聚类结果,图(c)为CFSFDP算法聚类结果,图(d)为IDPCA算法聚类结果,图(e)为DBSCAN算法聚类结果,图(f)为K-means聚类结果.

图8是5种算法聚类准确率对比图,从图中可看出Aggregation和Three cluster数据集整体聚类结果偏好,聚类准确率浮动不大;从非线性和线性且密度有差异的两组数据集Jain和Data1中可看出,本文算法对密度差异大的线性和非线性数据聚类效果更好,其次是IDPCA算法,CFSFDP算法和K-means算法聚类效果相对较差.

图8 该5种算法聚类准确率对比图Fig.8 Clustering accuracy ratio comparison chart

其中,x轴坐标中0:样本真实分布;2:本文算法;4:CFSFDP算法;6:IDPCA算法;8:DBSCAN算法;10:K-means算法.

4.2.2 非可视化数据集实验结果分析

为了进一步验证本文算法的有效性,选取7组来自UCI数据库的实验数据集Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC数来测试,这7组数据都有明确的分类标签,因此可以用来对比验证聚类结果的好坏及算法的性能.

表2为各算法基于Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC 7个真实数据集聚类后的ACC评价指标值.

表2 7个数据集聚类后的ACC指标
Table 2 ACC indicator after clustering of data sets

数据集本文算法CFSFDPIDPCADBSCANKmeansIris0.9690.94—0.7930.78Wine0.9100.8830.8960.6650.7Seeds0.9470.8950.9380.7150.89Iono-sphere0.7880.6810.7690.6070.712WDBC0.9630.6130.9490.8700.928Waveform30.6980.5860.665—0.501CMC0.6750.65—0.560.35

从表2中可得出本文算法在聚类准确率上整体优于其他4种算法,尤其对高维度的数据集Ionosphere,WDBC,Waveform3聚类优势更明显.通过5种算法对UCI真实数据集的聚类准确性的对比分析可以发现,本文提出的算法具有良好的聚类性能,优于CFSFDP算法、IDPCA算法、DBSCAN算法和K-means算法.

5 总 结

本文针对由于CFSFDP算法聚类准确率低的问题,提出一种融合可拓关联函数的密度峰值聚类算法.采用平均差异度作为样本密度衡量指标,借鉴CFSFDP算法决策图选取簇心;从簇心出发引入k邻域及关联函数思想对未分配点完成准确聚类.该算法在不同类型数据集上的实验,证明了本文提出的算法对任意形状,任意密度的数据集的聚类效果和聚类准确性均优于经典的CFSFDP算法、DBSCAN算法、K-means算法及改进的IDPCA算法.但本文算法中k邻域的参数k的取值是凭经验选取,如何实现针对不同数量及不同维度的数据集自动选取最优k值是今后研究的方向.