自適應(yīng)閾值約束的密度簇主干聚類算法

張錦宏，陳 梅，張 弛

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 相關(guān)定義與說明

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

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

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

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

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

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

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

定義5（基于數(shù)據(jù)分布的數(shù)據(jù)點密度可達(dá)自適應(yīng)閾值）一組數(shù)據(jù)的偏度系數(shù)表征著數(shù)據(jù)分布的偏態(tài)程度，且密度可達(dá)閾值與數(shù)據(jù)集中點的密度分布情況息息相關(guān)。基于偏度系數(shù)調(diào)整密度均值的數(shù)據(jù)點密度可達(dá)自適應(yīng)閾值的計算公式如下：

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

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

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

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

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

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

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

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

3 自適應(yīng)閾值約束的密度簇主干聚類算法

3.1 算法思想

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

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

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

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

3.2 算法聚類過程

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

算法1DCBAT執(zhí)行總過程

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

3.2.1 獲取簇主干

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

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

3.2.2 生成初始簇

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

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

3.2.3 拆分初始簇得到最終簇

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

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

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

3.3 時間復(fù)雜度分析

設(shè)數(shù)據(jù)集D的大小為n，近鄰數(shù)量參數(shù)為k。

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

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

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

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

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

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

3.5 基于簇主干發(fā)現(xiàn)簇

經(jīng)典聚類算法如k-means 根據(jù)數(shù)據(jù)點與簇心之間的距離關(guān)系識別簇；DBSCAN 算法從單個數(shù)據(jù)點出發(fā)，基于密度可達(dá)性自底向上地發(fā)現(xiàn)整個簇；CFDP算法通過識別每個簇的聚類中心進(jìn)而發(fā)現(xiàn)簇。以上經(jīng)典算法聚類時僅考慮了單個數(shù)據(jù)點，缺乏對數(shù)據(jù)內(nèi)部整體結(jié)構(gòu)的考量。DCBAT充分考慮了數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，通過識別簇主干完成聚類。簇主干是一個簇的骨架，體現(xiàn)了簇內(nèi)數(shù)據(jù)點的分布特征，基于簇主干聚類不僅考慮了數(shù)據(jù)點間的關(guān)聯(lián)關(guān)系，還考慮了數(shù)據(jù)的內(nèi)部結(jié)構(gòu)特征，利用數(shù)據(jù)點與簇主干間的關(guān)系去識別簇。點間聯(lián)系與數(shù)據(jù)結(jié)構(gòu)特征的綜合考量保證了聚類結(jié)果的可靠性，有助于準(zhǔn)確識別簇。

4 實驗與結(jié)果分析

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

4.1 實驗數(shù)據(jù)集

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

表2 數(shù)據(jù)集信息Table 2 Information of datasets

4.2 對比算法說明

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

4.3 聚類評價指標(biāo)

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

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

NMI 是一個基于信息論的聚類結(jié)果評價標(biāo)準(zhǔn)，其計算公式為：

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

ARI是蘭德系數(shù)的調(diào)整形式，其衡量的是兩個數(shù)據(jù)分布的吻合程度，計算公式如下：

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

3 個指標(biāo)的取值越大說明聚類結(jié)果越接近數(shù)據(jù)的真實分布。對于二維數(shù)據(jù)集的實驗結(jié)果還以散點圖的形式進(jìn)行了可視化展示。

4.4 DCBAT算法及對比算法的參數(shù)

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

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

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

4.5 實驗結(jié)果及分析

4.5.1 二維數(shù)據(jù)集

圖2～圖6 分別展示了DCBAT 及對比算法在5 個二維數(shù)據(jù)集上的聚類結(jié)果，表5 統(tǒng)計了相應(yīng)的Acc、ARI 和NMI，由于T4 數(shù)據(jù)集沒有真實類標(biāo)，表5 中無對應(yīng)數(shù)據(jù)。

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

表5 DCBAT及對比算法的聚類指標(biāo)量化結(jié)果Table 5 Quantitative results of DCBAT and compared algorithms

（1）Aggregation數(shù)據(jù)集

Aggregation 數(shù)據(jù)集中包含典型的凸?fàn)畲兀貎?nèi)密度均勻，每個簇的密度大小相對統(tǒng)一，但不同簇中包含的數(shù)據(jù)點數(shù)量差異較大，且存在通過若干數(shù)據(jù)點相連在一起的兩對簇，這也是該數(shù)據(jù)集的聚類難點所在。圖2展示了DCBAT 與對比算法在該數(shù)據(jù)集上的聚類結(jié)果，其中圖2（g）為Aggregation 的真實簇分布情況，圖2（a）～（f）分別為DCBAT 及對比算法在該數(shù)據(jù)集上的聚類結(jié)果。

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

（2）Compound數(shù)據(jù)集

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

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

（3）Spiral數(shù)據(jù)集

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

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

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

（4）Flame數(shù)據(jù)集

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

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

（5）T4數(shù)據(jù)集

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

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

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

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

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

4.5.2 多維數(shù)據(jù)集

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

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

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

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

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

綜上所述，DCBAT算法基于核心點可達(dá)的思想，利用簇內(nèi)數(shù)據(jù)點密度變化趨勢平穩(wěn)的特點實現(xiàn)了任意簇的高效識別，算法整體具有魯棒性。

4.6 變密度簇敏感性分析

變密度簇識別一直是聚類分析的難點所在，給識別數(shù)據(jù)分布帶來了一定的阻礙。雖然變密度簇?fù)碛蟹蔷鶆虻拇貎?nèi)密度，但簇內(nèi)核心區(qū)域的局部密度總是相對較高，且簇內(nèi)密度變化趨勢相對穩(wěn)定。本文算法使用高密度區(qū)域的核心點生成簇主干，核心區(qū)域的高密度特性和自適應(yīng)的密度可達(dá)閾值使得簇主干的識別受簇密度變化的影響很小，降低了該過程對變密度簇的敏感性。簇主干可以體現(xiàn)一個簇的主體結(jié)構(gòu)，有效地反映了簇的內(nèi)部結(jié)構(gòu)信息，其余的低密度點本質(zhì)上都依托于簇主干來判定其歸屬簇，因此理論上本文算法對變密度簇不敏感。

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

5 結(jié)束語

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