帶有成對(duì)約束半監(jiān)督聚類(lèi)算法C-DBSCAN的設(shè)計(jì)與實(shí)現(xiàn)

閆 軍

(太原旅游職業(yè)學(xué)院，山西 太原 030032）

一、概述

數(shù)據(jù)挖掘作為一種從大量數(shù)據(jù)中發(fā)現(xiàn)感興趣信息的技術(shù)，已經(jīng)得到日益廣泛的應(yīng)用。而聚類(lèi)是一種重要的數(shù)據(jù)挖掘技術(shù)，其任務(wù)是將數(shù)據(jù)集分成若干個(gè)簇。同一個(gè)簇中的數(shù)據(jù)具有較高的相似性，而不同簇中的數(shù)據(jù)之間的相似性較低。

目前已經(jīng)存在的聚類(lèi)算法大致可以分為四種類(lèi)型：（1）基于劃分的聚類(lèi)算法。如k-means、k-medoids等。這種算法需要設(shè)定簇的數(shù)量，根據(jù)對(duì)象間的相似性將每個(gè)對(duì)象劃歸最近的簇。這種算法能夠發(fā)現(xiàn)超球狀的簇。（2）層次聚類(lèi)算法。層次聚類(lèi)可以從兩個(gè)方向產(chǎn)生，第一是凝聚，首先將所有對(duì)象標(biāo)記為簇，然后逐次合并距離最小的簇；第二是分裂，先將整個(gè)數(shù)據(jù)集視為一個(gè)簇，然后逐次分裂樣本較多的簇。層次聚類(lèi)需要人為設(shè)定終止條件，即凝聚或分裂到何種程度為止。根據(jù)簇相似性的不同定義，層次聚類(lèi)算法有Ward方法、BIRCH和CURE等。（3）基于統(tǒng)計(jì)模型的算法。如期望最大化(EM)算法。這類(lèi)算法基于數(shù)理統(tǒng)計(jì)理論，假定數(shù)據(jù)集是由一個(gè)統(tǒng)計(jì)過(guò)程產(chǎn)生的，并通過(guò)找出最佳擬合模型來(lái)描述數(shù)據(jù)集。（4）基于密度的算法。其中心思想是尋找數(shù)據(jù)集中被低密度區(qū)域隔開(kāi)的高密度區(qū)域，并將每個(gè)獨(dú)立的高密度區(qū)域作為一類(lèi)。根據(jù)對(duì)密度的不同定義，典型算法有 DBSCAN、OPTICS、DENCLULDE 等。

基于密度的聚類(lèi)方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類(lèi)，無(wú)需預(yù)先設(shè)定簇的數(shù)量，因而特別適合于對(duì)未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類(lèi)。DBSCAN是一種經(jīng)典的基于密度聚類(lèi)算法，它以超球狀區(qū)域內(nèi)數(shù)據(jù)對(duì)象的數(shù)量來(lái)衡量此區(qū)域密度的高低。DBSCAN算法能夠發(fā)現(xiàn)任意形狀的簇，并有效識(shí)別離群點(diǎn)，但聚類(lèi)之前需要人工選擇鄰域半徑Eps和類(lèi)內(nèi)最小數(shù)據(jù)對(duì)象個(gè)數(shù)MinPts這兩個(gè)參數(shù)。

基于密度的算法，例如DBSCAN算法得到結(jié)果僅僅是局部最佳的，因此在Carlos等人的研究中，提出了在基于密度的聚類(lèi)中使用成對(duì)約束，對(duì)DBSCAN算法進(jìn)行改進(jìn)并最終提出了C-DBSCAN算法，即對(duì)DBSCAN聚類(lèi)算法的一種帶約束的改進(jìn)。并且，該算法為了將成對(duì)約束引入聚類(lèi)過(guò)程中，還使用KD-Tree將數(shù)據(jù)劃分為最小單位的葉子結(jié)點(diǎn)。

本文的組織結(jié)構(gòu)如下：第兩部分介紹DBSCAN算法、成對(duì)約束和KD-Tree的相關(guān)內(nèi)容；第三部分詳細(xì)描述算法；第四部分通過(guò)實(shí)驗(yàn)驗(yàn)證算法的有效性；最后是全文的小結(jié)。

二、相關(guān)工作

1.DBSCAN算法

DBSCAN算法是一種經(jīng)典的基于密度的聚類(lèi)算法，該算法計(jì)算每個(gè)數(shù)據(jù)對(duì)象的Eps領(lǐng)域，通過(guò)把密度可達(dá)的數(shù)據(jù)對(duì)象聚成一個(gè)類(lèi)簇來(lái)得到聚類(lèi)結(jié)果。DBSCAN可以自動(dòng)確定類(lèi)簇的個(gè)數(shù)，發(fā)現(xiàn)任意形狀的類(lèi)簇，且對(duì)噪聲數(shù)據(jù)不敏感。DBSCAN中的定義如下：

定義1（數(shù)據(jù)對(duì)象p的鄰域）：數(shù)據(jù)對(duì)象的鄰域定義為以為核心,為半徑的維超球體區(qū)域內(nèi)包含的點(diǎn)的集合,即，其中，為維空間上的數(shù)據(jù)集，表示中點(diǎn)和之間的距離。

定義2（核心數(shù)據(jù)對(duì)象）：給定和,對(duì)于數(shù)據(jù)對(duì)象,如果鄰域內(nèi)包含的對(duì)象個(gè)數(shù)滿(mǎn)足,則稱(chēng)為核心數(shù)據(jù)對(duì)象。

定義3（直接密度可達(dá)）：給定和,對(duì)于數(shù)據(jù)對(duì)象,如果滿(mǎn)足且這兩個(gè)條件,則稱(chēng)從關(guān)于直接密度可達(dá)的。直接密度可達(dá)不滿(mǎn)足對(duì)稱(chēng)性。

定義4（密度可達(dá)）：給定和,對(duì)于數(shù)據(jù)對(duì)象,如果有一個(gè)數(shù)據(jù)對(duì)象序列,其中,并且是從直接密度可達(dá)的,則稱(chēng)從關(guān)于密度可達(dá)的。密度可達(dá)也不滿(mǎn)足對(duì)稱(chēng)性。

定義5（密度相連）：給定和,對(duì)于數(shù)據(jù)對(duì)象，如果存在一個(gè)數(shù)據(jù)對(duì)象使得和都是從密度可達(dá)的，則稱(chēng)和關(guān)于密度相連的。密度相連滿(mǎn)足對(duì)稱(chēng)性。

當(dāng)給定和時(shí),DBSCAN算法的簡(jiǎn)要流程如下：選擇任一未劃分的數(shù)據(jù)對(duì)象，判斷其是否為核心數(shù)據(jù)對(duì)象,若是,尋找所有與其密度可達(dá)的數(shù)據(jù)對(duì)象,將這些數(shù)據(jù)對(duì)象標(biāo)記為一類(lèi);若不是,則進(jìn)行噪聲數(shù)據(jù)對(duì)象判斷,若是噪聲,則對(duì)其進(jìn)行標(biāo)記,若不是噪聲,則不對(duì)該對(duì)象處理，如此重復(fù)直至所有的數(shù)據(jù)對(duì)象都被劃分。

2.成對(duì)約束

半監(jiān)督聚類(lèi)中一般以成對(duì)約束信息作為先驗(yàn)信息來(lái)引導(dǎo)聚類(lèi)過(guò)程，而成對(duì)約束信息包含must-link和cannot-link兩種（簡(jiǎn)記為ML和CL），分別表示兩個(gè)點(diǎn)必須屬于同一類(lèi)的和必須是不同類(lèi)的，這些信息能提高聚類(lèi)效果。其中，must-link約束規(guī)定：如果兩個(gè)樣本屬于該類(lèi)約束，那么這兩個(gè)樣本在聚類(lèi)時(shí)必須被分配到同一個(gè)聚類(lèi)中；cannot-link約束則相應(yīng)地規(guī)定：如果兩個(gè)樣本屬于該類(lèi)約束，那么這兩個(gè)樣本在聚類(lèi)時(shí)必須被分配到不同聚類(lèi)中。而約束信息的質(zhì)量是有差異的，約束并不是越多越好，應(yīng)該用盡量少的約束來(lái)得到盡量好的聚類(lèi)結(jié)果。

3.KD-Tree

KD-Tree是一種對(duì)k維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。KD-Tree是二叉樹(shù)，表示對(duì)k維空間的一個(gè)劃分。構(gòu)造KD-Tree相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將k維空間切分，構(gòu)成一系列的k維超矩形區(qū)域。KD-Tree的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)k維超矩形區(qū)域。

構(gòu)造KD-Tree的方法如下：構(gòu)造根結(jié)點(diǎn)，使根結(jié)點(diǎn)對(duì)應(yīng)于k維空間中包含所有實(shí)例點(diǎn)的超矩形區(qū)域；通過(guò)下面的遞歸方法，不斷地對(duì)k維空間進(jìn)行切分，生成子結(jié)點(diǎn)。在超矩形區(qū)域（結(jié)點(diǎn)）上選擇一個(gè)坐標(biāo)軸和在此坐標(biāo)軸上的一個(gè)切分點(diǎn)，確定一個(gè)超平面，這個(gè)超平面通過(guò)選定的切分點(diǎn)并垂直于選定的坐標(biāo)軸，將當(dāng)前超矩形區(qū)域切分為左右兩個(gè)子區(qū)域（子結(jié)點(diǎn)）；這時(shí)，實(shí)例被分到兩個(gè)子區(qū)域。這個(gè)過(guò)程直到子區(qū)域內(nèi)沒(méi)有實(shí)例時(shí)終止（終止時(shí)的結(jié)點(diǎn)為葉結(jié)點(diǎn)）。在此過(guò)程中，將實(shí)例保存在相應(yīng)的結(jié)點(diǎn)上。

三、帶約束半監(jiān)督聚類(lèi)算法C-DBSCAN

1.算法中的相關(guān)定義

局部聚類(lèi)：遍歷由KD-Tree得到的每一個(gè)葉子結(jié)點(diǎn)，在每一個(gè)葉子結(jié)點(diǎn)內(nèi)部，所有密度可達(dá)的點(diǎn)被聚為一類(lèi)。當(dāng)遍歷結(jié)束后會(huì)得到很多聚類(lèi)，需要強(qiáng)調(diào)的是，這樣得到的每一個(gè)聚類(lèi)中包含的點(diǎn)都是同一個(gè)葉子結(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)，這里用“局部聚類(lèi)”來(lái)表示這些初步的聚類(lèi)結(jié)果。

聚類(lèi)：每一對(duì)Must-Link約束都涉及到兩個(gè)數(shù)據(jù)點(diǎn)，對(duì)于每一對(duì)Must-Link約束，找到包含這兩個(gè)點(diǎn)的類(lèi)，并將這兩個(gè)類(lèi)合并為一類(lèi)，這里用“聚類(lèi)”來(lái)表示合并后的聚類(lèi)結(jié)果。

2.改進(jìn)后的C-DBSCAN算法步驟

第一步，在KD-Tree的幫助下，將原數(shù)據(jù)空間劃分為一些子空間，每個(gè)子空間都是KD-Tree的一個(gè)葉子結(jié)點(diǎn)，而且每一個(gè)葉子結(jié)點(diǎn)都將包含至少M(fèi)inPts個(gè)數(shù)據(jù)點(diǎn)。

第二步，分別考慮每一個(gè)葉子結(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)，在滿(mǎn)足Cannot-Link約束的情況下建立初始的局部聚類(lèi)。

第三步，在Must-Link的指導(dǎo)下，合并上一步得到的局部聚類(lèi)得到聚類(lèi)。

第四步，在滿(mǎn)足Cannot-Link約束的情況下，將距離聚類(lèi)最近的局部聚類(lèi)合并到該聚類(lèi)中，直到局部聚類(lèi)的個(gè)數(shù)不再變化為止。

此時(shí)得到的聚類(lèi)和仍舊留下的局部聚類(lèi)就是最后得到的聚類(lèi)結(jié)果。

3.改進(jìn)后的C-DBSCAN算法詳細(xì)描述

輸入：數(shù)據(jù)集D，Must-Link約束集，Cannot-Link約束集，鄰域半徑Eps，類(lèi)內(nèi)最小對(duì)象個(gè)數(shù)MinPts；

輸出：滿(mǎn)足ML和CL的聚類(lèi)結(jié)果。

Begin

Step 1：用KD-Tree對(duì)數(shù)據(jù)集D進(jìn)行劃分；

Step 2：在構(gòu)造得到的KDTree上建立局部聚類(lèi)

For（每一個(gè)葉子結(jié)點(diǎn)and每一個(gè)未標(biāo)記點(diǎn)）do if（）then

將點(diǎn)標(biāo)記為噪音點(diǎn)

elseif（在中存在滿(mǎn)足CL約束的點(diǎn)對(duì)）then

點(diǎn)以及中的每一個(gè)點(diǎn)都單獨(dú)成為一個(gè)局部聚類(lèi)

else

將點(diǎn)標(biāo)記為核心點(diǎn)

所有中的點(diǎn)成為一個(gè)局部聚類(lèi)

end

end

Step 3a：利用ML約束合并聚類(lèi)結(jié)果

For（約束集ML中的每一對(duì)約束）do

點(diǎn)和是一對(duì)滿(mǎn)足約束條件的點(diǎn)

找到聚類(lèi)和使得以及

將和合并為，并將合并后的類(lèi)標(biāo)記為聚類(lèi)

end

Step 3b：建立最后的聚類(lèi)結(jié)果

While（局部聚類(lèi)的數(shù)目減少）do

For（每一個(gè)局部聚類(lèi)C）do

聚類(lèi)為從聚類(lèi)密度可達(dá)的所有聚類(lèi)中距離聚類(lèi)最近的聚類(lèi)

if（聚類(lèi)和中的點(diǎn)不存在滿(mǎn)足CL約束的點(diǎn)對(duì)）then將聚類(lèi)合并入聚類(lèi)中，

end

end

end

將每一個(gè)聚類(lèi)以及仍舊剩余的局部聚類(lèi)作為返回值返回

End

4.C-DBSCAN算法舉例

圖1 C-DBSCAN算法實(shí)例

四、實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法的有效性，論文在人工數(shù)據(jù)集上做了對(duì)比試驗(yàn)。

測(cè)試數(shù)據(jù)如圖2(a)所示，數(shù)據(jù)集來(lái)自文獻(xiàn)，該數(shù)據(jù)集包含200個(gè)數(shù)據(jù)，其中用戶(hù)需求找到兩個(gè)不規(guī)則的類(lèi)。圖示中分別用不同的顏色以及不同的符號(hào)表示不同的類(lèi)；藍(lán)色的實(shí)線表示CL約束，黑色的實(shí)線表示ML約束。

論文通過(guò)將C-DBSCAN算法與標(biāo)準(zhǔn)DBSCAN算法進(jìn)行比較，從而驗(yàn)證算法的有效性。

圖2 在數(shù)據(jù)集Dataset上的對(duì)比試驗(yàn)

如圖所示，圖2(b)是數(shù)據(jù)集Dataset在DBSCAN算法上的實(shí)驗(yàn)結(jié)果。可以看出，DBSCAN算法在選擇合理的和的情況下，將數(shù)據(jù)集分成了四類(lèi)，因?yàn)檫@個(gè)結(jié)果只考慮到了單個(gè)數(shù)據(jù)點(diǎn)的屬性對(duì)分類(lèi)的影響，而沒(méi)有考慮到數(shù)據(jù)點(diǎn)與數(shù)據(jù)點(diǎn)之間的關(guān)系；圖2(c)是在數(shù)據(jù)集Dataset的基礎(chǔ)上加入了八對(duì)成對(duì)約束，其中六對(duì)ML約束，兩對(duì)CL約束；圖2(d)是數(shù)據(jù)集Dataset在 C-DBSCAN算法上的實(shí)驗(yàn)結(jié)果，在加入了成對(duì)約束后，考慮到了數(shù)據(jù)點(diǎn)之間的關(guān)系，得到了用戶(hù)需求的兩類(lèi)的聚類(lèi)結(jié)果。

因此，由實(shí)驗(yàn)可以得到，改進(jìn)后的算法相比于傳統(tǒng)的DBSCAN算法能夠充分利用成對(duì)約束的信息，得到較好的實(shí)驗(yàn)結(jié)果，從而提高了聚類(lèi)結(jié)果的質(zhì)量。

五、結(jié)束語(yǔ)

DBSCAN算法是一種經(jīng)典的基于密度聚類(lèi)算法，它能夠發(fā)現(xiàn)任意形狀的簇，并能夠自動(dòng)確定簇的數(shù)量。論文設(shè)計(jì)并實(shí)現(xiàn)了在DBSCAN的基礎(chǔ)上，通過(guò)引入成對(duì)約束提出的C-DBSCAN算法，使得改進(jìn)后的算法能夠應(yīng)用于半監(jiān)督學(xué)習(xí)中，并能很好地提高聚類(lèi)結(jié)果的質(zhì)量。由于算法中的成對(duì)約束需要人為給定，如何合理地給定成對(duì)約束，以使得用盡量少的成對(duì)約束來(lái)得到盡量好的聚類(lèi)結(jié)果，將是進(jìn)一步討論的問(wèn)題。

[1]行小帥,潘進(jìn),焦李成.基于免疫規(guī)劃的K-means聚類(lèi)算法[J].計(jì)算機(jī)學(xué)報(bào)，2003，（5）:605-610.

[2]Ester M,Kriegel H P,Sander J.A density-based algorithm for discovering clusters in large spatial databases with noise[C].Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining,1996:226-231.

[3]Carlos Ruiz，Myra Spiliopoulou，Ernestina Menasalvas.Density-based semi-supervised clustering[J].Data Miningand Knowledge Discovery，2010，（21）:345-370.

[4]Sugato Basu，Arindam Banerjee,Raymond J.Mooney.Active semi-supervision for pair-wise constrained clustering[C].Proceedings of the 2004 SIAM International Conference on Data Mining，2004:333-344.

[5]李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社，2012：41-45.