基于加權投票的主動密度峰值數據聚類算法

張蘇穎 許曙青

1(江蘇聯合職業技術學院南京工程分院 江蘇 南京 210035)

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

0 引 言

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

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

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

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

1 基本理論

1.1 主動聚類集成框架

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

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

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

圖2 ADPE方法計算框架

1.2 初始化

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

(1)

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

(2)

(3)

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

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

(4)

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

(5)

1.3 靜態代表性實例選擇

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

(6)

1.4 動態信息實例選擇

ADPE中每個實例的局部不穩定性的計算如下：

(7)

(8)

(9)

(10)

(11)

其中：

(12)

(13)

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

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

(14)

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

(15)

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

2 方法簡介

2.1 計算流程

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

(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)計算統一質量γ;

6.確定滑動窗口半徑r,以隨機選取的中心點C半徑為r的圓形滑動窗口開始滑動,不同的數據集半徑的確定通過自適應半徑方法計算得到,具體方法參考文獻[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分別是初始化、靜態代表性實例選擇和動態信息實例選擇的時間復雜性。TINIT依賴于計算成對距離的預處理階段,即O(n2m)。當集群中心數C遠小于n時,TSRIS=O(C·n)=O(n)。在動態選擇的每次迭代中,計算局部不穩定性和快速更新策略的時間復雜度分別為O(K·n)和O(n),其中K是平均鄰域數。因此,當TDIIS=O(qmax·(K·n+n))=O(n)時,qmax和K是取值較小的常數?？傮w而言,TADP計算如下：

TADP=TINIT+TSRIS+TDIIS+TCM=

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

O(s·n)=O(sn2m)

(19)

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

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

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

3 實驗與結果分析

3.1 數據集和實驗方法

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

表2 相關數據集信息

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

(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是一種單一的主動聚類算法,將其與隨機選擇成對約束的兩種半監督聚類方法和三種使用鄰域的主動聚類方法進行了比較。

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

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

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

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

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

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

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

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

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

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

3.2 參數值的影響

(20)

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

表3 α對18個數據集影響的分析總結

3.3 ADP與單聚類算法的比較

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

表4 不同的主動聚類算法的查詢數量

表5 不同算法多項統計檢驗值對比

3.4 ADPE與聚類集成的比較

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

3.5 局部/全局不穩定性的影響

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

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

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

3.6 發現未知集群的能力

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

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

3.7 聚類方法的比較

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

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

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

3.8 本文算法在大型數據集上的表現

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

表8 有關6個大數據集的統計信息

圖8 基于NMII的6大數據集不同方法的性能比較

3.9 運行時間的比較

為了有效地更新標簽,本文設計了快速更新策略。2.2節比較了不同的標簽在更新算法時的漸近計算復雜度。本節評估了這些方法在4個數據集上的運行時間。所有這些方法均基于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的運行時間有很大的區別,GPU明顯優于CPU。隨著數據量的增加,優勢變得更明顯。原因可能是快速更新策略不涉及復雜的操作,只遍歷歸屬樹中選定的節點子集來更新標簽。

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

4 結 語

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

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

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

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

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