基于群體智慧的簇連接聚類集成算法

張恒山 高宇坤 陳彥萍 王忠民

1(西安郵電大學計算機學院 西安 710121) 2(陜西省網絡數據分析與智能處理重點實驗室(西安郵電大學) 西安 710121)

聚類問題是機器學習領域中一個極具挑戰性的研究問題.聚類分析通過計算數據對象間的相似度把數據集劃分成若干個簇，使在相同簇的對象具有較高的相似度，不同簇的對象則差異較大[1].在聚類的過程中存在著許多問題:1)同種聚類算法的不同參數和初始化會影響聚類的結果;2)大部分聚類算法都很難得出數據集中真實類的數目;3)不同的聚類算法會產生不同的聚類結果.為了解決這些問題，研究者提出了聚類集成算法，通過合并不同的聚類結果得到一個魯棒性好、穩定性高的最終結果[2].聚類集成選擇(clustering ensemble select, CES)使用一致性度量來評估和選擇個體聚類結果[3]，通過對選擇的個體聚類結果進行集成，可以提高最終結果的準確性、穩定性.一般來說，聚類集成選擇包含4個組成部分:生成、評價、選擇和組合.首先，通過使用不同的聚類算法或重復一種算法生成多個聚類結果，這些結果可以在每次運行時隨機產生;其次，一個共識度量(如歸一化互信息)來評估產生的結果;再次，通過閾值選擇評估結果;最后，通過聚集機制得到最終的聚類結果[3-6].

在聚類集成選擇算法中有3大問題：1)生成策略；2)度量評價；3)閾值生成.為了解決聚類集成選擇算法中存在的3個問題，研究者利用了群體智慧理論來引導個體聚類的生成以及最終結果的集成，并基于此提出了一種框架——群體智慧聚類集成(wisdom of crowds ensemble, WOCE)框架[7].在該框架中，通過實現群體智慧的4個必備條件：獨立性、分散性、多樣性、聚集性，可以有效解決聚類集成選擇算法中存在的3個問題.然而該框架存在的問題是沒有充分利用數據點之間的關系，部分具有相似性的數據點之間的相似度計算為零，導致最終得到的聚類結果的準確性不足.

本文提出了一種基于群體智慧框架的簇鏈接聚類集成算法(clustering ensemble algorithm with cluster connection based on wisdom of crowds, CECWOC)，該算法先將原始數據集進行轉化，得到一個滿足群體智慧標準的可使用數據集，然后利用不同聚類算法構造多樣性的聚類成員，并采用連接三元組算法(connected triple algorithm, CTA)得到數據點之間的相似度矩陣.最后，對相似度矩陣使用層次聚類算法得到聚類結果.該算法充分挖掘了盡管計算得到的相似度為0但實際存在某些相似性的數據點之間的關系，提高了最終聚類結果的準確性.

1 相關算法與概念

1.1 群體智慧

群體智慧是由Russell(1983),Atlee(1993),Mayer-Kress (2003)等人與其他理論家共同描述.群體智慧對多個參與者獨立給出的評價意見進行聚合，可以得到準確性好于其中任何一個參與者的評價意見.Surowiecki[8]于2006年提出將群體智慧作為做出優化決策的一種框架，他對智慧群體提出了4個標準：1)獨立性.人們的觀點不會被周圍人的觀點所影響.2)分散性.人們能夠專注和利用自己的知識.3)多樣性.每個人都有各自的私人信息，即使對已知事實的認知偏差較大.4)聚集性.將私人的判斷轉化為集體決定的機制.

1.2 聚類集成

2003年Strehl等人提出“聚類集成”(cluster ensembles, CE)的概念，并給出了定義.聚類集成是指將一個對象集合的多個劃分組合成為一個統一聚類結果的算法[2].在文獻[9]中作者也給出該問題的一種描述：給定一個聚類結果的集合，聚類集成CE的目標就是要尋找一個聚類，相對于所有的輸入聚類結果來說，盡可能多地符合(或一致)[9].由此可見，聚類集成CE是利用多個聚類結果找到一個新的數據劃分，這個劃分在最大程度上共享了所有輸入的聚類結果對數據集的聚類信息.聚類集成過程為:假設數據集X有n個數據對象X={x1,x2,…,xn}，首先對數據集X使用N次聚類算法，得到N個聚類結果P={p1,p2,…,pN}，其中pi(i=1,2,…,N)為第i個聚類算法得到的聚類結果.然后一致性函數T對P中的聚類結果進行集成得到一個新的數據劃分P′，將此作為最終的聚類結果.

1.3 基于連接的相似度矩陣

相似度矩陣簡單易生成，但是它存在一個缺點，那就是只得到部分數據點之間的關系，對于具有弱相似度的數據點只能顯示為0.為了解決這一問題，得到更多數據點間的關系，文獻[10]提出了一種基于連接的相似度矩陣構造算法：連接三元組Δ=(VΔ,WΔ)是G的一個子圖，包含3個頂點VΔ=(A1,A2,A3)?V和2條邊WΔ=(eA1,A2,eA1,A3)?W，連接其他2個頂點的頂點稱為這個三元組的中心.其基本思想是：如果2個節點都與第3個節點有連接，則認為這2個節點之間存在相似性.

2 基于群體智慧框架的簇連接聚類集成算法

本文提出的基于群體智慧框架的簇連接聚類集成算法CECWOC，有效地擴充了相似度矩陣中數據點間的潛在信息，對其中相似度為0但實際還存在某些關聯關系的數據點進行了處理，使相似度矩陣包含更多的有效信息，提高了最終結果的準確率.

2.1 數據預處理

文獻[7,11]中分別使用群體智慧理論中的人群、信息、觀點來代替聚類問題中的算法、數據和結果.基于群體智慧框架的定義，人們必須采用獨立的信息來做決定.本質上就是通過刪除原始數據特征之間的相關性來生成新的數據特征，這些數據特征之間是相互獨立的.在使用聚類算法之前，有各種算法去除數據的相關性，如主成分分析或線性判別分析法等，刪除特征間相關性能夠顯著提高聚類結果的性能[12].在群體智慧框架中，分散性標準可以增加群體的智慧，減少最終結果的誤差，提高結果的準確率.本文在數據預處理階段通過整合多種算法，可以實現數據之間的獨立性和分散性.

首先，本文通過基于主成分分析的算法將數據映射到不同的維度，以使其特征之間的相關性較小.

給定一個數據集X={x1,x2,…,xn}，對數據集X求平均值：

(1)

其中,n表示數據集X中數據的個數，xi表示數據集X中第i個數據.此時，就可以求出

(2)

定義1.Q,X′∈Rm×n，Y∈Rm×n，其中m，n分別表示特征的個數和數據點的數目.這個映射的目標是極小化特征間的關聯性，根據主成分分析法，這個問題可以轉換為

Y=QTX′.

(3)

對于R，計算為

(4)

其次，本文利用本地知識構造散布矩陣，通過數據轉換實現數據的分散性，從而增加最終聚類結果的準確性、穩定性.在構造散布矩陣時用到的基本概念描述如下：

成對約束. Must-link規定2個點必須屬于同一類，即M={(xi,xj)}；Cannot-link規定2個點不能在同一類中，即C={(xi,xj)}.以成對約束為基礎，本文運用約束投影，即一組約束向量W={w1,w2,…,wd}，在數據轉換時，把M和C保存到被轉化的低維度表示zi=WTyi中.定義函數J(W)為

J(W)=trace(WT(SC-γSM)W),

(5)

其中,SC和SM分別定義為

(6)

(7)

其中,nC和nM分別代表C和M的基數，γ是比例系數.γ計算為

(8)

Z=WTY.

(9)

綜上所述，本文中采用的數據預處理算法流程為：

算法1. 數據預處理.

輸入：數據集X={x1,x2,…,xn}、特征數d、Must-link集M、Cannot-link集C;

輸出：待使用數據集Z.

② 使用式(2)計算X′；

④ 計算R的特征值∧和特征向量Q，并基于特征值對特征向量做降序排序；

⑤Y=QTX′；

⑥ 若M和C為空集時，Z=Y；否則使用式(6)～(8)計算SC，SM，γ；

⑧ 通過ζ≥0，得到W；

⑨Z=WTY.

2.2 基聚類結果的生成

事實上，多樣性是群體智慧理論和聚類集成選擇算法中共有的概念.多樣性增加了最終結果的準確性和穩定性.生成多樣的基聚類結果的方法有很多，如給同一種聚類算法取不同的參數；使用多種不同的聚類算法；選取數據集的不同子集進行聚類等.本文利用多種聚類算法生成基聚類結果，將生成的結果表示為一個參考集：E={P1,P2,…,Pi-1,Pi,Pi+1,…,PT}，其中T代表個體聚類結果的數目，Pi表示生成結果中的第i個分區(第i個基聚類結果).

本文運用均勻性[13]來表示分區P與參考集中所有分區的多樣性：

(10)

其中,E是參考集，P是參考集中的分區，

對于生成的基聚類結果，本文對其進行了分組處理，分組的原理是分別計算每個聚類結果與其他聚類結果的相似度Ci j：

其中,Pi,Pj∈E.

根據相似度生成相似度矩陣C：

然后使用K-means算法把基聚類結果分為若干組：

G={G1,G2,…,Gi},

(11)

其中,i代表分組的數目.根據文獻[14]關于群體智慧中群體分組的基本結論，一般將群體隨機分為4～5組，分組的差異對最終結果影響甚微.因而在實際應用中，建議利用K-means算法隨機將基聚類結果分為5組進行分組聚合.

2.3 基于連接三元組的聚類集成算法

聚類集成的核心問題之一是如何根據這些由聚類成員得到的聚類結果構造數據點之間的相似度矩陣.本文選用能得到數據點之間更多相似性信息的連接三元組算法[10]和群體智慧框架[13]來構造數據點之間的相似度矩陣.

在聚類問題上基于連接三元組的相似度矩陣的應用如圖1所示，黑心圓代表數據點，虛線圓代表不同的分區，空的正方形代表分區中的簇，帶影印的正方形表示通過連接三元組具有相似性的簇.

Fig. 1 Connection triplet clustering diagram圖1 連接三元組示意圖

連接簇Ci和簇Cj的邊的權重Wi j由這2個簇共同包含的數據點個數得到:

(12)

其中,xi和xj分別為屬于簇Ci和簇Cj的數據點的集合.鄰接點為簇Ck的2個簇Ci，Cj之間連接三元組的值為

(13)

簇Ci，Cj之間所有的三元組(1,2,…,q)可以計算為

(14)

簇Ci，Cj之間的相似度可以計算為

(15)

其中,WCTmax是任何2個簇WCT中最大的值，而DC是一個衰減因子.此時數據點xi，xj之間的相似度為

(16)

WCTE矩陣的計算為

(17)

其中,M為個體聚類結果的個數,Ni j表示樣本i和樣本j在M種劃分中屬于同一個簇時值為1，ρi j為權重，本文將2種聚類算法的平均均勻性[13]當作權重系數：

(18)

當2種聚類算法均具有較高的均勻性時就生成了有效的結果，同時當2種聚類算法在均勻性度量中值較小時，對生成結果的影響接近于0.因此，本文使用這種忽略低質量個體結果影響的機制代替通過生成閾值進行選擇.相對于傳統的互關聯矩陣來說，本文中相似度矩陣的計算考慮了當2個數據點不屬于同一個簇時，它們之間的相似度，擴充了數據點之間的潛在信息，有利于結構復雜的數據聚類.

綜上所述，CECWOC算法流程如下：

算法2. CECWOC算法.

輸入：數據集Z;

輸出：最終聚類結果T.

① 用不同的聚類算法對數據集Z進行聚類，聚類的結果放入一個參考集E中；

② 對參考集E進行分組，得到G；

③ 對G中的每組成員通過使用式(12)～(17)得到各自的WCTE矩陣；

④ 對G中分組成員的S矩陣使用Average-Linkage算法進行聚類，得到結果P;

⑤ 使用協相關矩陣對P進行整合，得到矩陣C；

⑥ 對矩陣C使用Average-Linkage算法進行最終聚類，得到結果T.

算法的流程如圖2所示.在本算法中，層次聚類的收斂時機一般設為達到某一聚類簇數量.在具體應用中，應根據應用場景盡可能客觀地確定聚類簇的數量.在本文的實驗中，因為試驗使用的數據集為標準數據集，已經包含對簇數量的說明.

Fig. 2 CECWOC algorithm flow chart圖2 CECWOC算法流程圖

3 實 驗

在本文中，我們利用標準數據集和它們的真實類比較了該算法與其他個體聚類算法和聚類集成選擇算法的性能.當然，監督信息將根據真實的類標簽生成.所有的算法將在MATLAB R2016a中實現.首先對算法進行10次獨立運算，然后將得到的聚類結果取平均值，作為該算法的最終結果.表1是實驗中用來產生基聚類的個體聚類算法，實驗中選用的數據集為UCI(university of california-irvine)數據庫中的真實數據集.

3.1 UCI數據集上無監督信息的聚類實驗

表2給出了實驗中選用的UCI數據庫中的真實數據集.在這8個數據集上，分別采用無監督信息的聚類集成算法：EAC[15],WPCK[16],GKPC[17],HCSS[18],GP-MGLA[19],WOCE[13]和本文提出的CECWOC算法進行聚類集成.其中，EAC算法作為對比的基礎算法，WPCK,GKPC,HCSS和GP-MGLA算法為4種效果良好的加權聚類集成算法，WOCE算法為一種使用群體智慧框架的聚類集成算法.通過計算準確率[12](最終聚類結果的標簽與數據集真實標簽的正確率)來評價聚類集成算法的性能.

Table 1 Individual Clustering Algorithm Used inthe Experiments

實驗得到的結果如圖3所示.由于在EAC算法中，并沒有使用群體智慧理論的4個標準，所以這是一個未利用群體智慧框架的例子，WPCK,GKPC,HCSS和GP-MGLA為4種加權聚類集成算法，WoCE算法使用了群體智慧框架且自身算法中包含加權算法的設計與使用，本文提出的CECWOC算法是在WoCE算法上的改進，添加了分組與連接的思想.不難看出在這8個數據集中，除了Iris數據集外，在其余數據集中本文提出的CECWOC算法都能得到最佳的聚類結果.對Iris數據集，CECWOC算法與最佳結果相差不到2%.在實驗結果圖中的Sonar數據集上，WoCE算法沒有跑贏HCSS算法，但是改進后的CECWOC算法展現出很好的性能.顯然將群體智慧理論應用到聚類集成中能產生更高的性能，在群體智慧框架下添加連接三元組算法進行聚類集成得到的聚類結果要優于直接使用群體智慧框架得到的聚類結果.

Table 2 UCI Data Sets Used in the Experiments WithoutSupervising Information

Fig. 3 Accuracy of clustering integration results for each data set圖3 各數據集聚類集成結果的準確率

3.2 添加監督信息的聚類實驗

由于大多數半監督聚類集成算法使用基于監督信息的特征選擇，本文在高維度和大規模的數據集上比較半監督聚類集成算法的性能，選擇表3中的數據集進行實驗.

本文中隨機選擇1%～5%樣本的類標簽生成監督信息(一半為must-link，另一半為cannot-link)；例如1%的樣本有500個，我們就選擇250個作為must-link，250個作為cannot-link.通過計算準確率[12](最終聚類結果的標簽與數據集真實標簽的正確率)來評價聚類集成算法的性能.

Table 3 Data Set Used in the Experiments withSupervising Information

Fig. 4 Relationship between pairwise constraints and algorithms in CNAE-9圖4 CNAE-9中成對約束與各算法的關系

實驗結果如圖4～6所示.圖4～6分別表示在CNAE-9,Letters和Sonar數據集上使用本文提出的CECWOC算法與RP[20],BGCM[21],SKMS[22],NBF[23]和WoCE[13]算法進行比較的結果.其中，RP算法是一種經典的半監督聚類集成算法；BGCM算法是一種新的基于圖的半監督聚類集成算法，但是它有2種版本，一種是無監督的，另一種是半監督的，這里我們使用的是半監督的算法；SKMS算法是一種基于核的半監督聚類集成算法；NBF和WoCE算法都屬于啟發式的半監督聚類集成算法.與不同種類的半監督聚類集成算法的比較結果顯示CECWOC算法具有更好的性能.

Fig. 5 Relationship between pairwise constraints and algorithms in Letters圖5 Letters中成對約束與各算法的關系

Fig. 6 Relationship between pairwise constraints and algorithms in Sonar圖6 Sonar中成對約束與各算法的關系

如圖5所示，在Letters數據集的實驗中，不難看出除了WoCE算法和本文提出的CECWOC算法外，其余算法在成對約束增加的條件下性能很不穩定，有時會下降；事實上，成對約束往往是導致高度不穩定聚類性能的原因，以前的一些算法不能處理額外的監督信息，監督信息使個體聚類結果不穩定，顯著降低了上述算法的性能.在這些情況下，本文提出采用群體智慧理論處理監督信息的算法，擁有更好的數據表示(獨立性和分散性)、強大的個體聚類評價(均勻性度量)、有效集聚機制，得到了更加穩定的性能和更好的結果.在圖4～6中，很容易觀察到，WoCE算法和本文所提出的CECWOC算法在性能上是很穩定的，在群體智慧框架的基礎上分組并加入連接三元組算法能有效提高準確率.

4 總 結

本文將群體智慧理論應用于聚類集成，并在此基礎上提出連接三元組算法，顯著提高聚類集成結果的準確性.本文提出的算法具有的優點是：1)引入獨立性和分散性的概念，用于提高基聚類結果的準確率.2)提出了一個新的框架，在滿足4個標準的條件下，采用了一系列生成基聚類結果和獲得最終結果的新機制.3)在映射函數中使用期望值和協方差的概念最小化特征之間的相關性來滿足獨立性，提出了基于成對約束的高維到低維數據的分散準則.此外，文中用一種稱為均勻性的新度量來評估基聚類結果的多樣性.4)提出了基聚類結果的聚集算法，通過連接三元組的方式增加關聯矩陣中樣本間的潛在信息，使最終結果更加準確.在未來的研究工作中，我們將結合工業大數據中數據需要聚類分析的實際應用，不斷改進提出的算法，尤其需要研究本文提出的算法的并行執行效率，爭取將其運用到實際的工業數據分析中去.