基于密度的半監(jiān)督聚類算法研究

姜美羨

（四川大學軟件學院，成都 610065）

0 引言

在很多數據挖掘的實際問題中，數據集包括大量無標記的數據，輔以少量先驗知識作為監(jiān)督信息。半監(jiān)督學習介于無監(jiān)督學習和監(jiān)督學習之間，使用少量的有標記數據樣本來輔助學習[1]。理論研究表明，即使是少量的有標記樣本數據也能大幅度提升對應的無監(jiān)督學習模型的效果[2]。

根據監(jiān)督信息的使用方式，現有的半監(jiān)督聚類算法可分為三類[3]：①基于約束的方法，使用監(jiān)督信息約束聚類的搜索過程。②基于距離的方法，利用標記數據訓練一種相似性度量，然后用基于距離量度的聚類算法進行聚類。③將這兩類方法結合在一起使用。

本文通過改進傳統(tǒng)的密度聚類算法DBSCAN[4]得到半監(jiān)督聚類算法SDBSCAN，是一種基于約束的半監(jiān)督聚類算法。此算法相對于Lelis等人[5]和Ruiz等人[6]提出的基于密度的半監(jiān)督聚類算法來說，具有監(jiān)督信息無需覆蓋所有聚類簇和無需事先指定聚類的目標簇數的優(yōu)點。SDBSCAN不僅能有效利用監(jiān)督信息形成已知聚類簇，還能根據數據的分布密度特性，自動地形成新的未知聚類簇。

1 算法原理

本文通過三個步驟來擴展DBSCAN以得到半監(jiān)督的密度聚類算法SDBSCAN。首先使用KD-Tree（K維空間分割樹）[7]將數據空間劃分為更密集的子空間，并對子空間內的數據點根據監(jiān)督信息和密度構建初始的局部集群。第二步，根據監(jiān)督信息合并屬于同一類別的數據點所在集群。第三步，在不合并不同標簽數據的前提下，合并密度可達的集群得到最終的聚類結果。接下來，本節(jié)對SDBSCAN算法進行詳細的介紹。

算法：半監(jiān)督密度聚類算法SDBSCAN

輸入：數據集D={x1,x2,x3…xn}，已知標簽的樣本S=Ukj-1Sj,Minpts,eps

輸出：數據集D上的聚類結果

function SDBSCAN（D,S,Minpts,eps）

kdtree=BuildKDTree（D）

for每個葉子節(jié)點v∈kdtree

if?xi,xj∈v,xi∈Sa,xj∈Sa,a≠b then

葉節(jié)點中的每個點各形成一個集群

else

for每個未處理的數據樣例點xi∈v

if|Neps（xi）|>=Minpts then

xi標記為CORE_POINT，并將?x∈Neps（xi）標記為同一集群

else xi標記為NOISE_POINT

for i=1,2,…,k

for x∈Si

合并與x屬于同一集群的點

for xi∈CORE_POINT

min=eps

for xj∈CORE_POINT

if dist（xi,xj）≤min

min=dist（xi,xj）

將xi屬于的集群與xj屬于的集群標記為同一集群

for xi∈NOISE_POINT

min=eps

for xj∈CORE_POINT

if dist（xi,xj）≤min

min=dist（xi,xj）

將xi標記為與xj同一集群

return所有的類別

2 實驗

對本文提出的基于密度的半監(jiān)督聚類算法SDB?CAN進行了相關的實驗研究并通過比較此算法在多個數據集上的蘭德指數，得到了較好聚類效果。

2.1 評價指標

為了對檢測效果進行更好地評價，利用調整蘭德指數（ARI）[8]對聚類結果進行客觀評價。

用X表示實際類別信息，Y表示聚類結果，a表示在X與Y中都是同類別的元素對數，b表示在X與Y中都是不同類別的元素對數。是數據集中可以組成的總元素對數。ARI取值范圍為[-1,1]，值越大表明聚類結果與真實情況越吻合。

2.2 數據集和實驗結果

實驗使用的數據集是來自UCI機器學習標準數據集[9]中的三組現實數據集iris、ionosphere和banknote。表1列出了數據集的名稱、樣本數、數據維度和類別信息。

表1 實驗數據集

以10%的增長從0到1選取11個不同百分比值，然后給出對應百分比值的樣本的標簽作為約束信息。在約束集隨機選取的情況下，在三個數據集上進行100次獨立的實驗,計算得到一系列調整蘭德指數的平均值。

表2 SDBSCAN在不同大小約束集上的聚類效果圖

用橫坐標表示約束集占樣本集的比例，縱坐標表示根據聚類結果得到的蘭德指數值，繪制并連接實驗結果數據點得到圖1所示的曲線圖。

圖1 SDBSCAN在不同大小約束集上的聚類效果圖

3 結果和分析

由圖1的實驗結果可見，在未加入約束條件時，SDBSCAN的聚類效果等同于DBSCAN。在加入少量約束后，SDBSCAN與DBSCAN相比，性能有明顯提高。圖1所示的曲線表明，SDBCAN明顯克服了DB?SCAN的缺點，實現了對數據集較準確的聚類。數據集iris和banknote分別在加入了10%和20%的約束信息的情況下蘭德指數超過了0.8，聚類準確度實現了明顯的提升。此外，由于約束集中的樣本是隨機選擇的，所以實驗結果表明少量的隨機選取的約束集足以使得SDBCAN得到很好地聚類結果，沒有必要為了更好的聚類效果增加約束集的大小。

基于密度的聚類是一種很實用的簡單算法，而將其半監(jiān)督化可以極大地提高其準確性和穩(wěn)定性。本文的下一步工作是從不同的視角對算法進改進，并選取一種半監(jiān)督聚類算法在更大規(guī)模的真實數據集上與之比較。