一種改進(jìn)的自適應(yīng)聚類集成選擇方法

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

聚類分析的目標(biāo)是依據(jù)對(duì)象之間的相似度對(duì)其自動(dòng)分組/簇,使得簇內(nèi)對(duì)象彼此相似度盡量高,而簇間對(duì)象彼此相似度盡量低[1?2].雖然已有上千種聚類算法,但沒(méi)有一種能有效識(shí)別不同大小,不同形狀,不同密度甚至可能包含噪聲的簇[1].已有聚類方法主要分為:1)基于劃分的方法,將聚類問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題,并采用不同的優(yōu)化策略,例如,K均值算法(K-means,KM)[3]、非負(fù)矩陣分解(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],將聚類問(wèn)題轉(zhuǎn)化為模型的充分統(tǒng)計(jì)量估計(jì)問(wèn)題;4)基于密度的方法,通過(guò)尋找被低密度區(qū)域分離的高密度區(qū)域來(lái)進(jìn)行聚類,例如密度峰值(Density peaks,DP)算法[9]、譜聚類方法[10];5)基于譜圖理論將聚類問(wèn)題轉(zhuǎn)化為圖劃分問(wèn)題.

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

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

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

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

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

1.1 聚類成員生成

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

1.2 聚類成員選擇

文獻(xiàn)[32]指出當(dāng)聚類成員多樣性較高時(shí)能夠獲得更好的集成效果.與此不同,文獻(xiàn)[33]指出適中的多樣性能夠獲得最佳的集成效果.文獻(xiàn)[28]認(rèn)為不同數(shù)據(jù)集產(chǎn)生的聚類成員具有不同的特點(diǎn),應(yīng)該區(qū)別對(duì)待,提出了ACES:1)采用AL對(duì)聚類集體(Full集)進(jìn)行集成,獲得一致劃分π?;2)計(jì)算所有聚類成員與π?的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對(duì)High集進(jìn)行集成得到最終的聚類集成結(jié)果.

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

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

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

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

2 本文方法

2.1 聚類成員之間的差異性計(jì)算

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

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

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

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

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

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

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

2.3 聚類成員選擇方法

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

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

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

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

3 實(shí)驗(yàn)

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

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

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

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

3.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

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

表2給出了分別根據(jù)ACES和IACES方法判定的聚類集體穩(wěn)定性結(jié)果,其中MNMI值根據(jù)式(1)計(jì)算,Number表示與π?的NMI值大于0.5的聚類成員個(gè)數(shù),TANMI根據(jù)式(2)計(jì)算,Propor-tion根據(jù)式(3)計(jì)算,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,可以進(jìn)行以下比較:

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

2)如果以Proportion是否高于0.5來(lái)判定聚類集體穩(wěn)定與否,那么在所有數(shù)據(jù)集上的判定結(jié)果都與依據(jù)TANMI判定的結(jié)果一致,而在部分?jǐn)?shù)據(jù)集上與依據(jù)MNMI判定的結(jié)果不一致.究其原因,當(dāng)半數(shù)以上的聚類成員之間的NMI值大于0.5時(shí),聚類集體的差異性相對(duì)較低,聚類集體穩(wěn)定.此時(shí),TANMI值也大于0.5,絕大多數(shù)聚類成員(Number>500)與π?的NMI值大于0.5,故MNMI也大于0.5.因此,根據(jù)TANMI和ANMI判定的結(jié)果都是聚類集體穩(wěn)定.然而,當(dāng)半數(shù)以下的聚類成員之間的NMI值大于0.5時(shí),聚類集體的差異性相對(duì)較高,聚類集體不穩(wěn)定.此時(shí),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)定性,只客觀地依賴于聚類集體本身的特性,因此能夠準(zhǔn)確判定其穩(wěn)定性;而由于ACES依據(jù)MNMI判定聚類集體穩(wěn)定性,與初始一致劃分π?有關(guān),因此會(huì)將某些不穩(wěn)定的聚類集體誤判為穩(wěn)定.

3.2.2 聚類成員選擇方法對(duì)比

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

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

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

a)對(duì)于聚類集體不穩(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時(shí)獲得的聚類結(jié)果(NMI值和F值)Fig.2 Clustering results obtained when using cluster ensembleP1(NMI scores and F measures)

b)對(duì)于其他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時(shí)獲得的聚類結(jié)果(NMI值和F值)Fig.3 Clustering results obtained when using cluster ensembleP2(NMI scores and F measures)

c)總體來(lái)看,當(dāng)采用聚類集體P1時(shí),與ACES相比,采用IACES進(jìn)行成員選擇,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í)函數(shù)根據(jù)ACES和IACES選擇聚類成員并進(jìn)行集成獲得的NMI值和F值,可以發(fā)現(xiàn):

a)對(duì)于聚類集體不穩(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)對(duì)于其他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)總體來(lái)看,當(dāng)采用聚類集體P2時(shí),與ACES相比,采用IACES進(jìn)行成員選擇,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選擇聚類成員進(jìn)行CSPA,AL,SC和KM++集成在絕大部分情況下都獲得了更高的NMI值和F值,每個(gè)共識(shí)函數(shù)設(shè)計(jì)方法在所有數(shù)據(jù)集上獲得的平均NMI值和F值都更高.

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

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

由圖4和圖5可見(jiàn):

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

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

圖4 當(dāng)采用聚類集體P1時(shí)獲得的聚類結(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)總體來(lái)看,IACES在所有數(shù)據(jù)集上獲得了最高的平均結(jié)果,ACES次之,即自適應(yīng)聚類成員選擇方法ACES優(yōu)于CAS方法,而本文的方法則比ACES更加優(yōu)越.

4 結(jié)論

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

圖5 當(dāng)采用聚類集體P1時(shí)獲得的聚類結(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)