基于先驗信息和譜分析的聚類融合算法

摘 要:在聚類過程中利用先驗信息能顯著提高聚類算法的性能，但已存在的聚類融合算法很少考慮到數據集的先驗信息。基于先驗信息和譜分析，提出一種聚類融合算法，將成對限制信息引入到譜聚類算法中，用受限的譜聚類算法產生聚類成員，再采用基于互聯合矩陣的集成方法生成最后的聚類結果。實驗結果表明，利用先驗信息能有效提高聚類的效果。

關鍵詞:聚類融合; 先驗信息; 成對限制; 譜聚類

中圖分類號:TP181; TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2103-03

doi:10.3969/j.issn.1001-3695.2010.06.031

Clustering ensemble algorithm based on prior knowledge and spectral analysis

HOU Juan1， FEI Yaoping1， HU Xiaoxia2， LI Juerun2

(1.College of Information Science Engineering， Central South University， Changsha 410075， China; 2.Jiangsu LSYW System Integration Co.Ltd.， Wuxi Jiangsu 214001， China)

Abstract:The prior knowledge can improve clustering performance， but few of clustering ensemble algorithms consider the prior knowledge of the datasets. This paper proposed a clustering ensemble algorithm based on prior knowledge and spectral analysis. It incorporated the pairwise constraints into the spectral clustering algorithm to generate clustering members. And obtained the final result by using the combining method of coassociation matrix. The experimental results demonstrate that the proposed method can efficiently improve the clustering performance.

Key words:clustering ensemble; prior knowledge; pairwise constraints; spectral clustering

聚類分析是數據分析的有效工具，在數值分析、數據挖掘和模式識別領域有著非常廣泛的應用。目前的文獻已提出了許多聚類算法，但還沒有一個單一的算法能夠識別出任意形態的數據結構分布。因此Strehl等人[1]于2002年提出聚類融合的概念，將不同算法或者同一算法下使用不同參數得到的結果進行合并，從而得到比單一算法更為優越的結果。該方法能夠很好地提高聚類算法的穩定性，并且能夠實行并行計算。

在以前的研究中，大多數聚類融合算法都是把重點放在聚類成員的差異性和如何令聚類融合應用在各種不同的數據集上，而很少有聚類融合算法考慮數據集的先驗信息。大量研究表明，在聚類搜索過程中充分利用先驗信息會顯著提高聚類算法的性能。利用先驗信息所提出的算法被稱為半監督聚類。根據使用先驗信息方法的不同，半監督算法被分成兩大類:a)基于限制的方法[2]，該類方法修改聚類算法本身;b)基于測度的方法[3]。建立在譜圖理論上的譜聚類算法[4]，在數據相似性矩陣的基礎上求解拉普拉斯矩陣，是一種點對聚類算法，這使得在聚類過程中利用成對限制[5]這一先驗信息變得非常容易。Kamvar等人[6]通過直接修改相似性矩陣的方法將成對限制信息引入譜聚類算法中，提出了受限的半監督譜聚類算法;XU Qianjun等人[7]認為，當數據集合中包含奇異點時，相似性矩陣中的對角元素容易造成單元素聚類，為克服這一缺陷提出了CSC算法。

本文結合受限的半監督譜聚類算法和聚類融合的概念，提出了一種基于先驗信息和譜分析的聚類融合算法。該算法將成對限制信息引入到譜聚類算法中，產生多個聚類成員，再采用基于互聯合矩陣的集成方法合并多個聚類成員，得到最后的聚類結果。實驗表明，該算法有效地提高了聚類結果的準確度。

1 基于先驗信息和譜分析的聚類融合算法

在聚類融合算法中，先要產生對數據集X的B個聚類成員，然后對這B個聚類成員的結果進行合并。本文提出的聚類融合算法首先隨機抽樣生成B個數據子集(D={D1，D2，…，DB}，B是子集個數)，將先驗信息引入到譜聚類中;分別在B個數據子集運行該算法，得到B個聚類成員(I={I1，I2，…，IB});最后用一致性函數對聚類成員進行融合，如圖1所示。

根據聚類融合算法的思想，需要解決兩個問題:a)如何得到B個相互具有差異性的聚類成員;b)如何合并B個聚類成員。

1.1 聚類成員的產生

本文用于產生聚類成員的是譜聚類算法CSC。首先使用隨機抽樣的方法產生數據子集，基于這一點來產生B個具有差異性的聚類成員。

譜聚類算法相對于其他聚類算法具有明顯的優勢，能識別非凸分布的聚類，非常適合于許多實際問題，而且執行起來比較容易。它是一種基于兩點間相似關系的算法，先根據給定的數據集定義一個描述成對數據點相似度的相似矩陣，再計算矩陣的特征值和特征向量，然后選擇合適的特征向量聚類不同的數據點。可用以下三個步驟來表示:a)構造描述成對數據點的矩陣;b)通過計算矩陣的前k個特征值與特征向量構建特征向量空間;c)利用Kmeans算法對特征向量進行聚類。

在具體實現過程中，不同的算法在數據集矩陣的表示上存在著不同。受限的譜聚類算法CSC通過直接修改矩陣的方法將成對限制信息引入譜聚類算法中。成對限制有兩種，即mustlink和cannotlink。其中，mustlink限制規定兩個數據必須在同一個聚類中;cannotlink限制規定兩個數據不能在同一聚類中。

1.2 一致性函數

采用基于互聯合矩陣的集成方法，計算兩個數據點被聚類成員分在同一個簇中的次數占聚類成員數的比例，如式(1)所示，以此作為數據點對間的相似性度量。

構造coassociation 矩陣S:

Sij=nijB=∑Bb=1Cb(i，j)B(1)

其中:nij是數據對(xi，xj)在B個聚類成員中被分到相同簇的次數。如果它們在第b個聚類成員中被分到相同簇中，則Cb(i，j)=1，否則為0。矩陣S導出了數據對間的相似性。

在構造的相似度矩陣S上應用多路譜聚類NJW[4]算法來完成數據的聚類。

1.3 算法描述

該聚類融合算法的詳細描述如下:

a)隨機抽樣產生一組數據子集D={D1，D2，…，DB}。

b)(a)設數據子集Db(b∈[1，B])有n個數據。xi，xj∈Db，構造相似矩陣F:

fij=exp-δij2/2σ2(2)

其中:i，j∈[1，n]，δij是兩點間的歐氏距離;σ為事先指定的參數。通常設置對角線元素fii=0。

(b)添加成對限制信息:

fij=fji=1 if(xi，xj)∈mustlink

0 if(xi，xj)∈cannotlink(3)

(c)定義一個對角矩陣R，對角線上的元素rii=∑nj=1fij，i∈[1，n]。

(d)定義一個矩陣P=R-1F;

(e)求P的k個最大特征值所對應的特征向量構建特征向量空間，得到一個n×k矩陣Z。

(f)將Z的每一行看做是一個新數據，使用Kmeans算法將其聚為K類。如果Z的第i行屬于第k類，則相應的數據點xi也屬于第k類。

c)在數據子集上重復運行CSC算法B次，得到聚類成員I={I1，I2，…，IB}，每個聚類成員Ib把數據集Db劃分成K個類，其中Ib={C1b，C2b，…，CKb}，b∈[1，B]，∪iCib=Db。

d)構造coassociation 矩陣S。

e)在N×N矩陣S上應用多路譜聚類NJW算法。

(a)設置S中的元素sii=0。

(b)定義對角線矩陣D，dii=∑Nj=1sij;并構造規范化相似性矩陣L=D-1/2SD-1/2。

(c)求L的k個最大特征值所對應的特征向量構建特征向量空間，得到一個N×k矩陣U。

(d)將U的行向量規范化后得到一個新的矩陣Y，yij=uij/∑ju2ij1/2。

(e)重復b)。

(f)得到最后的聚類結果。

2 實驗結果

本文在UCI Machine Learning Repository提供的機器學習數據集上進行了測試，并與文獻[1]中的經典聚類融合算法進行了對比，實驗結果表明，本文提出的聚類融合算法在精度方面有很好的效果。實驗所用環境是Celeron M 440 CPU 1.86 GHz，512 MB內存，Windows XP操作系統，開發工具為VC++6.0。

2.1 實驗數據集與評價準則

表1給出了實驗數據集的數據特征(K為聚類個數，n為數據個數，d為維數)。

表1中，Wine數據集來源于意大利藥物和食品分析研究中心，包含了178條記錄、13個屬性，其結構分為了三個類(第一個類有59個，第二個類有71個，第三個類有48個)。Iris數據集是測試標準庫中非常著名的一個數據集，該數據集共四個屬性，包含三個類，每個類有50個實例，類的結構比較均勻。第一個類明顯地區分于其他兩個類，而另兩個類部分重疊。Sonar數據集包含了208條記錄，其結構分為了兩個類。

Rand指標是常用的聚類性能的評價指標，是對聚類結果中每一成對點是否來自同一類進行判斷。這里將聚類劃分看做是樣本之間的一種關系，即每一對樣本要么被劃分在同一類，要么在不同類。對于一個具有n個樣本的數據集，存在n(n-1)/2個樣本對，也就是說，對于一個聚類劃分存在n(n-1)/2個成對決策。Wagstaff根據算法所獲得的正確決策數來評價聚類算法的性能，即使用所謂的rand指標，如式(4)所示:

RI=#CDn(n-1)/2(4)

其中:#CD表示由算法獲得的正確決策對數。為了將rand指標用于對半監督聚類算法的評價， Klein 等人對rand指標進行修正得到CRI指標，如式(5)所示:

CRI=#CD-#Cnn(n-1)/2-#Cn(5)

其中:#Cn表示成對限制的數目。CRI指標是對數據點是否來自同一類進行判斷，指的是通過判斷不同類之間的數據對是否被劃分在不同類中，同一類的數據對是否仍被劃分在同一類中對聚類結果進行評價。本文實驗中提到的聚類準確度即指CRI值。

2.2 實驗結果分析

1)成對限制數目對算法的影響

實驗中將成對限制的數目從0變化到100，B=50。對于每一個給定的限制數目進行20次實驗，取平均結果。從圖2~4可以看出，隨著成對限制數目的增加，本文算法的準確度也隨之增加。在Iris數據集上，準確度從0.887增加到0.932;在Wine數據集上，準確度從0.751增加到0.861;但是在Sonar數據集上，本文算法的準確度增加得很少，平均只有0.011。原因可能有兩個:譜聚類算法不適合Sonar數據集;成對限制這一先驗信息對聚類造成了誤導。

2)與經典聚類融合算法比較

以前的經典聚類融合算法很少考慮數據集的先驗信息，在實驗中選取了CK算法(互聯合矩陣的集成方法與Kmeans算法的結合)、HGPA、CSPA。本文算法中成對限制的數目定為100，B=50，取20次實驗結果的平均值。將四種算法在Iris和Wine數據集上進行了對比實驗。從表2可以看出在兩個數據集上，本文算法的性能明顯優于傳統聚類融合算法。實驗證明，在聚類搜索過程中利用先驗信息會顯著提高聚類算法的性能。

表2 算法比較

datasetCKHGPACSPA本文算法

Iris0.7910.8630.8890.9305

Wine0.6690.7080.7550.8531

3 結束語

本文在半監督聚類融合算法的思想基礎上，把引入成對限制的譜聚類與聚類融合結合起來，得到一種基于先驗信息和譜分析的聚類融合算法。實驗結果表明，先驗信息對聚類融合算法是有利的，在大多數數據集上能夠獲得一個較好的聚類結果。但是有些數據集并沒有很好地利用成對限制信息，準確度沒有明顯提高。在今后的工作中，將繼續研究如何將更豐富的先驗信息有效應用到聚類融合算法中，進一步提高聚類結果的準確度。

參考文獻:

[1]STREHL A， GHOSH J. Cluster ensembles: a knowledge reuse framework for combining multiple partitions[J]. Journal ofMachine Learning Research， 2003， 3(3):583-617.

[2]WAGSTAFF K， CARDIE C， ROGERS S， et al. Constrained Kmeans clustering with background knowledge[C]//Proc of the 18th International Conference on Machine Learning. San Franscisco: Morgan Kaufmann Publishers， 2001: 577-584.

[3]KLEIN D， KAMVAR S D， MANNING C D. From instancelevel constraints to spacelevel constraints:making the most of prior knowledge in data clustering[C]//Proc of the 19th International Conference on Machine Learning. San Franscisco: Morgan Kaufmann Publishers， 2002: 307-314.

[4]NG A Y， JORDAN M I， WEISS Y. On spectral clustering: analysis and an algorithm[M]//Advances in Neural Information Processing Systems. Cambridage: MIT Press， 2002: 849-856.

[5]WAGSTAFF K， CARDIE C. Clustering with instancelevel constraints[C]//Proc of the17th International Conference on Machine Learning. San Franscisco: Morgan Kaufmann Publishers， 2000: 1103-1110.

[6]KAMVAR S D， KLEIN D， MANNING C D. Spectral learning[C]//Proc of the 18th International Joint Conference on Artificial Intelligence. San Franscisco: Morgan Kaufmann Publishers， 2003: 561-566.

[7]XU Qianjun， DESJARDINS M， WAGSTAFF K. Constrained spectral clustering under a local proximity structure assumption[C]// Proc ofthe 18th International Conference on the Florida Artificial Intelligence ResearchSociety. [S.l.]: AAAI Press， 2005:866-867.