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

韓忠華 畢開元 司雯 呂哲

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

關鍵詞：數據聚類;適應性;降維;密度峰值快速聚類;譜分析

中圖分類號： TP301.6

文獻標志碼：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 引言

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

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

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

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

1.1 CFSFDP聚類算法

CFSFDP算法是一種基于密度峰值的聚類算法，與傳統的

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

4 結語

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

參考文獻：

[1] 蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J]. 計算機科學，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] 申彥.大規模數據集高效數據挖掘算法研究[D].鎮江：江蘇大學， 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] 唐東明. 聚類分析及其應用研究[D].成都：電子科技大學， 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] 賀玲，蔡益朝，楊征.高維數據聚類方法綜述[J]. 計算機應用研究，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]. 合肥：中國科學技術大學， 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] 張蓉，彭宏.一種基于超圖模式的高維空間數據聚類方法[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].中國礦業大學學報，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].計算機應用研究，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] 馬春來，單洪，馬濤.一種基于簇中心點自動選擇策略的密度峰值聚類算法[J].計算機科學，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] 蔣禮青，張明新，鄭金龍.快速搜索與發現密度峰值聚類算法的優化研究[J].計算機應用研究，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] 李金澤，徐喜榮，潘子琦，等.改進的自適應譜聚類NJW算法[J].計算機科學，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] 李屆家，郭鵬程，韓忠華.在高維數據上的近鄰傳播聚類降維研究[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] 周世兵，徐振源，唐旭清.基于近鄰傳播算法的最佳聚類數確定方法比較研究[J].計算機科學，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] 呂宗磊.對聚類及聚類評價若干問題的研究[D].南京：南京航空航天大學，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.）