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

劉小康, 張 菁 , 張延遲

(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算法在不同維度以及不同形狀的數據集上都可以準確找到聚類中心,較其他算法相比能夠獲得更準確的聚類中心和更高的聚類精度。