自適應閾值約束的密度簇主干聚類算法

張錦宏，陳 梅，張 弛

蘭州交通大學 電子與信息工程學院，蘭州 730070

如何自動化地分析、理解和總結數據是當前面臨的一個主要問題，數據聚類分析是一種解決該問題的有效技術[1]。聚類分析是一種無監督機器學習方法，其根據數據點間的相似性將數據點劃分到不同的簇中，從而識別出數據的內在模式并提取有用的知識[2]。然而，現有的部分聚類算法在處理多種類型的復雜數據集時存在聚類精度不理想的情況[3]，因此，提出更優秀的聚類算法是非常必要的。

目前相關研究人員已經提出很多聚類算法[3]，且被廣泛應用于生物[4]、交通[5]、大數據[6]、電力[7]等領域。經典的基于劃分的聚類算法包括k-means[8]和k-Medoids[9]等。該類算法的簇個數通常依賴于用戶設定，簇的數量對聚類結果有決定性影響。此外劃分聚類算法對非球狀簇的識別效果較差。基于密度的經典聚類算法之一DBSCAN（density-based spatial clustering of application with noise）[10]通過高密度區域的連通性發現簇，利用低密度區域對高密度區域的隔斷性標識不同的簇，對簇的形狀和大小不敏感，但聚類質量隨著簇內點密度變化劇烈程度的增加而降低，且算法閾值參數難以直接確定[11]。OPTICS（ordering points to identify the clustering structure）[12]是DBSCAN 的改進版本，該算法不顯式地生成聚類結果，而是生成一個數據點的有序序列，通過調整鄰域半徑參數從而在該序列中得到相對應的聚類結果，但該算法對簇內數據點密度變化的敏感度依然較高。Chameleon[13]是層次聚類算法的典型代表，該算法通過動態考慮初始小簇間的相對互連性和相對近似性將小簇歸并得到最終簇。盡管該算法可以識別任意形狀的簇，但算法運行時間成本較高。基于網格的聚類方法也是一種有效的基本聚類方法，其中STING（statistical information grid）[14]將數據空間按層次順序分割為不同分辨率的單元格，基于每個單元中的數據統計信息對單元格進行聚類。雖然網格化數據空間有助于提高算法執行速度，但其導致的數據空間分辨率下降在聚類任意密度數據集時會影響結果的精度。

上述現有聚類算法中存在難以識別多中心點任意簇、對簇內點密度變化敏感[15]及閾值取值難以確定等問題。近年來，為了應對檢測任意形狀、任意密度簇的聚類問題，學者們又提出了一些新穎的聚類算法。CFDP（clustering by fast search and find of density peaks）[16]結合了密度聚類和劃分聚類的特點，基于密度和距離識別出每個簇的聚類中心，然后基于劃分的方法完成非聚類中心點的分配，得到聚類結果。雖然該算法可以準確地識別出聚類中心點，但CFDP 認為每個聚類中心點僅代表一個簇，因此會分割多中心點的復雜簇，且非中心點的分配策略具有層次依賴性，若先分配的數據點出現錯誤會影響后續所有分配。SCC（sub-cluster component algorithm）[17]是可擴展的層次聚類算法，該算法使用一系列遞增的距離閾值來確定在特定輪次中合并哪些子簇。該算法在不犧牲質量換取速度的前提下實現了很好的可伸縮性。MulSim（a novel similar-to-multiple-point clustering algorithm）[18]采用多點相似聚類策略，在綜合考慮節點間以及節點與對方近鄰間相似關系的情況下進行聚類，從而可以發現任意形狀、大小和密度的簇。基于上述分析，可以看出基于密度進行聚類是識別任意簇的一種有效思路，因此本文將基于密度聚類算法進行進一步研究。

為了更精確地識別出復雜數據集中的任意分布簇，本文提出自適應閾值約束的密度簇主干聚類算法（density backbone clustering algorithm based on adaptive threshold，DCBAT）。根據密度可達閾值，DCBAT 算法首先將可達核心點識別為簇主干，接著將非聚類核心點分配到密度較大的最近鄰所在簇中得到初始簇，最后根據密度差閾值對初始簇進行拆分得到最終簇。該算法考慮到數據點間的密度可達性往往與數據點的整體分布有關，因此基于數據分布自適應地計算密度可達閾值，克服了DBSCAN 等以密度可達思想進行聚類時密度閾值難以直接確定的問題。同時，復雜分布數據集中各簇的密度不均勻給聚類帶來了一定的困難，但單個簇內由核心到邊界方向的數據點密度由大到小的變化趨勢是相對穩定的，因此該算法基于各簇內點的密度差值自適應地計算密度差閾值，根據簇內數據點間的密度差值與對應閾值的大小關系分割錯誤合并的初始簇，克服了任意密度影響聚類結果的問題，提高了算法識別精度，降低了異常點對結果的影響。該算法時間復雜度較低，在參數不變的情況下聚類結果唯一，具有穩定性，可以識別任意簇。

1 相關工作

傳統的密度聚類算法雖然具備識別任意簇的能力，但依然存在閾值取值不好確定、對變密度簇敏感等問題[15]。

對于閾值取值問題，自適應DBSCAN 算法（selfadaptive density-based spatial clustering of applications with noise，SA-DBSCAN）[19]在DBSCAN 的基礎上利用數據集的統計特性自動確定鄰域半徑Eps和鄰域內對象數Minpts參數，避免了閾值取值的人工干預。自適應基于廣度優先搜索鄰居的聚類算法（selfadaptive broad first search neighbors，SA-BFSN）[20-21]改進了基于廣度優先搜索鄰居的聚類算法（broad first search neighbors，BFSN）中距離參數r和參數λ的確定方式，在Dk曲線上進行逆高斯分布擬合確定參數r，接著分析噪聲點數量的分布特征選擇合適的參數λ。自適應密度峰值聚類（adaptive density peak clustering，ADPC）[22]對CFDP 算法進行了改進，使用基尼系數對CFDP 的dc參數進行約束，從而實現自適應選擇截斷距離dc的目的。

對于變密度簇敏感問題，VDBSCAN（varied density based spatial clustering of applications with noise）[23]首先利用k-dist圖識別密度層次，對每層選擇一組鄰域半徑Eps和鄰域內對象數Minpts參數，分別調用DBSCAN算法實現不同密度簇的聚類。基于邊界點檢測的變密度聚類算法（varied density clustering algorithm based on border point detection，VDCBD）[24]通過識別簇邊界點發現簇核心結構，依據高密度近鄰分配原則劃分邊界點到相應的簇核心結構中，以這種方式聚類變密度簇。融合網格劃分與FDBSCAN 的改進聚類算法（fusion of grid partition and FDBSCAN clustering algorithm，G_FDBSCAN）[25]利用網格劃分技術將數據集分為稀疏區域和密集區域并分而治之，合并相鄰的密集區域形成子類，根據稀疏網格的鄰居子類中是否存在核心點判斷是否將稀疏網格識別為噪聲，達到識別變密度簇的目的。

受上述工作啟發，本文發現可以利用數據自身的統計特性和分布特征自適應地確定合適的閾值，同時可以利用簇內及簇間點密度變化特點克服變密度簇聚類問題。本文提出一種自適應閾值約束的密度簇主干聚類算法，它基于數據自身特點自適應地確定算法閾值識別簇主干，并利用簇內和簇間數據點密度變化的特征獲取最終聚類結果。

2 相關定義與說明

定義1（k近鄰）對于?xi∈D，D中與xi距離最近的前k個數據點定義為xi的k近鄰，記作Nk(xi)。

定義2（點的局部密度）對于?xi∈D，點xi與其近鄰點間的距離關系反映了xi的局部密度。點的局部密度與其近鄰數量成正比，與鄰居和該點之間的距離之和成反比。本文采用式（1）計算數據點的局部密度：

其中，ρi為點xi的局部密度，k為點xi的近鄰數量，disij為點xi與其近鄰xj之間的距離。

定義3（點的相對距離）對于?xi∈D，其相對距離δi定義為點xi與點xj之間的距離，其中xj的局部密度大于xi的局部密度，且距離xi最近的數據點，稱xj為xi的歸屬點。點xi的相對距離δi的計算公式如下：

特殊情況下，若點xi具有全局最大局部密度，則：

定義4（聚類核心點）潛在的聚類核心點應該具備局部密度較大和相對距離較大兩個特征，定義為：

其中，Ω是聚類核心點集合。ρT是局部密度閾值，其取值為所有數據點密度的中位數。δT是相對距離閾值，其取值為所有數據點相對距離的上四分位數。

定義5（基于數據分布的數據點密度可達自適應閾值）一組數據的偏度系數表征著數據分布的偏態程度，且密度可達閾值與數據集中點的密度分布情況息息相關。基于偏度系數調整密度均值的數據點密度可達自適應閾值的計算公式如下：

其中，RT表示密度可達閾值，表示數據集D中點的密度均值，λ為D中數據點密度的偏度系數，λ的計算公式如下：

其中，Q3表示D中數據點密度的上四分位數，Q2表示數據點密度的中位數，Q1表示數據點密度的下四分位數。

定義6（數據點可達）對于?xi,xj∈D，若存在一組數據點序列x1,x2,…,xm,…,xT∈D，其中x1=xi,xT=xj，該序列滿足xm的局部密度ρm大于密度可達閾值RT且xm+1∈Nk(xm)，則稱xi到xj數據點可達。

定義7（基于密度分布的密度差自適應閾值）本文新定義密度差閾值的計算公式如下：

其中，ρm_T表示單個簇的密度差閾值；ρm_ave表示一個簇中所有密度差值的均值；μ為比例系數，用于放大密度差均值。

密度差值反映一個簇中數據點密度變化趨勢的緩急程度，均值體現了一組數據的統計學特征，因此可以利用ρm_ave判斷簇內密度差值的變化情況。為避免均值取值過小導致算法對密度變化過于敏感，將經比例系數μ適當放大后的密度差均值作為密度差閾值。用該閾值評判密度差值可以為是否拆分初始簇提供可靠的信息參考。

為了便于后文中描述算法，將本文中用到的定義符號整理如表1所示。

表1 DCBAT算法中常用符號定義Table 1 Definition of commonly used symbols in DCBAT algorithm

3 自適應閾值約束的密度簇主干聚類算法

3.1 算法思想

簇核心點具有較高的局部密度，且與其他簇核心點之間的距離相對較遠。同一個簇中的核心點之間是密度可達的，且簇內高密度區域到低密度區域的數據點密度變化趨勢相對平滑，跨簇時數據點密度會出現劇烈變化。本文立足于數據點的分布情況和簇內數據點的密度變化趨勢提出DCBAT 算法，定義了基于數據點分布的密度可達自適應閾值作為核心點間的可達性度量，以簇內數據點密度變化趨勢作為依據決定是否對簇進行拆分。

本文以Flame 數據集為例直觀地展示算法聚類思想，如圖1所示。第一階段基于局部密度度量和相對距離度量準則，篩選出全部數據點中的聚類核心點，核心點分布如圖1（b）所示。根據數據點密度可達自適應閾值檢測核心點間的可達性，將聚類核心點劃分為若干集合，每個集合代表一個初始簇的簇主干，圖1（c）展示了簇主干。第二階段將剩余數據點合并到其密度較大的最近鄰所在簇中，得到初始簇，結果如圖1（d）所示。第三階段基于每個初始簇中數據點的密度差自適應閾值對初始簇進行拆分。圖1（e）繪制了圖1（d）中上方初始簇內數據點密度由高到低的變化趨勢，可以看到數據點密度在紅框處出現了驟降，斷層處的兩數據點密度差值遠大于密度差閾值，因此斷層上下的數據點應屬于不同的簇。以斷層處為界將上方初始簇拆分，得到最終簇結構，結果如圖1（f）所示。對比聚類結果和圖1（a）所示的數據集真實分布，DCBAT 可以準確識別Flame 中包括左上角兩個異常點在內的每個點。

圖1 DCBAT算法思想示例Fig.1 Example of DCBAT algorithm idea

DCBAT算法基于密度可達閾值正確判定了聚類核心點的所屬簇，準確識別了非核心點分配策略中頂層數據點的所屬簇，有效降低了該策略的層次依賴性對聚類結果的影響，提高了算法識別簇的容錯率。DCBAT算法通過簇內數據點間的密度差值與對應閾值的大小關系判斷初始簇劃分的合理性，以大于閾值的密度差所對應的數據點為界將初始簇拆分，大大提高了最終簇的識別精度，同時還可以對異常點進行有效識別。

3.2 算法聚類過程

DCBAT 算法使用點的近鄰數量k作為算法參數，通過3 個階段完成簇識別。DCBAT 的總執行過程如算法1所示。

算法1DCBAT執行總過程

在算法1 中，第2～3 行計算每個點的局部密度和相對距離，第5 行根據定義4 篩選出潛在的聚類核心點，第7 行根據第6 行計算出的密度可達閾值RT判斷這些核心點之間的可達性，形成初始簇主干；接著第8 行對非聚類核心點進行分配，得到初始簇結構；最后在第9～13 行檢測初始簇的合理性，對錯誤合并的簇進行拆分，得到最終的簇結構。

3.2.1 獲取簇主干

算法1.1 識別可達核心點，獲取簇主干

本算法第一階段如算法1.1所示。第2～3行首先使用式（1）基于每個點的k近鄰計算點的局部密度ρi，所有ρi組成局部密度集合ρ。第4～12 行識別每個點的歸屬點。對于點xi，根據定義3 在其k近鄰范圍內尋找其歸屬點xj，得到xi的相對距離δi；若k近鄰范圍內不存在滿足條件的點，則在全局范圍內進行檢索。所有δi構成相對距離集合δ，所有的歸屬點xj構成歸屬點集合B。第14行取ρ的中位數和δ的上四分位數分別作為局部密度度量閾值ρT和相對距離度量閾值δT，第15 行判斷數據集中的每個點xi是否滿足定義4的要求，若滿足則將該點標記為聚類核心點，否則標記為非核心點。接著第16 行利用式（4）基于數據集中點的密度分布情況計算密度可達閾值RT。在第17～28 行中算法隨機選擇一個聚類核心點xi，根據定義6 找到xi的全部密度可達核心點，將xi與其密度可達的聚類核心點劃分到一個簇中，生成一個初始簇的主干。然后隨機選擇一個未訪問的聚類核心點重復上述過程，直到訪問完全部聚類核心點，得到全部初始簇主干。

3.2.2 生成初始簇

算法1.2分配非核心點，生成初始簇

本算法第二階段如算法1.2 所示。DCBAT 按密度降序依次遍歷所有非核心點，將每個點歸并到其歸屬點所在簇，得到初始簇結構。

3.2.3 拆分初始簇得到最終簇

算法1.3拆分初始簇，獲取最終簇

本算法第三階段如算法1.3 所示。為了判斷初始簇的合理性，DCBAT 以單個初始簇為單位，在第6～7 行對每個簇中的點按密度降序排序，并計算降序序列中相鄰兩個點之間的密度差值。在8～12行中使用式（6）計算出的密度差閾值找到每個簇中密度差值的異常值。第13～14 行以異常值對應的數據點為界，將降序序列劃分為若干個子序列，即將初始簇劃分為若干新簇，得到最終的簇結構。

根據所得密度差閾值，簇內密度變化異常的初始簇在密度變化波動較大的位置被分割為若干個子簇，即最終簇。最終簇的簇內密度變化趨勢平穩，且簇內數據點密度分布的均勻性與密度變化趨勢相對獨立，不會影響初始簇的分割過程。

3.3 時間復雜度分析

設數據集D的大小為n，近鄰數量參數為k。

第一階段采用k-d樹[26]作為數據結構來獲取每個數據點的k近鄰，所需時間復雜度為O(n×lbn)。在k近鄰的基礎上計算每個點的局部密度ρi花費O(k×n)。計算每個點的相對距離并生成歸屬點集合B時需要遍歷k近鄰矩陣，時間復雜度為O(k×n)；若k近鄰中不存在密度較大的點，則需在全局范圍內進行檢索。對數據集D中的點按局部密度降序排序，這樣檢索時只需要遍歷降序序列中該點之前的數據點即可，單個數據點檢索的平均時間復雜度為O(0.5×n)，實驗中發現在k近鄰中檢索到密度較大點的概率超過90%，因此計算相對距離的總時間復雜度約為O(0.9×k×n+0.1×0.5×n)。篩選聚類核心點前要計算局部密度度量閾值ρT和相對距離度量閾值δT，需要對局部密度集合ρ和相對距離集合δ進行排序，所花費時間復雜度為O(2×n×lbn)，接著遍歷數據集D對每個數據點進行判斷，時間復雜度為O(n)。最后確定核心點之間的可達性，在最差的情況下需要訪問全部數據點，時間復雜度為O(n)。本階段的總時間復雜度為O(n×lbn)。

第二階段分配非核心點需要遍歷全部數據點，階段總時間復雜度為O(n)。

第三階段需要遍歷每個初始簇。首先需要將單個簇中的數據點按密度降序排序，然后計算每個簇中相鄰兩點之間的密度差值并找出差值中的異常值。總的排序時間復雜度為O(n×lbn)；計算密度差花費時間O(n-cl)，其中cl為初始簇的個數，且cl?n；尋找異常密度差值時間復雜度為O(n)。本階段的總時間復雜度為O(n×lbn)。

綜上所述，算法的總時間復雜度為O(n×lbn)。

3.4 基于密度可達性判定核心點所屬簇

對于單個簇而言，核心點構成的簇主干蘊含著簇的內部結構信息，因此準確識別簇主干可以保證聚類的準確性。簇內部區域的局部密度相對較高，而邊緣區域和簇間區域的局部密度一般較低。構成簇主干的核心點一般位于遠離簇邊緣的內部區域，由于簇內部區域的密度高，同一簇中的核心點間具有更好的密度可達性；不同簇間存在低密度區域，導致不同簇中核心點間的密度可達性較差。綜上，核心點間是否密度可達是判斷其是否屬于同一個簇的重要依據，密度可達的核心點同屬于一個簇。算法第一階段借助能夠體現數據分布特點的偏度系數和體現數據統計特征的密度均值計算出合適的密度可達閾值，使用該閾值識別彼此之間密度可達的核心點，基于此可以有效地判斷每個核心點的所屬簇，為后續步驟打下良好基礎。

3.5 基于簇主干發現簇

經典聚類算法如k-means 根據數據點與簇心之間的距離關系識別簇；DBSCAN 算法從單個數據點出發，基于密度可達性自底向上地發現整個簇；CFDP算法通過識別每個簇的聚類中心進而發現簇。以上經典算法聚類時僅考慮了單個數據點，缺乏對數據內部整體結構的考量。DCBAT充分考慮了數據的內部結構，通過識別簇主干完成聚類。簇主干是一個簇的骨架，體現了簇內數據點的分布特征，基于簇主干聚類不僅考慮了數據點間的關聯關系，還考慮了數據的內部結構特征，利用數據點與簇主干間的關系去識別簇。點間聯系與數據結構特征的綜合考量保證了聚類結果的可靠性，有助于準確識別簇。

4 實驗與結果分析

為了驗證算法在任意形狀、任意密度數據集上的性能，將本文提出的算法與5 種對比算法分別在8個數據集上進行測試。對比算法包括3 種經典算法和兩種新算法。

4.1 實驗數據集

本次實驗共采用8 個數據集，其中包括5 個二維數據集（Aggregation、Compound、Spiral、Flame 和T4）和3 個多維數據集（Column_3C、Ecoli和Seeds），其中二維數據集和多維數據集分別獲取自東芬蘭大學（http://cs.joensuu.fi/sipu/datasets/）和UCI 網站（https://archive.ics.uci.edu/ml/datasets.php）。8 個數據集囊括了任意形狀、任意密度、含噪聲點、不同維度以及不同規模簇的數據分布情況。各數據集的詳細信息如表2所示。

表2 數據集信息Table 2 Information of datasets

4.2 對比算法說明

為對比本文算法與現有算法之間的性能差異，本節使用5個算法與本文算法進行對比實驗，其中包括3種經典算法（k-means、DBSCAN 和OPTICS）和兩種新算法（CFDP 和MulSim）。其中k-means 是劃分聚類算法的典型代表，DBSCAN和OPTICS是基于密度的聚類算法，CFDP 將基于密度與基于劃分兩種聚類算法思想相結合通過尋找聚類中心從而得到聚類結果，MulSim基于單點和多點間的相似原則識別簇。3種經典算法均來自Python 的“scikit-learn”庫，其余算法代碼均由其作者提供。

4.3 聚類評價指標

為了更直觀地比較各算法間的性能差異，本文使用精度（accuracy，Acc）、調整蘭德系數（adjusted Rand index，ARI）和歸一化互信息（normalized mutual information，NMI）對算法的性能進行量化評價。

Acc 是數據集中正確劃分的數據點數N1與數據點總數N的比值，其計算公式為：

NMI 是一個基于信息論的聚類結果評價標準，其計算公式為：

其中，I(Ω,C)表示聚類結果和數據真實分布的互信息，H(Ω)和H(C)分別表示聚類結果和數據真實分布的熵。

ARI是蘭德系數的調整形式，其衡量的是兩個數據分布的吻合程度，計算公式如下：

其中，RI表示蘭德系數，E(RI)表示蘭德系數的期望值。

3 個指標的取值越大說明聚類結果越接近數據的真實分布。對于二維數據集的實驗結果還以散點圖的形式進行了可視化展示。

4.4 DCBAT算法及對比算法的參數

引言部分已經介紹了對比算法，DCBAT 算法和各對比算法的具體參數如表3 所示。實驗中各算法的參數取值通過多次實驗尋優確定，各算法在不同數據集下的最優參數如表4所示。通過實驗發現，本文算法的密度差自適應閾值中的比例系數μ取值為25左右時可以在各數據集得到較好的聚類結果。

表3 DCBAT算法及各對比算法參數Table 3 Parameters description of DCBAT and compared algorithms

表4 DCBAT及對比算法在數據集上的參數取值Table 4 Parameter value of DCBAT and compared algorithms on datasets

4.5 實驗結果及分析

4.5.1 二維數據集

圖2～圖6 分別展示了DCBAT 及對比算法在5 個二維數據集上的聚類結果，表5 統計了相應的Acc、ARI 和NMI，由于T4 數據集沒有真實類標，表5 中無對應數據。

圖2 DCBAT與對比算法在Aggregation數據集上的聚類結果Fig.2 Clustering results of DCBAT and compared algorithms on Aggregation dataset

表5 DCBAT及對比算法的聚類指標量化結果Table 5 Quantitative results of DCBAT and compared algorithms

（1）Aggregation數據集

Aggregation 數據集中包含典型的凸狀簇，簇內密度均勻，每個簇的密度大小相對統一，但不同簇中包含的數據點數量差異較大，且存在通過若干數據點相連在一起的兩對簇，這也是該數據集的聚類難點所在。圖2展示了DCBAT 與對比算法在該數據集上的聚類結果，其中圖2（g）為Aggregation 的真實簇分布情況，圖2（a）～（f）分別為DCBAT 及對比算法在該數據集上的聚類結果。

通過圖2 和表5 可以看出，DCBAT 僅錯誤識別一個點，取得了最佳的Acc、ARI 和NMI。本文算法基于合理的數據點密度可達閾值，通過判斷數據點間的可達性對隸屬于不同簇的核心點正確地進行了劃分，在初始階段就確定了每個簇的簇主干，避免了簇間連通部分對聚類結果的影響，解決了聚類難點。CFDP 的Acc、ARI 和NMI 與DCBAT 并列第一，MulSim 排名第二，二者除簇間連接區域外均可以準確地識別出數據點的所屬簇。DBSCAN算法的Acc、ARI 和NMI 排名第四，由于其采用固定的數據點密度可達閾值，對左上角密度較小的簇邊緣區域數據點未能正確識別，且受到簇間銜接部分的影響，沒有劃分開右側的相連簇。OPTICS 算法在DBSCAN的基礎上進行了優化，但仍不能準確識別簇邊緣區域的部分數據點，其Acc、ARI 和NMI 排名第三。k-means 算法受到相距較近的兩個簇的尺寸影響，錯誤地選取了簇心，導致未能識別出左下角的兩個相連簇。

（2）Compound數據集

Compound 數據集中包含3 類簇，其中左上角的兩個簇距離較近且具有不均勻的簇內密度；右側兩個簇擁有不同的簇內密度。左下角外圈的簇中不存在顯著的簇中心點。數據集的聚類難點在于數據點分布情況錯綜復雜，同時存在多中心點簇和變密度簇。圖3展示了DCBAT 與對比算法在該數據集上的聚類結果，其中圖3（g）為Aggregation 的真實簇分布情況，圖3（a）～（f）分別為DCBAT 及對比算法在該數據集上的聚類結果。

從圖3和表5可以看出，DCBAT算法的Acc、ARI和NMI排名第一，對Compound數據集的識別最為準確，僅識別錯誤一個點，且基于初始簇內的密度變化趨勢正確地分割了右側的兩個簇。MulSim算法聚類結果排名第二，其在識別右側兩個相鄰簇的邊界區域時遇到了困難。DBSCAN 和OPTICS 的聚類結果指標依次排名第三和第四，兩個算法受限于固定的密度閾值參數，不能準確識別右側不同密度的簇。由于算法思想的制約，CFDP 沒能識別出左下角的多中心點簇。k-means對于右側的不同密度簇和左下角的無清晰中心點簇的聚類效果較差。

（3）Spiral數據集

Spiral 數據集中包含3 個螺旋狀的簇，每個簇內的數據點密度隨著螺旋向外延伸而遞減。圖4 展示了DCBAT 與對比算法在該數據集上的聚類結果，其中圖4（g）為Spiral的真實簇分布，圖4（a）～（f）分別為DCBAT以及對比算法的聚類結果。

圖4 DCBAT與對比算法在Spiral數據集上的聚類結果Fig.4 Clustering results of DCBAT and compared algorithms on Spiral dataset

從圖4和表5可以看出，DCBAT、DBSCAN、CFDP和MulSim 算法獲得了完美的劃分結果，聚類指標均達到了1.000 0。k-means將數據集劃分成了3個球狀簇。OPTICS 未能正確識別螺旋尾部密度較小的數據點，將其劃分為了異常點。

（4）Flame數據集

Flame 數據集中包含兩個簇，兩個簇中的數據點分布比較稀疏，且簇內密度與兩簇相連區域處的密度差異較小。圖5展示了DCBAT 與對比算法在該數據集上的聚類結果，其中圖5（g）為Flame的真實簇分布情況，圖5（a）～（f）分別為DCBAT 以及對比算法的聚類結果。

從圖5和表5可以清晰地看出，DCBAT完美地識別出了真實的簇結構，取得了最好的聚類結果，其聚類指標達到了1.000 0。k-means 將數據集強行分為3個簇，未能識別左上角的兩個異常點，還將下方的簇一分為二。由于上、下簇之間的數據點分布較為稀疏，且異常點距離簇較遠，DBSCAN 和OPTICS 的聚類結果較為理想，只有簇相連處的部分數據點識別錯誤。CFDP 基于數據點的分配策略錯誤地將下方簇的右側部分劃分給了上方簇，導致聚類效果不佳。MulSim 的聚類結果與DBSCAN 的結果相似，效果也比較理想。

（5）T4數據集

T4 數據集中的數據不包含真實類標簽，但數據集中包含異常點，且通過散點圖可以容易地看出簇的數量、形狀以及周圍的異常點。T4 數據集中包含任意形狀的簇。圖6展示了DCBAT 與對比算法在該數據集上的聚類結果，圖6（a）～（f）分別為DCBAT 以及對比算法的聚類結果。

很明顯，DCBAT 和DBSCAN 都可以正確檢測出簇結構，并且將周圍的稀疏點判定為異常點，更能凸顯簇結構。k-means 算法無法識別任意形狀簇，因此未能識別出簇結構和異常點。CFDP 算法無法識別出異常點，且錯誤識別了部分簇。OPTICS 將所有數據點劃分為兩個簇。MulSim算法正確識別出了部分異常點，但由于右側存在一條較為密集的數據點帶連接兩個簇，該算法錯誤地將兩個簇進行了合并。

圖2～圖6以可視化的形式直觀地展示了DCBAT和對比算法在二維數據集上的聚類結果。為了更清晰地量化對比DCBAT 與對比算法的性能差異，圖7（a）～（c）繪制了二維數據集上3 種聚類評價指標的條形圖。

圖7 DCBAT與對比算法在二維數據集上的指標條形圖Fig.7 Measurement bar diagram of DCBAT and compared algorithms on two-dimensional datasets

從圖7可以看出，DCBAT算法在4個二維數據集上的聚類評價指標均高于對比算法，該算法不但能識別出正確的簇結構，且相較于對比算法具有最佳的聚類性能。

4.5.2 多維數據集

表5 中后半部分羅列了DCBAT 與各對比算法在多維數據集Column_3C、Ecoli和Seeds上的聚類結果評價指標，由于高維數據集無法以散點圖的形式直觀地展示聚類結果，采用聚類評價指標條形圖的形式來展示和對比算法性能。

圖8（a）～（c）所示為DCBAT及對比算法在3個多維數據集上的Acc、ARI和NMI指標的結果。從圖中可以看到，DCBAT 算法的聚類結果評價指標整體高于對比算法，說明其具有較強的識別數據真實分布的能力。

圖8 DCBAT與對比算法在多維數據集上的指標條形圖Fig.8 Measurement bar diagram of DCBAT and compared algorithms on multi-dimensional datasets

最后，為對比算法的綜合性能，將DCBAT 及對比算法在全部數據集上的聚類評價指標通過箱線圖的形式進行展示，結果如圖9 所示。在盒圖中，每個盒體的上下邊界表示對應數據的上下四分位數，盒體中的實線表示對應數據的中位數，自盒體延伸出的上下方的短線代表數據中的最大值和最小值，“×”表示異常值。通過圖9 中的盒圖可知，DCBAT 算法對應的盒圖中各特征數據（中位數、上下四分位數和最值等）所處位置整體高于對比算法，盒體的高度整體低于對比算法，且不存在異常值，說明該算法的聚類評價指標取值較大且波動較小，算法聚類性能相較于對比算法更優。

圖9 DCBAT及對比算法的評價指標盒圖Fig.9 Measurement box diagram of DCBAT and compared algorithms

綜上所述，DCBAT算法基于核心點可達的思想，利用簇內數據點密度變化趨勢平穩的特點實現了任意簇的高效識別，算法整體具有魯棒性。

4.6 變密度簇敏感性分析

變密度簇識別一直是聚類分析的難點所在，給識別數據分布帶來了一定的阻礙。雖然變密度簇擁有非均勻的簇內密度，但簇內核心區域的局部密度總是相對較高，且簇內密度變化趨勢相對穩定。本文算法使用高密度區域的核心點生成簇主干，核心區域的高密度特性和自適應的密度可達閾值使得簇主干的識別受簇密度變化的影響很小，降低了該過程對變密度簇的敏感性。簇主干可以體現一個簇的主體結構，有效地反映了簇的內部結構信息，其余的低密度點本質上都依托于簇主干來判定其歸屬簇，因此理論上本文算法對變密度簇不敏感。

為了驗證本文算法對變密度簇的敏感性，本文在調整的Compound 數據集上進行了實驗。針對數據集左上角的變密度簇（如圖10（a）中紅圈所示），本文以10%為步長，按80%～150%的比例縮放簇內數據點間的距離來模擬簇密度變化的情景，不同縮放比例下的聚類結果如圖10 所示，聚類指標如表6 所示。可以看出，在多個比例的縮放下，本文算法均能有效識別簇，評價指標均高于0.95。當縮放比例達到140%及以上時，由于縮放比例過大導致變密度簇下方邊緣區域的點距離整個簇過遠，且更靠近左下方高密度簇，因此未能正確識別該區域的少部分點，但仍可以識別變密度簇中的大部分點。實驗結果表明DCBAT 在調整后的Compound 數據集上的聚類性能良好，對變密度簇不敏感，可以保證聚類精度。

5 結束語

為了解決聚類中任意簇識別困難、對簇內密度變化敏感以及閾值確定困難等問題，本文提出了DCBAT 算法。DCBAT 將具備高局部密度和高相對距離且彼此相互可達的數據點識別為簇主干，并以此為基準劃分剩余數據點得到初始簇，接著對初始簇進行拆分處理得到最終聚類結果。新定義的兩種閾值基于數據分布計算得到，具有良好的自適應性。同時，利用簇內密度變化趨勢來決定是否拆分初始簇，更好地考慮了數據的內部結構，有效降低了算法對變密度簇的敏感性，提高了聚類精度。為了驗證DCBAT 算法的有效性，本文選擇了五種先進算法在八個不同維度和各具特點的數據集上與本文算法進行了對比實驗。結果表明DCBAT 算法相較于對比算法具有良好的性能，能更精確地識別任意簇，對異常點不敏感，算法結果穩定。在將來的研究中，擬基于簇內密度變化趨勢進行縱向研究，提出更多高效的聚類算法。