融合密度峰值的高斯混合模型聚类算法

陶志勇，刘晓芳,2，王和章

(1.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105; 2.阜新力兴科技有限责任公司, 辽宁 阜新 123000)(*通信作者电子邮箱1367251096@qq.com)

0 引言

大数据信息处理过程中的关键步骤就是对数据聚类，也就是将大数据中同类属性对应的关键特征参数进行科学、系统、准确的挖掘，进而实现对大数据的分析、统计、研究。当前阶段，常见的大数据库、专家系统等均以数据聚类为依据，为广大使用客户提供诊断分析、模式判断等相关的服务[1]。查阅大量文献资料可知，相关研究人员已经将数据聚类作为数据挖掘的关键与核心研究方向，经过长期的分析研究已经取得了一定成果，最具代表性的就是聚类算法，例如：常见的K均值聚类[2]、模糊C均值聚类[3]、核密度聚类[4]及构建有限混合模型[5]聚类等。

经过近些年的深入分析与研究，高斯混合模型(Gaussian Mixture Model, GMM)算法发展非常迅猛，然而它的缺陷也非常明显，很多研究人员对其进行改进，并给出了新型的GMM算法，如：Yang等[6]提出了一种鲁棒的有限高斯混合模型聚类算法，该算法直接将系统的初始模型相关参量作为原始样本的总数，同时对信息熵惩罚因子加入分量混合系数，虽然该算法不必随机选取初始值，但实验结果表明此算法聚类准确率不高且运行时间长；Saravia等[7]提出了一种分裂合并的马尔可夫链蒙特卡洛(Markov Chain Monte Carlo, MCMC)方法用于聚类个数的确定，该方法可准确得到聚类个数，但实现过程较为复杂；崔玮等[8]将GMM算法用于无线传感器网络室内节点定位，采用粒子群算法对最大期望(Expectation Maximization, EM)算法进行优化，同时结合优选残差加权算法对距离值进行定位估计，此方法对节点定位有一定的适用性，但所提的GMM算法在初始化阶段采用K均值算法，具有一定的随机性，所得到的聚类效果不理想；王垚等[9]将逆模拟退火算法与半监督高斯混合模型中的EM算法相结合，与传统的高斯混合模型EM算法相比收敛速度快、准确率高，但差于融合密度峰值的GMM聚类算法(Clustering algorithm of GMM based on Density Peaks, DP-GMMC)聚类结果，且处理大规模数据集的能力较弱；Scrucca[10]采用密度估计的方法得到聚类中心，再利用EM算法进行计算，该方法可发现非高斯集群，但算法的开销很大;Li等[11]采用自适应的层次聚类方法用于GMM算法初始值的确定，相比经典的GMM算法具有较强的聚类能力，但随着数据量的增大，此方法寻优迭代次数也会大幅度增加。利用高斯混合模型聚类时，若样本属于不完全数据，通常采用EM算法求解最大似然值，而EM算法收敛速度慢，系统模型计算过程中对初始值的设置非常敏感，故而容易收敛到局部最优解。通过对大量相关研究的分析与总结可知，部分研究已经对EM算法的混合模型等多种估算问题进行分析与探究，并取得了一定成果，如：Liu等[12]将GMM算法用于基因聚类，为了解决EM算法初始化的问题，通过添加和删除EM算法的初始值，把簇的数量作为已知参数并且采用准赤池信息准则(Quasi Akaike Information Criterion, QAIC)，改进后的算法在基因聚类上有一定的效果；Li等[13]则通过K最近邻(K-Nearest Neighbors,KNN)算法删除异常值，再使用K均值初始化EM算法，但聚类对应的个数是不确定的，而且设置过程比较复杂。

密度峰值聚类算法[14]将具有局部极大密度估计值的样本点视为聚类中心，通过对模型聚类中心的快速搜索，并将每一个非中心样本点沿着密度递增的最近邻方向迭代划分给相应的聚类中心，进而实现对大数据的分类。然而，该算法中ρ和δ值的分布依赖于截断距离参数dc，算法聚类的质量受参数dc的影响。本文针对此问题进行了改进，根据μ律15折线的方法对数据点之间的距离进行压缩，避免了参数dc对数据聚类的影响。鉴于GMM和DP算法各自的优缺点，本文提出了一种融合密度峰值的高斯混合模型聚类算法(DP-GMMC)。首先，利用改进后的密度峰值算法对聚类中心进行自动查找，再将得到的聚类中心作为GMM算法的初值，最后完成数据点的聚类。本文的工作主要是在DP算法中引入了μ律15折线，减弱了人工选择参数对结果的干扰，并将DP算法应用在标准GMM算法初始值确定上，通过密度峰值自动确定聚类数，提高了原始算法的聚类能力。

1 高斯混合模型

设{x1,x2,…,xn|x∈Rd}为随机变量x的n个随机样本值，则含有k个成分的d变量混合模型的概率密度函数表示如式(1)所示：

(1)

若随机变量θj∈{1,2,…,k}表示生成样本xj的高斯混合分布，其取值未知。显然，θj的先验概率P(θj=i)对应于ζi(i=1,2,…,k)，根据贝叶斯定理，θj的后验分布对应于：

gM(θj=i|xj)=P(θj=i)·gM(xj|θj=i)/gM(xi)=

(2)

由式(2)可知，gM(θj=i|xj)给出了样本xj由第i个高斯混合成分生成的后验概率。

假设所有分布具有相同的函数形式(例如服从d个随机变量的高斯分布)，其特性由参数向量μi、Σi和ζi决定。设一组n个独立同分布样本x={x1,x2,…,xn}，对应的对数似然值如式(3)所示：

(3)

借助EM计算方法[15]进行极大似然估计，其对应的计算步骤如下：

1)初始化：根据得到的聚类中心计算混合模型中各密度分布待估计参数μi、Σi、ζi的初始值设置。

2)E步：计算第m次迭代每个样本点i属于第j类的后验概率gM(θj=i|xj)。

3)M步：计算样本数据似然函数的期望值方程达到最大值时的结果，得到用于下一次迭代的新参数μi′、Σi′和ζi′。

4)收敛条件：不断迭代E步和M步，重复更新参数直至变化不显著，否则转第2)步。

2 融合密度峰值的高斯混合模型

EM算法能够将目标样本与高斯混合模型(GMM)进行有效的融合，进而获得最佳的拟合数据。该处理方式与传统的GMM计算方法有着本质的区别，传统方法一般对数学模型的相关参数进行预设，进而直接导致拟合效果与数据样本有一定程度的差异，效果不稳定、不精确。针对上述问题，本文设计了一种新型的GMM算法，该算法的核心就是将系统原始数据依据密度峰值(DP)算法对其距离与密度进行有效估算，进而选择聚类中心，再利用GMM算法对剩余数据点进行聚类。

2.1 DP算法原理

DP算法实际计算过程中对密度峰值进行检索与发现，将具有局部最大密度值的样本点作为聚类中心，快速实现样本数据的划分，待确定的聚类中心一般包括以下两个特征：1)本身的密度大; 2)与其他密度更大的数据点的距离更大。

为了准确找到聚类中心，该算法引入样本i的局部密度ρi和到局部密度比它大且距离它最近的样本j的距离δi，其定义如式(4)～(6)所示：

(4)

其中:dij=dist(xi,xj)为样本i、j间的欧氏距离;dc为截断距离。

(5)

对于局部密度ρi最大的样本i，其δi如下：

(6)

根据式(4)可以看出，计算密度时均需要确定dc值，这对聚类中心的确定有一定的影响，为此本文采用μ律15折线的方法对样本点之间的距离dij进行压缩，每个样本点i的ρ值为剩余样本点到i点的压缩距离之和，其计算式如下：

(7)

其中xij=1-dij/dmax;dmax=maxdij;μ=255。

根据式(5)对样本点i的距离δi的实际定义，假设i的密度ρi是全局最大密度，那么i的δi会远大于其他样本的δ。因此，类簇中心往往是δ异常大的样本点，这些样本点的密度也相对较大。

故DP算法提供了一种启发式方法，即通过计算ρ和δ的决策图(如图1)来选择预期聚类中心，其中聚类中心与其他聚类点相比具有更大的ρ值和δ值，根据决策图中的ρ和δ来判断聚类中心。

图1 节点决策图Fig. 1 Decision graph of node

在本算法中聚类中心可以自动确定，将ρ值和δ值综合考虑，其计算式可以用式(8)表示：

γi=ρi×δi

(8)

由式(8)可知，数值γ越大，则xi属于数据中心点的可能性越大。因此，本文将γ进行降序排列，截取若干聚类中心点，具体变化见图2,选择横轴作为系统的指标集，并将系统的γ作为纵轴。由图2可知，非聚类中心对应的γ数值较为平滑，由非聚类中心向聚类中心进行过渡时，γ存在极其明显的跳跃现象，通过跳跃点，即可找寻数据各类对应的中心点。

图2 γ决策图Fig. 2 Decision graph of γ

2.2 DP-GMMC

GMM算法具体应用过程中存在一定缺陷，为解决此问题，本文选择DP算法对其初始值预设过程进行优化。DP-GMMC的核心工作为：首先，DP算法对系统样本对应的聚类中心、个数进行明确，以获取平均数值，进而得出对应类的协方差矩阵，构建系统的初始参数；然后，借助EM进行预估，构建混合密度数学模型；最后，根据贝叶斯准则对样本概率进行验算。该算法能够降低局部搜索迭代次数，增加初始化多样性，有效克服传统GMM算法存在的缺陷。

DP-GMMC的具体步骤如下所示：

输入 样本数据集χ，迭代停止阈值η；

输出 簇划分C={C1,C2,…,Ck}。

步骤1 基于数据点的距离dij，构建相似度矩阵。

步骤2 根据相似度矩阵计算每个数据点的局部密度ρ，并计算数据点的高密度距离δ。

步骤3 使用决策图选取聚类个数k以及聚类中心集合{v1,v2,…,vk}。

步骤4 利用聚类中心集合初始化均值向量μi、协方差矩阵Σi及高斯混合分布的模型参数ζi，根据式(1)计算xj由各混合成分生成的后验概率，即gM(θj=i|xj)。

步骤5 根据式(9)～(11)计算新均值向量μi′、协方差矩阵Σi′和混合系数ζi′。

(9)

(10)

(11)

步骤7 确定xj的簇标记ζj，将xj划入相应的簇。

2.3 算法时间复杂度分析

DP-GMMC时间复杂度由两部分组成，即DP算法时间复杂度和GMM算法时间复杂度。使用改进后DP算法自动确定聚类中心过程中，计算参数dij、采用μ律15折线得到的ρi以及δi，时间复杂度均为O(N2)，其中N为数据点的个数；然后，计算ρi和δi的归一化乘积γi，并将γi按降序排列，时间复杂度分别为O(N)和O(klogk)，其中k为候选聚类中心个数。因此DP算法的时间复杂度为：O(N2+N2+N2+N+klogk)=O(N2)。相比于GMM算法，初始聚类中心确定过程增加的时间复杂度为O(N2)，同时初始值率先选取有利于减小GMM算法的迭代次数，总体看来本文算法增加了一定的时间开销，有待于下一步的研究改进。

3 实验结果及分析

为了验证DP-GMMC的有效性，将本文算法与经典的DP、GMM算法、文献[6]的鲁棒GMM的EM聚类(Robust EM for GMM, REM-GMM)算法及文献[11]的层次EM聚类(EM via Adaptive Hierarchical Clustering, AHC-EM)算法进行实验仿真，分别从算法准确度、有效性、纯净度方面对5个算法的性能进行了分析和比较。实验仿真环境为Pentium E53002，内存为2 GB，操作系统为Windows 7，仿真软件为Matlab 2015a。

3.1 算法准确度实验

此次实验分两组数据集进行，第一组数据集是来自UCI的Breast cancer、Indian Liver、Iris数据集以及聚类常用4k2_far、Aggregation数据集，其数据集属性如表1所示。

表1 第一组数据集属性Tab. 1 Properties of first group of datasets

此外，基于5组标准数据集分别对4种算法进行50次仿真实验，所得的平均聚类准确率和标准差如表2所示。

根据表2的实验结果可知，本文算法在5个数据集上均获得了较高的聚类准确率，在Iris数据集下的平均聚类准确率可达到96.67%，相比于传统GMM算法提高了33.6个百分点。DP算法是基于密度的聚类算法，对于聚类中心的选取较准确，但后期的聚类能力较差，导致聚类准确率不高；GMM算法对于初值非常敏感，每次迭代随机选取聚类中心导致聚类效果很差；AHC-EM算法采用基于层次算法对初值中心进行寻优，相比于前两种算法有确定聚类中心、增强聚类能力的优势，但层次聚类相比于密度聚类算法迭代速度慢、寻优精度低，导致最终在数据集上的聚类准确率低于DP-GMMC；而DP-GMMC则同时兼具了DP算法全局搜索能力强以及GMM算法局部搜索能力强的优势，聚类准确率最高，聚类识别效果也最好。从标准差也可看出DP-GMMC每次运行结果较稳定，变化不大。

表2 4种算法第一组数据集上的实验结果对比Tab. 2 Comparison of experimental results of 4 algorithms on first group of datasets

第二组实验所采用的数据集是3组高斯数据集，数据集属性如表3所示。

表3 第二组数据集属性Tab. 3 Properties of second group of datasets

其中,数据集1：μ1=(0 0)T，μ2=(20 0)T，Σ1=(1 0;0 1)，Σ2=(9 0;0 9);数据集2：μ1=(0 0)T，μ2=(20 0)T，μ3=(0 20)T，Σ1=(30 0;0 20)，Σ2=(9 0;0 9)，Σ3=(10 0; 0 10)；数据集3：μ1=μ2=(-4 -4)T，μ3=(2 2)T，μ4=(-1 -6)T，Σ1=(1 0.5;0.5 1)，Σ2=(6 -2;-2 6)，Σ3=(2 -1;-1 2)，Σ4=(0.125 0;0 0.125)。

在3个高斯数据集上比较DP-GMMC与经典GMM算法以及REM-GMM、AHC-EM算法的聚类能力，其实验结果如表4所示。

从表4可以看出，4种算法在高斯数据集上表现出较高的聚类能力。在聚类中心选取上，本文算法可快速、准确得到聚类个数及聚类中心，相比于REM-GMM算法及AHC-EM算法需要多次迭代有很大的优势。对于数据集1，4个算法的正确率均可达到100%。而在另外两个数据集上，原始的GMM算法聚类效果较差，且标准差最大，因为GMM算法每次聚类时需随机选取聚类中心，中心点的好坏直接影响最后的聚类准确率，故每次的结果不稳定；REM-GMM算法虽然准确率有一定的提升，但因中心点的变化也导致每次的结果不稳定；本文算法相比于AHC-EM算法的聚类能力有少许的提升，稳定性也更优。

表4 4种算法在第二组数据集上的实验结果对比Tab. 4 Comparison of experimental results of 4 algorithms on second group of datasets

3.2 算法有效性实验

为验证本文所提出的融合密度峰值的高斯混合模型聚类算法(DP-GMMC)可得到最佳聚类数，本文采用三个内部指标进行仿真测试，分别为CH(Calinski-Harabasz)指标、DB(Davies-Bouldin)指标和Sil(Silhouette)指标，数据集采用第一组数据集。

CH指标通过类内离差矩阵描述紧密度，类间离差矩阵描述分离度，指标定义用式(12)表示为：

(12)

其中:k表示聚类的数目;i为当前的类;trB(i)表示类间离差矩阵的迹;trW(i)为类内离差矩阵的迹。CH值越大代表类自身越紧密，类与类之间越分散，即聚类效果更好。

DB指标描述样本的类内散度与各聚类中心的间距，其计算式如式(13)所示：

(13)

其中：Wi表示类Ci中的所有样本到其聚类中心的平均距离；Wj表示类Ci中的所有样本到类Cj中心的平均距离；Cij表示类Ci和Cj中心之间的距离。可以看出，DB值越小表示类与类之间的相似度越低，从而对应越优的聚类结果。

本文通过采用CH值和DB值的比值描述最佳聚类数，当比值越大，表明得到的聚类数为最佳值。

Sil指标通过描述簇内不相似度和簇间不相似度判断聚类效果的好坏，其计算式如式(14)所示：

(14)

其中：a(i)表示样本i到同簇其他样本的平均距离；b(i)为样本i到其他簇的所有样本的平均距离。

以数据集4k2_far为例，运用CH值和DB值的比值、Sil指标确定数据集最佳聚类数的情况分别如图3、图4所示。

图3和图4分别显示了运用CH指标、DB指标和Sil指标对数据集4k2_far的聚类数进行评估的情况。由图3和图4可以得到,最佳聚类数为4，对应的CH/DB指标值为1.356 5×104，Sil指标值为0.922 4。

图3 聚类数与CH/DB指标关系Fig. 3 Relationship of cluster number and CH/DB

图4 聚类数与Sil指标关系Fig. 4 Relationship of cluster number and Sil

几种有效性指标估计出的第一组数据集最佳聚类数情况如表5所示。

表5 第一组数据集的最佳聚类数Tab. 5 The optimal number of clusters on first datasets

从表5可知，对真实类数分别为4、7、2、2、3的数据集，运用CH、DB和Sil指标确定最佳聚类数，其中DB指标和Sil指标均能确定出5个数据集的最佳聚类数，而CH指标则不够稳定，得到的最佳聚类数不够准确。由此可见，本文算法通过DP算法对初始值进行寻优确实获得了准确的聚类个数，使用GMM算法可较好对数据点进行聚类，保证类内的距离较远而类间的距离较近。而DP-GMMC既保证了聚类中心个数的确定又可进行准确的聚类。

3.3 算法的纯净度分析

纯净度标志着某一个聚类结果包含预先定义的某一个类别数据多少的程度，整个划分的纯净度是所有簇纯净度的均值，其计算式如式(15)所示：

(15)

其中：k为簇类数；Ni是Ci中类标识数目；Nti代表该簇中标识为t的数目。P(C)值越大表示聚类效果越好。

本实验选取Iris数据集进行50次实验，然后从50次中选取聚类效果较好的3次，分别求它们的聚类纯净度，最后对比5个算法的聚类纯净度，结果如表6所示。由表6结果可以得出本文算法在聚类稳定性和有效性方面确实具有优异性。

从表6可以看出， GMM算法应用于Iris数据集时受初始值随机选取的影响很大，全局搜索能力差，导致聚类的纯净度相对较小；DP算法引入了局部密度和距离策略可以较快地得到聚类中心，但算法聚类效果较差，导致很难达到全局最优解；REM-GMM算法使成分数初值等于样本个数，再对成分的混合系数施加熵惩罚算子，在迭代中根据一定的准则自动减少成分数，使得算法迭代不依赖于初始成分数，但全局搜索能力不明显，使得聚类结果不理想；AHC-EM算法采用自适应层次聚类算法来确定GMM算法的初始值，此方法可避免随机选取聚类中心的缺陷，提高了聚类纯净度;DP-GMMC通过采用DP算法对初始值进行寻优可获得较好的聚类效果，从而避免了初始值敏感、易陷入局部最优解等问题，有效地提高了聚类纯净度。

表6 5种算法纯净度比较Tab. 6 Purity comparison of five algorithms

4 结语

根据密度峰值优化理论和GMM算法各自存在的缺陷，本文提出了一种融合密度峰值的高斯混合模型聚类算法(DP-GMMC)。DP算法在初始化阶段对全局空间进行寻优，当得到最优的初始值时转向GMM算法以取得最快的收敛。该算法克服了传统聚类算法对初始值敏感、易陷入局部最优等问题，大量的实验结果表明本文算法在性能上优于DP、GMM、REM-GMM及AHC-EM聚类算法，能够有效地对数据点进行聚类。目前本文算法对于低维数据集聚类效果较好，但对于高维数据集及分布不规范的数据集聚类效果仍待研究，同时如何降低算法时间复杂度、提高算法速度、提升在高维数据集上的运算能力都将是下一步重点研究的方向。