基于譜分析的密度峰值快速聚類算法

韓忠華 畢開元 司雯 呂哲

摘 要：針對密度峰值快速聚類（CFSFDP）算法對不同數(shù)據(jù)集聚類效果的差異，利用譜聚類對密度峰值快速聚類算法加以改進(jìn)，提出了一種基于譜分析的密度峰值快速聚類算法CFSFDP-SA。首先，將高維非線性的數(shù)據(jù)集映射到低維子空間上實(shí)現(xiàn)降維處理，將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題以增強(qiáng)算法對數(shù)據(jù)全局結(jié)構(gòu)的適應(yīng)性;然后，利用CFSFDP算法對處理后的數(shù)據(jù)集進(jìn)行聚類。結(jié)合這兩種聚類算法各自的優(yōu)勢，能進(jìn)一步提升聚類算法的性能。在5個(gè)人工合成數(shù)據(jù)集（2個(gè)線性數(shù)據(jù)集和3個(gè)非線性數(shù)據(jù)集）與4個(gè)UCI數(shù)據(jù)庫中真實(shí)數(shù)據(jù)集上的聚類結(jié)果顯示，相比CFSFDP算法，CFSFDP-SA算法的聚類精度有一定提升，在高維數(shù)據(jù)集的聚類精度上最多提高了14%，對原始數(shù)據(jù)集的適應(yīng)性更強(qiáng)。

關(guān)鍵詞：數(shù)據(jù)聚類;適應(yīng)性;降維;密度峰值快速聚類;譜分析

中圖分類號： TP301.6

文獻(xiàn)標(biāo)志碼：A

Abstract： For different clustering effects of Clustering by Fast Search and Find of Density Peaks （CFSFDP） on different datasets， an improved CFSFDP algorithm based on spectral clustering was proposed， namely CFSFDP-SA （CFSFDP based on Spectrum Analysis）. Firstly， a high-dimensional non-linear dataset was mapped into a low-dimensional subspace to realize dimension reduction， then the clustering problem was transformed into the optimal partitioning problem of the graph to enhance the algorithm adaptability to the global structure of the data. Secondly， the CFSFDP algorithm was used to cluster the processed dataset. Combining the advantages of these two clustering algorithms， the clustering performance was further improved. The clustering results of two artificial linear datasets， three artificial nonlinear datasets and four real datasets in UCI show that compared with CFSFDP， the CFSFDP-SA algorithm has higher clustering precision， achieving up to 14% improvement in accuracy for high-dimensional dataset， which means CFSFDP-SA is more adaptable to the original datasets.

Key words： data clustering; adaptability; dimension reduction; Clustering by Fast Search and Find of Density Peaks （CFSFDP）; spectrum analysis

0 引言

聚類算法是一種應(yīng)用極其廣泛的數(shù)據(jù)分析方法，在機(jī)器學(xué)習(xí)及模式識別領(lǐng)域被稱為無監(jiān)督學(xué)習(xí)，其過程是將數(shù)據(jù)分組成多個(gè)類或簇，在同一類或簇中的數(shù)據(jù)相似度較高，不同類或簇中的數(shù)據(jù)相似度較低[1]。隨著各種聚類算法不斷的發(fā)展和完善，至今已被廣泛應(yīng)用于商業(yè)選址、計(jì)算機(jī)視覺、流量識別、圖像分割及數(shù)據(jù)庫等領(lǐng)域[2-3]。然而，隨著信息時(shí)代的飛速發(fā)展，隨之而來的是數(shù)據(jù)量呈指數(shù)級增長以及數(shù)據(jù)自身維度的大幅提高，因此聚類分析算法在原始數(shù)據(jù)的適應(yīng)性上面臨更大的挑戰(zhàn)，在聚類精度和聚類時(shí)間上往往都難以得到滿意的結(jié)果[4]。

2014年《Science》上發(fā)表了一種新型的密度聚類算法——密度峰值快速聚類（Clustering by Fast Search and Find of Density Peaks， CFSFDP）算法，該算法與其他密度算法相似，能處理形狀復(fù)雜的聚類，并同時(shí)具有指定參數(shù)少、自動(dòng)生成聚類中心并且無需迭代的特點(diǎn)。該算法研究小組利用CFSFDP算法處理Olivetti人臉數(shù)據(jù)庫的實(shí)驗(yàn)驗(yàn)證了該算法對高維復(fù)雜數(shù)據(jù)的處理能力。

然而，通過進(jìn)一步實(shí)驗(yàn)分析可知，CFSFDP算法在擁有上述眾多優(yōu)點(diǎn)之外仍存在一些缺陷：首先，該算法對于線性可分的低維數(shù)據(jù)集聚類效果比較好，但對于密度不均勻的樣本集或線性不可分?jǐn)?shù)據(jù)集的聚類效果并不理想，并且相對稀疏的聚類中心往往容易被淹沒，有可能出現(xiàn)同一個(gè)類被分裂的情況[5];另外，隨著數(shù)據(jù)維度的不斷增大，距離計(jì)算過程復(fù)雜度不斷提高，處理時(shí)間也隨之上升。因此，本文提出了一種基于譜分析的密度峰值聚類算法（CFSFDP based on Spectrum Analysis， CFSFDP-SA）——通過譜聚類將高維非線性的數(shù)據(jù)映射到幾乎線性的子空間上進(jìn)行降維處理，再利用CFSFDP算法對處理后的數(shù)據(jù)進(jìn)行聚類。譜聚類算法建立在譜圖理論的基礎(chǔ)上，其本質(zhì)是利用圖的最優(yōu)劃分思路來解決聚類問題[6]，該方法首先計(jì)算拉氏矩陣特征值，然后選取前K個(gè)最大特征值對應(yīng)的特征向量來構(gòu)成一個(gè)與原始數(shù)據(jù)相對應(yīng)的空間， 最后在該空間中進(jìn)行聚類。譜聚類較傳統(tǒng)聚類算法對數(shù)據(jù)分布的適應(yīng)性更強(qiáng)，聚類效果更優(yōu)秀并且計(jì)算量也小很多。經(jīng)譜聚類預(yù)處理的CFSFDP算法既能保留CFSFDP算法中參數(shù)少、自動(dòng)生成聚類中心且無需迭代的特點(diǎn)，也能有效彌補(bǔ)原始數(shù)據(jù)分布所帶來的一些奇異性問題。

1 CFSFDP聚類算法原理及性能分析

1.1 CFSFDP聚類算法

CFSFDP算法是一種基于密度峰值的聚類算法，與傳統(tǒng)的

基于密度的噪聲應(yīng)用空間聚類（Density-Based Spatial Clustering of Applications with Noise， DBSCAN）算法不同[7]，該算法不需要進(jìn)行復(fù)雜的參數(shù)設(shè)定，并且可以對不同類型的數(shù)據(jù)集進(jìn)行聚類分析。CFSFDP算法的基本思路是：1）通過決策圖篩選出密度極點(diǎn)即聚類中心;2）依據(jù)密度大小排列將數(shù)據(jù)點(diǎn)歸類到距離其最近且密度比它大的數(shù)據(jù)點(diǎn)所屬的類中[8]。在聚類中心的篩選上主要取決于兩個(gè)重要參數(shù)，局部密度ρ 和相鄰密度點(diǎn)距離δ， 二者的乘積越大則成為聚類中心的可能性越大。局部密度的定義是以當(dāng)前數(shù)據(jù)點(diǎn)為中心，以dc 為半徑的圓形區(qū)域內(nèi)所包含的數(shù)據(jù)點(diǎn)的數(shù)量，如式（1）所示：

4 結(jié)語

本文從聚類算法對高維復(fù)雜數(shù)據(jù)樣本適應(yīng)性這一角度出發(fā)，利用譜聚類對CFSFDP算法進(jìn)行了改進(jìn)。經(jīng)過譜聚類的處理，將高維非線性的數(shù)據(jù)映射到幾乎線性的子空間上，提升了CFSFDP聚類算法對非測度樣本空間分布的適應(yīng)性，有效提升了聚類的能力。實(shí)驗(yàn)結(jié)果表明，本文提出的CFSFDP-SA算法不但保留了CFSFDP算法中參數(shù)少、自動(dòng)生成聚類中心且無需迭代的特點(diǎn)，同時(shí)也有效彌補(bǔ)了原始數(shù)據(jù)分布所帶來的一些奇異性問題。但本文所選取的數(shù)據(jù)集具有一定的局限性，還有更多更為復(fù)雜和龐大的高維數(shù)據(jù)集有待進(jìn)一步驗(yàn)證。所以我們下一步工作將深入研究CFSFDP改進(jìn)算法對高維復(fù)雜數(shù)據(jù)集的聚類效果。與此同時(shí)，由于譜聚類算法對數(shù)據(jù)樣本具有很強(qiáng)的適應(yīng)性，并且對非凸分布的聚類能力較好，非常適合用于解決很多實(shí)際問題，在此基礎(chǔ)上結(jié)合簡便快捷的CFSFDP算法將會應(yīng)用于實(shí)際領(lǐng)域，因此下一步研究工作也將會結(jié)合實(shí)際問題來進(jìn)一步研究CFSFDP改進(jìn)算法的有效性。

參考文獻(xiàn)：

[1] 蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J]. 計(jì)算機(jī)科學(xué)，2008，35（7）：14-18. （CAI X Y， DAI G Z， YANG L B. Survey on spectral clustering algorithms [J]. Computer Science， 2008， 35（7）： 14-18.）

[2] 申彥.大規(guī)模數(shù)據(jù)集高效數(shù)據(jù)挖掘算法研究[D].鎮(zhèn)江：江蘇大學(xué)， 2013：1-8. （SHEN Y. The research of high efficient data mining algorithms for massive data sets [D]. Zhenjiang： Jiangsu University， 2013： 1-8.）

[3] 唐東明. 聚類分析及其應(yīng)用研究[D].成都：電子科技大學(xué)， 2010： 13-27. （TANG D M. Study on clustering analysis and its applications [D]. Chengdu： University of Electronic Science and Technology of China， 2010： 13-27.）

[4] 賀玲，蔡益朝，楊征.高維數(shù)據(jù)聚類方法綜述[J]. 計(jì)算機(jī)應(yīng)用研究，2010，27（1）：23-27. （HE L， CAI Y C， YANG Z. Survey of clustering algorithms for high-dimensional data [J]. Application Research of Computers， 2010， 27（1）： 23-27.）

[5] 張文開.基于密度的層次聚類算法研究[D]. 合肥：中國科學(xué)技術(shù)大學(xué)， 2015：15-26. （ZHANG W K. Research on density-based hierarchical clustering algorithm [D]. Hefei： University of Science and Technology of China， 2015： 15-26.）

[6] 張蓉，彭宏.一種基于超圖模式的高維空間數(shù)據(jù)聚類方法[J]. 計(jì)算機(jī)工程，2002，28（7）：54-55. （ZHANG R， PENG H. Method for data clustering in a high dimensional space based on a hypergraph model [J]. Computer Engineering， 2002， 28（7）： 54-55.）

[7] 馮少榮，肖文俊. DBSCAN聚類算法的研究與改進(jìn)[J].中國礦業(yè)大學(xué)學(xué)報(bào)，2008，37（1）：105-106. （FENG S R， XIAO W J. An improved DBSCAN clustering algorithm [J]. Journal of China University of Mining & Technology， 2008，37（1）：105-106.）

[8] 馬春來，單洪，馬濤，等.一種基于CFSFDP改進(jìn)算法的重要地點(diǎn)識別方法研究[J].計(jì)算機(jī)應(yīng)用研究，2017，34（1）：136-140. （MA C L， SHAN H， MA T， et al. Research on important places identification method based on improved CFSFDP algorithm [J]. Application Research of Computers， 2017， 34（1）： 136-140.）

[9] 馬春來，單洪，馬濤.一種基于簇中心點(diǎn)自動(dòng)選擇策略的密度峰值聚類算法[J].計(jì)算機(jī)科學(xué)，2016，43（7）：255-258. （MA C L， SHAN H， MA T. Improved density peaks based clustering algorithm with strategy choosing cluster center automatically [J]. Computer Science， 2016，43（7）：255-258.）

[10] 蔣禮青，張明新，鄭金龍.快速搜索與發(fā)現(xiàn)密度峰值聚類算法的優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用研究，2016，33（11）：3251-3254. （JIANG L Q， ZHANG M X， ZHENG J L. Optimization of clustering by fast search and find of density peaks [J]. Application Research of Computers， 2016， 33（11）： 3251-3254.）

[11] 李金澤，徐喜榮，潘子琦，等.改進(jìn)的自適應(yīng)譜聚類NJW算法[J].計(jì)算機(jī)科學(xué)，2017，44（6）：424-427. （LI J Z， XU X R， PAN Z Q， et al. Improved adaptive spectral clustering NJW algorithm [J]. Computer Science， 2017， 44（6）： 424-427.）

[12] 李屆家，郭鵬程，韓忠華.在高維數(shù)據(jù)上的近鄰傳播聚類降維研究[J]. 控制工程，2016，23（9）：1419-1422. （LI J J， GUO P C， HAN Z H. Research of affinity propagation clustering dimension reduction on high-dimensional data [J]. Control Engineering of China， 2016，23（9）：1419-1422.）

[13] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數(shù)確定方法比較研究[J].計(jì)算機(jī)科學(xué)，2011，38（2）：225-228. （ZHOU S B， XU Z Y， TANG X Q. Comparative study on method for determining optimal number of clusters based on affinity propagation clustering [J]. Computer Science， 2011， 38（2）： 225-228.）

[14] 呂宗磊.對聚類及聚類評價(jià)若干問題的研究[D].南京：南京航空航天大學(xué)，2009：10-24. （LYU Z L. The research on several issues of clustering and clustering validity indexes [D]. Nanjing： Nanjing University of Aeronautics and Astronautics， 2009： 10-24.）