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

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

1 引 言

聚類作為重要的機(jī)器學(xué)習(xí)方法，對(duì)于復(fù)雜度高的數(shù)據(jù)集，單一的聚類算法很難正確地辨別出它的類簇結(jié)構(gòu)，為了獲得穩(wěn)定且準(zhǔn)確的聚類結(jié)果，人們提出了聚類集成算法.在很多方面聚類集成的性能都能夠超越單個(gè)聚類算法的性能，如魯棒性、穩(wěn)定性和一致性估計(jì).近年來，聚類集成已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域中的熱點(diǎn)研究問題之一，最初它是由Strehl和Ghosh[1]正式提出.Topchy等人[2]指出通過聚類集成算法得到的聚類結(jié)果要比單一聚類算法得到的結(jié)果好；而且聚類集成的結(jié)果受噪聲和孤立點(diǎn)的影響，它們?cè)缴伲Y(jié)果的魯棒性和穩(wěn)定性越好.Fred和Jain[3]提出了一種證據(jù)累積的聚類集成算法(簡(jiǎn)稱EAC)，首先計(jì)算所有基聚類結(jié)果的共聯(lián)矩陣，然后使用最小生成樹的分級(jí)聚類算法求得最終結(jié)果.周志華等人[4]將聚類集成與投票問題放在一起考慮，設(shè)計(jì)了一種投票機(jī)制，通過投票結(jié)果計(jì)算出聚類集成的結(jié)果.Naldi 和Carvalho等人[5]提出了一種基于相對(duì)有效指標(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)簽對(duì)齊，接下來一對(duì)一相乘，最后設(shè)計(jì)一致性函數(shù)，做歸一化處理.Lam-on和Boongoen等人[9]提出了一種基于鏈接的聚類集成算法，該算法解決了共聯(lián)矩陣中信息使用不充分的問題，在生成共聯(lián)矩陣時(shí)不僅考慮點(diǎn)與點(diǎ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ù)集中會(huì)存在冗余特征屬性，而且相似度矩陣只能得到部分?jǐn)?shù)據(jù)點(diǎn)之間的關(guān)系，對(duì)于具有弱相似度的數(shù)據(jù)點(diǎn)只能顯示為0.為解決這些問題，本文提出了一種基于多鏈接特征子集的聚類集成算法(Clustering ensemble algorithm based on multi-link feature subset，CEBMLF)，該算法在基聚類結(jié)果的生成階段使用獨(dú)立特征選擇法，消除了冗余特征，降低了原始數(shù)據(jù)集的維數(shù)，提高聚類集成結(jié)果的準(zhǔn)確率；然后通過將數(shù)據(jù)點(diǎn)與簇的相關(guān)性集成信息矩陣轉(zhuǎn)化為反映數(shù)據(jù)點(diǎn)之間的相關(guān)性關(guān)系矩陣，解決了相似度矩陣只能得到數(shù)據(jù)點(diǎn)之間的部分關(guān)系，對(duì)于具有弱相似度的數(shù)據(jù)點(diǎn)只能顯示為0的缺點(diǎn)；融合基聚類結(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í)它也是模式識(shí)別中數(shù)據(jù)預(yù)處理的關(guān)鍵步驟.

2.2 聚類集成

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

3.1 特征子集的選取算法

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

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

算法1.獨(dú)立特征子集選取算法

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

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

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

6.選取Xc_mean中k個(gè)最接近0的值；

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

3.2 基聚類的生成策略

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

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

(6)

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

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

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

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

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

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

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

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

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

4 實(shí) 驗(yàn)

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

表1 實(shí)驗(yàn)所用的個(gè)體聚類算法Table 1 Individual clustering algorithm used in the experiment

4.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

(7)

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

4.2 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

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

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

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

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

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

使用獨(dú)立特征選擇法時(shí)，需要為數(shù)據(jù)子集選擇k個(gè)特征，為了確定數(shù)據(jù)子集中k的取值范圍，本文分別給k取特征總數(shù)的10%，20%，30%，40%，50%，60%，70%，80%，90%，100%作為新的特征進(jìn)行實(shí)驗(yàn)，以RI值為依據(jù)，觀察 取不同值時(shí)對(duì)RI值產(chǎn)生的影響，劃定k的范圍.因?yàn)橐獙?duì)k分別取值，所以特征總數(shù)不能太少，我們?nèi)”?中特征數(shù)大于10的數(shù)據(jù)集進(jìn)行實(shí)驗(yà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)行實(shí)驗(yà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%時(shí)，大部分聚類集成算法獲得的RI值都是最高的.說明數(shù)據(jù)子集中的取值范圍在總體特征個(gè)數(shù)的70%-80%時(shí)為最佳.

實(shí)驗(yàn)在表2的數(shù)據(jù)集上進(jìn)行，將本文的CEBMLF算法與EAC[3]、CSPA[1]、HGPA[1]、MCLA[1]、GKPC[16]、HCSS[17]這6種聚類集成算法進(jìn)行對(duì)比.得到結(jié)果并計(jì)算它們的RI值，實(shí)驗(yàn)結(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個(gè)數(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 (%)

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

5 結(jié) 論

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