帶有成對約束半監督聚類算法C-DBSCAN的設計與實現

閆 軍

(太原旅游職業學院，山西 太原 030032）

一、概述

數據挖掘作為一種從大量數據中發現感興趣信息的技術，已經得到日益廣泛的應用。而聚類是一種重要的數據挖掘技術，其任務是將數據集分成若干個簇。同一個簇中的數據具有較高的相似性，而不同簇中的數據之間的相似性較低。

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

基于密度的聚類方法以數據集在空間分布上的稠密程度為依據進行聚類，無需預先設定簇的數量，因而特別適合于對未知內容的數據集進行聚類。DBSCAN是一種經典的基于密度聚類算法，它以超球狀區域內數據對象的數量來衡量此區域密度的高低。DBSCAN算法能夠發現任意形狀的簇，并有效識別離群點，但聚類之前需要人工選擇鄰域半徑Eps和類內最小數據對象個數MinPts這兩個參數。

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

本文的組織結構如下：第兩部分介紹DBSCAN算法、成對約束和KD-Tree的相關內容；第三部分詳細描述算法；第四部分通過實驗驗證算法的有效性；最后是全文的小結。

二、相關工作

1.DBSCAN算法

DBSCAN算法是一種經典的基于密度的聚類算法，該算法計算每個數據對象的Eps領域，通過把密度可達的數據對象聚成一個類簇來得到聚類結果。DBSCAN可以自動確定類簇的個數，發現任意形狀的類簇，且對噪聲數據不敏感。DBSCAN中的定義如下：

定義1（數據對象p的鄰域）：數據對象的鄰域定義為以為核心,為半徑的維超球體區域內包含的點的集合,即，其中，為維空間上的數據集，表示中點和之間的距離。

定義2（核心數據對象）：給定和,對于數據對象,如果鄰域內包含的對象個數滿足,則稱為核心數據對象。

定義3（直接密度可達）：給定和,對于數據對象,如果滿足且這兩個條件,則稱從關于直接密度可達的。直接密度可達不滿足對稱性。

定義4（密度可達）：給定和,對于數據對象,如果有一個數據對象序列,其中,并且是從直接密度可達的,則稱從關于密度可達的。密度可達也不滿足對稱性。

定義5（密度相連）：給定和,對于數據對象，如果存在一個數據對象使得和都是從密度可達的，則稱和關于密度相連的。密度相連滿足對稱性。

當給定和時,DBSCAN算法的簡要流程如下：選擇任一未劃分的數據對象，判斷其是否為核心數據對象,若是,尋找所有與其密度可達的數據對象,將這些數據對象標記為一類;若不是,則進行噪聲數據對象判斷,若是噪聲,則對其進行標記,若不是噪聲,則不對該對象處理，如此重復直至所有的數據對象都被劃分。

2.成對約束

半監督聚類中一般以成對約束信息作為先驗信息來引導聚類過程，而成對約束信息包含must-link和cannot-link兩種（簡記為ML和CL），分別表示兩個點必須屬于同一類的和必須是不同類的，這些信息能提高聚類效果。其中，must-link約束規定：如果兩個樣本屬于該類約束，那么這兩個樣本在聚類時必須被分配到同一個聚類中；cannot-link約束則相應地規定：如果兩個樣本屬于該類約束，那么這兩個樣本在聚類時必須被分配到不同聚類中。而約束信息的質量是有差異的，約束并不是越多越好，應該用盡量少的約束來得到盡量好的聚類結果。

3.KD-Tree

KD-Tree是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構。KD-Tree是二叉樹，表示對k維空間的一個劃分。構造KD-Tree相當于不斷地用垂直于坐標軸的超平面將k維空間切分，構成一系列的k維超矩形區域。KD-Tree的每個結點對應于一個k維超矩形區域。

構造KD-Tree的方法如下：構造根結點，使根結點對應于k維空間中包含所有實例點的超矩形區域；通過下面的遞歸方法，不斷地對k維空間進行切分，生成子結點。在超矩形區域（結點）上選擇一個坐標軸和在此坐標軸上的一個切分點，確定一個超平面，這個超平面通過選定的切分點并垂直于選定的坐標軸，將當前超矩形區域切分為左右兩個子區域（子結點）；這時，實例被分到兩個子區域。這個過程直到子區域內沒有實例時終止（終止時的結點為葉結點）。在此過程中，將實例保存在相應的結點上。

三、帶約束半監督聚類算法C-DBSCAN

1.算法中的相關定義

局部聚類：遍歷由KD-Tree得到的每一個葉子結點，在每一個葉子結點內部，所有密度可達的點被聚為一類。當遍歷結束后會得到很多聚類，需要強調的是，這樣得到的每一個聚類中包含的點都是同一個葉子結點中的數據點，這里用“局部聚類”來表示這些初步的聚類結果。

聚類：每一對Must-Link約束都涉及到兩個數據點，對于每一對Must-Link約束，找到包含這兩個點的類，并將這兩個類合并為一類，這里用“聚類”來表示合并后的聚類結果。

2.改進后的C-DBSCAN算法步驟

第一步，在KD-Tree的幫助下，將原數據空間劃分為一些子空間，每個子空間都是KD-Tree的一個葉子結點，而且每一個葉子結點都將包含至少MinPts個數據點。

第二步，分別考慮每一個葉子結點中的數據點，在滿足Cannot-Link約束的情況下建立初始的局部聚類。

第三步，在Must-Link的指導下，合并上一步得到的局部聚類得到聚類。

第四步，在滿足Cannot-Link約束的情況下，將距離聚類最近的局部聚類合并到該聚類中，直到局部聚類的個數不再變化為止。

此時得到的聚類和仍舊留下的局部聚類就是最后得到的聚類結果。

3.改進后的C-DBSCAN算法詳細描述

輸入：數據集D，Must-Link約束集，Cannot-Link約束集，鄰域半徑Eps，類內最小對象個數MinPts；

輸出：滿足ML和CL的聚類結果。

Begin

Step 1：用KD-Tree對數據集D進行劃分；

Step 2：在構造得到的KDTree上建立局部聚類

For（每一個葉子結點and每一個未標記點）do if（）then

將點標記為噪音點

elseif（在中存在滿足CL約束的點對）then

點以及中的每一個點都單獨成為一個局部聚類

else

將點標記為核心點

所有中的點成為一個局部聚類

end

end

Step 3a：利用ML約束合并聚類結果

For（約束集ML中的每一對約束）do

點和是一對滿足約束條件的點

找到聚類和使得以及

將和合并為，并將合并后的類標記為聚類

end

Step 3b：建立最后的聚類結果

While（局部聚類的數目減少）do

For（每一個局部聚類C）do

聚類為從聚類密度可達的所有聚類中距離聚類最近的聚類

if（聚類和中的點不存在滿足CL約束的點對）then將聚類合并入聚類中，

end

end

end

將每一個聚類以及仍舊剩余的局部聚類作為返回值返回

End

4.C-DBSCAN算法舉例

圖1 C-DBSCAN算法實例

四、實驗結果

為了驗證算法的有效性，論文在人工數據集上做了對比試驗。

測試數據如圖2(a)所示，數據集來自文獻，該數據集包含200個數據，其中用戶需求找到兩個不規則的類。圖示中分別用不同的顏色以及不同的符號表示不同的類；藍色的實線表示CL約束，黑色的實線表示ML約束。

論文通過將C-DBSCAN算法與標準DBSCAN算法進行比較，從而驗證算法的有效性。

圖2 在數據集Dataset上的對比試驗

如圖所示，圖2(b)是數據集Dataset在DBSCAN算法上的實驗結果。可以看出，DBSCAN算法在選擇合理的和的情況下，將數據集分成了四類，因為這個結果只考慮到了單個數據點的屬性對分類的影響，而沒有考慮到數據點與數據點之間的關系；圖2(c)是在數據集Dataset的基礎上加入了八對成對約束，其中六對ML約束，兩對CL約束；圖2(d)是數據集Dataset在 C-DBSCAN算法上的實驗結果，在加入了成對約束后，考慮到了數據點之間的關系，得到了用戶需求的兩類的聚類結果。

因此，由實驗可以得到，改進后的算法相比于傳統的DBSCAN算法能夠充分利用成對約束的信息，得到較好的實驗結果，從而提高了聚類結果的質量。

五、結束語

DBSCAN算法是一種經典的基于密度聚類算法，它能夠發現任意形狀的簇，并能夠自動確定簇的數量。論文設計并實現了在DBSCAN的基礎上，通過引入成對約束提出的C-DBSCAN算法，使得改進后的算法能夠應用于半監督學習中，并能很好地提高聚類結果的質量。由于算法中的成對約束需要人為給定，如何合理地給定成對約束，以使得用盡量少的成對約束來得到盡量好的聚類結果，將是進一步討論的問題。

[1]行小帥,潘進,焦李成.基于免疫規劃的K-means聚類算法[J].計算機學報，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]李航.統計學習方法[M].北京:清華大學出版社，2012：41-45.