基于高階一致性學(xué)習(xí)的聚類集成算法

甘艦文，陳 艷，周 芃，杜 亮，4*

（1.山西大學(xué) 計算機與信息技術(shù)學(xué)院，太原 030006；2.四川大學(xué) 計算機學(xué)院，成都 610065；3.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥 230601；4.山西大學(xué) 大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院，太原 030006）

0 引言

聚類是一種重要的無監(jiān)督分類技術(shù)，在統(tǒng)計、模式識別、機器學(xué)習(xí)、數(shù)據(jù)挖掘等不同領(lǐng)域都得到了廣泛的研究。根據(jù)幾種聚類準則和不同的相似性度量方法，可以揭示一個數(shù)據(jù)集的底層結(jié)構(gòu)。在無監(jiān)督學(xué)習(xí)中，由于訓(xùn)練數(shù)據(jù)集沒有標簽，聚類算法很難驗證聚類結(jié)果的有效性，給設(shè)計聚類算法帶來很大的挑戰(zhàn)。每種聚類算法都有自己的優(yōu)缺點，傳統(tǒng)的聚類算法同時還面臨其他問題［1］，例如同一種聚類算法，由于目標函數(shù)的不同，在相同的數(shù)據(jù)集上也會得到不同的聚類結(jié)果。K-均值（K-Means）算法高度依賴初始化和數(shù)據(jù)分布。為了提高單個聚類算法結(jié)果的魯棒性、一致性、新穎性和穩(wěn)定性，聚類集成（聚類融合或共識聚類）利用多個聚類結(jié)果的共識并將它們組合成最優(yōu)解。聚類集成提供了一種框架，可以將多個基聚類器的結(jié)果組合在一起，生成一致聚類［1］。

現(xiàn)有的聚類算法可以被分為三類：

1）基于相似性矩陣的算法。將基聚類結(jié)果轉(zhuǎn)化為相似性矩陣，通過不同的聚類集成方法生成一致性矩陣。

2）圖方法。將輸入的基聚類結(jié)果轉(zhuǎn)化為無向圖，通過圖劃分得到最終的聚類結(jié)果。

3）基于重標記的方法。將基聚類結(jié)果轉(zhuǎn)化為新的標簽向量，然后通過標簽對齊找到集合聚類。

基于相似性矩陣的方法和圖方法近年來有著廣泛的應(yīng)用。相似性矩陣反映樣本對之間的關(guān)系，在聚類集成算法中使用廣泛。不同的相似度度量方式會得到不同的結(jié)果。但這兩種方法的輸入數(shù)據(jù)易受離群點影響而破壞簇的邊界，從而影響到最終聚類結(jié)果［2］。本文通過基聚類器生成相似性矩陣，從不同的角度度量樣本對之間的相似性。

1 相關(guān)工作

聚類集成融合多種輸入結(jié)果試圖得到一個更好的結(jié)果，至今已經(jīng)發(fā)展出一大批聚類集成方法。在聚類集成方法發(fā)展早期，一些以信息論為基礎(chǔ)的方法被提出，如Strehl 等［3］以信息共享為基礎(chǔ)，將聚類集成問題轉(zhuǎn)化為組合優(yōu)化問題。近年來，更多的方法被應(yīng)用到聚類集成中，如利用對齊的方法結(jié)合多個K-Means 的聚類結(jié)果［4］。一些工作利用非負矩陣分解將關(guān)聯(lián)矩陣分解為兩個指示矩陣［5］。除了以K-Means 作為基聚類輸入，譜聚類也有聚類集成的工作。一些方法引入了概率理論將圖模型轉(zhuǎn)化為聚類集合，如Wang 等［6］使用了貝葉斯模型聚類集成學(xué)習(xí)了一個帶有因子圖的共識聚類結(jié)果。

由于聚類的多樣性和質(zhì)量在集成學(xué)習(xí)中至關(guān)重要，許多方法都充分利用多樣性和質(zhì)量來組合基聚類。如Abbasi等［7］提出了一種新的穩(wěn)定性測度——歸一化互信息（Normalized Mutual Information，NMI），并將它用于集合基聚類；Bagherinia 等［8］考慮基聚類結(jié)果的多樣性和質(zhì)量提出了一種模糊聚類集合。除了使用所有基聚類器的結(jié)果作為輸入進行聚類集成，還有一些工作試圖選擇一些具有高質(zhì)量信息且無冗余的基聚類結(jié)果進行集成。Azimi 等［9］提出了一種自適應(yīng)聚類集合選擇方法來選擇基聚類結(jié)果；Hong 等［10］采用重采樣方法選擇基聚類；Parvin 等［11］提出了一種加權(quán)局部自適應(yīng)聚類集合選擇算法；Yu 等［12］將聚類選擇轉(zhuǎn)化為特征選擇，設(shè)計了一種混合策略來選擇基聚類結(jié)果；Zhao 等［13］提出了用于聚類集合選擇的內(nèi)部有效性指標；Shi 等［14］將遷移學(xué)習(xí)擴展到聚類集成，提出了遷移聚類集成選擇方法。

根據(jù)算法思想和原理這些聚類集成方法可歸類為：基于關(guān)系矩陣的方法、直接融合法和基于圖的方法。Li 等［15］提出了規(guī)范化邊的概念用來度量樣本的相似度，用層次聚類來融合最終的結(jié)果；Huang 等［16］使用概率軌跡的概念重新構(gòu)造樣本相似度。直接融合法首先匹配基聚類器中的類簇，然后通過投票機制融合結(jié)果。圖方法在基聚類器上構(gòu)建圖表示，利用圖分割技術(shù)發(fā)現(xiàn)群組結(jié)構(gòu)。常用的圖劃分技術(shù)包括歸一化切割（Normalized CUT，N-CUT）［17］和層次化的分割算法METIS［18］。聚類方法的設(shè)計和輸入的基聚類結(jié)果都會顯著影響聚類集成的性能?；垲惤Y(jié)果應(yīng)該盡可能地體現(xiàn)差異性，而不是追求數(shù)量。獲得差異性的基聚類結(jié)果主要有以下幾種方式：1）使用不同的聚類方法對同一數(shù)據(jù)集進行聚類；2）使用不同的初始化值和有差異性的參數(shù)值；3）對進行聚類的數(shù)據(jù)集使用不同的辦法抽樣，獲得有區(qū)別的數(shù)據(jù)片段。

本文方法基于相似性矩陣，一方面利用高階信息有效地發(fā)掘數(shù)據(jù)樣本之間的聯(lián)系，另一方面不同角度的信息使得參與融合的基聚類信息具有較大的差異性。同時，利用多種信息源也會帶來處理高階數(shù)據(jù)耗時長、計算量大的問題。針對以上問題本文提出一種新的高階信息融合算法——基于高階一致性學(xué)習(xí)的聚類集成（Clustering Ensemble with Highorder Consensus Learning，HCLCE）算法。首先將每種高階信息融合成一個新的結(jié)構(gòu)化的一致性矩陣；然后再對得到的多個一致性矩陣進行融合。算法通過雙隨機約束，使得一致性矩陣行列求和的值都為1，因此樣本對之間的相似度，同時也表示了該樣本與其他樣本屬于同一個類的概率。

2 基于高階一致性學(xué)習(xí)的聚類集成

本章首先介紹高階信息的表示方法，然后描述HCLCE算法的具體細節(jié)，最后對目標函數(shù)進行求解優(yōu)化。

X={X1，X2，…，Xi，…，Xm}為d維空間中未標記的n個樣本，通過K-Means 算法進行m次聚類，生成基聚類結(jié)果H={H1，H2，…，Hi，…，Hm}，其中：Hi表示第i次聚類的結(jié)果；c表示簇的個數(shù)，假設(shè)所有基聚類器結(jié)果簇的個數(shù)一樣?；贖i，相似性矩陣Si可以表示為：，同時定義1 表示大小為n× 1 的列向量。

2.1 高階矩陣信息定義

單個基聚類器相似性矩陣是一次聚類的結(jié)果，為了挖掘樣本之間進一步的聯(lián)系，利用多次聚類的結(jié)果，獲取更具有代表性和差異性的高階信息。本文通過以下幾種方式，從不同的角度獲得聚類信息增益。

2.1.1 一階一致性

單次聚類結(jié)果的相似性矩陣結(jié)果Si之間差異性較小。以表示把單個相似性矩陣作為第一種輸入信息。

加權(quán)結(jié)構(gòu)化的過程可以分為兩步，由于一階信息是由m個聚類共識結(jié)果組成，每個聚類結(jié)果之間具有一定差異性，因此第一步對集合A1中的每個相似性矩陣賦予權(quán)重，融合成一個相似性矩陣，表示為：

其中：k是集合A1中元素的數(shù)量，在一階情況下k的大小等于輸入的相似性矩陣的個數(shù)；是k個相似性矩陣加權(quán)融合的結(jié)果為矩陣中的元素；wi是權(quán)重向量w的第i個元素。通過對結(jié)構(gòu)化使簇的結(jié)構(gòu)更清楚，同時滿足相似性矩陣性質(zhì)的約束。

其中：L是拉普拉斯矩陣；λ是自適應(yīng)參數(shù)。

求得的M11 對稱且滿足雙隨機約束，是一階信息加權(quán)結(jié)構(gòu)化后的一致性矩陣。

2.1.2 二階簇級一致性

二階簇級一致性表示兩個基聚類器對同一個簇的一致性進行投票。得分越大，說明不同基聚類器之間同一個樣本所在的兩個簇之間交集越大，越具有相似性。簇的一致性的投票計算過程如圖1 所示，可以表示為

圖1 相似性矩陣Si和Sj簇間交集大小的計算Fig.1 Calculation of intersection size between clusters of similarity matrix Si and Sj

二階簇級一致性是基聚類器兩兩運算，基聚類器之間不進行運算，所以m個輸入會產(chǎn)生m2-m個結(jié)果，而相似性矩陣本身對稱，因此只需要計算(m2-m)/2 次，對A2加權(quán)得：

求得M2對稱且滿足雙隨機約束，表示二階的簇級信息加權(quán)結(jié)構(gòu)化后的一致性矩陣。

2.1.3 二階樣本對一致性

相似性矩陣的每一個元素的值代表著不同樣本對兩兩之間一致性的大小。通過相似性矩陣兩兩之間進行點乘運算，只有在兩種樣本對取值都為1 的情況下，樣本對是否屬于一個類才能達成一致，否則認為不屬于同一類，這說明點乘運算只會保留達成一致的樣本對，不一致的樣本將會舍去，計算過程如圖2 所示，相似性矩陣對同一個樣本對相似性進行乘法運算，顯然只有達成一致的樣本對相似性為1，否則為0。所以這種情況下的高階信息同時增強了樣本對之間的確定性和不確定性，表示為對 于m個 相似性矩陣哈達瑪積也會產(chǎn)生(m2-m)/2個結(jié)果。

圖2 相似性矩陣Si和Sj樣本對的一致性計算Fig.2 Consistency calculation of similarity matrix Si and Sj sample pair

對A3加權(quán)得：

求得M3對稱且滿足雙隨機約束，是二階樣本對之間信息加權(quán)結(jié)構(gòu)化的一致性矩陣。

2.1.4m階樣本對一致性

在此基礎(chǔ)上，可以提出一種更加嚴格的樣本對一致性信息挖掘方式，表示為，這種運算表示對所有單次聚類結(jié)果進行連乘點積運算，只有所有結(jié)果達成一致的樣本對才會被保留，任何一個相似性矩陣的不一致結(jié)果，都會使該樣本對結(jié)果為0，計算過程如圖3?？梢钥吹?，對不同相似性矩陣中的樣本對相似度相乘，只有所有相似性矩陣在該樣本對上的值為1 時，得到的最終矩陣才會保留該樣本對相似度為1。因此，保留下的樣本對具有最大的確定性，同時該矩陣也最稀疏。A4最后結(jié)果只有一個矩陣，因此不需要賦予權(quán)重。定義S4=A4，對結(jié)構(gòu)化的過程為：

圖3 所有相似性矩陣樣本對一致性計算Fig.3 Consistency calculation for all similarity matrix sample pairs

求得M4對稱且滿足雙隨機約束，是m階樣本對級別的信息加權(quán)結(jié)構(gòu)化后的一致性矩陣。

2.1.5 高階信息融合

聚類集成將多個共識結(jié)果組合為一個最優(yōu)解，由于對高階信息的發(fā)掘，特別是相似性矩陣兩兩之間的關(guān)聯(lián)，使得需要融合的共識結(jié)果迅速增多，一次性融合這些信息需要耗費巨大的時間和計算量，為此本文提出一種分階段融合的框架。對每種高階信息進行計算，先融合成一種加權(quán)結(jié)構(gòu)化后的高階信息，將它作為輸入，最終融合為一個一致性矩陣。用M表示滿足約束條件，是最終學(xué)習(xí)的一致性矩陣。整體算法流程如圖4 所示。

圖4 分階段融合算法流程Fig.4 Flowchart of phased fusion algorithm

由于每種高階信息攜帶的信息和側(cè)重點不同，為了放大信息間差異性的作用，仍需要對每種信息賦予權(quán)重，如式（8）所示：

其中：L是拉普拉斯矩陣，LM=DM-M，DM為矩陣M的度矩陣，DM∈Rn×n定義為一個對角矩陣，第i個元素為，通過增加秩約束，使得rank(LM)=n-c，學(xué)得的一致性矩陣有c個連通片，從而獲得更加清晰的簇結(jié)構(gòu)［19］；d是需要融合信息的個數(shù)；λ是自適應(yīng)參數(shù)，隨著rank(LM)的大小自動調(diào)整；Mi是第i種加權(quán)結(jié)構(gòu)化后的高階信息輸入。下面介紹如何求解所提出的目標函數(shù)。

2.2 模型優(yōu)化

本節(jié)主要介紹優(yōu)化問題的求解方法和算法流程。

2.2.1 加權(quán)優(yōu)化

優(yōu)化問題式（1）、（3）、（5）為同一種問題，區(qū)別在于權(quán)重個數(shù)不同。以式（1）為例，迭代更新w和A1。

2.2.2 結(jié)構(gòu)化算法

優(yōu)化問題式（2）、（4）、（6）、（7）為同一類問題。以式（2）為例：

1）固定F，更新M1。

根據(jù)Von Neumann 交替投影定理［20］。本文使用的這種相互投影策略將收斂于由問題（14）和（15）形成的兩個子空間的交叉。對式（14）［21］求解可得：

將得到M1作為B代入式（14），如此迭代直至M1收斂。

2）固定M1，更新F。

優(yōu)化問題（2）可化簡為：

根據(jù)Ky Fan’s theorem 理論［22］，F(xiàn)為L前c個最小的特征向量。

2.2.3 融合算法

求解式（8），可以迭代地更新M、W、F，詳細過程如下：

1）固定M，更新w。

固定M，式（8）可化簡為：

其中，F(xiàn)為L前c個最小的特征向量。

下面對目標函數(shù)求解過程進行總結(jié)。

求解式（1）、（3）、（5）的算法流程算法1 所示。

算法1 加權(quán)優(yōu)化。

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)集

本文使用以下8 種不同類型的數(shù)據(jù)集進行聚類集成實驗：1）CSTR（http：//www.ncdc.ac.cn/portal/metadata/1a0e7fc8-8dc1-4c74-a6b2-e6a20d7b6ee4）；2）GLIOMA（https：//sites.google.com/site/feipingnie/file/）；3）Prostate（https：//cdas.cancer.gov/datasets/plco/20/）；4）ORL（http：//www.uk.research.att.com/facedatabase.html）；5）YALE（http：//cvc.yale.edu/projects/yalefaces/yalefaces.html）；6）Tr41（http：//www.cs.umn.edu/～karypis/cluto/files/datasets.tar.gz）；7）Jaffe（http：//www.kasrl.org/jaffe.html）；8）AR（http：//www2.ece.ohio-state.edu/～aleix/ARdatabase.html）。使用不同類型的數(shù)據(jù)集可以更好地評估算法性能，數(shù)據(jù)集的詳細信息如表1所示。

表1 數(shù)據(jù)集詳細信息Tab.1 Detailed information of datasets

3.2 對比方法

實驗對比了以下9 種算法：

1）K-Means（簡寫為KM）：表示K均值聚類的結(jié)果。聚類集成通常使用該算法作為基線。

2）CSPA（Cluster-based Similarity Partitioning Algorithm）［3］：表示了同一個簇種樣本的關(guān)系，用于度量樣本對之間的相似度。

3）HGPA（HyperGraph Partitioning Algorithm）［3］：一種基于超圖劃分鄰域的方法，將超圖的超邊以及頂點所有的權(quán)重設(shè)為統(tǒng)一值。設(shè)置分區(qū)大小以避免出現(xiàn)大量碎片分區(qū)。

4）MCLA（Meta-CLustering Algorithm）［3］：該算法將聚類集成問題轉(zhuǎn)化為簇一致性問題。

5）LWEA（Locally Weighted Evidence Accumulation）［23］：層次聚類方法，基于集成不確定估計和局部加權(quán)策略。

6）LWGP（Locally Weighted Graph Partitioning）［23］：一種基于局部加權(quán)策略的圖劃分算法；此外，通過熵的準則判斷簇的可靠性。

7）RSEC（Robust Spectral Ensemble Clustering）［24］：一種具有魯棒性的譜聚類方法。

8）DREC（Dense Representation Ensemble Clustering）［2］：該算法利用密集表示模型構(gòu)造樣本相似性矩陣。

9）SPEC（Self-Paced Clustering Ensemble）［25］：該方法從易到難進行學(xué)習(xí)，并將難度評估和集成學(xué)習(xí)融合在統(tǒng)一的框架中。

3.3 評價指標

本文實驗采用聚類準確率（ACCuracy，ACC）和歸一化互信息（Normalized Mutual Information，NMI）兩種常見的聚類有效性外部評價指標評估算法性能。

ACC 用于比較獲得的標簽和數(shù)據(jù)提供的真實標簽，用VACC表示，取值范圍是［0，1］，值越大說明獲得的標簽準確性越高，將樣本正確劃分的效果越好。

其中：pi是聚類后的標簽；qi是真實標簽；n為樣本總數(shù)。δ表示指示函數(shù)，具體如下：

NMI 度量聚類結(jié)果的相似性程度，取值范圍為［0，1］，值越大，說明變量之間的關(guān)系越密切，聚類結(jié)果越相近：

其中：H(A)、H(B)是A、B的熵；I(A，B)是互信息，表示一個變量包含另一個變量的信息量；A是真實數(shù)據(jù)的標簽集合，B是聚類算法劃分的類集合?；バ畔(A，B)表示為：

其中：p(ai)為從數(shù)據(jù)集中任意選定一個樣本點屬于A類的概率；p(ai，bi)為任選的數(shù)據(jù)點同時屬于A類和B類的概率。

3.4 實驗結(jié)果與分析

本文將通過實驗驗證高階信息以及高階信息融合的有效性。不同算法在8 個數(shù)據(jù)集上的結(jié)果對比如表2～4 所示，其中：最優(yōu)結(jié)果加粗表示；次優(yōu)結(jié)果用下劃線表示；括號中的數(shù)據(jù)為方差。

表2 ACC實驗結(jié)果對比Tab.2 Comparison of ACC experimental results

表2 為不同算法的ACC 結(jié)果，可以看出：HCLCE 算法在一定程度上提高了聚類集成的聚類效果，在不同數(shù)據(jù)集上的實驗結(jié)果大部分高于對比算法；并且HCLCE 算法相比其他對比算法，具有較小的方差，說明HCLCE 算法的穩(wěn)定性更好。對比魯棒性方法RSEC，HCLCE 算法具有更好的表現(xiàn)。

表3 為不同算法的NMI 結(jié)果對比。從表2～3 可以看出，HCLCE 算法的ACC 和NMI 在所有數(shù)據(jù)集上的均值均好于對比算法。與次優(yōu)的LWEA 相比，ACC 平均提升了7.22%，NMI 平均提升了9.19%。

表3 NMI實驗結(jié)果對比Tab.3 Comparison of NMI experimental result

HCLCE 算法融合多種高階信息，在多數(shù)情況下好于僅使用一種信息的聚類結(jié)果。使用不同高階信息矩陣A作為輸入，進行加權(quán)結(jié)構(gòu)化后得到新的關(guān)聯(lián)矩陣M。表4 為不同的M在融合前的聚類效果和融合后整體的聚類效果。其中Ai的定義已在前面介紹，不同的集合代表著不同的高階信息計算方式，集合從大小到所表示信息具有很大差異性。M1是加權(quán)結(jié)構(gòu)化后的一階信息關(guān)聯(lián)矩陣，以M1為基礎(chǔ)進行聚類，效果比對比方法有一定提升，說明對不同輸入加權(quán)起到了讓質(zhì)量好的輸入權(quán)重大、質(zhì)量差的輸入權(quán)重小的作用，從而提高聚類結(jié)果。并且結(jié)構(gòu)化和秩約束使樣本對關(guān)系表達得更加清楚，簇的結(jié)構(gòu)更加清晰。融合的過程再次對不同階信息分配權(quán)重，使各種信息再次組合。

表4 信息融合前后不同階的ACC對比Tab.4 ACC Comparison at different leves before and after information fusion

每種高階信息從不同的角度表示樣本對相似性，因此有不同的特點。以CSTR 數(shù)據(jù)集為例，不同階信息表示的關(guān)聯(lián)矩陣經(jīng)過加權(quán)結(jié)構(gòu)化后的直觀展示如圖5 所示：顏色越深，樣本相似性越??；顏色越淺，樣本相似性越大。

圖5 不同階數(shù)信息的結(jié)構(gòu)化關(guān)聯(lián)矩陣Fig.5 Structured correlation matrices of different order information

從圖5 可以看出：1）使用原始輸入的聚類結(jié)果得到的結(jié)構(gòu)化相似性矩陣M1中，大量樣本對之間相似性處于0.5～0.6，很難判斷兩個樣本是否屬于同一類。2）對于矩陣叉乘M2，得到的相似性矩陣區(qū)分度不高，大量樣本對同時具有高相似度，這種信息過于冗余，基聚類輸入兩兩之間在簇上的產(chǎn)生交集的概率很大，特別是在基聚類器之間差異性不大的情況下，同樣不具有區(qū)分性。3）矩陣樣本對之間的一致性介于原始輸入和簇級一致性之間，說明基聚類器兩兩之間在樣本對一致性判斷上不能統(tǒng)一，有的簇中樣本對一致性較大，有些簇中樣本對一致性趨于二分，不容易判斷。4）單獨使用所有關(guān)聯(lián)矩陣點積連乘運算獲得的m階信息的聚類效果明顯下降。這是因為m階信息雖然可靠但非常稀疏，只保留了所有輸入達成共識的樣本對，沒有保留一致性較大的樣本對，關(guān)聯(lián)不好的簇作為輸入會影響整體聚類的效果。

HCLCE 算法對融合的每種信息賦予權(quán)重：與目標差異越大的信息獲得的權(quán)重越小，減輕了不好的基聚類器帶來的影響；質(zhì)量高的基聚類器占據(jù)主導(dǎo)地位，提高了最后的聚類結(jié)果。經(jīng)過高階信息融合后得到的關(guān)聯(lián)矩陣簇結(jié)構(gòu)更清晰，去除了很多冗余樣本對信息，更加滿足關(guān)聯(lián)矩陣的性質(zhì)。

4 結(jié)語

本文提出了一種新的數(shù)據(jù)高階信息挖掘方法，利用高階一致性共識的信息，從不同角度刻畫樣本之間的聯(lián)系，驗證了不同層面的共識信息的差異性。HCLCE 算法通過加權(quán)減少信息之間的質(zhì)量差異性帶來的影響，引入對關(guān)聯(lián)矩陣雙隨機約束和秩約束，使得最終融合的關(guān)聯(lián)矩陣更加符合其內(nèi)在特性。通過對多種高階信息的融合，得到了比聚類集成算法和單獨使用一種信息更好的聚類結(jié)果。實驗結(jié)果表明，差異性大的輸入對于聚類結(jié)果的提升具有幫助。其次，通過實驗驗證了每一種信息的特點和有效性，以及融合算法要好于單獨使用某一種信息。此外觀察到m階信息雖代表了可信度最高的一致性樣本對信息，但是在融合過程中沒有起到明顯的提升效果或者是約束樣本對一致性的監(jiān)督作用。在后續(xù)工作中，應(yīng)探索在聚類過程中如何充分利用可靠信息，從可靠信息中發(fā)掘樣本潛在的一致性信息，從而更大程度地減少低質(zhì)量信息對聚類結(jié)果產(chǎn)生的負面影響。