基于子簇融合和线性判别分析的密度峰值聚类算法*

刘小康, 张 菁 , 张延迟

(1.上海工程技术大学 电子电气工程学院,上海201620； 2.上海电机学院 电气学院,上海 200240)

0 引 言

聚类属于无监督分类,根据样本点的相似度将对象划分成簇。最经典聚类方法K-means[1]应用最为广泛。但是,基于K-means的聚类结果对初始选择的聚类中心非常敏感,而且无法区分噪声点和距离。Ester M等人[2]提出基于密度的聚类算法——BSCAN聚类算法,能够有效处理噪声点。但是DBSCAN算法往往距离度量为欧氏距离,对于高维数据集会带来维度灾难。

Rodriguez A等人[3]提出密度峰值聚类(dcnsity peak clustering,DPC)算法,该算法简单高效,可快速找到高密度峰值点；但算法在处理不同密度或高维数据集时聚类结果较差,并且算法容错能力差。因此提出一些相关的改进算法。何洋等人[4]提出一种融合K近邻的改进的DPC算法,算法引入K近邻和关联系数,有效解决了数据密度不均衡的问题。文献[5]认为将剩余样本点按局部密度降序分配给与其最近邻密度较高的簇容易引起簇标错误传播,提出一种基于加权局部密度序列和最近邻分配的DPC方法,引入加权局部密度序列和两阶段分配策略提高聚类效率。文献[6]提出一种基于非负矩阵分解和改进的DPC的社区检测算法,克服了算法在高维数据集上聚类不佳的缺陷。文献[7]提出一种基于支持向量机(support vector machine,SVM)的子簇融合(sub-cluster fusion,SCF)策略,将SVM和DPC算法结合,通过计算每个聚类结果之间的反馈值,根据反馈值进行子簇融合。文献[8]认为DPC中没有考虑数据原始特征,提出考虑数据的原始拓扑特征的DPC算法,显著提高了聚类效果。然而上述模型仍然存在以下缺点：算法中通常采用欧氏距离来计算样本点之间的距离,容易忽略样本之间的相关性。在子簇融合时容错性差,并且在高维数据集上不能产生有效的聚类结果。

本文提出一种基于SCF和线性判别分析(linear discriminant analysis,LDA)的DPC算法。重新定义了局部密度ρi计算函数。提出利用Pearson相关系数绝对值的倒数作为权值的加权欧氏距离来度量样本点间的距离。将SCF算法与DPC算法结合,提高算法容错性。引入LDA算法,对高维数据降维,提高算法在高维数据集上聚类精度和有效性。

1 DPC算法

DPC算法核心是[9]计算样本点局部密度和到邻近最大密度的距离,以距离最近较大密度点的距离作为聚类中心,并根据密度对其余点划分融合。主要步骤为：对于样本点xi∈X,X={x1,x2,…,xn},定义点xi的局部密度ρi为

(1)

式中dij为样本点xi与xj的距离,dc为截止距离。

样本点xi到高密度点的最近邻距离δi定义为

(2)

局部或全局密度高样本点不存在高密度邻近,与最近的较大密度点的距离定义为

(3)

以γi作为选择聚类中心的指标,γi计算公式为

γi=ρiδi

(4)

2 SCF-LDA-DPC算法

2.1 加权欧氏距离

针对DPC算法并未考虑数据局部结构特征和样本相关性问题,引入基于Pearson相关系数的加权高斯核密度估计函数计算每个采样点局部密度。

定义1基于高斯核密度估计函数,样本点的局部密度公式定义为

ρi=∑exp(-dij/dc)2

(5)

式中dij为样本点xi与xj的距离。

定义2Pearson相关系数是度量属性之间相关性的常用标准,其公式为

(6)

式中 当Pearson相关系数rxy=±1时,样本x和y相关；当rxy=0时,样本x和y无关。

定义3引入Pearson相关系数绝对值的倒数作为权重重新定义加权欧氏距离函数为

(7)

式中xi,xj为样本数据的特征值。

定义4由于样本之间的距离由加权欧氏距离函数计算,因此基于Pearson相关系数的样本局部密度计算公式为

(8)

2.2 子簇合并策略(SCF算法)

传统DPC算法根据γi最大值确定聚类中心,有容错性差的缺陷。因此,提出一种SCF算法。算法核心思想：当簇A和B的簇密度相似且边界距离较小才可以融合。充分考虑数据加权内平均距离、簇间密度差和簇间距离。

定义5数据内平均距离αi

(9)

式中 数据集为n维；k(i)为数据点i的k邻域集合。

定义6簇间距离AB

AB=min(d(ri,rj))

(10)

式中d(ri,rj)为数据集A和B内的点距离。

定义7簇间密度差CD

(11)

dSCF(A,B)可表示为

dSCF(A,B)=AB·CD2

(12)

实验发现,当dSCF(A,B)大于簇间相似性阈值(所有数据的0.2×mean(dSCF))时,子簇间差异性较大,不能融合。因此,设定簇间阈值为0.2×mean(dSCF)。

算法1SCF算法

输入：数据集及聚类中心

输出：聚类结果

step1 按式(9)计算数据加权内平均距离αi

step2 按式(10)计算簇间距离AB

step3 按式(11)计算簇间密度差CD

step4 按式(12)计算dSCF(A,B)

step5 判断dSCF(A,B)是否小于阈值,若小于,进行子簇融合

step6 输出聚类结果

2.3 LDA算法

为解决DPC算法对高维数据集处理困难的问题,首先采用降维方法对高维数据降维。线性判别式分析(LDA)应用于数据降维中[10],通过线性函数来处理数据,实现数据降维。

算法2LDA算法

输入：数据集X={x1,x2,…,xn}

输出：低维数据集Y={y1,y2,…,yn}

step1 计算每个类的均值向量ui,得到原始数据集样本空间类内离散度矩阵

step2 计算类内总离散度矩阵

step3 计算类间离散矩阵

step4 计算LDA准则函数的最优值

step5 计算降维后的数据集Y=wTX

2.4 SCF-LDA-DPC算法

首先调用算法2对数据集X降维处理得到数据集Y；按照式(8)计算ρi,按照式(2)和式(3)计算δi,并由式(4)计算γi并绘制出决策图并选择聚类中心；然后把剩余数据点分配到对应簇中,并删除噪声数据。最后调用SCF算法。

算法3SCF-LDA-DPC算法

输入：数据集X={x1,x2,…,xn}

输出：聚类结果

step1 若X是高维数据集,执行step2,否则执行step3

step2 调用算法2 对数据集X进行降维,得到降维数据集Y

step3 根据式(7)计算距离矩阵dij

step4 根据式(8)计算ρi,根据式(2)和式(3)计算δi

step5 由式(4)计算γi,绘制决策图并选择聚类中心

step6 将其他数据分配给聚类中心

step7 删除噪声数据

step8 调用算法1进行子簇融合

3 实验结果与分析

在不同维度数据集验证SCF-LDA-DPC算法的聚类性能。利用MATLAB 2017a编程,实验环境为Win8,RAM8G,Intel®CoreTMi5-3200U 2.20 GHz。

3.1 低维数据集实验

测试SCF-LDA-DPC算法在9个低维数据集(如表1)的可行性和有效性,并与DPC算法、K-means算法、FKNN-DPC算法和DBSCAN算法比较,评 价 指 标为AMI、ARI、FMI 指数[11],对照算法参数设置如文献[12]。结果为15次实验均值。表2为5种算法在数据集中性能指标值。图1为SCF-LDA-DPC算法在部分数据集上聚类结果。

表1 9个数据集参数

表2 5种算法在不同数据集上的性能

图1 SCF-LDA-DPC算法聚类结果

从表2中可知,SCF-LDA-DPC算法在多组数据集上表现优于另外4种聚类算法。尤其是在数据集Seeds,Jain和R15中,只有采用加权欧氏距离的SCF-LDA-DPC算法AMI、ARI和FMI的值都为1,能够正确找到聚类中心。在数据集Waveform上SCF-LDA-DPC算法具有独特优势,能快速准确寻找到聚类中心,聚类精度和效果明显高于另外4种算法。从图1中可知,在数据集Spiral和Flam上5种算法均有很好效果,因此,对简单数据集Spiral和Flam,参数设置对聚类结果影响较小。综合分析,SCF-LDA-DPC算法优于其他4种算法,在所有二维数据集上都有较好的效能和准确性。

3.2 高维数据集实验

实验选取6个高维基因表达数据集(数据参数见文献[13])验证SCF-LDA-DPC算法聚类性能。并与HMM算法[13]、HKAP-LLE算法[14]、IG-SGA算法[15]和APCES算法[15]比较聚类结果。采用5倍交叉验证法。选用3个评价指标[15](R、S和AC)对聚类检验。对照算法参数如文献[15]。表3为5种算法在数据集Colon、Leukemia和Prostate上结果比较。

表3 5种算法在3个高维数据集上R和S值比较

R和S的值越接近1,说明聚类精度越高;反之,聚类精度越低。从表3中可知,在数据集Colon上SCF-LDA-DPC算法指标R和S值均为1,大于另外4种算法的值,表明算法在该数据集上聚类性能优于其他4种算法。对于数据集Leukemia,SCF-LDA-DPC的R值最大,虽然指标S值略小于最优值,但两者相差不大,表明算法综合性能优越。在数据集Prostate上,SCF-LDA-DPC算法和IG-SGA算法R和S指标值均为1,远大于其余3种算法值。

表4为5种算法在数据集SRBCT,Leukemia1和9-Tumor上AC值的比较。从表4中可知,传统算法K-means、C-NMF和S-NMF在数据集上表现较差。较新的HKAP-LLE算法AC值较高,说明该算法聚类精度高于3种传统算法。而SCF-LDA-DPC算法和HKAP-LLE算法相比,在3个数据集上的聚类精度分别提升3.60 %，15.63 %和5.60 %,表明该算法性能更加优越。综合分析可知,SCF-LDA-DPC算法效果最佳,具有在高维基因表达数据集上聚类结果的有效性和准确性。

表4 5种算法在3个高维数据集上AC值比较

4 结 论

本文对DPC算法改进，提出SCF-LDA-DPC算法。引入Pearson相关系数作为权重，基于加权欧氏距离的核密度估计函数计算样本间的局部密度，既考虑了连续数据集的局部结构特征，又考虑了样本间的相关性。提出SCF，可以有效避免DPC算法容错性差的问题，最后利用LDA算法对高维数据降维，更有效地解决高维数据集上表现不佳的问题，提高了算法在高维数据集上的鲁棒性和准确性。实验结果表明：SCF-LDA-DPC算法在不同维度以及不同形状的数据集上都可以准确找到聚类中心,较其他算法相比能够获得更准确的聚类中心和更高的聚类精度。