基于核心點虛擬標(biāo)簽傳播的密度聚類算法*

劉雷 甘騰

(桂林航天工業(yè)學(xué)院 計算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004)

聚類是一種無監(jiān)督的數(shù)據(jù)分析過程，其目的是把相似性高的數(shù)據(jù)點劃分到同一類簇中，把相似性低的數(shù)據(jù)點劃分到不同類簇中。聚類算法在數(shù)據(jù)挖掘、網(wǎng)絡(luò)安全、生物信息、圖像分割等諸多領(lǐng)域有廣泛應(yīng)用[1-2]。最近幾十年來，研究學(xué)者們對聚類問題進(jìn)行了深入研究，提出了大量的聚類算法[3]。

密度聚類算法是聚類算法中的一個分支，此類算法大都具有可自動計算類簇數(shù)量、對噪聲不明感、可識別噪聲或異常點等優(yōu)點。DBSCAN[4]是一種經(jīng)典的密度聚類算法，使用前需要預(yù)先設(shè)置參數(shù)eps和minPts。對于某一個數(shù)據(jù)點，如果在其半徑為eps的范圍內(nèi)具有至少minPts個數(shù)據(jù)點，就認(rèn)為該點是核心點。DBSCAN算法可以很好地處理類簇形狀不規(guī)則的情況，但是當(dāng)不同類簇的密度差異較大時，聚類效果不理想。密度峰值算法DP[5]根據(jù)預(yù)先設(shè)置的密度閾值ρ和局部密度最大點之間的距離閾值δ計算出一組密度峰值點，然后在這些峰值點的基礎(chǔ)上進(jìn)行類簇劃分。DP算法可以有效處理類簇間密度差異大的問題，提高聚類效果，但是當(dāng)同一類簇中有多個密度峰值點時，該算法有可能會把一個類簇錯誤地劃分為多個類簇[6]。

除了用特定半徑內(nèi)數(shù)據(jù)點的個數(shù)表征密度，k近鄰和反向k近鄰也被廣泛應(yīng)用于計算數(shù)據(jù)點的密度。反向k近鄰的數(shù)量越多，表明該點的密度越大，重要性越大。HkNN[7]、RNN-DBSCAN[8]等算法就利用反向k近鄰的數(shù)量表征數(shù)據(jù)點的密度。利用反向k近鄰的數(shù)量表征數(shù)據(jù)點的密度只需要一個參數(shù)，簡單高效，同時可以有效處理不同類簇間密度差異大的問題。近年有很多密度聚類算法[9-10]采用這種方法。

大部分真實數(shù)據(jù)集都具有類簇間密度差異大和類簇形狀不規(guī)則等特點。這些特點會嚴(yán)重影響聚類效果。為提升此類情況下的聚類效果，本文提出了一種基于核心點虛擬標(biāo)簽傳播的聚類算法(VLPC，virtual label propagation of core points)。該算法以反向k近鄰的數(shù)量表征密度，并結(jié)合了圖論中的相關(guān)方法和標(biāo)簽傳播算法[11-13]。在人工合成數(shù)據(jù)集和實際數(shù)據(jù)集上的測試表明，VLPC算法有效提升了類簇形狀不規(guī)則、類簇密度差異大等情況下的聚類效果。

1 相關(guān)定義

數(shù)據(jù)集表示為X={x1,…,xn}，其中x表示一個m維的數(shù)據(jù)點。任意兩個數(shù)據(jù)點xi和xj之間的距離用歐氏距離表示，記為sij。對于任意一個數(shù)據(jù)點xi，距離其最近的k個數(shù)據(jù)點定義為xi的k近鄰，用Nk(xi)表示。對于任意兩個數(shù)據(jù)點xi和xj，如果xi∈Nk(xj)和xj∈Nk(xi)同時滿足，則稱xi和xj為互近鄰。數(shù)據(jù)點xi的所有互近鄰用Mk(xi)表示。如果xi∈Nk(xj)，則稱xj是xi的反向k近鄰。xi的所有反向k近鄰記為Rk(xi)?？梢?，如果兩個數(shù)據(jù)點是互近鄰關(guān)系，那么它們也是互為反向k近鄰。

在k值確定的情況下，每個數(shù)據(jù)點反向k近鄰的數(shù)量是不一樣的。一般來說，處于類簇中心高密度區(qū)的數(shù)據(jù)點可能是更多數(shù)據(jù)點的k近鄰，從而具有更多的反向k近鄰；反之，處于類簇邊緣區(qū)域的數(shù)據(jù)點可能具有較少的反向k近鄰。因此，以反向k近鄰作為指標(biāo)衡量一個數(shù)據(jù)點的密度和重要性是合理的。

如圖1所示，帶箭頭的線段表示k近鄰關(guān)系，箭頭端的點是無箭頭端點的k近鄰，圖中k的值取2。處于類簇中心高密度區(qū)域的點A、B、C各具有3個反向k近鄰，而處于邊緣低密度區(qū)域的點D、E、F沒有反向k近鄰。

圖1 k近鄰示意圖

2 算法描述

2.1 構(gòu)建核心區(qū)域

構(gòu)建核心區(qū)域分兩步進(jìn)行，首先需要找出核心點，然后合并關(guān)聯(lián)緊密的核心點形成核心區(qū)域。

每個數(shù)據(jù)點都具有k個近鄰，則平均每個點同樣具有k個反向k近鄰。但由于每個數(shù)據(jù)點的位置不同，周圍數(shù)據(jù)點的密集程度不同，導(dǎo)致不同數(shù)據(jù)點的反向k近鄰有差異。以平均值k作為閾值，對于數(shù)據(jù)點xi，如果|Rk(xi)|≥k，則xi是核心點，否則xi是邊界點。核心點是對聚類效果有重要影響的數(shù)據(jù)點，是構(gòu)建核心區(qū)域的基礎(chǔ)。如圖1所示，點A、B、C的反向k近鄰的個數(shù)大于等于k值，因此這3個點是核心點。而點D、E、F的反向k近鄰的個數(shù)小于k值，因此這3個點是邊界點。

數(shù)據(jù)點之間的緊密程度可通過近鄰關(guān)系表示?；ソ応P(guān)系要強(qiáng)于單向近鄰關(guān)系，而單向近鄰關(guān)系要強(qiáng)于非近鄰關(guān)系。為了確保兩個核心點之間的關(guān)系足夠緊密，同時滿足以下條件的兩個核心點xi和xj可以進(jìn)行合并：

1)xi和xj是互近鄰關(guān)系，即xj∈Mk(xi)或xi∈Mk(xj)；

2)存在點xp，xi和xj都是xp的k近鄰，即?xp∈X，xi∈Nk(xp)且xj∈Nk(xp)。

滿足條件1表示兩個核心點聯(lián)系緊密；條件2進(jìn)一步增強(qiáng)了聯(lián)系程度，同時也表示點xi和xj處于中心區(qū)域。將所有核心點按照上述條件合并之后，即構(gòu)建出了核心區(qū)域。每個核心點只屬于一個核心區(qū)域，而一個核心區(qū)域包含一個或多個核心點。只包含一個核心點的核心區(qū)域可能是虛假核心區(qū)域。因此，最后需要遍歷所有的核心區(qū)域，去除掉那些只包含一個核心點的核心區(qū)域。

構(gòu)建核心區(qū)域的具體實現(xiàn)步驟如下：

Step 1：計算數(shù)據(jù)點兩兩之間的距離，得到距離矩陣S，其中元素sij表示點xi和xj之間的歐氏距離；

Step 2：根據(jù)距離矩陣S，得到每個數(shù)據(jù)點的k近鄰和反向k近鄰；

Step 3：根據(jù)每個數(shù)據(jù)點反向k近鄰的數(shù)量，判斷其是否為核心點；

Step 4：合并滿足要求的核心點，得到核心區(qū)域；

Step 5：篩選Step 4中的核心區(qū)域，去除掉只包含一個核心點的核心區(qū)域，剩下的即為最終的核心區(qū)域。

2.2 虛擬標(biāo)簽傳播

相同核心區(qū)域中的核心點被劃分到相同的類簇中，不同核心區(qū)域中的核心點被劃分到不同的類簇中。每個邊界點需要根據(jù)其與核心點之間的聯(lián)系進(jìn)行類簇的劃分。為了確定每個邊界點所歸屬的類簇，本文給每個核心點設(shè)置一個虛擬標(biāo)簽，然后通過標(biāo)簽傳播的方法將這些標(biāo)簽發(fā)散到邊界點上，從而得到邊界點的類簇劃分結(jié)果。

虛擬標(biāo)簽采用one-hot編碼的形式，相同核心區(qū)的核心點具有相同的標(biāo)簽，不同核心區(qū)的核心點具有不同的標(biāo)簽。假設(shè)共有c個核心區(qū)域，核心點xi屬于第j個核心區(qū)域Cj，則xi的標(biāo)簽可表示為c維列向量yi，其中yi的第j個元素為1，其余元素為0。

數(shù)據(jù)點之間的聯(lián)系與距離有關(guān)，距離越遠(yuǎn)聯(lián)系越小，距離越近聯(lián)系越大。 本文用W表示關(guān)系矩陣，其中的元素wij表示點xi和xj之間的聯(lián)系：

(1)

其中：

(2)

關(guān)系緊密的數(shù)據(jù)點更可能屬于相同的類簇，即標(biāo)簽應(yīng)該相同或者相近。帶有虛擬標(biāo)簽的核心點以k近鄰關(guān)系為基礎(chǔ)向邊界點進(jìn)行標(biāo)簽傳播，邊界點的標(biāo)簽可以通過求解以下目標(biāo)函數(shù)的最優(yōu)解獲得：

(3)

其中：y1…yl表示l個核心點的虛擬標(biāo)簽，yl+1…yn表示待確定的m=n-l個邊界點的虛擬標(biāo)簽。

式(3)可以寫成矩陣的形式：

(4)

Y是虛擬標(biāo)簽矩陣Y=[y1…yn]T。為了方便計算，令Yc=[y1…yl]T，Yb=[yl+1…yn]T，則Y可表示為：

(5)

(6)

其中：Lcc和Lbb分別為l×l維和m×m維的方陣。將式(4)和式(5)帶入式(3)可得：

(7)

(8)

式(7)對Yb求導(dǎo)，并令導(dǎo)數(shù)為0，可得：

(9)

利用式(9)可求得每個邊界點的虛擬標(biāo)簽，但是這些邊界點的虛擬標(biāo)簽并不是one-hot編碼形式。為了轉(zhuǎn)化為one-hot編碼形式，對每一個邊界的虛擬標(biāo)簽yi，取其中最大元素設(shè)置為1，其他元素都設(shè)置為0。

矩陣Lbb可能存在不可逆的情況，這是由于近鄰個數(shù)k的取值過小所引起的，可以通過增大k的取值解決此問題。

遍歷所有的數(shù)據(jù)點，把具有相同虛擬標(biāo)簽的劃分為同一個類簇，具有不同虛擬標(biāo)簽的劃分為不同類簇。

2.3 算法時間復(fù)雜度分析

3 實驗與結(jié)果分析

為檢驗VLPC算法的聚類效果，本文選取了8個公開數(shù)據(jù)集進(jìn)行測試，其中包括Compound、Jain、Pathbased 、Mouse 4個人工合成數(shù)據(jù)集和Iris 、Wine 、Appendicitis 、Banknote 4個由真實數(shù)據(jù)組成的數(shù)據(jù)集。每個數(shù)據(jù)集的詳細(xì)描述如表1所示。

表1 數(shù)據(jù)集描述

選取DP、RNN-DBSCAN(簡寫為RDBS)和NPIR算法作為對比算法。DP算法是經(jīng)典密度峰值聚類算法，RDBS算法與本文提出的VLPC算法都使用反向鄰居計算數(shù)據(jù)點密度，NPIR是一種最近提出的基于k近鄰的聚類算法。

聚類效果使用NMI指數(shù)和ARI指數(shù)進(jìn)行評估。這是兩種常用的評價聚類效果的指數(shù)，取值范圍在0到1之間，且越接近1表示聚類效果越好。由于在多個數(shù)據(jù)集上進(jìn)行測試，將每個算法在所有數(shù)據(jù)集上的平均排名作為該算法的最終排名。各算法在人工合成數(shù)據(jù)集上的聚類效果如表2和表3所示。由測試結(jié)果可看出，無論采用NMI或ARI指數(shù)評價，VLPC算法在除Mouse和Iris數(shù)據(jù)集上的聚類效果都優(yōu)于其他3個對比算法。VLPC算法在Mouse和Iris數(shù)據(jù)集上的聚類效果排名第2。

表2 聚類效果的NMI指數(shù)

表3 聚類效果的ARI指數(shù)

圖2-圖5是VLPC算法在人工合成數(shù)據(jù)集上的聚類效果。從圖中可看出，除了Compound數(shù)據(jù)集中右部存在對數(shù)據(jù)點較為明顯的錯誤劃分，VLPC算法在類簇形狀不規(guī)則和類簇間密度差異大的情況下可以得到較好地聚類效果。

圖2 Compound聚類效果

圖3 Jain聚類效果

圖4 Pathbased聚類效果

圖5 Mouse聚類效果

VLPC算法的綜合聚類效果最優(yōu)，主要可歸結(jié)于兩點。第一，采用反向k近鄰表征數(shù)據(jù)點的重要性可以有效避免不同類簇間密度差異過大給聚類效果帶來的負(fù)面影響。反向k近鄰對密度差異具有自動補(bǔ)償?shù)男Ч?，無論局部密度大或小，處于中心位置的核心點始終都具有更多的反向k近鄰。第二，在k近鄰圖上采用標(biāo)簽傳播法可以有效處理類簇形狀不規(guī)則問題。k近鄰圖表現(xiàn)了樣本點之間的相似關(guān)系，與類簇形狀無關(guān)。標(biāo)簽傳播法的傳播路徑以k近鄰圖為基礎(chǔ)，虛擬標(biāo)簽在樣本點之間的傳播強(qiáng)度與k近鄰圖中邊的權(quán)重有關(guān)，因此可以有效處理類簇形狀不規(guī)則問題。

4 結(jié)束語

本文采用反向k近鄰表征數(shù)據(jù)點的密度和重要性，得到核心點和核心區(qū)域，并使用標(biāo)簽傳播算法將核心點的虛擬標(biāo)簽擴(kuò)散到各個邊界點，從而完成類簇劃分。通過在人工合成數(shù)據(jù)集和真實數(shù)據(jù)集上的測試，并與DP、RNN-DBSCAN和NPIR算法進(jìn)行比較，表明VLPC算法的聚類效果整體上優(yōu)于對比算法，能夠很好地處理類簇形狀不規(guī)則、密度差異大等問題。