張 梅，陳 梅，李 明

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

1 引言

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

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

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

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

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

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

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

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

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

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

2.1 相關(guān)定義

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

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

定義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個(gè)點(diǎn),n為數(shù)據(jù)集中點(diǎn)的個(gè)數(shù)。

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

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

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

(1)

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

Di=DHi-DLi

(2)

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

2.2 DBLCM聚類過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集說明

實(shí)驗(yàn)采用的二維數(shù)據(jù)集有Aggregation、Compound、Spiral和Toy，其中Toy數(shù)據(jù)集引用于文獻(xiàn)[17]，其它的二維數(shù)據(jù)集均來自于東芬蘭大學(xué)的網(wǎng)站(http://cs.joensuu.fi/sipu/datasets/)。數(shù)據(jù)集包含球狀簇、螺旋簇、均勻密度簇和不均勻密度簇，能分別代表數(shù)據(jù)點(diǎn)的各種復(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 對(duì)比算法說明

本節(jié)將使用3個(gè)經(jīng)典算法和3個(gè)優(yōu)秀的新算法作為對(duì)比算法，其中DBLCM算法的代碼用Python語言實(shí)現(xiàn)，k-Means[4]和DBSCAN算法[6]均來自“scikit-learn”(http://scikit-learn.org/stable/index.html)庫(kù)中,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與對(duì)比算法在Aggregation 數(shù)據(jù)集上的聚類結(jié)果

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

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

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

3.4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5中統(tǒng)計(jì)了DBLCM和對(duì)比算法在4個(gè)多維數(shù)據(jù)集上的量化結(jié)果。圖7a和圖7b采用直方圖的方式，說明DBLCM算法在Glass、Iris和Leaf 3個(gè)數(shù)據(jù)集上ARI和NMI指標(biāo)排名都高于對(duì)比算法。而在數(shù)據(jù)集SPECTF上，雖然DBSCAN算法具有排名最高的NMI指標(biāo)，但ARI指標(biāo)值為0，該情況下算法的劃分結(jié)果是無效的?？v觀其他算法在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與對(duì)比算法在二維數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)直方圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.7 DBLCM算法特點(diǎn)分析

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

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

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

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

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

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

4 結(jié)束語

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