姜美羨

（四川大學(xué)軟件學(xué)院，成都 610065）

0 引言

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

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

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

1 算法原理

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

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

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

輸出：數(shù)據(jù)集D上的聚類結(jié)果

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每個未處理的數(shù)據(jù)樣例點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進行了相關(guān)的實驗研究并通過比較此算法在多個數(shù)據(jù)集上的蘭德指數(shù)，得到了較好聚類效果。

2.1 評價指標

為了對檢測效果進行更好地評價，利用調(diào)整蘭德指數(shù)（ARI）[8]對聚類結(jié)果進行客觀評價。

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

2.2 數(shù)據(jù)集和實驗結(jié)果

實驗使用的數(shù)據(jù)集是來自UCI機器學(xué)習(xí)標準數(shù)據(jù)集[9]中的三組現(xiàn)實數(shù)據(jù)集iris、ionosphere和banknote。表1列出了數(shù)據(jù)集的名稱、樣本數(shù)、數(shù)據(jù)維度和類別信息。

表1 實驗數(shù)據(jù)集

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

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

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

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

3 結(jié)果和分析

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

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