融合密度峰值的高斯混合模型聚類(lèi)算法

陶志勇，劉曉芳,2，王和章

(1.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105; 2.阜新力興科技有限責(zé)任公司, 遼寧 阜新 123000)(*通信作者電子郵箱1367251096@qq.com)

0 引言

大數(shù)據(jù)信息處理過(guò)程中的關(guān)鍵步驟就是對(duì)數(shù)據(jù)聚類(lèi)，也就是將大數(shù)據(jù)中同類(lèi)屬性對(duì)應(yīng)的關(guān)鍵特征參數(shù)進(jìn)行科學(xué)、系統(tǒng)、準(zhǔn)確的挖掘，進(jìn)而實(shí)現(xiàn)對(duì)大數(shù)據(jù)的分析、統(tǒng)計(jì)、研究。當(dāng)前階段，常見(jiàn)的大數(shù)據(jù)庫(kù)、專(zhuān)家系統(tǒng)等均以數(shù)據(jù)聚類(lèi)為依據(jù)，為廣大使用客戶(hù)提供診斷分析、模式判斷等相關(guān)的服務(wù)[1]。查閱大量文獻(xiàn)資料可知，相關(guān)研究人員已經(jīng)將數(shù)據(jù)聚類(lèi)作為數(shù)據(jù)挖掘的關(guān)鍵與核心研究方向，經(jīng)過(guò)長(zhǎng)期的分析研究已經(jīng)取得了一定成果，最具代表性的就是聚類(lèi)算法，例如：常見(jiàn)的K均值聚類(lèi)[2]、模糊C均值聚類(lèi)[3]、核密度聚類(lèi)[4]及構(gòu)建有限混合模型[5]聚類(lèi)等。

經(jīng)過(guò)近些年的深入分析與研究，高斯混合模型(Gaussian Mixture Model, GMM)算法發(fā)展非常迅猛，然而它的缺陷也非常明顯，很多研究人員對(duì)其進(jìn)行改進(jìn)，并給出了新型的GMM算法，如：Yang等[6]提出了一種魯棒的有限高斯混合模型聚類(lèi)算法，該算法直接將系統(tǒng)的初始模型相關(guān)參量作為原始樣本的總數(shù)，同時(shí)對(duì)信息熵懲罰因子加入分量混合系數(shù)，雖然該算法不必隨機(jī)選取初始值，但實(shí)驗(yàn)結(jié)果表明此算法聚類(lèi)準(zhǔn)確率不高且運(yùn)行時(shí)間長(zhǎng)；Saravia等[7]提出了一種分裂合并的馬爾可夫鏈蒙特卡洛(Markov Chain Monte Carlo, MCMC)方法用于聚類(lèi)個(gè)數(shù)的確定，該方法可準(zhǔn)確得到聚類(lèi)個(gè)數(shù)，但實(shí)現(xiàn)過(guò)程較為復(fù)雜；崔瑋等[8]將GMM算法用于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)室內(nèi)節(jié)點(diǎn)定位，采用粒子群算法對(duì)最大期望(Expectation Maximization, EM)算法進(jìn)行優(yōu)化，同時(shí)結(jié)合優(yōu)選殘差加權(quán)算法對(duì)距離值進(jìn)行定位估計(jì)，此方法對(duì)節(jié)點(diǎn)定位有一定的適用性，但所提的GMM算法在初始化階段采用K均值算法，具有一定的隨機(jī)性，所得到的聚類(lèi)效果不理想；王垚等[9]將逆模擬退火算法與半監(jiān)督高斯混合模型中的EM算法相結(jié)合，與傳統(tǒng)的高斯混合模型EM算法相比收斂速度快、準(zhǔn)確率高，但差于融合密度峰值的GMM聚類(lèi)算法(Clustering algorithm of GMM based on Density Peaks, DP-GMMC)聚類(lèi)結(jié)果，且處理大規(guī)模數(shù)據(jù)集的能力較弱；Scrucca[10]采用密度估計(jì)的方法得到聚類(lèi)中心，再利用EM算法進(jìn)行計(jì)算，該方法可發(fā)現(xiàn)非高斯集群，但算法的開(kāi)銷(xiāo)很大;Li等[11]采用自適應(yīng)的層次聚類(lèi)方法用于GMM算法初始值的確定，相比經(jīng)典的GMM算法具有較強(qiáng)的聚類(lèi)能力，但隨著數(shù)據(jù)量的增大，此方法尋優(yōu)迭代次數(shù)也會(huì)大幅度增加。利用高斯混合模型聚類(lèi)時(shí)，若樣本屬于不完全數(shù)據(jù)，通常采用EM算法求解最大似然值，而EM算法收斂速度慢，系統(tǒng)模型計(jì)算過(guò)程中對(duì)初始值的設(shè)置非常敏感，故而容易收斂到局部最優(yōu)解。通過(guò)對(duì)大量相關(guān)研究的分析與總結(jié)可知，部分研究已經(jīng)對(duì)EM算法的混合模型等多種估算問(wèn)題進(jìn)行分析與探究，并取得了一定成果，如：Liu等[12]將GMM算法用于基因聚類(lèi)，為了解決EM算法初始化的問(wèn)題，通過(guò)添加和刪除EM算法的初始值，把簇的數(shù)量作為已知參數(shù)并且采用準(zhǔn)赤池信息準(zhǔn)則(Quasi Akaike Information Criterion, QAIC)，改進(jìn)后的算法在基因聚類(lèi)上有一定的效果；Li等[13]則通過(guò)K最近鄰(K-Nearest Neighbors,KNN)算法刪除異常值，再使用K均值初始化EM算法，但聚類(lèi)對(duì)應(yīng)的個(gè)數(shù)是不確定的，而且設(shè)置過(guò)程比較復(fù)雜。

密度峰值聚類(lèi)算法[14]將具有局部極大密度估計(jì)值的樣本點(diǎn)視為聚類(lèi)中心，通過(guò)對(duì)模型聚類(lèi)中心的快速搜索，并將每一個(gè)非中心樣本點(diǎn)沿著密度遞增的最近鄰方向迭代劃分給相應(yīng)的聚類(lèi)中心，進(jìn)而實(shí)現(xiàn)對(duì)大數(shù)據(jù)的分類(lèi)。然而，該算法中ρ和δ值的分布依賴(lài)于截?cái)嗑嚯x參數(shù)dc，算法聚類(lèi)的質(zhì)量受參數(shù)dc的影響。本文針對(duì)此問(wèn)題進(jìn)行了改進(jìn)，根據(jù)μ律15折線(xiàn)的方法對(duì)數(shù)據(jù)點(diǎn)之間的距離進(jìn)行壓縮，避免了參數(shù)dc對(duì)數(shù)據(jù)聚類(lèi)的影響。鑒于GMM和DP算法各自的優(yōu)缺點(diǎn)，本文提出了一種融合密度峰值的高斯混合模型聚類(lèi)算法(DP-GMMC)。首先，利用改進(jìn)后的密度峰值算法對(duì)聚類(lèi)中心進(jìn)行自動(dòng)查找，再將得到的聚類(lèi)中心作為GMM算法的初值，最后完成數(shù)據(jù)點(diǎn)的聚類(lèi)。本文的工作主要是在DP算法中引入了μ律15折線(xiàn)，減弱了人工選擇參數(shù)對(duì)結(jié)果的干擾，并將DP算法應(yīng)用在標(biāo)準(zhǔn)GMM算法初始值確定上，通過(guò)密度峰值自動(dòng)確定聚類(lèi)數(shù)，提高了原始算法的聚類(lèi)能力。

1 高斯混合模型

設(shè){x1,x2,…,xn|x∈Rd}為隨機(jī)變量x的n個(gè)隨機(jī)樣本值，則含有k個(gè)成分的d變量混合模型的概率密度函數(shù)表示如式(1)所示：

(1)

若隨機(jī)變量θj∈{1,2,…,k}表示生成樣本xj的高斯混合分布，其取值未知。顯然，θj的先驗(yàn)概率P(θj=i)對(duì)應(yīng)于ζi(i=1,2,…,k)，根據(jù)貝葉斯定理，θj的后驗(yàn)分布對(duì)應(yīng)于：

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

(2)

由式(2)可知，gM(θj=i|xj)給出了樣本xj由第i個(gè)高斯混合成分生成的后驗(yàn)概率。

假設(shè)所有分布具有相同的函數(shù)形式(例如服從d個(gè)隨機(jī)變量的高斯分布)，其特性由參數(shù)向量μi、Σi和ζi決定。設(shè)一組n個(gè)獨(dú)立同分布樣本x={x1,x2,…,xn}，對(duì)應(yīng)的對(duì)數(shù)似然值如式(3)所示：

(3)

借助EM計(jì)算方法[15]進(jìn)行極大似然估計(jì)，其對(duì)應(yīng)的計(jì)算步驟如下：

1)初始化：根據(jù)得到的聚類(lèi)中心計(jì)算混合模型中各密度分布待估計(jì)參數(shù)μi、Σi、ζi的初始值設(shè)置。

2)E步：計(jì)算第m次迭代每個(gè)樣本點(diǎn)i屬于第j類(lèi)的后驗(yàn)概率gM(θj=i|xj)。

3)M步：計(jì)算樣本數(shù)據(jù)似然函數(shù)的期望值方程達(dá)到最大值時(shí)的結(jié)果，得到用于下一次迭代的新參數(shù)μi′、Σi′和ζi′。

4)收斂條件：不斷迭代E步和M步，重復(fù)更新參數(shù)直至變化不顯著，否則轉(zhuǎn)第2)步。

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

EM算法能夠?qū)⒛繕?biāo)樣本與高斯混合模型(GMM)進(jìn)行有效的融合，進(jìn)而獲得最佳的擬合數(shù)據(jù)。該處理方式與傳統(tǒng)的GMM計(jì)算方法有著本質(zhì)的區(qū)別，傳統(tǒng)方法一般對(duì)數(shù)學(xué)模型的相關(guān)參數(shù)進(jìn)行預(yù)設(shè)，進(jìn)而直接導(dǎo)致擬合效果與數(shù)據(jù)樣本有一定程度的差異，效果不穩(wěn)定、不精確。針對(duì)上述問(wèn)題，本文設(shè)計(jì)了一種新型的GMM算法，該算法的核心就是將系統(tǒng)原始數(shù)據(jù)依據(jù)密度峰值(DP)算法對(duì)其距離與密度進(jìn)行有效估算，進(jìn)而選擇聚類(lèi)中心，再利用GMM算法對(duì)剩余數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)。

2.1 DP算法原理

DP算法實(shí)際計(jì)算過(guò)程中對(duì)密度峰值進(jìn)行檢索與發(fā)現(xiàn)，將具有局部最大密度值的樣本點(diǎn)作為聚類(lèi)中心，快速實(shí)現(xiàn)樣本數(shù)據(jù)的劃分，待確定的聚類(lèi)中心一般包括以下兩個(gè)特征：1)本身的密度大; 2)與其他密度更大的數(shù)據(jù)點(diǎn)的距離更大。

為了準(zhǔn)確找到聚類(lèi)中心，該算法引入樣本i的局部密度ρi和到局部密度比它大且距離它最近的樣本j的距離δi，其定義如式(4)～(6)所示：

(4)

其中:dij=dist(xi,xj)為樣本i、j間的歐氏距離;dc為截?cái)嗑嚯x。

(5)

對(duì)于局部密度ρi最大的樣本i，其δi如下：

(6)

根據(jù)式(4)可以看出，計(jì)算密度時(shí)均需要確定dc值，這對(duì)聚類(lèi)中心的確定有一定的影響，為此本文采用μ律15折線(xiàn)的方法對(duì)樣本點(diǎn)之間的距離dij進(jìn)行壓縮，每個(gè)樣本點(diǎn)i的ρ值為剩余樣本點(diǎn)到i點(diǎn)的壓縮距離之和，其計(jì)算式如下：

(7)

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

根據(jù)式(5)對(duì)樣本點(diǎn)i的距離δi的實(shí)際定義，假設(shè)i的密度ρi是全局最大密度，那么i的δi會(huì)遠(yuǎn)大于其他樣本的δ。因此，類(lèi)簇中心往往是δ異常大的樣本點(diǎn)，這些樣本點(diǎn)的密度也相對(duì)較大。

故DP算法提供了一種啟發(fā)式方法，即通過(guò)計(jì)算ρ和δ的決策圖(如圖1)來(lái)選擇預(yù)期聚類(lèi)中心，其中聚類(lèi)中心與其他聚類(lèi)點(diǎn)相比具有更大的ρ值和δ值，根據(jù)決策圖中的ρ和δ來(lái)判斷聚類(lèi)中心。

圖1 節(jié)點(diǎn)決策圖Fig. 1 Decision graph of node

在本算法中聚類(lèi)中心可以自動(dòng)確定，將ρ值和δ值綜合考慮，其計(jì)算式可以用式(8)表示：

γi=ρi×δi

(8)

由式(8)可知，數(shù)值γ越大，則xi屬于數(shù)據(jù)中心點(diǎn)的可能性越大。因此，本文將γ進(jìn)行降序排列，截取若干聚類(lèi)中心點(diǎn)，具體變化見(jiàn)圖2,選擇橫軸作為系統(tǒng)的指標(biāo)集，并將系統(tǒng)的γ作為縱軸。由圖2可知，非聚類(lèi)中心對(duì)應(yīng)的γ數(shù)值較為平滑，由非聚類(lèi)中心向聚類(lèi)中心進(jìn)行過(guò)渡時(shí)，γ存在極其明顯的跳躍現(xiàn)象，通過(guò)跳躍點(diǎn)，即可找尋數(shù)據(jù)各類(lèi)對(duì)應(yīng)的中心點(diǎn)。

圖2 γ決策圖Fig. 2 Decision graph of γ

2.2 DP-GMMC

GMM算法具體應(yīng)用過(guò)程中存在一定缺陷，為解決此問(wèn)題，本文選擇DP算法對(duì)其初始值預(yù)設(shè)過(guò)程進(jìn)行優(yōu)化。DP-GMMC的核心工作為：首先，DP算法對(duì)系統(tǒng)樣本對(duì)應(yīng)的聚類(lèi)中心、個(gè)數(shù)進(jìn)行明確，以獲取平均數(shù)值，進(jìn)而得出對(duì)應(yīng)類(lèi)的協(xié)方差矩陣，構(gòu)建系統(tǒng)的初始參數(shù)；然后，借助EM進(jìn)行預(yù)估，構(gòu)建混合密度數(shù)學(xué)模型；最后，根據(jù)貝葉斯準(zhǔn)則對(duì)樣本概率進(jìn)行驗(yàn)算。該算法能夠降低局部搜索迭代次數(shù)，增加初始化多樣性，有效克服傳統(tǒng)GMM算法存在的缺陷。

DP-GMMC的具體步驟如下所示：

輸入 樣本數(shù)據(jù)集χ，迭代停止閾值η；

輸出 簇劃分C={C1,C2,…,Ck}。

步驟1 基于數(shù)據(jù)點(diǎn)的距離dij，構(gòu)建相似度矩陣。

步驟2 根據(jù)相似度矩陣計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度ρ，并計(jì)算數(shù)據(jù)點(diǎn)的高密度距離δ。

步驟3 使用決策圖選取聚類(lèi)個(gè)數(shù)k以及聚類(lèi)中心集合{v1,v2,…,vk}。

步驟4 利用聚類(lèi)中心集合初始化均值向量μi、協(xié)方差矩陣Σi及高斯混合分布的模型參數(shù)ζi，根據(jù)式(1)計(jì)算xj由各混合成分生成的后驗(yàn)概率，即gM(θj=i|xj)。

步驟5 根據(jù)式(9)～(11)計(jì)算新均值向量μi′、協(xié)方差矩陣Σi′和混合系數(shù)ζi′。

(9)

(10)

(11)

步驟7 確定xj的簇標(biāo)記ζj，將xj劃入相應(yīng)的簇。

2.3 算法時(shí)間復(fù)雜度分析

DP-GMMC時(shí)間復(fù)雜度由兩部分組成，即DP算法時(shí)間復(fù)雜度和GMM算法時(shí)間復(fù)雜度。使用改進(jìn)后DP算法自動(dòng)確定聚類(lèi)中心過(guò)程中，計(jì)算參數(shù)dij、采用μ律15折線(xiàn)得到的ρi以及δi，時(shí)間復(fù)雜度均為O(N2)，其中N為數(shù)據(jù)點(diǎn)的個(gè)數(shù)；然后，計(jì)算ρi和δi的歸一化乘積γi，并將γi按降序排列，時(shí)間復(fù)雜度分別為O(N)和O(klogk)，其中k為候選聚類(lèi)中心個(gè)數(shù)。因此DP算法的時(shí)間復(fù)雜度為：O(N2+N2+N2+N+klogk)=O(N2)。相比于GMM算法，初始聚類(lèi)中心確定過(guò)程增加的時(shí)間復(fù)雜度為O(N2)，同時(shí)初始值率先選取有利于減小GMM算法的迭代次數(shù)，總體看來(lái)本文算法增加了一定的時(shí)間開(kāi)銷(xiāo)，有待于下一步的研究改進(jìn)。

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證DP-GMMC的有效性，將本文算法與經(jīng)典的DP、GMM算法、文獻(xiàn)[6]的魯棒GMM的EM聚類(lèi)(Robust EM for GMM, REM-GMM)算法及文獻(xiàn)[11]的層次EM聚類(lèi)(EM via Adaptive Hierarchical Clustering, AHC-EM)算法進(jìn)行實(shí)驗(yàn)仿真，分別從算法準(zhǔn)確度、有效性、純凈度方面對(duì)5個(gè)算法的性能進(jìn)行了分析和比較。實(shí)驗(yàn)仿真環(huán)境為Pentium E53002，內(nèi)存為2 GB，操作系統(tǒng)為Windows 7，仿真軟件為Matlab 2015a。

3.1 算法準(zhǔn)確度實(shí)驗(yàn)

此次實(shí)驗(yàn)分兩組數(shù)據(jù)集進(jìn)行，第一組數(shù)據(jù)集是來(lái)自UCI的Breast cancer、Indian Liver、Iris數(shù)據(jù)集以及聚類(lèi)常用4k2_far、Aggregation數(shù)據(jù)集，其數(shù)據(jù)集屬性如表1所示。

表1 第一組數(shù)據(jù)集屬性Tab. 1 Properties of first group of datasets

此外，基于5組標(biāo)準(zhǔn)數(shù)據(jù)集分別對(duì)4種算法進(jìn)行50次仿真實(shí)驗(yàn)，所得的平均聚類(lèi)準(zhǔn)確率和標(biāo)準(zhǔn)差如表2所示。

根據(jù)表2的實(shí)驗(yàn)結(jié)果可知，本文算法在5個(gè)數(shù)據(jù)集上均獲得了較高的聚類(lèi)準(zhǔn)確率，在Iris數(shù)據(jù)集下的平均聚類(lèi)準(zhǔn)確率可達(dá)到96.67%，相比于傳統(tǒng)GMM算法提高了33.6個(gè)百分點(diǎn)。DP算法是基于密度的聚類(lèi)算法，對(duì)于聚類(lèi)中心的選取較準(zhǔn)確，但后期的聚類(lèi)能力較差，導(dǎo)致聚類(lèi)準(zhǔn)確率不高；GMM算法對(duì)于初值非常敏感，每次迭代隨機(jī)選取聚類(lèi)中心導(dǎo)致聚類(lèi)效果很差；AHC-EM算法采用基于層次算法對(duì)初值中心進(jìn)行尋優(yōu)，相比于前兩種算法有確定聚類(lèi)中心、增強(qiáng)聚類(lèi)能力的優(yōu)勢(shì)，但層次聚類(lèi)相比于密度聚類(lèi)算法迭代速度慢、尋優(yōu)精度低，導(dǎo)致最終在數(shù)據(jù)集上的聚類(lèi)準(zhǔn)確率低于DP-GMMC；而DP-GMMC則同時(shí)兼具了DP算法全局搜索能力強(qiáng)以及GMM算法局部搜索能力強(qiáng)的優(yōu)勢(shì)，聚類(lèi)準(zhǔn)確率最高，聚類(lèi)識(shí)別效果也最好。從標(biāo)準(zhǔn)差也可看出DP-GMMC每次運(yùn)行結(jié)果較穩(wěn)定，變化不大。

表2 4種算法第一組數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比Tab. 2 Comparison of experimental results of 4 algorithms on first group of datasets

第二組實(shí)驗(yàn)所采用的數(shù)據(jù)集是3組高斯數(shù)據(jù)集，數(shù)據(jù)集屬性如表3所示。

表3 第二組數(shù)據(jù)集屬性Tab. 3 Properties of second group of datasets

其中,數(shù)據(jù)集1：μ1=(0 0)T，μ2=(20 0)T，Σ1=(1 0;0 1)，Σ2=(9 0;0 9);數(shù)據(jù)集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)；數(shù)據(jù)集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個(gè)高斯數(shù)據(jù)集上比較DP-GMMC與經(jīng)典GMM算法以及REM-GMM、AHC-EM算法的聚類(lèi)能力，其實(shí)驗(yàn)結(jié)果如表4所示。

從表4可以看出，4種算法在高斯數(shù)據(jù)集上表現(xiàn)出較高的聚類(lèi)能力。在聚類(lèi)中心選取上，本文算法可快速、準(zhǔn)確得到聚類(lèi)個(gè)數(shù)及聚類(lèi)中心，相比于REM-GMM算法及AHC-EM算法需要多次迭代有很大的優(yōu)勢(shì)。對(duì)于數(shù)據(jù)集1，4個(gè)算法的正確率均可達(dá)到100%。而在另外兩個(gè)數(shù)據(jù)集上，原始的GMM算法聚類(lèi)效果較差，且標(biāo)準(zhǔn)差最大，因?yàn)镚MM算法每次聚類(lèi)時(shí)需隨機(jī)選取聚類(lèi)中心，中心點(diǎn)的好壞直接影響最后的聚類(lèi)準(zhǔn)確率，故每次的結(jié)果不穩(wěn)定；REM-GMM算法雖然準(zhǔn)確率有一定的提升，但因中心點(diǎn)的變化也導(dǎo)致每次的結(jié)果不穩(wěn)定；本文算法相比于AHC-EM算法的聚類(lèi)能力有少許的提升，穩(wěn)定性也更優(yōu)。

表4 4種算法在第二組數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比Tab. 4 Comparison of experimental results of 4 algorithms on second group of datasets

3.2 算法有效性實(shí)驗(yàn)

為驗(yàn)證本文所提出的融合密度峰值的高斯混合模型聚類(lèi)算法(DP-GMMC)可得到最佳聚類(lèi)數(shù)，本文采用三個(gè)內(nèi)部指標(biāo)進(jìn)行仿真測(cè)試，分別為CH(Calinski-Harabasz)指標(biāo)、DB(Davies-Bouldin)指標(biāo)和Sil(Silhouette)指標(biāo)，數(shù)據(jù)集采用第一組數(shù)據(jù)集。

CH指標(biāo)通過(guò)類(lèi)內(nèi)離差矩陣描述緊密度，類(lèi)間離差矩陣描述分離度，指標(biāo)定義用式(12)表示為：

(12)

其中:k表示聚類(lèi)的數(shù)目;i為當(dāng)前的類(lèi);trB(i)表示類(lèi)間離差矩陣的跡;trW(i)為類(lèi)內(nèi)離差矩陣的跡。CH值越大代表類(lèi)自身越緊密，類(lèi)與類(lèi)之間越分散，即聚類(lèi)效果更好。

DB指標(biāo)描述樣本的類(lèi)內(nèi)散度與各聚類(lèi)中心的間距，其計(jì)算式如式(13)所示：

(13)

其中：Wi表示類(lèi)Ci中的所有樣本到其聚類(lèi)中心的平均距離；Wj表示類(lèi)Ci中的所有樣本到類(lèi)Cj中心的平均距離；Cij表示類(lèi)Ci和Cj中心之間的距離?？梢钥闯?，DB值越小表示類(lèi)與類(lèi)之間的相似度越低，從而對(duì)應(yīng)越優(yōu)的聚類(lèi)結(jié)果。

本文通過(guò)采用CH值和DB值的比值描述最佳聚類(lèi)數(shù)，當(dāng)比值越大，表明得到的聚類(lèi)數(shù)為最佳值。

Sil指標(biāo)通過(guò)描述簇內(nèi)不相似度和簇間不相似度判斷聚類(lèi)效果的好壞，其計(jì)算式如式(14)所示：

(14)

其中：a(i)表示樣本i到同簇其他樣本的平均距離；b(i)為樣本i到其他簇的所有樣本的平均距離。

以數(shù)據(jù)集4k2_far為例，運(yùn)用CH值和DB值的比值、Sil指標(biāo)確定數(shù)據(jù)集最佳聚類(lèi)數(shù)的情況分別如圖3、圖4所示。

圖3和圖4分別顯示了運(yùn)用CH指標(biāo)、DB指標(biāo)和Sil指標(biāo)對(duì)數(shù)據(jù)集4k2_far的聚類(lèi)數(shù)進(jìn)行評(píng)估的情況。由圖3和圖4可以得到,最佳聚類(lèi)數(shù)為4，對(duì)應(yīng)的CH/DB指標(biāo)值為1.356 5×104，Sil指標(biāo)值為0.922 4。

圖3 聚類(lèi)數(shù)與CH/DB指標(biāo)關(guān)系Fig. 3 Relationship of cluster number and CH/DB

圖4 聚類(lèi)數(shù)與Sil指標(biāo)關(guān)系Fig. 4 Relationship of cluster number and Sil

幾種有效性指標(biāo)估計(jì)出的第一組數(shù)據(jù)集最佳聚類(lèi)數(shù)情況如表5所示。

表5 第一組數(shù)據(jù)集的最佳聚類(lèi)數(shù)Tab. 5 The optimal number of clusters on first datasets

從表5可知，對(duì)真實(shí)類(lèi)數(shù)分別為4、7、2、2、3的數(shù)據(jù)集，運(yùn)用CH、DB和Sil指標(biāo)確定最佳聚類(lèi)數(shù)，其中DB指標(biāo)和Sil指標(biāo)均能確定出5個(gè)數(shù)據(jù)集的最佳聚類(lèi)數(shù)，而CH指標(biāo)則不夠穩(wěn)定，得到的最佳聚類(lèi)數(shù)不夠準(zhǔn)確。由此可見(jiàn)，本文算法通過(guò)DP算法對(duì)初始值進(jìn)行尋優(yōu)確實(shí)獲得了準(zhǔn)確的聚類(lèi)個(gè)數(shù)，使用GMM算法可較好對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)，保證類(lèi)內(nèi)的距離較遠(yuǎn)而類(lèi)間的距離較近。而DP-GMMC既保證了聚類(lèi)中心個(gè)數(shù)的確定又可進(jìn)行準(zhǔn)確的聚類(lèi)。

3.3 算法的純凈度分析

純凈度標(biāo)志著某一個(gè)聚類(lèi)結(jié)果包含預(yù)先定義的某一個(gè)類(lèi)別數(shù)據(jù)多少的程度，整個(gè)劃分的純凈度是所有簇純凈度的均值，其計(jì)算式如式(15)所示：

(15)

其中：k為簇類(lèi)數(shù)；Ni是Ci中類(lèi)標(biāo)識(shí)數(shù)目；Nti代表該簇中標(biāo)識(shí)為t的數(shù)目。P(C)值越大表示聚類(lèi)效果越好。

本實(shí)驗(yàn)選取Iris數(shù)據(jù)集進(jìn)行50次實(shí)驗(yàn)，然后從50次中選取聚類(lèi)效果較好的3次，分別求它們的聚類(lèi)純凈度，最后對(duì)比5個(gè)算法的聚類(lèi)純凈度，結(jié)果如表6所示。由表6結(jié)果可以得出本文算法在聚類(lèi)穩(wěn)定性和有效性方面確實(shí)具有優(yōu)異性。

從表6可以看出， GMM算法應(yīng)用于Iris數(shù)據(jù)集時(shí)受初始值隨機(jī)選取的影響很大，全局搜索能力差，導(dǎo)致聚類(lèi)的純凈度相對(duì)較?。籇P算法引入了局部密度和距離策略可以較快地得到聚類(lèi)中心，但算法聚類(lèi)效果較差，導(dǎo)致很難達(dá)到全局最優(yōu)解；REM-GMM算法使成分?jǐn)?shù)初值等于樣本個(gè)數(shù)，再對(duì)成分的混合系數(shù)施加熵懲罰算子，在迭代中根據(jù)一定的準(zhǔn)則自動(dòng)減少成分?jǐn)?shù)，使得算法迭代不依賴(lài)于初始成分?jǐn)?shù)，但全局搜索能力不明顯，使得聚類(lèi)結(jié)果不理想；AHC-EM算法采用自適應(yīng)層次聚類(lèi)算法來(lái)確定GMM算法的初始值，此方法可避免隨機(jī)選取聚類(lèi)中心的缺陷，提高了聚類(lèi)純凈度;DP-GMMC通過(guò)采用DP算法對(duì)初始值進(jìn)行尋優(yōu)可獲得較好的聚類(lèi)效果，從而避免了初始值敏感、易陷入局部最優(yōu)解等問(wèn)題，有效地提高了聚類(lèi)純凈度。

表6 5種算法純凈度比較Tab. 6 Purity comparison of five algorithms

4 結(jié)語(yǔ)

根據(jù)密度峰值優(yōu)化理論和GMM算法各自存在的缺陷，本文提出了一種融合密度峰值的高斯混合模型聚類(lèi)算法(DP-GMMC)。DP算法在初始化階段對(duì)全局空間進(jìn)行尋優(yōu)，當(dāng)?shù)玫阶顑?yōu)的初始值時(shí)轉(zhuǎn)向GMM算法以取得最快的收斂。該算法克服了傳統(tǒng)聚類(lèi)算法對(duì)初始值敏感、易陷入局部最優(yōu)等問(wèn)題，大量的實(shí)驗(yàn)結(jié)果表明本文算法在性能上優(yōu)于DP、GMM、REM-GMM及AHC-EM聚類(lèi)算法，能夠有效地對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)。目前本文算法對(duì)于低維數(shù)據(jù)集聚類(lèi)效果較好，但對(duì)于高維數(shù)據(jù)集及分布不規(guī)范的數(shù)據(jù)集聚類(lèi)效果仍待研究，同時(shí)如何降低算法時(shí)間復(fù)雜度、提高算法速度、提升在高維數(shù)據(jù)集上的運(yùn)算能力都將是下一步重點(diǎn)研究的方向。