張?zhí)K穎 許曙青

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

2(南京理工大學(xué)計(jì)算機(jī)學(xué)院 江蘇 南京 210000)

0 引 言

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

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

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

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

1 基本理論

1.1 主動(dòng)聚類(lèi)集成框架

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

圖1 兩類(lèi)不確定性問(wèn)題的可能聚類(lèi)結(jié)果

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

圖2 ADPE方法計(jì)算框架

1.2 初始化

采用高斯核來(lái)量化局部密度,其表示為：

(1)

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

(2)

(3)

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

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

(4)

式中：L(xi)是xi的標(biāo)簽,parent(xi)是歸屬樹(shù)中xi的父節(jié)點(diǎn)。密度峰值聚類(lèi)假設(shè)聚類(lèi)中心被局部密度較低的實(shí)例包圍,而遠(yuǎn)離任何局部密度較高的實(shí)例。這個(gè)性質(zhì)分別用ρ和δ來(lái)測(cè)量。因此,通過(guò)ρ和δ計(jì)算γ來(lái)表示實(shí)例成為聚類(lèi)中心的概率,其計(jì)算式為：

(5)

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

從特征子空間的角度看,實(shí)例具有不同的聚類(lèi)中心概率。為了綜合考慮所有子空間,ADPE計(jì)算γ的平均值來(lái)評(píng)估其代表性的強(qiáng)弱,其計(jì)算式如下：

(6)

1.4 動(dòng)態(tài)信息實(shí)例選擇

ADPE中每個(gè)實(shí)例的局部不穩(wěn)定性的計(jì)算如下：

(7)

(8)

(9)

(10)

(11)

其中：

(12)

(13)

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

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

(14)

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

(15)

采用快速更新策略對(duì)每個(gè)子空間的聚類(lèi)結(jié)果進(jìn)行細(xì)化。不穩(wěn)定性采樣和標(biāo)簽更新迭代運(yùn)行,直到滿足條件q≥qmax才停止。

2 方法簡(jiǎn)介

2.1 計(jì)算流程

為了整合所有改進(jìn)的聚類(lèi)結(jié)果,本文設(shè)計(jì)一種實(shí)例級(jí)加權(quán)投票一致性聚類(lèi)方法。盡管傳統(tǒng)的投票方法簡(jiǎn)單和快速,但是它有兩個(gè)局限性：(1) 應(yīng)該將標(biāo)簽事先進(jìn)行對(duì)齊;(2) 在每個(gè)聚類(lèi)結(jié)果中都沒(méi)有考慮實(shí)例的置信度。值得注意的是,每個(gè)子空間中的標(biāo)簽已對(duì)齊,因?yàn)楣侧徲蚣癁槊總€(gè)聚類(lèi)提供了統(tǒng)一的標(biāo)簽。實(shí)例的置信度用局部不穩(wěn)定性來(lái)評(píng)估,每個(gè)實(shí)例的加權(quán)投票標(biāo)簽定義如下：

(16)

其中：

(17)

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

算法1ADPE

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

輸出： 聚類(lèi)結(jié)果L。

1. for j = 1 to s do

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

4. end for

5.通過(guò)式(13)計(jì)算統(tǒng)一質(zhì)量γ;

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

7. for each inPdo

8. for eachNk∈Ndo

9.通過(guò)任何實(shí)例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. 通過(guò)式(4)從每個(gè)子空間得到s的初始聚類(lèi)結(jié)果;

19. repeat

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

21.通過(guò)每個(gè)滿足查詢x*;

22. for each subspaceFjdo

23. 采用快速更新策略更新標(biāo)簽;

24. end for

25. untilq≥qmax

26. 通過(guò)式(16)和式(17)計(jì)算實(shí)例級(jí)加權(quán)投票標(biāo)簽作為最終結(jié)果;

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

2.2 復(fù)雜性分析

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

TADP=TINIT+TSRIS+TDIIS

(18)

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

TADP=TINIT+TSRIS+TDIIS+TCM=

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

O(s·n)=O(sn2m)

(19)

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)集和實(shí)驗(yàn)方法

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

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

為了驗(yàn)證本文方法的性能,比較了其他算法。首先,ADP和ADPE的參數(shù)值設(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是一種單一的主動(dòng)聚類(lèi)算法,將其與隨機(jī)選擇成對(duì)約束的兩種半監(jiān)督聚類(lèi)方法和三種使用鄰域的主動(dòng)聚類(lèi)方法進(jìn)行了比較。

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

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

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

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

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

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

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

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

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

(4) ACCE[13]：基于boosting的聚類(lèi)集成方法,主動(dòng)選擇需要查詢的實(shí)例對(duì)。

3.2 參數(shù)值的影響

(20)

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

表3 α對(duì)18個(gè)數(shù)據(jù)集影響的分析總結(jié)

3.3 ADP與單聚類(lèi)算法的比較

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

表4 不同的主動(dòng)聚類(lèi)算法的查詢數(shù)量

表5 不同算法多項(xiàng)統(tǒng)計(jì)檢驗(yàn)值對(duì)比

3.4 ADPE與聚類(lèi)集成的比較

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

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

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

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

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

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

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

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

3.7 聚類(lèi)方法的比較

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

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

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

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

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

表8 有關(guān)6個(gè)大數(shù)據(jù)集的統(tǒng)計(jì)信息

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

3.9 運(yùn)行時(shí)間的比較

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

表9 不同方法更新一次標(biāo)簽所需的運(yùn)行時(shí)間 單位：s

4 結(jié) 語(yǔ)

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

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

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

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

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