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

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

1(西安郵電大學(xué) 計算機(jī)學(xué)院，西安 710121) 2(陜西省網(wǎng)絡(luò)數(shù)據(jù)分析與智能處理重點實驗室(西安郵電大學(xué))，西安 710121)E-mail：821566504@qq.com

1 引 言

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

2 相關(guān)概念

2.1 特征選取

特征選擇是為了減少數(shù)據(jù)集的維數(shù)，消除重復(fù)無用的特征屬性，所以本質(zhì)上也可以稱之為特征子集選擇或?qū)傩赃x擇.它是指從所有的特征中選擇部分特征來優(yōu)化系統(tǒng)的具體指標(biāo).從原始數(shù)據(jù)集的所有特征中選擇出最有效的特征來代表原始數(shù)據(jù)集，以此達(dá)到減小數(shù)據(jù)集維數(shù)和消除重復(fù)無用的特征屬性的目的，是提高學(xué)習(xí)算法性能的重要手段，同時它也是模式識別中數(shù)據(jù)預(yù)處理的關(guān)鍵步驟.

2.2 聚類集成

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

3.1 特征子集的選取算法

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

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

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

輸入：數(shù)據(jù)集X={D1,D2，…，DN}.

輸出：數(shù)據(jù)子集X*={D1,D2，…，Dk}.

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

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

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

3.2 基聚類的生成策略

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

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

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

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

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

連接簇Ci和簇Cj的邊的權(quán)重Wij由這兩個簇共同包含的數(shù)據(jù)點個數(shù)得到，如下式：

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

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

(6)

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

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

輸入：數(shù)據(jù)集X={x1，x2，…，xn}.

輸出：最終結(jié)果T.

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

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

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

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

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

4 實 驗

在文中，我們利用標(biāo)準(zhǔn)數(shù)據(jù)集和它們的真實類比較了該算法與其他聚類集成算法的性能.所有的算法將在MATLAB R2016a中實現(xiàn).表1是實驗中用來產(chǎn)生基聚類結(jié)果的基聚類算法.

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

4.1 實驗數(shù)據(jù)及評價標(biāo)準(zhǔn)

本文從UCI[14]數(shù)據(jù)庫中選取了9個數(shù)據(jù)集進(jìn)行實驗，見表2.

表2 實驗所用UCI數(shù)據(jù)集Table 2 UCI data set used in the experiment

實驗采用外部評價標(biāo)準(zhǔn)RI(rand index)[15]對聚類結(jié)果進(jìn)行評價.RI有如下定義：

(7)

其中Y表示真實標(biāo)簽；T表示結(jié)果集；n11表示數(shù)據(jù)在T中和在Y中都在同一個簇中的數(shù)目；n00表示數(shù)據(jù)在中和在T中不在Y同一個簇中的數(shù)目；n10表示數(shù)據(jù)在T中在同一個簇中在Y中不在同一個簇中的數(shù)目；n01表示數(shù)據(jù)在T中不在同一個簇中在Y中在同一個簇中的數(shù)目.文獻(xiàn)[15]中提出聚類的RI值越高，聚類的準(zhǔn)確率越高.

4.2 實驗設(shè)計及結(jié)果分析

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

為了證明獨立特征選擇法的優(yōu)越性，本文引入隨機(jī)抽樣法與其進(jìn)行對比，在表2的數(shù)據(jù)集中分別進(jìn)行實驗，使用本文提出的CEBMLF聚類集成算法，評價標(biāo)準(zhǔn)使用RI標(biāo)準(zhǔn).得到的實驗結(jié)果如圖2所示.

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

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

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

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

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

分別使用7種聚類集成算法在表3的數(shù)據(jù)集中進(jìn)行實驗，得到的結(jié)果如圖3-圖7所示.

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

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

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

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

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

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

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

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

表5 各種算法的標(biāo)準(zhǔn)差(%)Table 5 Standard deviation of various algorithms (%)

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

5 結(jié) 論

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