基于局部中心度量的邊界點劃分密度聚類算法*

張 梅，陳 梅，李 明

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

1 引言

在科學研究中，人們希望在無任何先驗知識的情況下挖掘出數(shù)據(jù)內(nèi)部潛在的特性，而聚類分析技術(shù)正好解決了這一問題[1]。聚類分析是一種無監(jiān)督的學習方式，通過簇內(nèi)數(shù)據(jù)間相似性高、簇間數(shù)據(jù)相似性低的原則來發(fā)現(xiàn)數(shù)據(jù)點在數(shù)據(jù)集中的真實分布[2]。

目前已有多種聚類算法被提出[3]。k-Means[4]和k-Mediods[5]算法是2種典型的基于劃分的算法。該類算法通常需要用戶提前輸入簇個數(shù)，通過迭代使得簇內(nèi)誤差平方和最小來獲得最終劃分結(jié)果，因此基于劃分的方法只能識別球狀簇。基于密度的噪聲應(yīng)用空間聚類DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[6]能夠在具有噪聲的數(shù)據(jù)中將高密度區(qū)域劃分成簇，但不同參數(shù)組合對最終聚類效果影響很大；OPTICS (Ordering Points To Identify the Clustering Structure)[7]會生成一個增廣的有序序列簇，不同密度對應(yīng)不同簇劃分結(jié)果，雖然參數(shù)選取較容易，但由于其實現(xiàn)涉及到二叉樹，生成的又是增廣序列，因此計算量較大、速度較慢。Chamelon算法[8]是典型的層次聚類算法，它采用動態(tài)模型來確定簇之間的相似性，雖然算法發(fā)現(xiàn)子簇的能力很強，但時間復(fù)雜度相對較高。網(wǎng)格聚類算法中較有代表性的是STING算法[9]，此算法雖適合大數(shù)據(jù)集，但對數(shù)據(jù)維度的可伸縮性較差，網(wǎng)格劃分過細時，計算復(fù)雜度較高。

近幾年來，為了能識別任意形狀、任意密度的簇，聚類研究領(lǐng)域?qū)W者們相繼提出了新的聚類算法[10 -12]。CLASP 算法[13]借鑒了基于劃分和基于層次的方法，使用k-Means獲取簇代表點，并根據(jù)互k近鄰相似性度量進行聚類，但輸入?yún)?shù)過多。CFDP(Clustering by Fast search and find of Density Peaks)算法[14]巧妙地將基于密度和基于劃分的方法相結(jié)合，它認為簇中心點的密度大，與其他密度更大的數(shù)據(jù)點間的“距離”相對更遠。算法可使用決策圖來選定聚類中心點，但它不能識別含有多個中心點構(gòu)成的簇。MulSim(a novel Similar-to-Multiple-point clustering algorithm)算法[15]考慮了單點和多點之間的相似原則，它認為當前點與另一點相似，同時也和該點的多個鄰居相似，那么這2點就會被分配到同一簇中。這種方式通過更為嚴格的條件限制，進一步保證了算法能夠有效地發(fā)現(xiàn)任意形狀、任意密度的簇。由以上分析可知基于密度的聚類算法對任意簇的數(shù)據(jù)集識別效果更好，因此本文將在密度算法的基礎(chǔ)上進行研究。

上述密度聚類算法存在輸入?yún)?shù)過多、參數(shù)選取敏感及迭代次數(shù)過多等缺點。為解決這類問題，本文提出基于局部中心度量的邊界點劃分密度聚類DBLCM(Density clustering algorithm of Boundary point division based on Local Center Measure)算法。該算法更側(cè)重考慮數(shù)據(jù)點的不同分布，克服以數(shù)據(jù)點局部密度作為局部中心度量的缺陷，如局部密度閾值較難給定、不同數(shù)據(jù)集中各簇的密度不均勻以及使用靜態(tài)密度設(shè)置方式難以識別數(shù)據(jù)集的真實分布[16]等問題。由于數(shù)據(jù)分布往往和數(shù)據(jù)點間的距離正相關(guān)，因此本文選用數(shù)據(jù)點對距離來充當局部中心度量，同時定義了基于互近鄰信息彌補的雙向絕對距離。根據(jù)雙向絕對距離與局部中心度量，數(shù)據(jù)點被劃分到核心區(qū)域或邊界區(qū)域。然后，將核心區(qū)域的點與它的互近鄰中高密度點合并形成初始簇。接著，將邊界區(qū)域的點加入到其最近鄰點所在的初始簇，得到最終簇。本文所提算法屬于非啟發(fā)式算法，無需迭代，輸入?yún)?shù)易確定，能識別任意簇，從而反映數(shù)據(jù)集的真實分布。

2 基于局部中心度量的邊界點劃分密度聚類算法

一般而言，核心區(qū)域的點具有較高的局部密度值，而邊界區(qū)域的點往往具有較低的局部密度值[16]。本文從距離角度出發(fā)提出DBLCM算法，定義數(shù)據(jù)點對的距離作為局部中心度量，以包含雙向信息的互近鄰距離來定義新的距離函數(shù)。

Figure 1 Clustering results of DBLCM algorithm圖1 DBLCM算法聚類結(jié)果示例

DBLCM通過3個主要階段得到正確的簇結(jié)構(gòu)，以Compound數(shù)據(jù)集為例，3個階段產(chǎn)生的簇如圖1所示。

第1階段在局部中心度量原則下，根據(jù)數(shù)據(jù)點的不同分布將其劃分到核心區(qū)域或邊界區(qū)域。第2階段對核心區(qū)域內(nèi)的點進行分配，每個數(shù)據(jù)點尋找互近鄰中距離最近且密度比其大的點進行合并。圖1b展示了核心區(qū)域點成簇的結(jié)果。該階段，DBLCM已將大部分點識別出來，直接決定了算法形成的初始簇的準確性。第3階段，對處于邊界區(qū)域內(nèi)的未標記點再進行分配，分配方式為尋找互近鄰中最近大密度點所在簇進行分配。本階段結(jié)束后，DBLCM獲得了最終的簇結(jié)構(gòu)，如圖1c所示。算法結(jié)束，可以對比圖1a中數(shù)據(jù)集的真實分布，DBLCM除左上角相接的2個簇的邊界部分中的一個點劃分錯誤外，其他點都準確識別。

同一個參數(shù)k值對應(yīng)的互近鄰集合是唯一的，“距離+密度”的尋找方式無疑確定了被尋找點的唯一互近鄰，因此形成的初始簇是穩(wěn)定不變的。后期邊界點只需要間接尋找互近鄰中最近鄰點所在的簇合并即可。同一參數(shù)k下無論算法運行多少次，初始簇的結(jié)構(gòu)都保持不變。

2.1 相關(guān)定義

為了方便后文描述清晰，將本文涉及到的符號定義總結(jié)如表1所示。

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

定義1(數(shù)據(jù)集D) 聚類是通過發(fā)掘內(nèi)部潛在的結(jié)構(gòu)將原始數(shù)據(jù)集劃分為不同子集的過程。在本文中,數(shù)據(jù)集D定義為：D={x1,x2,…,xi,…,xn}，xi表示數(shù)據(jù)集D中的第i個點,n為數(shù)據(jù)集中點的個數(shù)。

定義2(k-近鄰) 在數(shù)據(jù)集D中，按照歐氏距離將點的鄰居由近到遠排序，順序排在前k位的點被稱為xi的k-近鄰，記為Nk(xi)，Nk(xi)?D。

定義3(互k-近鄰) 在數(shù)據(jù)集D中，存在2點xi和xj，若xi在xj的k-近鄰集合中，同時xj也在xi的k-近鄰集合中，這時稱xi和xj互為k-近鄰，否則不存在互k-近鄰關(guān)系。xi的互k-近鄰,記為MNk(xi)。

定義4(點的局部密度) 數(shù)據(jù)集中點的局部密度與該點周圍的鄰居個數(shù)有關(guān)，本文采用式(1)計算數(shù)據(jù)點的局部密度。

(1)

定義5(點的距離) 數(shù)據(jù)點間的距離反映了數(shù)據(jù)分布的稀疏程度，本文新定義了基于互k-近鄰的雙向絕對距離度量方式，如式(2)所示：

Di=DHi-DLi

(2)

其中，Di表示點xi的新距離，DHi表示點xi與其互k-近鄰中距離最近且密度比其大的點之間的歐氏距離，DLi表示點xi與其互k-近鄰中距離最近且密度比其小的點之間的歐氏距離。很明顯，單一考慮2點之間的絕對距離不能適應(yīng)各類不同數(shù)據(jù)的動態(tài)變化，而基于互k-近鄰的雙向距離度量方式本質(zhì)上計算的是以該點為中心,合并其他數(shù)據(jù)點所能達到的有效范圍。

2.2 DBLCM聚類過程

DBLCM算法需要一個輸入?yún)?shù)，即點的近鄰個數(shù)k。算法主要通過3個階段來實現(xiàn)對數(shù)據(jù)集中簇的準確識別。首先計算數(shù)據(jù)點的局部密度和距離；接著根據(jù)局部中心度量原則劃分核心區(qū)域和邊界區(qū)域，核心區(qū)域的點形成初始簇；最后將邊界區(qū)域中的未標記的點進行分配形成最終簇。算法流程如算法1所示。

算法1基于局部中心度量的邊界點劃分密度聚類算法DBLCM

輸入：數(shù)據(jù)集D，近鄰個數(shù)k。

輸出：最終簇結(jié)構(gòu)cluster。

步驟1使用k-d樹獲得數(shù)據(jù)集D中所有點的k-近鄰矩陣。

步驟2在k-近鄰矩陣的基礎(chǔ)上獲得數(shù)據(jù)集D的互近鄰集合M。

步驟3根據(jù)不同數(shù)據(jù)集分布的特點得到局部中心度量閾值，使用式(1)計算所有點的局部密度ρi，追加到局部密度ρ集合中。

步驟4利用式(2)獲得所有點的絕對距離，并將其追加到點距離集合point_dist中。

步驟5遍歷point_dist，判斷集合中每個點的雙向絕對距離與局部中心度量閾值MD的關(guān)系，若point_disti

步驟5.1進入核心區(qū)域的點需要尋找互近鄰中距離它最近且密度比它大的數(shù)據(jù)點成簇，得到初始簇的正確劃分結(jié)果；

步驟5.2邊界區(qū)域的點進入待分配點集合unassign_cluster中;

步驟6對待分配點集合unassign_cluster中的點判斷其互k-近鄰中距離最近點與閾值的關(guān)系，確認該點是離群點還是簇內(nèi)的邊界點，繼而添加到初始簇中，得到最終簇結(jié)構(gòu)cluster；

步驟7算法結(jié)束。

以上6個步驟執(zhí)行完成之后，可得到對應(yīng)數(shù)據(jù)集的最終簇結(jié)構(gòu)。算法整個分配過程按步驟順序執(zhí)行，當數(shù)據(jù)集中的所有點被分配結(jié)束(即所有點都分配了類標)，算法就會自動停止，無需人為輸入停止迭代的參數(shù)。

DBLCM在初始階段首先借助k-近鄰矩陣來獲得互k-近鄰集合，步驟2中根據(jù)定義3判斷數(shù)據(jù)集中的每個點xi以及鄰居xj是否滿足互k-近鄰關(guān)系，滿足條件則將xj添加至xi的互k-近鄰集合保存，否則掃描下一個數(shù)據(jù)點，直到所有點訪問結(jié)束。步驟3計算點的局部密度和距離，其中式(1)用來計算每個數(shù)據(jù)點的局部密度ρi，對于點xi，若該點與其鄰居xj的歐氏距離小于閾值MD，可認為xj為xi的有效鄰居，反之xi的鄰居中不統(tǒng)計xj。其中，MD為設(shè)定的局部中心度量閾值，通過計算數(shù)據(jù)點對歐氏距離(不包含點自身的距離)，整體升序排序后取所有距離總數(shù)的0.02位次位置對應(yīng)值作為固定值賦予MD。步驟4利用式(2)計算每個點xi的新的絕對距離point_disti，在步驟2存儲的互k-近鄰列表中分別尋找比點xi密度大且離xi最近的鄰居xj,計算xi與xj的距離，尋找比點xi密度小且離其最近的鄰居xs,計算xi與xs的距離。

步驟5中，對于每個點xi，若絕對距離小于閾值MD，則認為該點處于核心區(qū)域;反之則認為該點處于邊界區(qū)域，將其添加到待分配簇中。對處于核心區(qū)域的點，依次遍歷，將點xi添加到其互k-近鄰中距離最近且密度比它大的鄰居點所在的簇。直到核心區(qū)域中的數(shù)據(jù)點遍歷結(jié)束，至此形成初始簇。

步驟6中，為了區(qū)分待分配簇中的點是屬于簇內(nèi)的邊界點還是離群點，算法采用間接判斷點xi的互k-近鄰中與其距離最近點的距離和閾值MD大小的方式，若點xi近鄰點的距離小于MD，表明該點分布在離簇較稀疏的部分，但仍屬于簇內(nèi)的有效點，因此將點xi分配給近鄰點所在的簇;反之將點xi視為離群點，直接更新點xi的類標值為-2。

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

為了評估DBLCM算法的有效性，本節(jié)將DBLCM與3個經(jīng)典算法和3個近幾年聚類領(lǐng)域?qū)W者新提出的優(yōu)秀算法，在包含任意形狀、任意密度的二維數(shù)據(jù)集及多維數(shù)據(jù)集上進行實驗對比。其中二維數(shù)據(jù)集的規(guī)模不大，方便采用可視化圖形展示方式對聚類效果進行呈現(xiàn)。為了在同一標準上更好地展示算法的性能，本文采用ARI(Adjusted Rand Index)和NMI(Normalized Mutual Information)2個外部評價指標進行量化評估。另外，本節(jié)還對DBLCM中參數(shù)k的敏感性、各對比算法的時間復(fù)雜度分別進行了分析說明。

3.1 實驗數(shù)據(jù)集說明

實驗采用的二維數(shù)據(jù)集有Aggregation、Compound、Spiral和Toy，其中Toy數(shù)據(jù)集引用于文獻[17]，其它的二維數(shù)據(jù)集均來自于東芬蘭大學的網(wǎng)站(http://cs.joensuu.fi/sipu/datasets/)。數(shù)據(jù)集包含球狀簇、螺旋簇、均勻密度簇和不均勻密度簇，能分別代表數(shù)據(jù)點的各種復(fù)雜分布。采用的多維數(shù)據(jù)集有Glass、Iris、Leaf和SPECTF，均來自UCI網(wǎng)站(http://archive.ics.uci.edu/ml/datasets.html)。各數(shù)據(jù)集的具體信息如表2所示。

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

3.2 對比算法說明

本節(jié)將使用3個經(jīng)典算法和3個優(yōu)秀的新算法作為對比算法，其中DBLCM算法的代碼用Python語言實現(xiàn)，k-Means[4]和DBSCAN算法[6]均來自“scikit-learn”(http://scikit-learn.org/stable/index.html)庫中,OPTICS算法[7]代碼來自GitHub，CLASP[13]、CFDP[14]和MulSim[15]代碼均由論文作者提供。

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

3.3 DBLCM算法及對比算法的參數(shù)

DBLCM算法及各對比算法具體參數(shù)如表3所示。

Table 3 Parameters description of the algorithms 表3 DBLCM算法及各對比算法參數(shù)

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

3.4.1 二維數(shù)據(jù)集上的結(jié)果分析說明

(1)Aggregation數(shù)據(jù)集。

Aggregation是一個球狀簇數(shù)據(jù)集，該數(shù)據(jù)集的簇內(nèi)密度比較均勻。聚類難點在于每個簇的大小不一，且數(shù)據(jù)集中的4個簇兩兩之間通過幾點連線的方式連接在一起。圖2所示為DBLCM與6個對比算法在該數(shù)據(jù)集上的可視化結(jié)果。其中圖2a為Aggregation的真實分布圖，圖2b～圖2h為6個對比算法的聚類結(jié)果圖。

從圖2 可以看出，在Aggregation數(shù)據(jù)集上，DBLCM和CFDP算法均準確識別出了簇的真實結(jié)構(gòu)，其中DBLCM算法采用了恰當?shù)木植恐行亩攘恐担瑒澐值暮诵膮^(qū)域的點遵循互近鄰一致性原則聚類，保證了在初始簇的尋找階段就將4個簇的連接部分劃分開來，解決了識別的難點。而k-Means算法受初始聚類中心的影響，識別出7個球狀簇，破壞了原簇的真實結(jié)構(gòu)。DBSCAN算法采用靜態(tài)密度設(shè)置方式，左上角簇中處于邊緣的點沒有正確識別，同時右邊的2個簇的中間銜接部分也沒有斷開。OPTICS算法對識別的效果雖然相對DBSCAN有所改進，但邊界區(qū)域仍有幾個點錯分。CLASP算法因借鑒k-Means來選取初始中心點，造成了左上角簇被劃分為2個小簇，因此結(jié)果也一般。MulSim算法除右邊2個簇連接部分的2個數(shù)據(jù)點被識別錯外，其他點均正確識別，較完美地解決了該數(shù)據(jù)集的識別難點。

Figure 3 Clustering results of DBLCM and the contrast algorithms on the Compound dataset圖3 DBLCM與對比算法在Compound 數(shù)據(jù)集上的聚類結(jié)果

(2)Compound數(shù)據(jù)集。

Compound數(shù)據(jù)集是不均勻密度的簇，識別的難點在于每個簇密度分布不一，同時包含多個中心點形成的簇。圖3所示為DBLCM與6個對比算法在該數(shù)據(jù)集上的可視化結(jié)果，其中圖3a為Compound的真實分布圖，圖3b～圖3h為6個對比算法的聚類結(jié)果圖。

從圖3可以看出，在Compound數(shù)據(jù)集上，DBLCM相較于真實分布只錯誤劃分了左上角2個簇間邊界的一個銜接點，識別效果優(yōu)于其他對比算法。而k-Means算法將左下角和右邊包含2個中心點的簇劃分成左右各半。CFDP算法受其思想的限制，沒有正確識別出包含2個中心點的簇。DBSCAN和OPTICS算法均因為靜態(tài)密度的設(shè)置在該數(shù)據(jù)集上的聚類遇到了困難。CLASP算法也沒有將右邊的簇正確識別出來。MulSim算法除2個簇中的幾個邊界點識別錯誤外，其余部分均正確識別了，較大程度上解決了數(shù)據(jù)集的識別難點。

(3)Spiral數(shù)據(jù)集。

Spiral數(shù)據(jù)集中的簇呈螺旋型的分布，密度隨螺旋的方向不一。圖4所示為DBLCM與6個對比算法在該數(shù)據(jù)集上的可視化結(jié)果，其中圖4a為Spiral的真實分布圖，圖4b～圖4h為6個對比算法的聚類結(jié)果圖。

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

從圖4可以看出，在Spiral數(shù)據(jù)集上，DBLCM、DBSCAN、CFDP和MulSim均正確識別出了真實的簇結(jié)構(gòu)。而k-Means、CLASP 2種算法只考慮了數(shù)據(jù)點間的絕對距離和基于單個中心點的聚類方式而導致識別效果很差。OPTICS算法受密度設(shè)置的影響只對密度大的點正確識別了，大多數(shù)點被識別為異常點。

(4)Toy數(shù)據(jù)集。

Toy是具有2個中心點的數(shù)據(jù)集。圖5所示為DBLCM與6個對比算法在該數(shù)據(jù)集上的可視化結(jié)果，其中圖5a為Toy的真實分布圖，圖5b～圖5h為6個對比算法的聚類結(jié)果圖。

從圖5可以看出，在Toy數(shù)據(jù)集上，DBLCM、DBSCAN、CLASP和MulSim均正確識別出了真實的簇結(jié)構(gòu)。而k-Means和CFDP將原簇劃分為了左右2個簇，沒有識別出簇的主要部分，原因在于它們都只是基于一個中心點的思想進行聚類，從而對該類基于多個中心點的數(shù)據(jù)集基本無效。OPTICS算法除了在靜態(tài)密度的限制下將內(nèi)部簇的邊界點劃分為離群點外，也識別出了基本正確的簇結(jié)構(gòu)。

表4統(tǒng)計了DBLCM與對比算法在二維數(shù)據(jù)集上的指標量化結(jié)果。從表4的統(tǒng)計結(jié)果看出，DBLCM性能整體優(yōu)于對比算法，評價指標準確反映了DBLCM能對數(shù)據(jù)集進行真實劃分。

圖2～圖5從可視化的角度展示了DBLCM和6個對比算法在二維數(shù)據(jù)集上的聚類結(jié)果。為了更加直觀地突出DBLCM算法相較于其他算法的優(yōu)勢，圖6采用直方圖的方式來展現(xiàn)。

Table 4 Quantitative results on two-dimensional datasets表4 二維數(shù)據(jù)集上指標量化結(jié)果

從圖6a和圖6b 2幅圖可以觀察到，DBLCM算法在本文使用的4個二維數(shù)據(jù)集上的2項指標均高于其他算法的對應(yīng)指標，這也表明了DBLCM識別到的最終簇的質(zhì)量高，算法整體優(yōu)于其他算法。

3.4.2 多維數(shù)據(jù)集結(jié)果分析說明

為了測試DBLCM在多維度數(shù)據(jù)集上的聚類效果，本節(jié)選用Glass、Iris、Leaf和SPECTF 4個多維數(shù)據(jù)集(http://cs.joensuu.fi/sipu/datasets/)進行實驗。考慮到多維數(shù)據(jù)集對應(yīng)的不同維數(shù)屬性的量級不一致，實驗中對數(shù)據(jù)集的每一維做了Z-score標準化處理。聚類最終效果采用直方圖方式來分析性能優(yōu)劣。

表5中統(tǒng)計了DBLCM和對比算法在4個多維數(shù)據(jù)集上的量化結(jié)果。圖7a和圖7b采用直方圖的方式，說明DBLCM算法在Glass、Iris和Leaf 3個數(shù)據(jù)集上ARI和NMI指標排名都高于對比算法。而在數(shù)據(jù)集SPECTF上，雖然DBSCAN算法具有排名最高的NMI指標，但ARI指標值為0，該情況下算法的劃分結(jié)果是無效的。縱觀其他算法在SPECTF數(shù)據(jù)集上的表現(xiàn)，DBLCM算法在SPECTF上僅次于MulSim算法，具有次優(yōu)ARI和NMI結(jié)果。

Figure 6 Index histogram of DBLCM and the contrast algorithms on two-dimensional datasets圖6 DBLCM與對比算法在二維數(shù)據(jù)集上的評價指標直方圖

Table 5 Quantitative results on multi-dimensional datasets表5 多維數(shù)據(jù)集上指標量化結(jié)果

Figure 7 Index histogram of DBLCM and the contrast algorithms on multi-dimensional datasets圖7 DBLCM與對比算法在多維數(shù)據(jù)集上的評價指標直方圖

各對比算法的參數(shù)通過大量的實驗尋優(yōu)獲得，不同數(shù)據(jù)集適用參數(shù)匯總?cè)绫?所示。

最后，為顯示算法在不同維度、任意密度、任意簇的數(shù)據(jù)集上的綜合性能,繪制了DBLCM在8個數(shù)據(jù)集上的NMI量化指標箱線圖，如圖8所示。圖8中各對比算法對應(yīng)的箱線圖有以下特征：〇表示溫和的異常值，即和正常數(shù)據(jù)偏差較小；黑色箱體的上下邊界分別表示數(shù)據(jù)分布中的上下四分位數(shù)，箱體的中間白色虛線表示數(shù)據(jù)分布中的中位數(shù)；箱體上下兩端的短橫線表示數(shù)據(jù)分布中最大值與最小值。

從圖8所示箱線圖中可以看出，DBLCM算法對應(yīng)的各項特征所處的位置都高于其他算法的特征的，說明本文算法在8個數(shù)據(jù)集上的值相對穩(wěn)定，綜合聚類性能優(yōu)于其他對比算法。

綜上所述，DBLCM算法在局部中心度量原則下，達到了高效識別任意簇的目的，和其他對比算法相比，DBLCM更具魯棒性。

Table 6 Parameter statistics of DBLCM and the contrast algorithms on datasets表6 DBLCM及對比算法在數(shù)據(jù)集上的參數(shù)統(tǒng)計

Figure 8 NMI indicators of DBLCM on 8 datasets圖8 DBLCM在8個數(shù)據(jù)集上NMI指標

3.5 參數(shù)敏感性分析

本節(jié)測試DBLCM對輸入?yún)?shù)k(近鄰個數(shù))的敏感性。實驗用到前文的8個數(shù)據(jù)集，通過更改k值來記錄聚類后簇的質(zhì)量。

由于DBLCM在形成初始簇階段采用互k-近鄰吸引的方式，因此合適的k值直接決定著聚類后簇的質(zhì)量。本節(jié)根據(jù)表6中DBLCM在各數(shù)據(jù)集上能取得的最優(yōu)結(jié)果對應(yīng)的參數(shù)k范圍繪制了圖9。從圖9可以看出，隨著k的增長，挖掘到的各數(shù)據(jù)集的簇的質(zhì)量在逐漸變高。同時也發(fā)現(xiàn)，當k值為5時，絕大多數(shù)數(shù)據(jù)集評價指標均能達到最優(yōu)指標的95%，當k大于5后，評價指標值隨k值增大逐漸穩(wěn)定，變化幅度不大。以上分析說明DBLCM對參數(shù)k不敏感。

Figure 9 Sensitivity test of parameter k for DBLCM algorithm圖9 DBLCM算法中參數(shù)k的敏感性測試

3.6 DBLCM算法時間復(fù)雜度分析

DBLCM算法首先使用k-d樹[18]來構(gòu)建k-近鄰矩陣，時間復(fù)雜度為O(n·logn)，n代表數(shù)據(jù)集D中點的數(shù)目。然后尋找互近鄰和計算點的局部密度均花費O(n·k)，其中k代表最近鄰個數(shù)。3個步驟對應(yīng)時間復(fù)雜度可近似記為O(n·logn)。接著形成初始簇的時間花費為O(n·k)。最后邊界區(qū)域的點分配的時間花費為O(m·k),其中,m為未分配簇列表中點的個數(shù)，通常情況下m?n，時間復(fù)雜度可以忽略不計。因此,DBLCM的總時間復(fù)雜度為O(n·logn)。

3.7 DBLCM算法特點分析

(1)DBLCM算法有效彌補了靜態(tài)密度設(shè)置方法的缺陷。

經(jīng)典的密度聚類算法常選用靜態(tài)密度設(shè)置的方式來獲得密度閾值，不能得到一個普適的閾值參數(shù)。而DBLCM算法考慮了數(shù)據(jù)集的不同分布，提出了自適應(yīng)密度的計算方式，將連接緊密但比較稀疏的2個簇成功斷開，從而較好地解決了經(jīng)典聚類算法遇到的密度設(shè)置問題。

(2)DBLCM算法有效彌補了單向距離挖掘數(shù)據(jù)方式的缺陷。

聚類算法例如k-Means、DBSCAN和OPTICS都需要生成一個相似性矩陣，常采用單向距離決定的數(shù)據(jù)挖掘方式。而DBLCM算法考慮了基于互k-近鄰的雙向絕對距離方式，本質(zhì)上計算的是以該點為中心，合并其它數(shù)據(jù)點所能達到的有效范圍。算法前期操作為初始簇的形成奠定了基礎(chǔ)，同時也大大提高了初始簇的劃分精確度。

(3)DBLCM算法穩(wěn)定，無需迭代，對參數(shù)不敏感，同一參數(shù)下結(jié)果唯一。

密度聚類算法中不同的參數(shù)組合對聚類結(jié)果影響大，涉及到誤差函數(shù)的還需要迭代多次尋優(yōu)。而DBLCM算法對參數(shù)k的選取不敏感，初始簇的形成穩(wěn)定、質(zhì)量高，算法無需迭代，同一參數(shù)下聚類結(jié)果唯一。

4 結(jié)束語

為了解決聚類中任意簇檢測精確度不高、迭代次數(shù)多及效果不佳等缺點，本文提出DBLCM算法。為了驗證DBLCM算法的有效性，本文選用了6個有代表性的優(yōu)秀對比算法在二維數(shù)據(jù)集及多維數(shù)據(jù)集上進行了對比實驗。另外，為了驗證DBLCM算法對參數(shù)k的敏感性，在本文使用的8個數(shù)據(jù)集上均做了測試。實驗結(jié)果表明，DBLCM算法相較于對比算法具有良好的性能，識別精確度更高，檢測任意簇的效果更好，而且對參數(shù)k的選取不敏感，算法無需迭代。