徐森 皋軍 花小朋 李先鋒 徐靜

聚類分析的目標是依據(jù)對象之間的相似度對其自動分組/簇,使得簇內(nèi)對象彼此相似度盡量高,而簇間對象彼此相似度盡量低[1?2].雖然已有上千種聚類算法,但沒有一種能有效識別不同大小,不同形狀,不同密度甚至可能包含噪聲的簇[1].已有聚類方法主要分為:1)基于劃分的方法,將聚類問題轉(zhuǎn)化為優(yōu)化問題,并采用不同的優(yōu)化策略,例如,K均值算法(K-means,KM)[3]、非負矩陣分解(Nonnegative matrix factorization,NMF)[4]、近鄰傳播算法(Affinity propagation,AP)[5]、子空間聚類算法[6]以及基于深度學(xué)習(xí)[7]的聚類算法[8];2)層次聚類[2],例如單連接(Single linkage,SL)、全連接(Complete linkage,CL)、組平均(Average linkage,AL);3)基于模型的方法[1],將聚類問題轉(zhuǎn)化為模型的充分統(tǒng)計量估計問題;4)基于密度的方法,通過尋找被低密度區(qū)域分離的高密度區(qū)域來進行聚類,例如密度峰值(Density peaks,DP)算法[9]、譜聚類方法[10];5)基于譜圖理論將聚類問題轉(zhuǎn)化為圖劃分問題.

2002年,文獻[11]正式提出聚類集成(Cluster ensemble),通過組合多個不同的聚類結(jié)果能夠獲得更加優(yōu)越的最終結(jié)果,具有傳統(tǒng)聚類算法無可比擬的優(yōu)勢[12].早期的聚類集成研究主要圍繞聚類成員生成和共識函數(shù)設(shè)計問題展開,目前已有較多聚類成員生成方法及共識函數(shù)設(shè)計方法[13?26].受“選擇性集成學(xué)習(xí)”研究啟發(fā),文獻[27]于2008年開啟了選擇性聚類集成研究,其關(guān)鍵問題為聚類成員選擇問題,即如何從所有聚類成員集合(稱為聚類集體)中選出部分聚類成員用于后續(xù)集成,獲得比對所有聚類成員進行集成更加優(yōu)越的結(jié)果.文獻[27]提出了質(zhì)量和多樣性綜合準則(Joint criterion,JC)、聚類并選擇(Cluster and select,CAS)和凸包(Convex hull,CH)三種方法.文獻[28]提出了自適應(yīng)聚類集成選擇(Adaptive cluster ensemble selection,ACES),依據(jù)聚類成員與初始一致劃分π?的歸一化互信息(Normalized mutual information,NMI)將聚類集體分為穩(wěn)定和不穩(wěn)定兩類,并選擇不同的聚類成員子集.ACES方法存在兩個問題:1)判定聚類集體穩(wěn)定性的方法不客觀,穩(wěn)定性與初始一致劃分π?有關(guān),在某些情況下容易將不穩(wěn)定的聚類集體誤判為穩(wěn)定.當(dāng)聚類成員之間差異性較低時,NMI值較大,且NMI值大于0.5的比例較高,聚類成員與π?的NMI值也較大,此時聚類集體穩(wěn)定;當(dāng)聚類成員之間差異性較高時,NMI值較低,平均NMI值低于0.5,且NMI值大于0.5的比例低于50%,但仍然有絕大多數(shù)的聚類成員與π?的NMI值大于0.5,此時雖然聚類集體不穩(wěn)定,但ACES方法卻判定聚類集體是穩(wěn)定的.2)聚類成員子集的選擇方法不夠合理.當(dāng)聚類集體穩(wěn)定時,ACES簡單地選擇Full集并輸出π?,而沒有進一步選擇差異性較高的聚類成員來提高集成效果;當(dāng)聚類集體不穩(wěn)定時,ACES簡單地選擇High集,可能會選出少量聚類質(zhì)量較差的聚類成員.

本文針對ACES存在的問題,提出了一種改進的自適應(yīng)聚類集成選擇方法(Improved adaptive cluster ensemble selection,IACES).本文把所有聚類成員的整體平均NMI值(Total average NMI,TANMI)作為判定聚類集體是否穩(wěn)定的依據(jù),若TANMI大于0.5,則聚類集體穩(wěn)定;否則,不穩(wěn)定.有效解決了上述第一個問題.當(dāng)聚類集體穩(wěn)定時,聚類成員提供相似的聚類結(jié)構(gòu),差異可能由聚類算法陷入局部最優(yōu)值引起,π?能夠在一定程度上減小聚類成員之間差異引起的方差,可能比聚類成員更加接近于真實分類結(jié)果.與ACES選擇Full集不同,本文首先選擇與π?的差異性最低(NMI值最大)的1/4的聚類成員,降低平均誤差;然后選擇與π?的差異性最高(NMI值最小)的1/4的聚類成員,增加平均差異性;另外,為了避免選出離群點,通過約束聚類成員的平均NMI值(Average NMI,ANMI)排名高于某一閾值.此時,選出的聚類成員既具有較高質(zhì)量,又具有適中的差異性,往往能夠獲得比π?更加優(yōu)越的結(jié)果.當(dāng)聚類集體不穩(wěn)定時,聚類成員提供了不同的聚類結(jié)構(gòu),差異可能由聚類算法本身的偏置或數(shù)據(jù)集的復(fù)雜結(jié)構(gòu)引起,此時π?偏離真實分類結(jié)果的可能性較大,因此應(yīng)該盡量降低聚類成員的平均誤差,選擇與π?差異性大的聚類成員(High集)往往會得到更好的結(jié)果.但High集里會存在一些質(zhì)量較差的聚類成員,此時通過約束聚類成員ANMI值排名高于某一閾值,能夠在很大程度上避免選出質(zhì)量較差的聚類成員.有效解決了上述第二個問題.

1 聚類集成相關(guān)研究

本文在文獻[11]提出的聚類集成框架上,增加聚類成員選擇模塊,形成選擇性聚類集成系統(tǒng)框架,如圖1所示,其中聚類成員選擇是本文的研究重點.選擇性聚類集成分為三步:第一步將數(shù)據(jù)集作為輸入,運行聚類算法,輸出聚類集體P={P(1),···,P(l)},這一步稱為聚類成員生成;第二步將聚類集體作為輸入,輸出若干聚類成員構(gòu)成的集合E={E(1),···,E(r)}?P,這一步稱為聚類成員選擇;第三步將E作為輸入,對它們進行組合,輸出最終的聚類結(jié)果,這一步稱為聚類組合(Combination)/集成(Ensemble)/融合(Fusion),也稱為共識函數(shù)(Consensus function)設(shè)計.下面對聚類集成相關(guān)研究予以闡述.

圖1 選擇性聚類集成系統(tǒng)框架Fig.1 Framework of selective cluster ensemble system

1.1 聚類成員生成

研究人員從聚類模型和數(shù)據(jù)集等角度入手提出了不同的聚類成員生成方法:1)采用同一種聚類算法[11?16,18?22,24?30].由于采用隨機初始化的KM每次運行會得到不同的聚類結(jié)果,因此可通過多次運行來生成聚類成員.該方法計算復(fù)雜度僅為O(lknd),其中l(wèi)為聚類成員的個數(shù),k為簇個數(shù),n為數(shù)據(jù)集大小,d為特征數(shù),因此成為產(chǎn)生聚類成員最常見的方法[31].2)對不同的數(shù)據(jù)子集進行聚類,例如隨機投影、投影到不同的子空間、采用不同的采樣技術(shù)、選擇不同的特征子集等[11,23].3)采用不同的聚類個數(shù),例如設(shè)置多個不同的k值或在指定的區(qū)間隨機選擇k[17].

1.2 聚類成員選擇

文獻[32]指出當(dāng)聚類成員多樣性較高時能夠獲得更好的集成效果.與此不同,文獻[33]指出適中的多樣性能夠獲得最佳的集成效果.文獻[28]認為不同數(shù)據(jù)集產(chǎn)生的聚類成員具有不同的特點,應(yīng)該區(qū)別對待,提出了ACES:1)采用AL對聚類集體(Full集)進行集成,獲得一致劃分π?;2)計算所有聚類成員與π?的NMI值,若平均NMI值(Mean NMI,MNMI)大于0.5,則聚類集體穩(wěn)定(Stable,S),否則,聚類集體不穩(wěn)定(Non-stable,NS);若聚類集體穩(wěn)定,則輸出π?為最終的聚類集成結(jié)果,若不穩(wěn)定,則選擇與π?差異大的一半子集High(具體地,將所有聚類成員與π?的NMI值按照降序排列,選擇NMI值小的一半子集),采用AL對High集進行集成得到最終的聚類集成結(jié)果.

文獻[27]提出了JC,CAS和CH三種聚類成員選擇方法,其中每個聚類成員的質(zhì)量與該成員和其他聚類成員的歸一化互信息之和(Sum of normalized mutual information,SNMI)成正比,而聚類集體的多樣性與所有聚類成員與其他成員的SNMI之和成反比.JC首先選擇質(zhì)量最高的聚類成員,然后逐一選擇使得目標函數(shù)值最大的聚類成員,直到選出預(yù)設(shè)的K個聚類成員為止.CAS使用NJW譜算法[34]將聚類集體劃分為K個分組,并從每個分組中選出一個質(zhì)量最高的聚類成員.CH首先根據(jù)聚類集體繪制質(zhì)量–多樣性圖,然后通過凸包創(chuàng)建該圖的簡要概括,其中包括質(zhì)量最高、多樣性最大的聚類成員所對應(yīng)的點,最后選出有凸包內(nèi)的點對應(yīng)的聚類成員.該文使用CSPA(Cluster-based similarity partitioning algorithm)[11]作為一致性函數(shù),對JC,CAS和CH進行了實驗比較,總體來看,CAS獲得了最佳聚類集成結(jié)果,但需要人工設(shè)置聚類成員個數(shù).

文獻[29]提出最有效一致劃分(Best validated consensus partition,BVCP),采用不同的聚類成員選擇方法選出不同子集,并對每個子集進行集成,獲得多個候選一致劃分(Candidate consensus partition,CCP),最后使用多個相對有效性指標評價每個CCP,得到最佳評價指標的CCP即為最終的一致劃分.近期,文獻[30]基于證據(jù)空間擴展有效性指標Davies-Bouldin(DB),利用聚類成員的類別相關(guān)矩陣度量差異性,以較高有效性和較大差異性為目標選擇聚類成員.

1.3 共識函數(shù)設(shè)計

聚類分析過程中,對象標簽是未知的,因此不同聚類成員得到的簇標簽沒有顯式的對應(yīng)關(guān)系.另外,聚類成員可能包含不同的簇個數(shù),使得簇標簽對應(yīng)問題極具挑戰(zhàn)[11].根據(jù)是否顯式解決簇標簽對應(yīng)問題,聚類集成方法可分為以下兩類:1)組對法(Pairwise approach),引入超圖的鄰接矩陣H將表示對象之間的兩兩關(guān)系,有效避免了簇標簽對應(yīng)問題.根據(jù)處理的矩陣不同,可以分為:a)對H(或其加權(quán)矩陣)進行處理,包括HGPA(Hypergraph partitioning algorithm)[11]和MCLA(Meta-clustering algorithm)[11]、基于NMF的方法[15]、基于KM 的方法[19]、結(jié)合KM與拉普拉斯矩陣的方法[26]、基于矩陣低秩近似的方法[35]等;b)對相似度矩陣S(或S的加權(quán)矩陣)進行處理,包括基于圖劃分算法的CSPA[11]、混合模型方法[12]、二部圖模型方法[13]、層次聚類法[14]、鏈接法[17]、加權(quán)共現(xiàn)矩陣(Weighted co-association matrices)方法[20]、使用多蟻群算法的方法[22]、基于AP的方法[24]、基于DP的方法[25]、基于譜聚類的方法[36]等.組對法因其思想簡單而成為解決共識函數(shù)設(shè)計問題的主要方法.2)重新標注法(Re-labeling approach),包括累積投票(Cumulative voting)[16]、PRI(Probabilistic rand index)[18]、選擇性投票[21]等.

2 本文方法

2.1 聚類成員之間的差異性計算

在沒有先驗知識的情況下,衡量聚類成員差異性大小的一種思路是依據(jù)聚類成員彼此之間的“相似”程度:兩個聚類成員越相似,差異越小,反之差異越大.本文采用源自信息論的NMI值[11]來度量聚類成員之間的相似度,NMI值越大,兩個聚類結(jié)果的匹配程度越高,其相似度越大,差異性越小.通過計算聚類成員兩兩之間的NMI值,即可得到聚類成員之間的相似度矩陣.

2.2 聚類集體穩(wěn)定性判定方法

假設(shè)l個聚類成員構(gòu)成的聚類集體P={P(1),···,P(l)},ACES首先采用AL對聚類集體進行集成,獲得一致劃分π?;然后計算所有聚類成員與π?的NMI值,若MNMI大于0.5,則聚類集體穩(wěn)定,否則,不穩(wěn)定.MNMI的計算方法如下:

與ACES不同,本文根據(jù)所有聚類成員之間的相似程度判定聚類集體的穩(wěn)定性,當(dāng)所有聚類成員的TANMI大于0.5(或NMI值大于0.5的比例Proportion較高,例如Proportion≥50%)時,說明聚類集體的整體相似度較高,差異性較低,聚類集體穩(wěn)定;否則,不穩(wěn)定.TANMI的計算方法如下:

其中,Sij表示聚類成員P(i)和P(j)之間的NMI值,Sij越大,其相似度越大,差異性越小.Proportion的計算方法如下:

其中,F(x)為指示函數(shù):當(dāng)x>0.5時,F(x)為1,否則為0.

由式(1)可知,MNMI的大小不僅與聚類集體有關(guān),還與π?有關(guān).由式(2)和式(3)可知,TANMI統(tǒng)計聚類集體的整體平均NMI值,Proportion統(tǒng)計聚類成員之間NMI值大于0.5的比例,對于給定的聚類集體,TANMI和Proportion是固定不變的.聚類集體穩(wěn)定性分為兩種情況:1)聚類集體穩(wěn)定,此時,多數(shù)聚類成員之間的相似度較高,差異性較低(NMI值大于0.50),Proportion>0.5,TANMI>0.5,多數(shù)聚類成員與π?的NMI值也大于0.5,故MNMI>0.5,因此,ACES與IACES方法都能正確判定聚類集體為穩(wěn)定.2)聚類集體不穩(wěn)定,此時,多數(shù)聚類成員之間的相似度較低,差異性較高(NMI值小于0.5),Proportion<0.5,TANMI<0.5,IACES方法能夠正確判定聚類集體為不穩(wěn)定,而ACES判定聚類集體是否穩(wěn)定與π?有關(guān).當(dāng)多數(shù)聚類成員與π?的NMI值大于0.5時,MNMI>0.5,ACES方法會將聚類集體誤判為穩(wěn)定;當(dāng)多數(shù)聚類成員與π?的NMI值小于0.5時,MNMI<0.5,ACES方法判定聚類集體不穩(wěn)定.

2.3 聚類成員選擇方法

根據(jù)集成學(xué)習(xí)理論[37],集成的泛化誤差E等于集成中各基學(xué)習(xí)器的平均泛化誤差與平均差異性之差,即.因此,要提高集成學(xué)習(xí)的性能,可從兩個方面著手:1)盡量降低各基學(xué)習(xí)器的誤差;2)盡量增加基學(xué)習(xí)器之間的差異性.

文獻[28]通過實驗對比了4種聚類成員集合,分別是所有聚類成員構(gòu)成的集合Full,與π?差異性最低的一半聚類成員構(gòu)成的集合Low,與π?差異性最高的一半聚類成員構(gòu)成的集合High,與π?差異性適中的一半聚類成員構(gòu)成的集合Medium,實驗結(jié)果顯示,當(dāng)聚類集體穩(wěn)定時,選擇Full集合進行集成獲得了最佳結(jié)果;當(dāng)聚類集體不穩(wěn)定時,選擇High集合進行集成獲得了最佳結(jié)果.

本文在ACES基礎(chǔ)上進行了改進,提出以下聚類成員選擇方法:當(dāng)聚類集體穩(wěn)定時,本文首先選擇與π?的NMI值最大的1/4的聚類成員,盡量降低聚類成員的平均誤差;然后選擇與π?的差異性最高(NMI值最小)的1/4的聚類成員,盡量增加平均差異性,構(gòu)成聚類成員集合LaH(Low and high);另外,為了避免選出精度較低的聚類成員(離群點),在LaH集合中剔除部分平均NMI值較低的聚類成員.具體地,本文對每個聚類成員與其他聚類成員的ANMI進行排名,限制選出的聚類成員排名在前θ以內(nèi),0%<θ≤100%.不妨假設(shè)聚類成員P(i)的ANMIi排名為Rank(i),則符合條件的聚類成員集合為C={P(i)|Rank(i)/l≥θ,1≤i≤l},因此,選擇的聚類成員集合為LaH∩C,其中∩表示集合的交運算.此時,LaH∩C既具有較高質(zhì)量,又具有適中的差異性,對其進行集成往往能夠獲得比π?更加優(yōu)越的結(jié)果.當(dāng)聚類集體不穩(wěn)定時,聚類成員提供了不同的聚類結(jié)構(gòu),差異可能由聚類算法本身的偏置或數(shù)據(jù)集的復(fù)雜結(jié)構(gòu)引起,此時π?很可能偏離了真實分類結(jié)果,因此應(yīng)該盡量降低聚類成員的平均誤差,選擇與π?差異性大的聚類成員(High集)可能會得到更好的結(jié)果.但High集里可能會存在一些質(zhì)量較差的聚類成員,此時可通過約束聚類成員的ANMI排名在某一范圍內(nèi).本文對每個聚類成員與其他聚類成員的ANMI進行排名,限制選出的聚類成員排名在前θ以內(nèi),0%<θ≤100%,因此,選擇的聚類成員集合為High∩C.

為了確定合理的θ,本文首先采用不同的θ選出不同的聚類成員子集,然后對每個子集進行集成,獲得多個CCP,最后使用內(nèi)部有效性指標DB對每個CCP進行評價,得到最低DB值的CCP即為最終的一致劃分.考慮到要確定最佳的參數(shù)θ需要運行l(wèi)次,而DB的計算復(fù)雜度較高,當(dāng)聚類成員個數(shù)l較大時,需要耗費極其高昂的計算代價.因此,為了提高算法效率,本文僅設(shè)置θ=10%,20%,···,100%,比較這10種情況下獲得的最佳結(jié)果,獲得一個較優(yōu)解.在本文實驗中,絕大多數(shù)情況下,當(dāng)θ等于70%,80%或90%時獲得了最低的DB值.

3 實驗

實驗平臺為Intel Xeon E5-1650六核處理器,頻率3.50GHz,內(nèi)存16.00GB,程序在MAT-LAB2016b下運行.

3.1 實驗數(shù)據(jù)集和評價指標

實驗采用13組公共文本測試集,具體描述如表1所示,數(shù)據(jù)集中的文本數(shù)(nd)從204～8580不等,特征數(shù)(nw)從5832～41681不等,類別數(shù)(k?)從3～10不等,平均每個類別包含的文本數(shù)(nc)從34～1774不等,平衡因子(Balance)從0.037～0.998不等(Balance等于最小類別包含的文本數(shù)除以最大類別包含的文本數(shù),值越小,數(shù)據(jù)集越不平衡,反之越平衡).對于每個數(shù)據(jù)集,使用停用詞表移去停用詞,并且去掉出現(xiàn)在少于兩個文本中的詞.數(shù)據(jù)集tr11,tr23,tr41和tr45取自TREC-5TREC-6和TREC-7數(shù)據(jù)集la1,la2和la12取自TREC-5,由洛杉磯時報(Los Angles Times)上的文章構(gòu)成.數(shù)據(jù)集hitech,reviews和sports取自報紙San Jose Mercury,它們是TREC文本集的一部分.數(shù)據(jù)集classic由用于評估信息檢索系統(tǒng)的四種摘要構(gòu)成,每個摘要集合構(gòu)成單獨的一類.數(shù)據(jù)集k1b來自于WebACE project[38],每個文本對應(yīng)于Yahoo!主題層次下的一個網(wǎng)頁.ng3為NG20的子集,包含了有關(guān)政治的3個不同方面,每方面分別包含約1000條信息.

表1 實驗數(shù)據(jù)集描述Table 1 Description of datasets

因為文本類別標簽已知,本文采用NMI值量化聚類結(jié)果和已知類別的匹配程度.當(dāng)兩個類別標簽一一對應(yīng)時,NMI值達到最大值1.另外,本文還采在信息檢索領(lǐng)域常用的綜合指標,F值(F-measure).F值越大,聚類質(zhì)量越高,反之越低.

3.2 實驗設(shè)計與結(jié)果分析

本節(jié)通過實驗對文獻[28]提出的ACES、本文提出的IACES、文獻[27]提出的CAS進行比較,其中ACES和IACES根據(jù)聚類集體的穩(wěn)定性自適應(yīng)選擇不同的聚類成員,CAS通過人工設(shè)置的方法選擇不同個數(shù)的聚類成員(分別設(shè)置為聚類集體大小的5%～25%,以5%遞增,本文沿用該方法).實驗分為兩部分:1)聚類集體穩(wěn)定性判定方法對比,分別根據(jù)ACES和IACES判定出聚類集體的穩(wěn)定性結(jié)果,并進行分析比較,驗證本文提出的聚類集體穩(wěn)定性判定方法的有效性;2)聚類成員選擇方法對比,分別根據(jù)ACES,IACES和CAS選擇不同的聚類成員集合并采用不同的共識函數(shù)設(shè)計方法進行集成,比較不同算法獲得的NMI值和F值,驗證本文的聚類成員選擇方法的有效性.下面對實驗中采用的聚類成員生成策略和共識函數(shù)設(shè)計方法進行介紹.

首先對經(jīng)過預(yù)處理的文本數(shù)據(jù)集進行TF-IDF(Term frequency-inverse document frequency)加權(quán),然后運行使用余弦相似度的KM算法l次,每次生成k0個簇,采用如下兩種不同的策略分別生成l=1000個聚類成員:1)k0=k?;2)k0隨機選自區(qū)間[2,2×k?],由此分別構(gòu)建聚類集體P1和P2.策略1是聚類集成研究中最常見的方法,由于采用了相同的聚類算法,每個算法生成的簇個數(shù)相等,因此聚類成員的差異性僅由不同初始聚類中心引起,聚類集體往往會缺乏多樣性.策略2試圖通過約束聚類成員具有不同的簇個數(shù)來提高聚類成員多樣性.

常見的共識函數(shù)設(shè)計方法有基于圖劃分算法的CSPA,HGPA,MCLA(其中CSPA總體聚類效果最好),基于層次聚類SL,CL,AL,WL的方法(其中AL總體聚類效果最好),基于譜聚類(Spectral clustering,SC)的方法,基于KM的方法.因此,本文采用CSPA,AL,SC和KM進行集成.CSPA調(diào)用了圖劃分算法METIS,不平衡因子UB取默認值0.05,得到穩(wěn)定的聚類結(jié)果.AL獲得了穩(wěn)定的聚類結(jié)果.譜聚類方法由于調(diào)用了KM算法,在部分數(shù)據(jù)集上獲得的聚類結(jié)果不夠穩(wěn)定,本文重復(fù)運行KM算法10次取最優(yōu)結(jié)果.基于KM的方法獲得的聚類結(jié)果極不穩(wěn)定,受初始聚類中心影響較大.為了提高聚類結(jié)果的穩(wěn)定性和聚類質(zhì)量,本文引入K-means++(KM++)算法,運行KM++10次取最優(yōu)結(jié)果.

3.2.1 聚類集體穩(wěn)定性判定方法對比

表2給出了分別根據(jù)ACES和IACES方法判定的聚類集體穩(wěn)定性結(jié)果,其中MNMI值根據(jù)式(1)計算,Number表示與π?的NMI值大于0.5的聚類成員個數(shù),TANMI根據(jù)式(2)計算,Propor-tion根據(jù)式(3)計算,Stability為“S”表示聚類集體穩(wěn)定,Stability為“NS”表示聚類集體不穩(wěn)定.

表2 分別根據(jù)ACES和IACES判定的聚類集體穩(wěn)定性結(jié)果Table 2 Stability results of cluster ensemble according to ACES and IACES

根據(jù)表2,可以進行以下比較:

1)因為在所有數(shù)據(jù)集上MNMI值都大于0.5,所以ACES將由不同聚類成員生成策略產(chǎn)生的聚類集體都判定為穩(wěn)定.當(dāng)k0=k?時,在hitech和ng3上,聚類集體的TANMI值小于0.5,所以IACES將其判定為不穩(wěn)定,而在其他11個數(shù)據(jù)集上,聚類集體的TANMI值大于0.5,所以IACES將其判定為穩(wěn)定;當(dāng)k0∈[2,2×k?]時,在la2,la12,hitech和ng3上,聚類集體的TANMI值小于0.5,所以IACES將其判定為不穩(wěn)定,而在其他9個數(shù)據(jù)集上,聚類集體的TANMI值都大于0.5,所以IACES將其判定為穩(wěn)定.

2)如果以Proportion是否高于0.5來判定聚類集體穩(wěn)定與否,那么在所有數(shù)據(jù)集上的判定結(jié)果都與依據(jù)TANMI判定的結(jié)果一致,而在部分數(shù)據(jù)集上與依據(jù)MNMI判定的結(jié)果不一致.究其原因,當(dāng)半數(shù)以上的聚類成員之間的NMI值大于0.5時,聚類集體的差異性相對較低,聚類集體穩(wěn)定.此時,TANMI值也大于0.5,絕大多數(shù)聚類成員(Number>500)與π?的NMI值大于0.5,故MNMI也大于0.5.因此,根據(jù)TANMI和ANMI判定的結(jié)果都是聚類集體穩(wěn)定.然而,當(dāng)半數(shù)以下的聚類成員之間的NMI值大于0.5時,聚類集體的差異性相對較高,聚類集體不穩(wěn)定.此時,TANMI值也小于0.5,但仍然有絕大多數(shù)聚類成員(Number>500)與π?的NMI值大于0.5,故MNMI仍然大于0.5.因此,根據(jù)TANMI判定的結(jié)果是聚類集體不穩(wěn)定,而根據(jù)ANMI判定的結(jié)果依然是聚類集體穩(wěn)定.

綜上,由于IACES依據(jù)TANMI判定聚類集體穩(wěn)定性,只客觀地依賴于聚類集體本身的特性,因此能夠準確判定其穩(wěn)定性;而由于ACES依據(jù)MNMI判定聚類集體穩(wěn)定性,與初始一致劃分π?有關(guān),因此會將某些不穩(wěn)定的聚類集體誤判為穩(wěn)定.

3.2.2 聚類成員選擇方法對比

1)分別根據(jù)ACES和IACES選擇聚類成員并進行集成獲得的結(jié)果對比.

圖2和圖3分別顯示了采用聚類集體P1和P2時根據(jù)ACES和IACES選擇聚類成員,并采用CSPA,AL,SC,KM++進行集成獲得的NMI值和F值,其中Average統(tǒng)計了8種算法(以“聚類成員選擇方法_共識函數(shù)設(shè)計方法”命名)在13組數(shù)據(jù)集上的平均結(jié)果.

根據(jù)圖2,分別比較不同共識函數(shù)根據(jù)ACES和IACES選擇聚類成員并進行集成獲得的NMI值和F值,可以發(fā)現(xiàn):

a)對于聚類集體不穩(wěn)定的2種情況(hitech和ng3),IACES_CSPA,IACES_AL,IACES_SC和IACES_KM++獲得的NMI值和F值都分別高于ACES_CSPA,ACES_AL,ACES_SC和ACES_KM++.

圖2 采用聚類集體P1時獲得的聚類結(jié)果(NMI值和F值)Fig.2 Clustering results obtained when using cluster ensembleP1(NMI scores and F measures)

b)對于其他11種聚類集體穩(wěn)定的情況,IACES_CSPA僅在tr23,la1,sports上獲得了比ACES_CSPA低的NMI值和F值,而在其他8組數(shù)據(jù)集上都獲得了高于ACES_CSPA的NMI值和F值;IACES-AL僅在la12和k1b上獲得了比ACES_AL低的NMI值和F值,而在其他9組數(shù)據(jù)集上都獲得了高于ACES_AL的NMI值和F值;IACES_SC僅在tr45上獲得了比ACES_SC低的NMI值,而在其他10組數(shù)據(jù)集上都獲得了高于ACES_SC的NMI值,IACES_SC僅在tr45和k1b上獲得了比ACES_SC低的F值,而在其他9組數(shù)據(jù)集上都獲得了高于ACES_SC的F值;IACES_KM++僅在la12上獲得了比ACES_KM++低的NMI值和F值,而在其他10組數(shù)據(jù)集上都獲得了高于ACES_KM++的NMI值和F值.

圖3 采用聚類集體P2時獲得的聚類結(jié)果(NMI值和F值)Fig.3 Clustering results obtained when using cluster ensembleP2(NMI scores and F measures)

c)總體來看,當(dāng)采用聚類集體P1時,與ACES相比,采用IACES進行成員選擇,CSPA分別以10/13和10/13的比例提高了NMI值和F值;AL分別以11/13和11/13的比例提高了NMI值和F值;SC分別以12/13和11/13的比例提高了NMI值和F值;KM++分別以12/13和12/13的比例提高了NMI值和F值;CSPA,AL,SC,KM++獲得的平均NMI值和F值都有不同程度的提高.

根據(jù)圖3,分別比較不同共識函數(shù)根據(jù)ACES和IACES選擇聚類成員并進行集成獲得的NMI值和F值,可以發(fā)現(xiàn):

a)對于聚類集體不穩(wěn)定的4種情況(la2,la12,hitech和ng3),IACES_CSPA在la2,la12和ng3上獲得的NMI值和F值低于IACES_CSPA,在hitech上獲得了比ACES_CSPA高的NMI和F值;IACES_AL,IACES_SC和IACES_KM++獲得的NMI值和F值都分別高于ACES_AL,ACES_SC和ACES_KM++.

b)對于其他7種聚類集體穩(wěn)定的情況,IACES_CSPA在所有7組數(shù)據(jù)集上都獲得了高于ACES_CSPA的NMI值和F值;IACES_AL僅在tr11和la1上獲得了比ACES_AL低的NMI值,而在其他5組數(shù)據(jù)集上都獲得了高于ACES_AL的NMI值,IACES_AL僅在la1上獲得了比ACES_AL低的F值,而在其他6組數(shù)據(jù)集上都獲得了高于ACES_AL的F值;IACES_SC僅在la1上獲得了比ACES_SC低的NMI值,而在其他6組數(shù)據(jù)集上都獲得了高于ACES_SC的NMI值,IACES_SC僅在tr41上獲得了比ACES_SC低的F值,而在其他6組數(shù)據(jù)集上都獲得了高于ACES_SC的F值;IACES_KM++僅在la1上獲得了比ACES_KM++低的NMI值和F值,而在其他6組數(shù)據(jù)集上都獲得了高于ACES_KM++的NMI值和F值.

c)總體來看,當(dāng)采用聚類集體P2時,與ACES相比,采用IACES進行成員選擇,CSPA分別以10/13和10/13的比例提高了NMI值和F值;AL分別以11/13和12/13的比例提高了NMI值和F值;SC分別以12/13和11/13的比例提高了NMI值和F值;KM++分別以12/13和12/13的比例提高了NMI值和F值;CSPA,AL,SC,KM++獲得的平均NMI值和F值都有不同程度的提高.

綜上,與ACES相比,根據(jù)IACES選擇聚類成員進行CSPA,AL,SC和KM++集成在絕大部分情況下都獲得了更高的NMI值和F值,每個共識函數(shù)設(shè)計方法在所有數(shù)據(jù)集上獲得的平均NMI值和F值都更高.

2)聚類成員選擇方法CAS,ACES,IACES綜合比較

本文實驗中聚類集體大小為1000,CAS分別選擇s=50,100,150,200,250個聚類成員,每個s對應(yīng)一種聚類成員選擇方法,例如CAS(s=50)表示根據(jù)CAS選擇50個聚類成員.圖4和圖5分別顯示了當(dāng)采用聚類集體P1和P2時,根據(jù)CAS,ACES和IACES選擇聚類成員并采用CSPA,AL,SC,KM++進行集成獲得的NMI值和F值的平均值(例如,圖4中的IACES表示4個聚類集成算法IACES_CSPA,IACES_AL,IACES_SC,IACES_KM++獲得的NMI值的平均值),其中Total average統(tǒng)計了7種不同聚成員選擇方法在13組數(shù)據(jù)集上的平均結(jié)果.

由圖4和圖5可見:

a)IACES在每個數(shù)據(jù)集上獲得的NMI值和F值的平均值都高于ACES和CAS.

b)ACES在某些數(shù)據(jù)集上獲得的NMI值和F值的平均值低于CAS(例如圖4中的tr23和ng3),但在絕大部分情況下都高于CAS.

圖4 當(dāng)采用聚類集體P1時獲得的聚類結(jié)果(平均NMI值和平均F值)Fig.4 Clustering results obtained by combining cluster members selected by ACES and IACES via CSPA,AL,SC and KM++when using cluster ensembleP1(Total average NMI scores and total average F measures)

c)總體來看,IACES在所有數(shù)據(jù)集上獲得了最高的平均結(jié)果,ACES次之,即自適應(yīng)聚類成員選擇方法ACES優(yōu)于CAS方法,而本文的方法則比ACES更加優(yōu)越.

4 結(jié)論

本文提出了一種改進的自適應(yīng)聚類集成選擇方法(IACES),有效解決了ACES存在的聚類集體穩(wěn)定性判定方法不客觀和聚類成員選擇方法不夠合理的問題.在多組基準數(shù)據(jù)集上進行了實驗,實驗結(jié)果表明:1)IACES能夠準確判定聚類集體的穩(wěn)定性,而ACES會將某些不穩(wěn)定的聚類集體誤判為穩(wěn)定;2)與其他聚類成員選擇方法相比,根據(jù)IACES選擇聚類成員進行集成在絕大部分情況下都獲得了更佳的聚類結(jié)果,在所有數(shù)據(jù)集上都獲得了更優(yōu)的平均聚類結(jié)果.

圖5 當(dāng)采用聚類集體P1時獲得的聚類結(jié)果(平均NMI值和平均F值)Fig.5 Clustering results obtained by combining cluster members selected by ACES and IACES via CSPA,AL,SC and KM++when using cluster ensembleP1(Total average NMI scores and total average F measures)