基于子簇融合和線性判別分析的密度峰值聚類算法*

劉小康, 張 菁 , 張延遲

(1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院,上海201620； 2.上海電機(jī)學(xué)院 電氣學(xué)院,上海 200240)

0 引 言

聚類屬于無監(jiān)督分類,根據(jù)樣本點(diǎn)的相似度將對(duì)象劃分成簇。最經(jīng)典聚類方法K-means[1]應(yīng)用最為廣泛。但是,基于K-means的聚類結(jié)果對(duì)初始選擇的聚類中心非常敏感,而且無法區(qū)分噪聲點(diǎn)和距離。Ester M等人[2]提出基于密度的聚類算法——BSCAN聚類算法,能夠有效處理噪聲點(diǎn)。但是DBSCAN算法往往距離度量為歐氏距離,對(duì)于高維數(shù)據(jù)集會(huì)帶來維度災(zāi)難。

Rodriguez A等人[3]提出密度峰值聚類(dcnsity peak clustering,DPC)算法,該算法簡(jiǎn)單高效,可快速找到高密度峰值點(diǎn)；但算法在處理不同密度或高維數(shù)據(jù)集時(shí)聚類結(jié)果較差,并且算法容錯(cuò)能力差。因此提出一些相關(guān)的改進(jìn)算法。何洋等人[4]提出一種融合K近鄰的改進(jìn)的DPC算法,算法引入K近鄰和關(guān)聯(lián)系數(shù),有效解決了數(shù)據(jù)密度不均衡的問題。文獻(xiàn)[5]認(rèn)為將剩余樣本點(diǎn)按局部密度降序分配給與其最近鄰密度較高的簇容易引起簇標(biāo)錯(cuò)誤傳播,提出一種基于加權(quán)局部密度序列和最近鄰分配的DPC方法,引入加權(quán)局部密度序列和兩階段分配策略提高聚類效率。文獻(xiàn)[6]提出一種基于非負(fù)矩陣分解和改進(jìn)的DPC的社區(qū)檢測(cè)算法,克服了算法在高維數(shù)據(jù)集上聚類不佳的缺陷。文獻(xiàn)[7]提出一種基于支持向量機(jī)(support vector machine,SVM)的子簇融合(sub-cluster fusion,SCF)策略,將SVM和DPC算法結(jié)合,通過計(jì)算每個(gè)聚類結(jié)果之間的反饋值,根據(jù)反饋值進(jìn)行子簇融合。文獻(xiàn)[8]認(rèn)為DPC中沒有考慮數(shù)據(jù)原始特征,提出考慮數(shù)據(jù)的原始拓?fù)涮卣鞯腄PC算法,顯著提高了聚類效果。然而上述模型仍然存在以下缺點(diǎn)：算法中通常采用歐氏距離來計(jì)算樣本點(diǎn)之間的距離,容易忽略樣本之間的相關(guān)性。在子簇融合時(shí)容錯(cuò)性差,并且在高維數(shù)據(jù)集上不能產(chǎn)生有效的聚類結(jié)果。

本文提出一種基于SCF和線性判別分析(linear discriminant analysis,LDA)的DPC算法。重新定義了局部密度ρi計(jì)算函數(shù)。提出利用Pearson相關(guān)系數(shù)絕對(duì)值的倒數(shù)作為權(quán)值的加權(quán)歐氏距離來度量樣本點(diǎn)間的距離。將SCF算法與DPC算法結(jié)合,提高算法容錯(cuò)性。引入LDA算法,對(duì)高維數(shù)據(jù)降維,提高算法在高維數(shù)據(jù)集上聚類精度和有效性。

1 DPC算法

DPC算法核心是[9]計(jì)算樣本點(diǎn)局部密度和到鄰近最大密度的距離,以距離最近較大密度點(diǎn)的距離作為聚類中心,并根據(jù)密度對(duì)其余點(diǎn)劃分融合。主要步驟為：對(duì)于樣本點(diǎn)xi∈X,X={x1,x2,…,xn},定義點(diǎn)xi的局部密度ρi為

(1)

式中dij為樣本點(diǎn)xi與xj的距離,dc為截止距離。

樣本點(diǎn)xi到高密度點(diǎn)的最近鄰距離δi定義為

(2)

局部或全局密度高樣本點(diǎn)不存在高密度鄰近,與最近的較大密度點(diǎn)的距離定義為

(3)

以γi作為選擇聚類中心的指標(biāo),γi計(jì)算公式為

γi=ρiδi

(4)

2 SCF-LDA-DPC算法

2.1 加權(quán)歐氏距離

針對(duì)DPC算法并未考慮數(shù)據(jù)局部結(jié)構(gòu)特征和樣本相關(guān)性問題,引入基于Pearson相關(guān)系數(shù)的加權(quán)高斯核密度估計(jì)函數(shù)計(jì)算每個(gè)采樣點(diǎn)局部密度。

定義1基于高斯核密度估計(jì)函數(shù),樣本點(diǎn)的局部密度公式定義為

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

(5)

式中dij為樣本點(diǎn)xi與xj的距離。

定義2Pearson相關(guān)系數(shù)是度量屬性之間相關(guān)性的常用標(biāo)準(zhǔn),其公式為

(6)

式中 當(dāng)Pearson相關(guān)系數(shù)rxy=±1時(shí),樣本x和y相關(guān)；當(dāng)rxy=0時(shí),樣本x和y無關(guān)。

定義3引入Pearson相關(guān)系數(shù)絕對(duì)值的倒數(shù)作為權(quán)重重新定義加權(quán)歐氏距離函數(shù)為

(7)

式中xi,xj為樣本數(shù)據(jù)的特征值。

定義4由于樣本之間的距離由加權(quán)歐氏距離函數(shù)計(jì)算,因此基于Pearson相關(guān)系數(shù)的樣本局部密度計(jì)算公式為

(8)

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

傳統(tǒng)DPC算法根據(jù)γi最大值確定聚類中心,有容錯(cuò)性差的缺陷。因此,提出一種SCF算法。算法核心思想：當(dāng)簇A和B的簇密度相似且邊界距離較小才可以融合。充分考慮數(shù)據(jù)加權(quán)內(nèi)平均距離、簇間密度差和簇間距離。

定義5數(shù)據(jù)內(nèi)平均距離αi

(9)

式中 數(shù)據(jù)集為n維；k(i)為數(shù)據(jù)點(diǎn)i的k鄰域集合。

定義6簇間距離AB

AB=min(d(ri,rj))

(10)

式中d(ri,rj)為數(shù)據(jù)集A和B內(nèi)的點(diǎn)距離。

定義7簇間密度差CD

(11)

dSCF(A,B)可表示為

dSCF(A,B)=AB·CD2

(12)

實(shí)驗(yàn)發(fā)現(xiàn),當(dāng)dSCF(A,B)大于簇間相似性閾值(所有數(shù)據(jù)的0.2×mean(dSCF))時(shí),子簇間差異性較大,不能融合。因此,設(shè)定簇間閾值為0.2×mean(dSCF)。

算法1SCF算法

輸入：數(shù)據(jù)集及聚類中心

輸出：聚類結(jié)果

step1 按式(9)計(jì)算數(shù)據(jù)加權(quán)內(nèi)平均距離αi

step2 按式(10)計(jì)算簇間距離AB

step3 按式(11)計(jì)算簇間密度差CD

step4 按式(12)計(jì)算dSCF(A,B)

step5 判斷dSCF(A,B)是否小于閾值,若小于,進(jìn)行子簇融合

step6 輸出聚類結(jié)果

2.3 LDA算法

為解決DPC算法對(duì)高維數(shù)據(jù)集處理困難的問題,首先采用降維方法對(duì)高維數(shù)據(jù)降維。線性判別式分析(LDA)應(yīng)用于數(shù)據(jù)降維中[10],通過線性函數(shù)來處理數(shù)據(jù),實(shí)現(xiàn)數(shù)據(jù)降維。

算法2LDA算法

輸入：數(shù)據(jù)集X={x1,x2,…,xn}

輸出：低維數(shù)據(jù)集Y={y1,y2,…,yn}

step1 計(jì)算每個(gè)類的均值向量ui,得到原始數(shù)據(jù)集樣本空間類內(nèi)離散度矩陣

step2 計(jì)算類內(nèi)總離散度矩陣

step3 計(jì)算類間離散矩陣

step4 計(jì)算LDA準(zhǔn)則函數(shù)的最優(yōu)值

step5 計(jì)算降維后的數(shù)據(jù)集Y=wTX

2.4 SCF-LDA-DPC算法

首先調(diào)用算法2對(duì)數(shù)據(jù)集X降維處理得到數(shù)據(jù)集Y；按照式(8)計(jì)算ρi,按照式(2)和式(3)計(jì)算δi,并由式(4)計(jì)算γi并繪制出決策圖并選擇聚類中心；然后把剩余數(shù)據(jù)點(diǎn)分配到對(duì)應(yīng)簇中,并刪除噪聲數(shù)據(jù)。最后調(diào)用SCF算法。

算法3SCF-LDA-DPC算法

輸入：數(shù)據(jù)集X={x1,x2,…,xn}

輸出：聚類結(jié)果

step1 若X是高維數(shù)據(jù)集,執(zhí)行step2,否則執(zhí)行step3

step2 調(diào)用算法2 對(duì)數(shù)據(jù)集X進(jìn)行降維,得到降維數(shù)據(jù)集Y

step3 根據(jù)式(7)計(jì)算距離矩陣dij

step4 根據(jù)式(8)計(jì)算ρi,根據(jù)式(2)和式(3)計(jì)算δi

step5 由式(4)計(jì)算γi,繪制決策圖并選擇聚類中心

step6 將其他數(shù)據(jù)分配給聚類中心

step7 刪除噪聲數(shù)據(jù)

step8 調(diào)用算法1進(jìn)行子簇融合

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

在不同維度數(shù)據(jù)集驗(yàn)證SCF-LDA-DPC算法的聚類性能。利用MATLAB 2017a編程,實(shí)驗(yàn)環(huán)境為Win8,RAM8G,Intel?CoreTMi5-3200U 2.20 GHz。

3.1 低維數(shù)據(jù)集實(shí)驗(yàn)

測(cè)試SCF-LDA-DPC算法在9個(gè)低維數(shù)據(jù)集(如表1)的可行性和有效性,并與DPC算法、K-means算法、FKNN-DPC算法和DBSCAN算法比較,評(píng) 價(jià) 指 標(biāo)為AMI、ARI、FMI 指數(shù)[11],對(duì)照算法參數(shù)設(shè)置如文獻(xiàn)[12]。結(jié)果為15次實(shí)驗(yàn)均值。表2為5種算法在數(shù)據(jù)集中性能指標(biāo)值。圖1為SCF-LDA-DPC算法在部分?jǐn)?shù)據(jù)集上聚類結(jié)果。

表1 9個(gè)數(shù)據(jù)集參數(shù)

表2 5種算法在不同數(shù)據(jù)集上的性能

圖1 SCF-LDA-DPC算法聚類結(jié)果

從表2中可知,SCF-LDA-DPC算法在多組數(shù)據(jù)集上表現(xiàn)優(yōu)于另外4種聚類算法。尤其是在數(shù)據(jù)集Seeds,Jain和R15中,只有采用加權(quán)歐氏距離的SCF-LDA-DPC算法AMI、ARI和FMI的值都為1,能夠正確找到聚類中心。在數(shù)據(jù)集Waveform上SCF-LDA-DPC算法具有獨(dú)特優(yōu)勢(shì),能快速準(zhǔn)確尋找到聚類中心,聚類精度和效果明顯高于另外4種算法。從圖1中可知,在數(shù)據(jù)集Spiral和Flam上5種算法均有很好效果,因此,對(duì)簡(jiǎn)單數(shù)據(jù)集Spiral和Flam,參數(shù)設(shè)置對(duì)聚類結(jié)果影響較小。綜合分析,SCF-LDA-DPC算法優(yōu)于其他4種算法,在所有二維數(shù)據(jù)集上都有較好的效能和準(zhǔn)確性。

3.2 高維數(shù)據(jù)集實(shí)驗(yàn)

實(shí)驗(yàn)選取6個(gè)高維基因表達(dá)數(shù)據(jù)集(數(shù)據(jù)參數(shù)見文獻(xiàn)[13])驗(yàn)證SCF-LDA-DPC算法聚類性能。并與HMM算法[13]、HKAP-LLE算法[14]、IG-SGA算法[15]和APCES算法[15]比較聚類結(jié)果。采用5倍交叉驗(yàn)證法。選用3個(gè)評(píng)價(jià)指標(biāo)[15](R、S和AC)對(duì)聚類檢驗(yàn)。對(duì)照算法參數(shù)如文獻(xiàn)[15]。表3為5種算法在數(shù)據(jù)集Colon、Leukemia和Prostate上結(jié)果比較。

表3 5種算法在3個(gè)高維數(shù)據(jù)集上R和S值比較

R和S的值越接近1,說明聚類精度越高;反之,聚類精度越低。從表3中可知,在數(shù)據(jù)集Colon上SCF-LDA-DPC算法指標(biāo)R和S值均為1,大于另外4種算法的值,表明算法在該數(shù)據(jù)集上聚類性能優(yōu)于其他4種算法。對(duì)于數(shù)據(jù)集Leukemia,SCF-LDA-DPC的R值最大,雖然指標(biāo)S值略小于最優(yōu)值,但兩者相差不大,表明算法綜合性能優(yōu)越。在數(shù)據(jù)集Prostate上,SCF-LDA-DPC算法和IG-SGA算法R和S指標(biāo)值均為1,遠(yuǎn)大于其余3種算法值。

表4為5種算法在數(shù)據(jù)集SRBCT,Leukemia1和9-Tumor上AC值的比較。從表4中可知,傳統(tǒng)算法K-means、C-NMF和S-NMF在數(shù)據(jù)集上表現(xiàn)較差。較新的HKAP-LLE算法AC值較高,說明該算法聚類精度高于3種傳統(tǒng)算法。而SCF-LDA-DPC算法和HKAP-LLE算法相比,在3個(gè)數(shù)據(jù)集上的聚類精度分別提升3.60 %，15.63 %和5.60 %,表明該算法性能更加優(yōu)越。綜合分析可知,SCF-LDA-DPC算法效果最佳,具有在高維基因表達(dá)數(shù)據(jù)集上聚類結(jié)果的有效性和準(zhǔn)確性。

表4 5種算法在3個(gè)高維數(shù)據(jù)集上AC值比較

4 結(jié) 論

本文對(duì)DPC算法改進(jìn)，提出SCF-LDA-DPC算法。引入Pearson相關(guān)系數(shù)作為權(quán)重，基于加權(quán)歐氏距離的核密度估計(jì)函數(shù)計(jì)算樣本間的局部密度，既考慮了連續(xù)數(shù)據(jù)集的局部結(jié)構(gòu)特征，又考慮了樣本間的相關(guān)性。提出SCF，可以有效避免DPC算法容錯(cuò)性差的問題，最后利用LDA算法對(duì)高維數(shù)據(jù)降維，更有效地解決高維數(shù)據(jù)集上表現(xiàn)不佳的問題，提高了算法在高維數(shù)據(jù)集上的魯棒性和準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明：SCF-LDA-DPC算法在不同維度以及不同形狀的數(shù)據(jù)集上都可以準(zhǔn)確找到聚類中心,較其他算法相比能夠獲得更準(zhǔn)確的聚類中心和更高的聚類精度。