基于連通性的三支密度峰值聚類算法

王江元,蔡明杰,2,祁明月

(1.湖南大學數學學院,湖南長沙 410082;2.湖南大學深圳研究院,廣東深圳 518055;3.河北閱思信息科技有限公司,河北石家莊 050000)

聚類被視為最重要的無監督學習方法之一,用于在無標簽數據中發現潛在結構。其最大優點是不需要先驗信息就能夠將對象集合分為彼此“相似”且與其他聚類中的對象“不相似”的群組[1],廣泛用于圖像分割[2]、文本挖掘[3]、生物信息學[4]、社區檢測[5]等多個領域。

密度峰值聚類(DPC)[6]是一種經典的基于密度的聚類算法,基于2個假設實現聚類:一是密度峰值點的密度應當比其周圍的點更高;二是密度峰值點與離其最近且比其密度高的點之間的距離應當比非峰值點與離其最近且比其密度高的點之間的距離更遠。DPC的大致流程如下,先計算每個樣本點的密度和到其他點的相對距離,再根據上述2個假設選擇密度峰值點作為聚類中心點,最后將非中心點分配到離其最近且比其密度高的點所在的簇中。然而,DPC算法也存在著一定的局限性,例如,密度峰值點的選擇問題和誤分配問題。對于密度峰值點的選擇問題,大多數改進算法通過改變密度以及距離的計算公式來解決[7-11]。對于誤分配問題,一般通過改變分配策略對算法進行改進[12-14]。當處理流形結構的數據時,如果不使用路徑距離,無論如何構造密度和距離的計算公式,總會出現同一類的樣本被分配給不同簇的情況,因為僅根據鄰域信息無法識別流形結構。若想利用路徑距離,那么又會消耗大量的計算資源和時間,尤其是在處理大規模數據時。此外,計算路徑距離前需要生成圖結構,根據生成圖的策略不同,或多或少還會損失原始數據的信息。

針對上述問題,本文提出了基于連通性的三支密度峰值聚類算法(CTW-DPC)。為了使DPC能夠識別流形數據且不使用路徑距離,引入連通性,通過三支聚類邊界的連通性判斷簇的連通性,合并被經典算法誤分成多個簇的流形結構。對于經典算法無法發現的簇,提出在迭代過程中逐步發現低密度簇的方法,解決簇之間密度差異帶來的問題。

1 相關工作

1.1 密度峰值聚類(DPC)

DPC算法作為中心聚類與密度聚類的結合體,以密度峰值點作為聚類中心,并在分配過程中使用密度聚類的思想。密度峰值點由局部密度和相對距離確定。對于數據集X,樣本點xi的局部密度ρi的定義如下:

(1)

或

(2)

式中:χ為示性函數,當x<0時,χ(x)=1,當x≥0時,χ(x)=0;d(xi,xj)為樣本點xi和xj之間的距離。局部距離δi通過計算比樣本點xi密度高且離其最近的點之間的距離得到,定義為

(3)

1.2 三支聚類

為了解決硬聚類的限制,即一個對象只屬于一個簇,人們提出了許多軟聚類方法。模糊均值聚類(FCM)[15-16]是最常用的軟聚類方法,其假設簇由反映漸變邊界的模糊集表示。另一個處理不確定性數據的有效工具是粗糙均值聚類算法(RKM)[17],它使用區間集表示具有模糊和不精確邊界的簇,并假設一個對象必須屬于1個下近似或者2個上近似的交集。盡管這個條件在粗糙集理論的背景下似乎是有效的,但對于一般的三支聚類來說,假設一個對象最多可以屬于1個正域或者至少1個邊界域似乎更為合理[18]。

基于三支決策[19],YU[20]提出了一種三支聚類模型,通過一對集合或3個集合來表示一個簇:考慮一對閾值(α,β)(α≥β)和一個評價函數φ(x),Ci是一個簇,U為一個論域,POS(Ci)={x∈U|φ(x)>α},BND(Ci)={x∈U|β≤φ(x)≤α},NEG(Ci)={x∈U|φ(x)<β}。由此定義的三支聚類對閾值的敏感性較大。WANG等[21]提出了三支聚類的理論框架,擴展了傳統K-means算法和譜聚類算法,分別為CE3 K-means聚類和CE3譜聚類,這2種聚類都使用k近鄰代替以閾值半徑確定的鄰域,來對正域和邊界域進行判斷。

由于集合的正域需要利用某些關系對該集合進行?；玫?因此需要由以下3個假設來確定簇的正域:

2 三支密度峰值聚類

通過改進DPC中的密度函數和分配策略,與三支聚類結合,提出一種改進的三支密度峰值聚類算法(TW-DPC)。對于TW-DPC生成的邊界域,給出一種判斷連通性的方式,使用連通分支概念對初始聚類結果進行合并。通過TW-DPC的反復迭代、連通性的判定與合并,發現TW-DPC無法探查到的低密度簇,實現CTW-DPC算法的高魯棒性。

2.1 改進的三支密度峰值聚類

為了有效探查到不同密度的簇,減少迭代次數,提出一種新的密度函數。該度量利用反向k近鄰(RKNN)定義。

定義1(反向k近鄰) 樣本點xi的反向k近鄰定義為一類樣本點x的集合,其k近鄰中包含xi,即RKNN(xi)={x∈D|xi∈KNN(xi)}。

通過圖1可以直觀了解一個樣本點的反向k近鄰的構成。

圖1 反向k近鄰示例,k=2

圖1中樣本由6個樣本點組成,灰色的圓代表其圓心的2近鄰。例如,x1的2近鄰由x2和x5組成。藍線代表的是x4的反向k近鄰,即R2NN(x4)={x6,x5,x2}。從圖1可以看出,反向k近鄰的分布擺脫了距離限制,可以更好地反映鄰域點到該點的連通性。一個樣本點反向k近鄰的基數越大,說明能夠到達該點的點越多,并且同一個樣本點的反向k近鄰與k近鄰的基數不必相同。

定義2對?x∈X,令RKNN(x)和KNN(x)分別為x的反向k近鄰與k近鄰,則本文定義的密度為

(4)

上述定義將Sigmoid函數與KNN-DPC中的密度定義結合起來形成了新的密度定義。k近鄰的基數越大時,密度也就越大。這種定義方式能夠有效探查到低密度的簇。圖2是在相同數據集下,TW-DPC與KNN-DPC不同定義下的密度分布圖?？梢钥闯?TW-DPC定義下的密度能夠探查到圓環上的點作為密度峰值,而KNN-DPC中則無法識別圓環上的點。

圖2 2種密度函數比較圖

對于相對距離函數δi,本文仍采取DPC算法中比樣本點xi密度高且離其最近的點之間的距離作為相對距離函數。為了消除密度過傳播帶來的影響,本文采取RNN-DBSC[22]中的方式,即在分配過程中,計算將要擴展點的反向k近鄰的基數,設置一個閾值α∈[0,+∞),對是否擴展進行判斷。因為反向k近鄰的基數在一定程度上反映了該點的連通性,因此通過控制閾值大小可以改變聚類結果的連通性。此外,本文引入互近鄰定義,進一步增強連通性的判別方式。

定義3(互近鄰) 對?xi,xj∈X,稱xj屬于xi的互近鄰,如果滿足xj∈KNN(xi)且xj∈RKNN(xi)。

互近鄰要求鄰域內的點滿足對稱性,使得互近鄰成為了一個等價關系。因此本文在分配過程中,使用互近鄰對將要添加到搜索隊列并被傳遞標簽的點作出限制,使得被算法分到同一個簇的點在鄰域關系層面上是等價的。這也與三支決策中正域的定義相吻合,即POS(X)={x∈X|[x]R?X},其中[x]R為等價關系R下x的等價類。

DPC因無法識別流形數據,導致一個連通流形上出現多個密度峰值點,即簇中心,這也導致在分配過程中,原本屬于同一等價類的樣本,因為從屬于不同的簇中心而被分配到不同的簇。因此,本文引入三支聚類的邊界域,對邊界域內的點進行討論,最終得到區間集形式的初始聚類結果。算法的大致流程如表1所示。

表1 算法的大致流程

2.2 基于連通性的聚類合并策略

使用TW-DPC得到簇的邊界后,從邊界點中選取m=min{k2,∑i|BND(Ci)|}個指標函數γ最大的邊界點,作為判斷邊界連通性的代表點。本文采用的連通性判斷指標仍然是代表點的反向k近鄰基數,若基數大于k,則與該代表點的k近鄰相交的簇在該點處連通,說明初始算法得到的聚類結果有誤,即在一個簇中找到了多個密度峰值點,使得簇的正域識別有誤。

通過上述操作得到初始聚類結果的連通性后,便可以構造簇之間的鄰接圖,再尋找鄰接圖的連通分支,將得到的極大連通分支作為合并后的聚類結果,并將所合并簇的最大密度的密度峰值點作為合并后新簇的簇中心。通過圖3可以直觀展現此合并過程。

圖3 合并策略效果圖

圖3中,TW-DPC將數據集分為9個簇,通過計算簇的邊界連通性,得到如圖3 c)的鄰接圖,其極大連通分支為{C1,C2,C4,C8},{C3,C9},{C5,C6,C7},通過合并每個極大連通分支中的簇,得到如圖3 d)所示的新簇。合并算法的偽代碼如表2所示。

表2 合并算法的偽代碼

2.3 CTW-DPC算法

由圖3 a)可以發現存在4個未被TW-DPC識別的簇。針對TW-DPC在密度差異大的數據集上表現不良的問題,使用迭代過程,將密度差異大的簇分開識別。通過將未分配的點作為下一次迭代的數據集,屏蔽高密度簇對未分配數據的影響,并再次使用TW-DPC,達到在低密度水平下的聚類識別,提高算法的魯棒性。本文最終提出的算法流程見表3。

表3 最終提出的算法流程

2.4 算法復雜度分析

本文提出的算法在TW-DPC部分主要計算所有樣本點的k近鄰、密度函數ρi以及距離函數δi,若樣本的個數為N,那么計算時間的復雜度分別為O(NlogN),O(kN)和O(N)。而在合并算法中,使用三支決策計算聚類邊界的時間復雜度為O(kN),若數據集的類別數為n,則判斷連通性的最大時間復雜度為O(n2k)。通常情況下,每次迭代后的樣本個數相比上一次大大減少,且k和n遠遠小于N,因此若算法的迭代次數為m,則算法總體的最大時間復雜度為O(mNlogN)。

3 實驗結果與分析

為了檢驗本文提出算法的準確性,在18個數據集上與經典的DPC算法和5個改進的DPC算法進行對比試驗。這18個數據集包括二維的人工數據集和來源于UCI的真實世界數據集,具體信息詳見表4。由于進行對比的7個算法求得最優解時的參數不盡相同,因此本文采取網格搜索方式對各個算法的最優參數進行搜索。對于浮點型參數dc與α,搜索網格為{0.01,0.02,…,1}∪{1.1,1.2,…,5};對于整數型參數k,搜索網格為{2,3,…,50}∪{50,55,…,200}。實驗評價指標采用調整蘭德系數(ARI)和歸一化互信息(NMI)。

表4 實驗數據集

3.1 人工數據集上的實驗結果

CTW-DPC與其他6種算法在8種人工數據集上聚類結果的ARI和NMI如表5所示,其中加粗字體表示該結果為該數據集上最優算法下的評價指標,這2種指標越趨近于1,說明算法效果越好,當其等于1時,則說明算法的預測結果與數據集給出的標簽完全一致?！啊北硎驹撍惴ǖ貌坏接行У膶嶒灲Y果。由表5可以看出,本文提出的算法在這8個人工數據集上的表現都比較優秀,尤其是在流形數據集Compound,Complex8,Complex9上,比之前提出的算法都有明顯提升。為了進一步展示實驗效果,以數據集Compound為例,給出不同算法的實驗對比圖,如圖4所示。

表5 人工數據集實驗結果

圖4 不同算法聚類結果比較圖

圖4中紅點表示聚類中心,可以明顯看出只有CTW-DPC找到了所有的簇,且沒有出現誤分配的問題,其余算法皆出現了誤分配的問題。DPC,KNN-DPC,SNN-DPC和DPC-DBFN均未能找到低密度的簇。BC-DPC與TW-RDPC因較好的密度函數定義,找到了低密度的簇,但仍沒能避免同一個簇中出現2個密度峰值點的情況,但本文提出的算法很好地解決了該問題。

3.2 真實數據集上的實驗結果

表6所呈現的結果為7種算法在10種真實數據集上的數值表現。雖然CTW-DPC在一些數據集上的表現未能超越之前的算法,但其總體表現穩定,與最優算法的評價指標相差不大,尤其是在Waveform和Heart數據集上較其他算法有了明顯的提升。此外,對于多類別的手寫數字圖像集Opt digits和Pendigits,本文提出的算法也有良好表現。

表6 真實數據集實驗結果

但需注意的是,包括本算法在內的這類密度峰值聚類算法,在真實數據集上的表現多數情況下劣于傳統的K-means聚類算法和譜聚類算法。這是因為在真實數據集中,不同類別的樣本往往會在邊界處有重合部分,使得該重合邊界在流形上是連通且密度較高的,導致出現誤分配以及錯誤選擇密度峰值點的問題。

4 結 語

本文提出的基于連通性的三支密度峰值聚類算法,可以有效解決密度峰值聚類中低密度聚類難以被發現和誤分配的問題。通過利用三支邊界域的良好數學性質并引入連通性的概念,將原本屬于同一正域的樣本點進行合并,既避免了復雜計算,又能更好地反映簇間的關系,對于處理大規模流形數據提供了有價值的解決方案。

本文以參數形式給出的連通性有著較大的敏感度,對于不同的數據集需要進行調參,因而會造成時間以及計算資源的浪費。未來將引入連通性和連通度的概念對算法進行改進和優化。

參考文獻/References：

[1] XU Rui,WUNSCH D.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678.

[2] DONG Guo,XIE Ming.Color clustering and learning for image segmentation based on neural networks[J].IEEE Transactions on Neural Networks,2005,16(4):925-936.

[3] LU Mei,ZHAO Xiangjun,ZHANG Li,et al.Semi-supervised concept factorization for document clustering[J].Information Sciences,2016,331:86-98.

[4] TRUONG H Q,NGO L T,PEDRYCZ W.Granular fuzzy possibilistic C-means clustering approach to DNA microarray problem[J].Knowledge-Based Systems,2017,133:53-65.

[5] JIAO Pengfei,YU Wei,WANG Wenjun,et al.Exploring temporal community structure and constant evolutionary pattern hiding in dynamic networks[J].Neurocomputing,2018,314:224-233.

[6] RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[7] XIE Juanying,GAO Hongchao,XIE Weixin,et al.Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J].Information Sciences,2016,354:19-40.

[8] DU Mingjing,DING Shifei,JIA Hongjie.Study on density peaks clustering based on K-nearest neighbors and principal component analysis[J].Knowledge-Based Systems,2016,99:135-145.

[9] LIU Rui,WANG Hong,YU Xiaomei.Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J].Information Sciences,2018,450:200-226.

[10] ZHANG Qinghua,DAI Yongyang,WANG Guoyin.Density peaks clustering based on balance density and connectivity[J].Pattern Recognition,2023,134.DOI:10.1016/j.patcog.2022.109052.

[11] 馬春來,單洪,馬濤.一種基于簇中心點自動選擇策略的密度峰值聚類算法[J].計算機科學,2016,43(7):255-258.

MA Chunlai,SHAN Hong,MA Tao.Improved density peaks based clustering algorithm with strategy choosing cluster center automati-cally[J].Computer Science,2016,43(7):255-258.

[12] LOTFI A,MORADI P,BEIGY H.Density peaks clustering based on density backbone and fuzzy neighborhood[J].Pattern Recognition,2020.DOI:10.1016/j.patcog.2020.107449.

[13] CHENG Dongdong,HUANG Jinlong,ZHANG Sulan,et al.K-means clustering with natural density peaks for discovering arbitrary-shaped clusters[J].IEEE Transactions on Neural Networks and Learning Systems,2023.DOI:10.1109/TNNLS.2023.3248064.

[14] SUN Chen,DU Mingjing,SUN Jiarui,et al.A three-way clustering method based on improved density peaks algorithm and boundary detection graph[J].International Journal of Approximate Reasoning,2023,153:239-257.

[15] BEZDEK J C,EHRLICH R,FULL W.FCM:The fuzzy C-means clustering algorithm[J].Computers &Geosciences,1984,10(2/3):191-203.

[16] 祖志文,李秦.基于馬氏距離的模糊聚類優化算法——KM-FCM[J].河北科技大學學報,2018,39(2):159-165.

ZU Zhiwen,LI Qin.KM-FCM:A fuzzy clustering optimization algorithm based on Mahalanobis distance[J].Journal of Hebei University of Science and Technology,2018,39(2):159-165.

[17] LINGRAS P,WEST C.Interval set clustering of web users with rough K-means[J].Journal of Intelligent Information Systems,2004,23(1):5-16.

[18] 姚一豫,祁建軍,魏玲.基于三支決策的形式概念分析、粗糙集與粒計算[J].西北大學學報(自然科學版),2018,48(4):477-487.

YAO Yiyu,QI Jianjun,WEI Ling.Formal concept analysis,rough set analysis and granular computing based on three-way decisions[J].Journal of Northwest University(Natural Science Edition),2018,48(4):477-487.

[19] YAO Yiyu.Three-way decisions with probabilistic rough sets[J].Information Sciences,2010,180(3):341-353.

[20] YU Hong.A framework of three-way cluster analysis[C]//International Joint Conference on Rough Sets.Olsztyn:Springer,2017:300-312.

[21] WANG Pingxin,YAO Yiyu.CE3:A three-way clustering method based on mathematical morphology[J].Knowledge-Based Systems,2018,155:54-65.

[22] BRYANT A,CIOS K.RNN-DBSCAN:A density-based clustering algorithm using reverse nearest neighbor density estimates[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(6):1109-1121.

[23] BENTLEY J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM,1975,18(9):509-517.