基于加權投票的主動密度峰值數(shù)據(jù)聚類算法

張?zhí)K穎 許曙青

1(江蘇聯(lián)合職業(yè)技術學院南京工程分院 江蘇 南京 210035)

2(南京理工大學計算機學院 江蘇 南京 210000)

0 引 言

由于聚類在無監(jiān)督學習中起著重要的作用,許多聚類方法得到了廣泛的研究,包括譜聚類、層次聚類等[1-2]。密度聚類方法與半監(jiān)督策略結合起來的方法可以解決標簽樣本數(shù)量不足的問題,這種方法基于隨機選擇的類邊界信息,由于隨機選擇成對約束會導致冗余和噪聲,繼而文獻[3]提出了一種主動聚類策略。

主動聚類采用的成對約束選擇策略已經存在許多方法。文獻[4]通過查詢具有代表性的實例實現(xiàn)初始化來構造鄰域,鄰域由一組已知屬于同一個聚類的實例組成。文獻[5]利用鄰域的概念為每個聚類至少發(fā)現(xiàn)一個實例。然而,僅僅通過簡單地使用具有代表性的實例是不夠的。選擇信息實例可以減少局部和全局的不確定性。

主動聚類查詢過程分為靜態(tài)選擇和動態(tài)選擇兩個階段,其中前者在半監(jiān)督聚類前產生完全約束集,忽略聚類結果。文獻[6]在訓練階段選擇了約束條件,以構建鄰域關系。文獻[7]通過流形學習獲得邊界信息,以促進半監(jiān)督聚類。后者在每次迭代中重復查詢和標簽更新的過程。文獻[8]重復進行半監(jiān)督聚類,以選擇信息門戶文檔。文獻[9]迭代地利用模糊超球體通過主動學習來發(fā)現(xiàn)和改進集群。文獻[10]通過最小化約束譜聚類后的期望誤差迭代地獲得約束。上述主動聚類方法均利用代表性或信息性實現(xiàn)查詢選擇,然而,沒有同時考慮代表性和信息性,使得查詢選擇提升效果有限。另外,上述方法還必須無效地重復半監(jiān)督聚類更新標簽,降低了計算效率。

針對上述問題,本文提出一種基于加權投票一致性的主動密度峰值數(shù)據(jù)聚類集成算法(Active Density Peak Ensemble Algorithm, ADPE),通過數(shù)據(jù)集驗證可以發(fā)現(xiàn)提出的方法有效解決了上述問題,并展示了良好的聚類性能。

1 基本理論

1.1 主動聚類集成框架

局部不穩(wěn)定性的一個缺點是它無法測量聚類模型實例的劃分難度。例如,在圖1中,每個矩形虛線框表示兩類數(shù)據(jù)集的邊界區(qū)域的可能的聚類結果,總共有s個聚類結果。特別地,來自上下區(qū)域的實例形成了兩個邊界區(qū)域。這些實例分為兩個集群。顯然,實例2由于其不穩(wěn)定的分區(qū)標簽比實例1更模糊。然而,實例1和實例2具有相同的局部不穩(wěn)定性。在這種情況下,有必要考慮全局不穩(wěn)定性來估計每個實例的劃分難度。

圖1 兩類不確定性問題的可能聚類結果

如圖2所示,為了進一步提高性能,提出主動聚類集成方案。首先,ADPE生成特征子空間以提供多角度視圖和各種信息。主動密度峰值(Active Density Peak, ADP)模型獨立應用于每個子空間,并且這些模型共享一個公共鄰域集。在靜態(tài)選擇階段,為了構造初始鄰域,通過考慮所有子空間中的γ來選擇代表性實例。在動態(tài)選擇階段,通過結合局部和全局不穩(wěn)定性來迭代選擇信息實例。最后設計一個實例級加權投票聚類方法,對多個成員進行集成,從而得到最終的聚類結果。

圖2 ADPE方法計算框架

1.2 初始化

采用高斯核來量化局部密度,其表示為：

(1)

式中：dij是xi和xj之間的距離。由于不同數(shù)據(jù)集的截止距離dc難以估計,根據(jù)文獻[11]估計了dc,使得鄰域的平均數(shù)目約為實例總數(shù)的(100α)%,其中α∈[0,1]是一個參數(shù)。dc計算式如下：

(2)

(3)

由于每個實例都與另一個具有更高密度的實例相連接,因此構造了一個具有多分支的樹狀圖,稱為歸屬樹,其中每個節(jié)點代表一個實例。如果滿足δi=d(xi,xj),則密度最高的實例是根節(jié)點,節(jié)點j是節(jié)點i的父節(jié)點。根據(jù)文獻[11],歸屬樹表示實例之間的關系,其中父節(jié)點的標簽被分配給其子節(jié)點。

L(xi)=L(parent(xi))

(4)

式中：L(xi)是xi的標簽,parent(xi)是歸屬樹中xi的父節(jié)點。密度峰值聚類假設聚類中心被局部密度較低的實例包圍,而遠離任何局部密度較高的實例。這個性質分別用ρ和δ來測量。因此,通過ρ和δ計算γ來表示實例成為聚類中心的概率,其計算式為：

(5)

1.3 靜態(tài)代表性實例選擇

從特征子空間的角度看,實例具有不同的聚類中心概率。為了綜合考慮所有子空間,ADPE計算γ的平均值來評估其代表性的強弱,其計算式如下：

(6)

1.4 動態(tài)信息實例選擇

ADPE中每個實例的局部不穩(wěn)定性的計算如下：

(7)

(8)

(9)

(10)

(11)

其中：

(12)

(13)

它利用熵來評估在所有聚類結果中被劃分為同一集群的實例的穩(wěn)定性。由于圖1中的實例2和實例3始終被劃分為同一集群,所以它們具有相同的全局不穩(wěn)定性。但是,實例2更靠近邊界中心,而且它應具有更高的查詢優(yōu)先級。為了克服這兩種不穩(wěn)定性的缺點,將局部和全局不穩(wěn)定性組合起來,計算式如下：

UADPE(xi)=Ul(xi)+Ug(xi)

(14)

較大的UADPE(xi)說明xi中包含較多的信息。不穩(wěn)定性最大的實例由以下公式得到：

(15)

采用快速更新策略對每個子空間的聚類結果進行細化。不穩(wěn)定性采樣和標簽更新迭代運行,直到滿足條件q≥qmax才停止。

2 方法簡介

2.1 計算流程

為了整合所有改進的聚類結果,本文設計一種實例級加權投票一致性聚類方法。盡管傳統(tǒng)的投票方法簡單和快速,但是它有兩個局限性：(1) 應該將標簽事先進行對齊;(2) 在每個聚類結果中都沒有考慮實例的置信度。值得注意的是,每個子空間中的標簽已對齊,因為公共鄰域集為每個聚類提供了統(tǒng)一的標簽。實例的置信度用局部不穩(wěn)定性來評估,每個實例的加權投票標簽定義如下：

(16)

其中：

(17)

式中：1-Uj_ADP(xi)是對Fj的置信度權重。最后的聚類結果用L={V(x1),V(x2),…,V(xn)}表示。具體算法如算法1所示。

算法1ADPE

輸入：X,qmax,s,ξmin,ξmax,αmin,αmax。

輸出： 聚類結果L。

1. for j = 1 to s do

2. 用隨機特征抽樣率生成特征子空間Fj

4. end for

5.通過式(13)計算統(tǒng)一質量γ;

6.確定滑動窗口半徑r,以隨機選取的中心點C半徑為r的圓形滑動窗口開始滑動,不同的數(shù)據(jù)集半徑的確定通過自適應半徑方法計算得到,具體方法參考文獻[9]。通過滑動窗口得到潛在集群中心P={xω1,xω2,…,xωt-1};

7. for each inPdo

8. for eachNk∈Ndo

9.通過任何實例xk∈Nk;q=q+1查詢xp;

10. if (xp,xk)∈MLthen

11.Nk=Nk∪{xp};L(xp)=k;break;

12. end if

13. end for

14. if 未得到MLthen

15.η=η+1;Nη={xp};N=N∪(〗Nη};L(xp)=η;

16. end if

17. end for

18. 通過式(4)從每個子空間得到s的初始聚類結果;

19. repeat

20. 由式(14)-式(15)得到確定性最差的實例x*;

21.通過每個滿足查詢x*;

22. for each subspaceFjdo

23. 采用快速更新策略更新標簽;

24. end for

25. untilq≥qmax

26. 通過式(16)和式(17)計算實例級加權投票標簽作為最終結果;

27. 得到最終的聚類結果L={V(x1),V(x2),…,V(xn)};

2.2 復雜性分析

本文分析了ADP和ADPE的時間復雜性。首先,ADP的時間復雜性可以由式(18)得到。

TADP=TINIT+TSRIS+TDIIS

(18)

式中：TINIT、TSRIS和TDIIS分別是初始化、靜態(tài)代表性實例選擇和動態(tài)信息實例選擇的時間復雜性。TINIT依賴于計算成對距離的預處理階段,即O(n2m)。當集群中心數(shù)C遠小于n時,TSRIS=O(C·n)=O(n)。在動態(tài)選擇的每次迭代中,計算局部不穩(wěn)定性和快速更新策略的時間復雜度分別為O(K·n)和O(n),其中K是平均鄰域數(shù)。因此,當TDIIS=O(qmax·(K·n+n))=O(n)時,qmax和K是取值較小的常數(shù)。總體而言,TADP計算如下：

TADP=TINIT+TSRIS+TDIIS+TCM=

O(s·n2·ξ·m)+O(n)+O(s·n)+

O(s·n)=O(sn2m)

(19)

隨著子空間s的數(shù)量增加,計算成本也隨之線性增加。與基于協(xié)關聯(lián)矩陣或圖的聚類方法復雜度分別為O(n2)和O(n3)的時間復雜度不同,本文提出的聚類方法將成本降低到O(n)。由于主要的計算費用都花在了初始化上,所以可以使用分布式技術或一些預分組方法來加速初始化計算。時間復雜度對比如表1所示。

表1 不同的發(fā)射式聚類和加速方法的時間復雜度比較

大多數(shù)最新的主動聚類方法通過重復耗時半監(jiān)督聚類來更新標簽。在表1中列出了不同半監(jiān)督聚類的時間復雜度和一些提高運算速度的方法。當m和n都很大時,半監(jiān)督k-means的時間復雜度高于快速更新策略,并且難以識別任意形狀的集群。半監(jiān)督譜聚類中的標準特征向量的時間復雜度為O(n3),這并不能運用到大規(guī)模數(shù)據(jù)集上。雖然可以應用一些提高運算速度的方法,但是由于抽樣和投影采用隨機方法,近似方法可能無法充分利用邊界信息。此外,URASC在不穩(wěn)定性估計運算中要求精確的特征值,近似方法并不適用。

3 實驗與結果分析

3.1 數(shù)據(jù)集和實驗方法

本節(jié)用歸一化互信息(Normalized Mutual Information,NMI)和調整蘭德指數(shù)(Adjusted Rand Index,ARI)對18個數(shù)據(jù)集(包括8個UCI數(shù)據(jù)集)和10個具有高維特征的基因數(shù)據(jù)集(D-9-D-18)進行了性能評估[12]。表2記錄了關于這些數(shù)據(jù)集的信息,其中c、n和m分別是集群、實例和特性的數(shù)量。

表2 相關數(shù)據(jù)集信息

為了驗證本文方法的性能,比較了其他算法。首先,ADP和ADPE的參數(shù)值設置如下。

(1) ADP：l=5,θ=0.000 01 andα=0.22。

(2) ADPE：s=10,[ξmin,ξmax]=[0.6,0.8] and [αmin,αmax]=[0.15,0.30]。

由于ADP是一種單一的主動聚類算法,將其與隨機選擇成對約束的兩種半監(jiān)督聚類方法和三種使用鄰域的主動聚類方法進行了比較。

(1) COPKM[4]：半監(jiān)督k均值聚類方法,在聚類時可以避免違反約束條件。

(2) E2CP[5]：基于k最近鄰圖的成對約束傳播方法。令μ=0.5和k=10,作為最佳聚類結果的參數(shù)值。

(3) APCKM[7]：主動k均值聚類方法,可以查詢具有代表性的實例以獲得更好的初始化效果。令w=1.0,與文獻[7]參數(shù)值相同。

(4) URASC[8]：主動光譜聚類方法,可以查詢信息量大的實例,最大程度地減少不穩(wěn)定性。計算了b=(1/2)n個實例的梯度,并令最大尺寸k=10。

(5) NPU[9]：適用于任何半監(jiān)督聚類算法的主動聚類框架。在URASC中使用相同的半監(jiān)督譜聚類方法,并將隨機森林的大小設置為50。

此外,將ADPE與聚類集成方法進行了比較,包括兩種半監(jiān)督集成方法和兩種主動聚類集成方法。這些方法中的集合成員數(shù)與ADPE相同,均為10個。

(1) GCC[10]：基于圖像的聚類集成框架。將E2CP作為基本聚類模型。

(2) RSEMICE[11]：優(yōu)化聚類結果置信因子的自適應半監(jiān)督聚類集成方法。將參數(shù)大小和原文設置一樣,μ=0.5,α=0.33,ζ=0.25。

(3) FACE[12]：基于全局不穩(wěn)定性選擇成對約束的主動聚類集成方法。

(4) ACCE[13]：基于boosting的聚類集成方法,主動選擇需要查詢的實例對。

3.2 參數(shù)值的影響

(20)

若得到的偏差較小,表示它更接近最小查詢時間。將[0.0,0.5]分為10個區(qū)間,計算18個數(shù)據(jù)集的平均標度偏差,結果如表3所示?？梢园l(fā)現(xiàn),當α在0.20到0.25之間變化時,ADP查詢效率最高。在ADP中令α=0.22,在ADPE中令[αmin,αmax]=[0.15,0.30]。

表3 α對18個數(shù)據(jù)集影響的分析總結

3.3 ADP與單聚類算法的比較

比較了ADP與COPKM、E2CP、APCKM、NPU和URASC在18個具有不同查詢次數(shù)的數(shù)據(jù)集的NMI值。結果如圖3所示。在設置相同的查詢數(shù)量時,ADP在大多數(shù)數(shù)據(jù)集上的NMI值總體上高于其他方法。ADP的性能隨著查詢量的增加而穩(wěn)定增加。然而,NPU和URASC在一些數(shù)據(jù)集上運行的結果有些波動,如Seeds、Synthetic-control和housevotes?？赡苁且驗橐恍┘s束條件混淆了半監(jiān)督聚類算法。此外,在18個數(shù)據(jù)集上采用ADP、NPU、URASC和APCKM方法,直到所有實例都能正確地實現(xiàn)聚類(NMI和ARI為1.0)。該方法使用的查詢數(shù)量越少,就越有效地利用了邊緣信息。結果如表4所示,其中“+”表示該方法無法收斂到NMI和ARI為1.0,即使它的查詢數(shù)量是ADP的兩倍。ADP對18個數(shù)據(jù)集中的15個數(shù)據(jù)集使用最少的查詢,說明它可以充分利用邊界信息。在表5中,記錄了多項統(tǒng)計檢驗(Friedman’s test, Bonferroni-Dunn’s test, Holm’s test, Hochberg’s test, and Hommel’s test)。得出的主要結論是零假設(qADP的顯著性比qNPU、qURASC和qAPCKM更小)在0.05的顯著性水平被拒絕。因此,算法ADP在查詢利用率方面優(yōu)于其他方法。

表4 不同的主動聚類算法的查詢數(shù)量

表5 不同算法多項統(tǒng)計檢驗值對比

3.4 ADPE與聚類集成的比較

ADPE采用隨機子空間來提供不同的信息,可以有效地減少噪聲和冗余特征對高維數(shù)據(jù)的影響。然而,這對于低維數(shù)據(jù)集沒有多大意義,因為可能會刪除一些關鍵特征。因此,在10個基因數(shù)據(jù)集上比較了ADP、GCC、RSEMICE、FACE和ACCE的性能。表6記錄了有關ARI的比較結果,其中粗體表示最佳結果。與ADP相比,ADPE在整體性能方面表現(xiàn)更好,主要有兩個原因：(1) 結合局部和全局不穩(wěn)定性,有效地選擇信息實例;(2) 將不同的集成成員聚類以獲得更全面的結果。此外,ADPE性能明顯優(yōu)于FACE、ACCE、RSEMICE和GCC。其原因可能是：(1) 在處理高維數(shù)據(jù)時,FACE和ACCE中的基本聚類模型不能提供良好的聚類結果;(2) RSEMICE和GCC由于約束條件的隨機選擇,不能充分利用邊緣信息。

3.5 局部/全局不穩(wěn)定性的影響

由于局部不穩(wěn)定性和全局不穩(wěn)定性各有優(yōu)勢,因此結合它們來選擇信息最豐富的實例以獲得更好的性能。首先僅使用局部不穩(wěn)定性(ADPE-L)或整體不穩(wěn)定性(ADPE-G)來測試ADPE的性能,如圖4和圖5所示,將局部和全局不穩(wěn)定性相結合可以在百分之八十的數(shù)據(jù)集上獲得最佳性能。局部不穩(wěn)定性在實例中確定邊界區(qū)域,在模型級別添加全局不穩(wěn)定性可以找出混淆性最大的實例。因此,局部和全局不穩(wěn)定性的組合具有非常滿意的性能。

圖4 局部和全局不確定性對NMI性能的影響

圖5 局部和全局不確定性對ARI性能的影響

3.6 發(fā)現(xiàn)未知集群的能力

基于鄰域的主動聚類方法可以在不需要已知聚類數(shù)目的情況下找到未知聚類。ADP和ADPE為每個鄰域查詢代表性實例,為了方便給數(shù)據(jù)集分配標簽。但是,URASC、NPU和APCKM是通過使用其所有相關實例來構建鄰域。表7記錄了這些方法用于發(fā)現(xiàn)所有集群所需的平均查詢數(shù)量。雖然本文方法在查詢未知集群方面并不比其他方法明顯優(yōu)越,但其代表性的實例對標簽分配任務的貢獻較大。

表7 通過不同的基于鄰域的主動聚類方法查找所有聚類的平均查詢數(shù)量

3.7 聚類方法的比較

ADPE通過提出的實例級加權投票聚類方法整合了多個聚類結果。將其與三種備選聚類方法進行比較：基于投票方法(APDE_V)[14]、基于關聯(lián)矩陣方法(ADPE_CAM)[15]和基于圖像方法(ADPE_NCUT)[16]。 圖6和圖7描繪了這些方法在NMI和ARI方面的性能。可以看出,在大多數(shù)數(shù)據(jù)集上,本文方法優(yōu)于其他方法。原因可能是本文方法考慮了每個子空間中實例的置信度,并降低了低質量標簽產生的影響。另外,避免了排列過程,從而使本文方法更加有效。

圖6 基于NMI的一致性方法比較

圖7 基于ARI的一致性方法比較

3.8 本文算法在大型數(shù)據(jù)集上的表現(xiàn)

表8記錄了不同方法在6個較大的數(shù)據(jù)集上的運行結果。前4個UCI數(shù)據(jù)集涵蓋了不同的領域,包括圖像、生物信息學、文本和醫(yī)學。其中,MSD是百萬首歌曲數(shù)據(jù)集的子集,由4種音樂風格(流行、電子、說唱和爵士樂)的8 000個實例組成,其中每個類有2 000個實例,一共提取了124種特征。RLCTS包含53 500個實例,從CT圖像中提取了384種特征。采用適合大數(shù)據(jù)的聚類算法(Mini Batch K-Means)對RLCTS中的相鄰實例進行預分組,并為所有方法生成5 000個具有代表性的實例。圖8顯示了本文方法(ADP和ADPE)和4種主動聚類方法(NPU、URASC、APCKM和ACCE)以及兩種半監(jiān)督聚類方法(E2CP和GCC)在NMI方面的性能?？紤]到效率問題,當n≥5 000時不適用URASC。與APCKM、ACCE、E2CP和GCC不同,本文方法不需要預先知道集群的真實數(shù)量,因此,在某些數(shù)據(jù)集(如cnae_9、MSD和RLCTS)上的性能可能會受到影響。然而,隨著查詢量的增加,ADP和APDE的性能都顯著提高,并且最終在大多數(shù)數(shù)據(jù)集上的性能優(yōu)于其他方法。結果表明,ADP和APDE在大型數(shù)據(jù)集上是可擴展的,預分組方法可以減少算法運行的時間,提高效率。

表8 有關6個大數(shù)據(jù)集的統(tǒng)計信息

圖8 基于NMII的6大數(shù)據(jù)集不同方法的性能比較

3.9 運行時間的比較

為了有效地更新標簽,本文設計了快速更新策略。2.2節(jié)比較了不同的標簽在更新算法時的漸近計算復雜度。本節(jié)評估了這些方法在4個數(shù)據(jù)集上的運行時間。所有這些方法均基于Scikitlearn[17],計算機的CPU為Intel 6核i7-8700K,主頻為 3.70 GHz。表9記錄了不同方法更新一次標簽所需的平均運行時間。PI表示加速方法采用的是冪迭代[18]。本文還基于PyTorch[19]框架,在1080Ti的GPU平臺上重復以上方法(例如MPCKM-GPU、semiSC-GPU和E2CP-GPU)。與CPU相比,GPU可以減少運行時間。該方法在CPU和GPU的運行時間有很大的區(qū)別,GPU明顯優(yōu)于CPU。隨著數(shù)據(jù)量的增加,優(yōu)勢變得更明顯。原因可能是快速更新策略不涉及復雜的操作,只遍歷歸屬樹中選定的節(jié)點子集來更新標簽。

表9 不同方法更新一次標簽所需的運行時間 單位：s

4 結 語

針對傳統(tǒng)方法缺乏對查詢標準的全面考慮,并且反復運行半監(jiān)督聚類來更新標簽等問題,提出一種基于加權投票一致性的主動密度峰值集成數(shù)據(jù)聚類算法。通過數(shù)據(jù)集驗證結果分析可得出如下結論：

(1) ADPE能充分利用邊緣信息,結合了局部不穩(wěn)定性和全局不穩(wěn)定性,在整體性能方面表現(xiàn)更好。

(2) 局部不確定性和全局不確定性的結合有助于選擇最模糊的邊界實例,以更好地分離聚類。

(3) ADPE采用隨機子空間來提供不同的信息,可以有效地減少噪聲和冗余特征對高維數(shù)據(jù)的影響,并且查詢利用率方面優(yōu)于其他方法。

(4) ADP和ADPE由于采用了快速更新策略,在效率上有很大的優(yōu)勢,并且ADP和APDE在大型數(shù)據(jù)集上是可擴展的,預分組方法可以減少算法運行的時間,提高效率。