基于邊界點檢測的變密度聚類算法

陳延偉，趙興旺*

（1.山西大學計算機與信息技術學院，太原 030006；2.計算智能與中文信息處理教育部重點實驗室（山西大學），太原 030006）

0 引言

聚類分析依據一定的準則將數據對象劃分為不同的類，使同一類別中的對象具有較高的相似度，而不同類中的對象之間相似度較低。作為一種重要的數據挖掘技術，聚類分析已經在社交網絡分析、模式識別、生物信息學等諸多領域得到了廣泛應用［1-3］。

經過數十年的發展，研究者針對不同的領域提出了大量聚類分析算法，主要分為以下幾類：基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法以及基于圖的聚類算法等［4］。其中，密度聚類算法由于具有對噪聲魯棒、善于處理結構復雜數據且事先不需要指定類個數等優勢，近年來得到研究者的大量關注［5］。1996 年Ester 等［6］提出基于密度的噪聲應用空間聚類（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）算法，通過將高密度區域劃分為類，能夠在含“噪聲”的空間數據庫中發現任意形狀的類。1999 年Ankerst 等［7］提出通過點排序識別聚類結構（Ordering Points To Identify the Clustering Structure，OPTICS）算法，得到一個有序的對象列表用于提取聚類信息，但不顯式地生成數據聚類結果。2014 年Rodriguez 等［8］提出一種新型的基于密度峰值的聚類算法（Density Peaks Clustering Algorithm，DPCA），該算法基于類中心的密度大于周圍鄰居點的密度和類中心與更高密度點之間的距離相對較大的假設，用于尋找被低密度點隔離的高密度區域以達到對數據聚類的目的。盡管經典的密度聚類算法在處理形狀復雜、包含噪聲的數據方面具有一定優勢，但是，該類算法面臨著由于數據集中不同類的密度分布不均，且類與類之間邊界難以區分等導致聚類效果較差的問題。

針對以上問題，本文提出了一種基于邊界點檢測的變密度聚類算法（Varied Density Clustering algorithm based on Border point Detection，VDCBD）。算法主要包括以下步驟：1）基于給出的相對密度度量方法識別變密度類之間的邊界點，以此增強相鄰類的可分性；2）對非邊界區域的點進行聚類以找到數據集的核心類結構；3）依據高密度近鄰分配原則將檢測到的邊界點分配到核心類結構中；4）基于類結構信息識別數據集中的噪聲點。在人造數據集和UCI 數據集上與已有的經典聚類算法進行了比較分析。實驗結果表明，本文算法可以有效解決類分布密度不均、邊界難以區分的問題，并在4 個評價指標上優于已有算法。

1 相關工作

本章主要對已有的變密度聚類算法進行介紹。

2014 年在Science上發表了快速搜索和發現密度峰值聚類算法（DPCA）［8］。該算法結合了劃分聚類算法和密度聚類算法的優點，通過尋找合適的聚類中心點以得到理想的聚類結果，但不能保證每個類中有且僅有一個密度峰，因此DPCA 對變密度數據的聚類效果有限。為了解決變密度聚類問題，一些學者從不同角度對DPCA 進行了改進［9-10］。2016 年Du 等［11］介紹了一種基于k近鄰和主成分分析的密度峰值（Density Peak Clustering based onk-Nearest Neighbors，DPC-kNN）算法，該算法引入k最近鄰重新定義局部密度以考慮數據集的局部分布情況，減少了截斷距離對聚類結果的影響，并引入了主成分分析（Principal Component Analysis，PCA）以處理高維數據集；2016 年，Xie 等［12］提出了一種模糊加權k近鄰的密度峰值聚類（Fuzzy weightedk-Nearest Neighbors Density Peak Clustering，FkNN-DPC）算法，該算法通過引入k最近鄰給出了一種新穎的局部密度度量方法，并使用兩種新的點分配策略將剩余點分配到最可能的類以消除DPCA 點的分配策略導致的“多米諾效應”［13］；2018 年Liu等［14］提出了一種基于共享鄰居的密度峰值聚類（Shared Nearest Neighbor based Density Peaks Clustering，SNN-DPC）算法，該算法基于共享鄰居重新定義數據對象的局部密度和相對距離，并引入兩種基于共享鄰居信息的分配策略提高非中心點分配的準確性；2020 年Flores 等［15］提出了一種基于中心點自動檢測的密度峰值（Density Peak Clustering with Gap-Based automatic center detection，GBDPC）算法，通過對一維決策圖中數據點連續對之間的距離處理以自動確定聚類中心點個數，以解決多密度峰值的問題；2020 年Wang 等［16］提出了一種多中心密度峰值聚類（Multi-center Density Peak Clustering，McDPC）算法，該算法通過對決策圖進行再規劃，將樣本劃分為不同的密度層用來識別低密度區域的類，并對參數δ（與更高密度點的最近距離）進行類似的劃分以識別包含多個密度峰值的類。

另一部分學者提出新的聚類算法用于處理變密度數據。2016 年Chen 等［17］提出了一種有效識別密度主干的聚類（CLUstering based on Backbone，CLUB）算法，該算法通過將DPCA 中尋找聚類中心的策略轉換為尋找密度主干，并利用k近鄰生成初始類以此定義基本密度骨架，然后根據高密度近鄰原則分配其余點并識別噪聲點以獲得最終的聚類結果；2016 年，Zhu 等［18］提出了基于密度比的聚類算法解決變密度問題，該算法通過使用密度估計器計算密度比和對現有數據進行自適應的縮放兩種方法用于對變密度數據的處理；2017年Louhichi 等［19］提出了一種基于樣條的無監督變密度聚類（Multi Density ClUsTering，MDCUT）算法，該算法利用k最近鄰距離的指數樣條尋找合理的密度層次，并利用這些密度層次作為局部密度閾值獲取不同密度的類；2020 年Averbuch-Elor 等［20］提出一種邊界剝離聚類（Border Peeling clustering，BP）算法，通過迭代剝離邊界點并建立邊界點與其相鄰非邊界點的聯系，之后利用核心點間的可達性進行核心點的聚類并通過建立的聯系分配剝離的邊界點。現有算法在不同程度上可以識別變密度數據集的類結構，但是仍然面臨著相鄰類之間的邊界難以區分等導致聚類效果較差的問題。

2 基于邊界點檢測的變密度聚類算法

假設D={x1，x2，…，xn}表示由n個數據對象組成的數據集，其中xi表示數據集中第i個對象。

定義1k最近鄰：對于D中的每個數據對象xi，在歐氏距離下與xi最相似的k個數據對象稱為xi的k最近鄰，表示為KNk(xi)，其中KNk(xi) ?D。

定義2逆k最近鄰：對于D中的數據對象xi，如果其余任一對象xj的k最近鄰中包含xi，則xj為xi的逆k最近鄰，形式化描述如下：

本文算法主要包括邊界點檢測、非邊界點聚類、邊界點分配以及噪聲點識別4 個步驟。

2.1 邊界點檢測

邊界點位于每個類的邊緣位置，當兩個類相距較近時，兩者之間的邊界很難識別，受INFLO（INFLuenced Outlierness）算法［21］思想的啟發，提出了一種基于相對密度的邊界檢測方法，用于識別不同變密度類難以區分的邊界點，增強數據類結構的可分性。為了提高的運行效率，檢測邊界點過程中僅考慮所有數據點密度排序后一半低密度的數據點。

定義3數據點密度：一個數據集中每個數據點的密集程度可以表示為該點到與它最近的k個鄰居間的距離之和。通常來說，距離和越大，該點與它的鄰居間的距離越遠，因此，這個點的密度也就越小。考慮到兩個類中數據密度為變密度時，該方法不能有效體現兩個類中密度的關系，因此，通過增加一個權重提升稀疏類中相對密集點的密度大小。給定一個數據點x與它的k最近鄰間的距離集合為{d1，d2，…，dk}，數據點x的密度形式化描述如下：

其中：den(x)代表點x的密度；k代表最近鄰的個數；di表示數據點x與第i個最近鄰點的距離；count(RKN(x))表示數據點x的逆k最近鄰個數。

定義4相對密度：將該點的密度與其周圍點的密度的均值作比較。比值越小，該點的相對密度越小，即該點成為邊界點的可能性越大，數據點x的相對密度形式化描述如下：

其中：RDx表示數據點x的相對密度；RKKN(x)表示數據點x的k最近鄰和逆k最近鄰的并集。

定義5邊界點：將該點的相對密度與其k最近鄰點的相對密度作比較，如果該點的相對密度小于其k最近鄰的均值，則該點為邊界點。形式化描述如下：

為了更直觀地體現每個步驟的效果，下面分別以在Flame 和Jain 數據集上處理的結果為例進行介紹，其中Flame數據集由兩個相距較近的類組成，Jain 數據集則由兩個密度不同的類構成。圖1 為Flame 和Jain 數據集上的邊界檢測結果，邊界點使用藍色空白點表示。由圖1 可知，通過該步驟可以有效識別出類與類之間的邊界點，進而增強類之間的可分性。

圖1 Flame數據集和Jain數據集上的邊界識別結果Fig.1 Border recognition results on Flame dataset and Jain dataset

2.2 非邊界點的初始聚類

通過對原始數據進行邊界點識別，相鄰類之間的間距因排除邊界點而增大，使類結構探測更為容易。該步驟主要通過對非邊界點進行聚類進而找到數據集的核心類結構。首先，從非邊界點找到密度最大點，將該點放入一個新的隊列中；然后將該點的k最近鄰點中尚未分配標簽的點加入到該隊列中，遍歷隊列中的下一個點，也將其尚未分配標簽的k最近鄰點加入隊列中，依次遍歷隊列，直到沒有尚未分配的非邊界點與隊列中數據點存在k最近鄰關系；最后給隊列中數據點分配新的類標簽。以這種方式，訪問剩余尚未分配的非邊界點，直到所有非邊界點類標簽分配完畢。

圖2 為該步驟對非邊界點進行聚類的結果，可以看出通過第一步的邊界區域識別后，可以對非邊界點進行有效的聚類（空白點是邊界點），得到數據集的核心類結構。

圖2 Flame數據集和Jain數據集上的非邊界點聚類Fig.2 Non-border point clustering on Flame dataset and Jain dataset

2.3 邊界點分配

在該步驟中，對第一步中識別的邊界點進行分配。分配時，將每個邊界點分配到它的最近鄰且密度比其大的數據點所在的類中。該方法通過先識別核心類結構再分配邊界點的方法，有效地解決了DPCA 聚類中心點難以確定、因數據點的單步分配策略的容錯性較差產生的“多米諾骨牌效應”等問題。圖3 為經過邊界點的分配后得到的最終類結構。

2.4 噪聲點識別

經過邊界點分配后的聚類結果中可能包含噪聲點。例如，圖3（a）為Flame 數據集的聚類結果，在左上方有兩個明顯遠離大多數數據點的點，應為噪聲點。該步驟通過對噪聲點有效識別的過程進一步對聚類結果進行提升。根據數據異常校驗中常用的拉依達準則（PauTa 準則），該步驟通過對各類中邊界點的密度與所屬類的密度信息比較判斷是否為噪聲點，噪聲點的形式化描述如下：

圖3 Flame數據集和Jain數據集上的邊界點分配Fig.3 Border point allocation on Flame dataset and Jain dataset

其中：noise表示滿足條件的噪聲點集合；den(xi)表示數據點xi的密度；cl(xi)表示數據點xi所在類的標號；mean(cl(xi))表示數據點xi所在類cl中點的密度均值；std(cl(xi))表示數據點xi所在類cl中點的標準差。

如圖4 所示，該步驟在有噪聲的Flame 和無噪聲的Jain數據集上進行了噪聲識別結果。通過圖4（a）中可以看出左上角的兩個噪聲點可以被成功識別出來，并得到最終的聚類結果。

圖4 Flame數據集和Jain數據集上的噪聲點識別Fig.4 Noise point recognition on Flame dataset and Jain dataset

因此，基于上述思想，本文提出一種基于邊界點檢測的變密度聚類算法，如算法1 所示。

算法1 基于邊界點檢測的變密度聚類算法（VDCBD）。

輸入數據集D；最近鄰數k。

輸出聚類結果cluster。

3 實驗與結果分析

為驗證VDCBD 的有效性，與多個聚類算法在人造數據集和真實數據集上進行了比較。比較算法包括經典的K-means 算法［2］、DBSCAN 算法［6］，以及三個新算法DPCA［8］、CLUB 算法［17］和BP 算法［20］。其中，DPCA 和CLUB 算法可以處理具有任意密度的復雜數據集。對于每個算法，通過大量的迭代實驗調整其相應的輸入參數確定最優的聚類結果。其中只有BP 算法基于Python3.8 運行，本文所提VDCBD 和其余對比算法都是基于Matlab 2019b 上運行的結果。實驗環境為Windows10 操作系統，Intel Core i7-4790 CPU @3.60 GHz。

3.1 人造數據集的聚類結果

VDCBD 和5 個比較算法在8 個人造數據集上進行了聚類結果的可視化展示并通過幾種評價指標對其聚類結果進行了評價。8 個數據集的樣本數、特征數、真實類個數和來源如表1 所示，其中6 個都標明了來源，S1 和S2 是自制的變密度數據集，數據集T4、T8、S1 和S2 沒有真實類別信息。

表1 人造數據集描述Tab.1 Description of artificial datasets

8 個數據集的真實分布如圖5 所示，不同顏色和形狀代表不同的類別，其中黑色空白點表示數據集中的噪聲點。

圖5 8個數據集的真實分布Fig.5 Real distribution of 8 datasets

本文采用4 種不同的指標對算法性能進行了度量，包括準確度（Accuracy，ACC）［23］、F 度量（F-Measure，FM）［24］、標準化互信息（Normalized Mutual Information，NMI）［25］和調整蘭德指數（Adjusted Rand Index，ARI）［26］。其中只有ARI取值范圍為［-1，1］，其余三個評價指標取值范圍為［0，1］，其值越大，表明算法聚類結果與真實標簽越吻合，聚類結果越好。

圖6～13 分別為6 種算法在8 個人造數據集上的聚類結果。每個算法都有自己的參數設置，其中K-means 算法中參數K表示數據集類的個數；DBSCAN 算法中參數epsion表示數據集中每個對象的鄰域半徑閾值，參數MinPts表示對象的鄰域半徑中對象個數的閾值；DPCA 中參數percent表示求截斷距離時的百分比大小；CLUB 算法和本文VDCBD 的參數k表示k最近鄰的個數。每個算法名稱后括號中的數字表示該最優結果對應的參數值。

圖6 6種算法在Flame數據集上的結果Fig.6 Results of 6 algorithms on Flame dataset

圖6 為6 種算法對Flame 數據集的聚類結果。從圖6（a）可以看出，K-means 算法因只能處理球形數據集無法對該數據集進行有效聚類。從圖6（b）～（c）可以看出，DBSCAN 算法和DPCA 雖然能準確識別出數據的基本框架，但未能準確識別其中的噪聲點，對后續的數據分析工作造成一定的影響。CLUB 算法、BP 算法和VDCBD 可以得到正確的聚類結果。

圖7 為6 種算法在Jain 數據集上的聚類結果，Jain 數據集是一個典型的變密度數據集。從圖7 可以看出：K-means 算法和DPCA 將下方數據集的一部分錯誤地分配給了上方的類，而DBSCAN 算法則將數據集的一部分錯分成為一個新的類，CLUB 算法則將其上方類錯誤地分成三個小類并將一部分點識別為噪聲點，BP 算法則將其錯誤地分成多個類并產生了大量的噪聲點，只有VDCBD 對Jain 數據集的聚類效果最好。

圖7 6種算法在Jain數據集上的結果Fig.7 Results of 6 algorithms on Jain dataset

圖8 所示的6 種算法在Aggregation 數據集上的聚類結果表明：大多數算法可以對Aggregation 數據集進行有效聚類，只有K-means 算法無法對該數據集進行有效聚類，DBSCAN算法和CLUB 算法則將少量的數據點識別為噪聲點。圖9 為6 種算法在具有典型球形結構的D31 數據集上的聚類結果。從圖9（b）可以看出DBSCAN 算法未能將相鄰的兩個類分開，且將大量的數據點識別為噪聲點，CLUB 算法和BP 算法將部分的數據點識別為噪聲點，其余算法對D31 數據集的聚類結果都較好。

圖8 6種算法在Aggregation數據集上的結果Fig.8 Results of 6 algorithms on Aggregation dataset

圖9 6種算法在D31數據集上的結果Fig.9 Results of 6 algorithms on D31 dataset

圖10～11 展示了6 種算法在兩個數據規模達到8 000 的數據集上的聚類結果，T4 和T8 均是具有復雜結構和噪聲點的數據集，且T8 數據集中包含不同密度的類為典型的變密度數據集。從圖10 中可以看出，算法在對復雜數據集T4 聚類時，K-means 算法、BP 算法和DPCA 未能識別真實類結構，DBSCAN 算法雖能識別出數據的真實類，但卻有多個小類被錯誤識別，只有VDCBD 和CLUB 算法可以對數據進行有效地聚類且能識別出噪聲點。從圖11 中可以看出，只有VDCBD 能夠準確識別T8 數據集的類結構，并能識別其中的噪聲點，其余算法都不能識別真實的類結構。

圖10 6種算法在T4數據集上的結果Fig.10 Results of 6 algorithms on T4 dataset

圖11 6種算法在T8數據集上的結果Fig.11 Results of 6 algorithms on T8 dataset

圖12～13 所用數據集為本文提供的兩個變密度數據集。從圖12 所示的6 種算法在S1 數據集的聚類結果可以看出：只有VDCBD 可以得到較好的聚類結果，DBSCAN 算法錯誤地將上方類分為幾個新類且將大量的點識別為噪聲點。CLUB 算法可以識別出三個真實類，但將上方類中的部分數據點錯誤劃分為其他類或噪聲點，其余算法均未能識別真實的類結構。圖13 的S2 數據集相較于S1 相鄰的類之間的密度差更大，從（d）可以看出對S1 數據集有較好聚類效果的CLUB 算法也未能將兩個密度相差較大的類進行準確地聚類，DPCA 和CLUB 算法無法識別出上方半環型的類。只有VDCBD 準確地識別了數據集的類結構，僅將少量的點識別為噪聲點。

圖12 6種算法在S1數據集上的結果Fig.12 Results of 6 algorithms on S1 dataset

圖13 6種算法在S2數據集上的結果Fig.13 Results of 6 algorithms on S2 dataset

從8 個人造數據集的可視化結果中可以發現，本文VDCBD 相較于其他算法在處理具有復雜結構且密度不均的數據集時更加有效。表2 為VDCBD 與對比算法在4 個人造數據集上通過四種評價指標進行質量評價的結果，其中T4、T8、S1 和S2 數據集由于沒有真實標簽，因此這四個數據集沒有出現在表2 中。

從表2 中可以看出，在具有復雜結構的Flame 數據集和Aggregation 數據集中，除了K-means 算法外，其余算法均獲得了較好的聚類結果，VDCBD 達到了最高的聚類結果，且參數k的取值在一定程度上有著不錯的魯棒性。在對變密度數據集Jain 的聚類中，VDCBD 可以對該數據集準確聚類，在四個評價指標上均達到了最高值1，說明了本文算法在處理變密度數據集時的有效性。在典型的球形數據集D31 結果中可以看出，VDCBD 和K-means 算法的聚類結果相差無幾，僅在ARI 和NMI 評價指標上略低于K-means 算法，但VDCBD 在四種評價指標上均高于其余4 種密度聚類算法。綜上所述，本文提出的VDCBD 在處理復雜結構的人工數據集，尤其是在變密度數據集時與其他算法相比可以獲得更優的聚類結果。

表2 6種算法在4個人造數據集上的聚類結果Tab.2 Clustering results of 6 algorithms on 4 artificial datasets

3.2 真實數據集的聚類結果

為了驗證算法在真實環境下的有效性，用6 種聚類算法對真實數據集進行聚類來驗證算法的有效性。其中，真實數據集來源于UCI 機器學習數據庫［27］，其詳細信息可見表3。

表3 真實數據集描述Tab.3 Description of real datasets

在UCI 數據集上的聚類結果仍然采用ARI、NMI、FM 和ACC 四個評價指標進行質量評價，并給出了聚類結果對應的參數。6 種算法在真實數據集的聚類結果如表4 所示。

表4 6種算法在8個真實數據集上的聚類結果Tab.4 Clustering results of 6 algorithms on 8 real datasets

從6 種算法在真實數據集上的聚類評價結果可以看出，VDCBD 相較于對比算法在Iris、Leaf 和Ecoli 三個數據集上聚類效果最好；在Wine 數據集上雖未達到最好的聚類結果，但相較于其余4 種密度聚類算法有不小的提升。在Seeds 數據集中，VDCBD 在ARI 評價指標上達到了最好結果，并且在四種評價指標上均高于K-means、DBSCAN、DPCA 與BP 算法。在Segmentation 數據集中，VDCBD 和DBSCAN 算法在該數據集的聚類結果相差無幾，在ARI 和FM 兩個指標上相比DBSCAN 算法略有提升。當數據規模達到5 000 以上時，VDCBD 與對比的密度聚類算法相比仍具有一定的競爭力。綜上所知，VDCBD 在處理真實數據集上的聚類結果相較于對比算法有一定的提升。

3.3 時間復雜度及運行效率分析

本文VDCBD 在計算數據點的密度時，時間復雜度為O（n2），其中n為數據集大小；在第一步邊界點的檢測過程中，時間代價至多為O（k×n）+O（r×n），其中k為最近鄰個數（k?n），r為數據點最大的RKKN 的個數；在第二步對非邊界點的識別過程中，其時間代價最大為O（k×m2），其中m為非邊界點的個數；第三步對邊界點的分配過程中，時間代價為O（n×（n-m））+O（n）；最后對各類中噪聲點的識別過程中，時間代價為O（c_count×g）+O（m），其中c_count為類別數，g為類中的最大數據個數。綜合以上分析，本文算法的總時間復雜度為O（n2）。

K-means 算法的時間復雜度為O（t×n×K×ml），為線性時間復雜度，其中：t為迭代次數，K為類的數目，n為數據集總個數，ml為數據點維度；DPCA 和DBSCAN 算法的時間復雜度為O（n2）；BP 算法的時間復雜度為O（t×（k×n+fknn）），其中：fknn是k最近鄰的漸進時間復雜度。CLUB 算法的時間復雜度為O（nlogn）。

由于6 種算法在小規模數據集上的運行時間均較小，因此文中只比較了在數據規模達到5 000 以上的數據集的實際運行耗時。圖14 展示了6 種聚類算法在較大規模數據集上的運行時間比較。為了保證數據的穩定性，每種算法均獨立運行50 次，取平均值作為算法在該數據集上的運行時間。

通過圖14 可以看出，當數據規模較大時，VDCBD 的運行效率高于DPCA、CLUB 算法和BP 算法。

圖14 6種算法的運行時間比較Fig.14 Comparison of running time of 6 algorithms

4 結語

本文提出了一種基于邊界點檢測的變密度聚類算法VDCBD，用于更加有效地處理具有復雜結構、任意密度的數據集。不同于以往通過尋找聚類中心點聚類的方法，算法首先識別各類邊界區域，擴大各類間的距離；第二步，通過對非邊界區域的點進行聚類獲得數據集的核心類結構，之后根據高密度近鄰分配原則將檢測到的邊界點分配到核心類結構中；最后基于類結構信息識別數據集中的噪聲點，得到最終的聚類結果。實驗結果表明，本文所提VDCBD 在人造數據集和真實數據集上具有一定的優勢，相較于對比算法更加準確有效，尤其在變密度數據集上聚類效果更加明顯。

在未來的工作中，考慮將分而治之的思想融入到提出的密度聚類算法中，進而使其能夠高效地處理大規模數據。另外，現有數據可能存在特征值缺失的情況，給密度聚類算法來了新的挑戰，這也是下一步工作的研究重點。