基于多鏈接特征子集的聚類集成算法

陳彥萍，高宇坤，張恒山，夏 虹

1(西安郵電大學 計算機學院，西安 710121) 2(陜西省網絡數據分析與智能處理重點實驗室(西安郵電大學)，西安 710121)E-mail：821566504@qq.com

1 引 言

聚類作為重要的機器學習方法，對于復雜度高的數據集，單一的聚類算法很難正確地辨別出它的類簇結構，為了獲得穩定且準確的聚類結果，人們提出了聚類集成算法.在很多方面聚類集成的性能都能夠超越單個聚類算法的性能，如魯棒性、穩定性和一致性估計.近年來，聚類集成已經成為機器學習領域中的熱點研究問題之一，最初它是由Strehl和Ghosh[1]正式提出.Topchy等人[2]指出通過聚類集成算法得到的聚類結果要比單一聚類算法得到的結果好；而且聚類集成的結果受噪聲和孤立點的影響，它們越少，結果的魯棒性和穩定性越好.Fred和Jain[3]提出了一種證據累積的聚類集成算法(簡稱EAC)，首先計算所有基聚類結果的共聯矩陣，然后使用最小生成樹的分級聚類算法求得最終結果.周志華等人[4]將聚類集成與投票問題放在一起考慮，設計了一種投票機制，通過投票結果計算出聚類集成的結果.Naldi 和Carvalho等人[5]提出了一種基于相對有效指標的聚類集成選擇算法，通過利用不同的有效指標進行聚類集成.Rafiee和Dlay等人[6]提出一種基于聚類集成的兩階段無監督分割算法，該算法能夠從圖像中提取自己指定的區域.楊林云等人[7]提出了一種基于模糊相似度量的軟聚類集成算法，在軟聚類集成算法中添加了三種模糊度量標準，提高了聚類集成結果的性能.王海深等人[8]提出了一種軟投票聚類集成算法，首先將聚類結果進行重標簽處理，使其標簽對齊，接下來一對一相乘，最后設計一致性函數，做歸一化處理.Lam-on和Boongoen等人[9]提出了一種基于鏈接的聚類集成算法，該算法解決了共聯矩陣中信息使用不充分的問題，在生成共聯矩陣時不僅考慮點與點之間的關系，還考慮了簇與簇之間的關系.Yousefnezhad等人[10]提出了一種利用群體智慧理論進行聚類集成的算法，該算法將群體智慧框架應用到聚類集成的問題中，獲得了較好的聚類結果.江志良等人在文獻[11]中提出了一種基于特征關系的加權投票聚類集成算法，該算法使用子數據集作為聚類成員的輸入并使用加權投票的聚類集成算法，提高聚類的準確性和穩定性.在之前的聚類集成算法中，原始數據集中會存在冗余特征屬性，而且相似度矩陣只能得到部分數據點之間的關系，對于具有弱相似度的數據點只能顯示為0.為解決這些問題，本文提出了一種基于多鏈接特征子集的聚類集成算法(Clustering ensemble algorithm based on multi-link feature subset，CEBMLF)，該算法在基聚類結果的生成階段使用獨立特征選擇法，消除了冗余特征，降低了原始數據集的維數，提高聚類集成結果的準確率；然后通過將數據點與簇的相關性集成信息矩陣轉化為反映數據點之間的相關性關系矩陣，解決了相似度矩陣只能得到數據點之間的部分關系，對于具有弱相似度的數據點只能顯示為0的缺點；融合基聚類結果的關系矩陣，使用Average-Linkage算法進行聚類，得到最終結果.該算法能使最終聚類的準確率得到提升.

2 相關概念

2.1 特征選取

特征選擇是為了減少數據集的維數，消除重復無用的特征屬性，所以本質上也可以稱之為特征子集選擇或屬性選擇.它是指從所有的特征中選擇部分特征來優化系統的具體指標.從原始數據集的所有特征中選擇出最有效的特征來代表原始數據集，以此達到減小數據集維數和消除重復無用的特征屬性的目的，是提高學習算法性能的重要手段，同時它也是模式識別中數據預處理的關鍵步驟.

2.2 聚類集成

3 一種基于多鏈接特征子集的聚類集成算法

3.1 特征子集的選取算法

假設數據集X有M條數據{x1,x2,…,xM}和N個特征{d1,d2，…，dN}.將X表示為{D1，D2，…，DN}，其中Di為列向量(M維)，表示M條數據在第i個特征上的值.

在對數據集X進行聚類時，如果其中特征間的相關性很大，那么這次聚類使用的信息就會包含很多的重復信息，真實有用的信息就會很少.特征間的相關性指的是特征之間的獨立程度或依賴程度.本文使用相關系數來計算特征之間的相關性.數據子集的選取要使得特征之間相互獨立，所以要避免選取相關的特征，最好選取相互獨立的特征.本文提出一種獨立特征子集選取的算法，它以數據集的特征為基礎，選出與其相關性最小的個特征，構成相對獨立的數據特征子集.

算法1.獨立特征子集選取算法

輸入：數據集X={D1,D2，…，DN}.

輸出：數據子集X*={D1,D2，…，Dk}.

5.計算矩陣Xr中列向量的平均值Xc_mean；

6.選取Xc_mean中k個最接近0的值；

該算法考慮了所有特征的相關性，比隨機抽取獲得的結果要好，對于選擇的特征個數k，本文在實驗中通過聚類集成結果的RI值確定了的k的取值范圍.

3.2 基聚類的生成策略

基聚類的生成有很多方法，如：用不同的聚類算法(k-means、層次聚集算法、譜聚類算法等)來生成基聚類結果；通過改變聚類算法的初始值、參數等設置，生成基聚類結果；通過不同的抽樣方式得到數據子集，對數據子集進行聚類，生成基聚類結果；用不同的選擇方法選取數據集的特征，生成特征子集，然后對特征子集進行聚類，得到基聚類結果.

本文首先從原始數據集中選取特征子集，然后使用多種不同的聚類算法得到基聚類結果.這樣做能提高基聚類結果的獨立性和多樣性.

3.3 基于多鏈接的聚類集成算法

聚類的核心問題之一是如何構造數據點之間的相似度矩陣.本文借鑒連接三元組算法[9]的思想來構造數據點之間的相似度矩陣.

圖1 多鏈接聚類示意圖Fig.1 Multi-link clustering diagram

連接簇Ci和簇Cj的邊的權重Wij由這兩個簇共同包含的數據點個數得到，如下式：

(1)

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

(2)

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

(3)

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

(4)

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

(5)

其中C(xi)=C(xj)代表xi和xj在同一個簇中，C(xi)≠C(xj)表示xi和xj不在同一個簇中，此時的值為xi和xj分別所在簇的相似度.

融合基聚類后數據點xi，xj之的相似度矩陣為：

(6)

其中M為基聚類結果的個數，Nij表示樣本i和樣本j在M種劃分中屬于同一個簇時值為1，C(xi)=C(xj)代表xi和xj在同一個簇中，C(xi)≠C(xj)表示xi和xj不在同一個簇中.

算法2.基于多鏈接特征子集的聚類集成算法

輸入：數據集X={x1，x2，…，xn}.

輸出：最終結果T.

1.先使用算法1，得到獨立的子集X*；

2.對X*使用不同的聚類算法得到不同的基聚類結果；

3.對每個基聚類結果使用公式(1)-公式(5)得到各自的相似度矩陣；

4.使用公式(6)融合所有基聚類結果的相似度矩陣；

5.對融合后的相似度矩陣使用Average-Linkage算法進行最終聚類，得到結果T.

4 實 驗

在文中，我們利用標準數據集和它們的真實類比較了該算法與其他聚類集成算法的性能.所有的算法將在MATLAB R2016a中實現.表1是實驗中用來產生基聚類結果的基聚類算法.

表1 實驗所用的個體聚類算法Table 1 Individual clustering algorithm used in the experiment

4.1 實驗數據及評價標準

本文從UCI[14]數據庫中選取了9個數據集進行實驗，見表2.

表2 實驗所用UCI數據集Table 2 UCI data set used in the experiment

實驗采用外部評價標準RI(rand index)[15]對聚類結果進行評價.RI有如下定義：

(7)

其中Y表示真實標簽；T表示結果集；n11表示數據在T中和在Y中都在同一個簇中的數目；n00表示數據在中和在T中不在Y同一個簇中的數目；n10表示數據在T中在同一個簇中在Y中不在同一個簇中的數目；n01表示數據在T中不在同一個簇中在Y中在同一個簇中的數目.文獻[15]中提出聚類的RI值越高，聚類的準確率越高.

4.2 實驗設計及結果分析

設置基聚類成員個數，分別運行表1中的10種基聚類算法.為了降低結果的偶然性，最終的取值為集成算法運行10次的平均值.

為了證明獨立特征選擇法的優越性，本文引入隨機抽樣法與其進行對比，在表2的數據集中分別進行實驗，使用本文提出的CEBMLF聚類集成算法，評價標準使用RI標準.得到的實驗結果如圖2所示.

由圖2分析可知，和隨機抽樣法相比，獨立特征選擇法的RI值在8個數據集上都比前者要高.所以可以得出相對隨機抽樣而言，獨立特征選擇法用于聚類集成時的效果也比前者好.

使用獨立特征選擇法時，第一步要計算數據集中各個特征的相關性，然后按照數值的大小對特征進行排序，之后從中選取k個特征，這里k的取值經過后續實驗得出為總特征的70%-80%為最佳，無論數據集特征的多少，我們是按照百分比抽取相關性最小的特征，這與數據集特征的多少是無關的，在圖2的實驗中也有驗證.其中Sonar與CNAE-9為高維數據集(特征多)，其余數據集屬于低維數據集(特征少).

圖2 兩種數據子集選擇算法的對比Fig.2 Comparison of two data subset selection methods

使用獨立特征選擇法時，需要為數據子集選擇k個特征，為了確定數據子集中k的取值范圍，本文分別給k取特征總數的10%，20%，30%，40%，50%，60%，70%，80%，90%，100%作為新的特征進行實驗，以RI值為依據，觀察 取不同值時對RI值產生的影響，劃定k的范圍.因為要對k分別取值，所以特征總數不能太少，我們取表1中特征數大于10的數據集進行實驗，所選數據集見表3.

表3 確定k范圍所用數據集Table 3 Determine the data set used for the k range

分別使用7種聚類集成算法在表3的數據集中進行實驗，得到的結果如圖3-圖7所示.

075070065060055050045.......RI值02.04.06.08.10.k和總特征數的比值EACCSPAHGPAMCLAGKPCHCSSCEBMLF圖3 Wine下RI值圖4 Vehicle下RI值圖5 Statlog下RI值Fig.3 RIvalueunderWineFig.4 RIvalueunderVehicleFig.5 RIvalueunderStatlog

圖3-圖7中每一條折線代表一種聚類集成算法，當取到特征總數的70%-80%時，大部分聚類集成算法獲得的RI值都是最高的.說明數據子集中的取值范圍在總體特征個數的70%-80%時為最佳.

實驗在表2的數據集上進行，將本文的CEBMLF算法與EAC[3]、CSPA[1]、HGPA[1]、MCLA[1]、GKPC[16]、HCSS[17]這6種聚類集成算法進行對比.得到結果并計算它們的RI值，實驗結果見表4，最好的結果加亮顯示.

圖6 Sonar下RI值Fig.6 RI value under Sonar

圖7 CNAE-9下RI值Fig.7 RI value under CNAE-9

圖8 各種算法的結果變化幅度比較Fig.8 Comparison of the results of various methods

由表4分析可知，CEBMLF算法在7個數據集上獲得了最高的RI值，在剩下的數據集上也獲得了較好的結果(為第二位)且與最好結果相差不到1%.說明CEBMLF算法聚類集成的準確率高.

表4 各種算法的RI值Table 4 RI values of various algorithms

表5 各種算法的標準差(%)Table 5 Standard deviation of various algorithms (%)

然后計算7種集成算法在表2中9種數據集上的標準差.見表5.通過表5可以看出本文提出的CEBMLF算法較其余6種聚類集成算法相對穩定.也可以通過圖8直接觀察，在圖中，CEBMLF算法位于7種算法的最底端，而且上下限的范圍相對較小，得出CEBMLF算法的結果變化幅度相對其余算法較小，比較穩定.

5 結 論

本文提出了一種基于多鏈接特征子集的聚類集成算法.該算法為了得到準確率更高的聚類集成結果，在基聚類結果的生成階段使用了特征子集和多種不同的聚類算法，通過獨立特征選擇法選出獨立的特征子集作為多種不同聚類算法的輸入，然后將數據點與簇的相關性集成信息矩陣轉化為數據點之間的相關性關系矩陣，融合基聚類結果的關系矩陣，對融合的關系矩陣使用Average-Linkage算法進行聚類，得到最終結果.通過實驗結果表明該算法能使最終聚類的準確率得到提升.