江志良，侯 遠，吳 敏

華東師范大學 計算機科學與軟件工程學院，上海 200062

1 引言

聚類是最重要的無監(jiān)督學習方法之一。對于復雜數(shù)據(jù)集，單一的聚類算法較難發(fā)現(xiàn)數(shù)據(jù)穩(wěn)定和較優(yōu)的分類結(jié)構(gòu)，而聚類集成可以解決這一問題[1]。

聚類集成的實現(xiàn)策略有基于數(shù)據(jù)點的共現(xiàn)關系及基于中值劃分[2]的方法。第一種策略包括重標簽和投票[3-4]、基于共生矩陣的二次聚類[5]、基于圖或者超圖的集成聚類[6-7]；第二種策略主要通過Mirkin-Distance[8]等方法進行集成，其實現(xiàn)往往是NP難的[9-10]，因此需應用啟發(fā)式方法加以改進[11]。

對于具有較多特征的數(shù)據(jù)，一種較好的聚類集成策略包括如下兩個步驟：（1）用單聚類算法對數(shù)據(jù)的不同特征子集進行聚類，得到若干個聚類成員；（2）由于使用不同數(shù)據(jù)子集進行聚類，因此每個聚類成員的質(zhì)量是不一樣的，需要對其進行加權(quán)投票。

在選擇聚類成員的數(shù)據(jù)子集時，一般可用隨機抽樣，但較難確定樣本容量大小和抽樣次數(shù)。本文從特征相關性的角度出發(fā)，將數(shù)據(jù)集中每個特征與之不相關的K個特征（K＜總特征數(shù)）組成數(shù)據(jù)子集，作為聚類成員的數(shù)據(jù)輸入。這種數(shù)據(jù)選擇方法相比隨機抽樣而言不確定的參數(shù)更少，從實驗結(jié)果來看，其聚類集成效果也優(yōu)于隨機抽樣。

基于加權(quán)投票的聚類集成方法實現(xiàn)簡單，但需要對每個聚類成員進行重標簽操作。已有的重標簽方法主要有二分匹配（匈牙利算法）[12]、累積投票（Cumulative Voting）[13]等，但這些方法實現(xiàn)較為復雜。本文基于數(shù)據(jù)子集相似度，提出一種改進的Jaccard距離方法來解決重標簽問題。

加權(quán)集成的另一重要問題是如何確定單聚類結(jié)果的權(quán)重準則。Vega-Pons[14]等基于CVI準則作為聚類加權(quán)標準，陽琳赟[15]等通過互信息對聚類成員進行加權(quán)，Devi K N V R[16]等將屬性相關性作為加權(quán)標準，潘俊[17]等依據(jù)特征劃分進行聚類集成。本文將經(jīng)典的Davies-Bouldin-Index（DBI）[18]聚類準則作為權(quán)重計算方法之一，該方法不需借助外部標簽，使用質(zhì)心作為類簇的代表但計算量較大。相應的，本文將質(zhì)心替換成均值、方差等基本統(tǒng)計量，提出一種計算量較小的權(quán)重計算方法。此外，本文還從特征關系出發(fā)將信息增益[19]、RELIEF[20]這兩種特征選擇方法改進為權(quán)重計算方法，并提出一種基于特征取值差異的權(quán)重計算方法。實驗表明，這五種權(quán)重計算方法能很好處理球狀類簇的數(shù)據(jù)集，信息增益和RELIEF方法對不規(guī)則形狀類簇的數(shù)據(jù)集性能更好。

本文的內(nèi)容安排如下：第2章給出聚類集成的問題描述；第3章論述基于最小特征相關性的數(shù)據(jù)子集的選取方法；第4章提出改進的相似度計算方法及重標簽的步驟；第5章介紹了五種權(quán)重計算方法的定義和差別；第6章描述了基于加權(quán)投票的聚類集成步驟；第7章通過實驗展現(xiàn)了不同權(quán)重計算方法對聚類集成的準確率影響及最小相關特征選擇法的優(yōu)勢；第8章是對本文的總結(jié)。

2 問題描述

假定數(shù)據(jù)集D共有M條數(shù)據(jù){d1,d2,…,dM}和N個特征{f1,f2,…,fN}。為論述方便，將D形式化表示成{F1,F2,…,FN}，其中Fi為一個M維列向量，代表所有M條數(shù)據(jù)在第i個特征的值。

本文的聚類集成方法框架如下：用同一種聚類算法對數(shù)據(jù)集的不同部分進行聚類，最后將所有聚類結(jié)果進行融合。該框架的主要步驟有數(shù)據(jù)子集選擇，聚類成員的權(quán)重計算，聚類結(jié)果的重標簽和最終的加權(quán)投票。

3 基于特征相關性的數(shù)據(jù)子集選擇

聚類集成的每個聚類成員都需要對數(shù)據(jù)集D的一個子集進行聚類。如果一個數(shù)據(jù)子集的特征間相關性很大，那么該次聚類能夠使用的特征信息就很少，聚類集成就不能覆蓋整個特征空間。所謂特征相關性，是指特征之間相互獨立或相互依賴的程度。若特征之間是線性相關的，則可用皮爾遜系數(shù)來衡量其大?。桓话愕南嚓P性則使用互信息的方法來計算。本文使用與互信息等價的信息增益[19]方法來計算特征之間的相關性。數(shù)據(jù)子集的選取，一般可通過隨機抽樣來確定，但若要選取盡量不相關的特征，抽樣大小和次數(shù)較難掌握。本文提出最小相關的特征選取方法，它以數(shù)據(jù)集的每個特征為基準，選擇與其相關性最小的K個特征構(gòu)成數(shù)據(jù)子集。具體包括如下兩種策略：

算法1（子數(shù)據(jù)集選擇）

策略1對數(shù)據(jù)集D的特征集{fi,f2,…,fN}中每一特征fi，計算D-{fi}中每一特征和fi的相關性，并選取與fi相關性最小的K-1個特征和fi一起組成數(shù)據(jù)子集Subi。

策略2

策略1只考慮與每個特征相關性最小的若干個特征，因而較容易獲取特征子集，但也可能會導致特征重復，如 f2,f3,f4是和 f1相關性最小的3個特征，但 f2和 f4之間的相關性可能很大。策略2對策略1進行了改進，盡量考慮了所有特征的相關性。

實驗表明策略1和策略2的聚類集成準確率都高于隨機抽樣，且策略2在聚類數(shù)較少時效果更優(yōu)。

對于每個子特征集的大小K，從理論上來說并沒有嚴格的限制。在后續(xù)的實驗中本文給出了使得聚類準確率較高的K值的參考范圍。

4 重標簽

不同聚類過程對同一數(shù)據(jù)集進行聚類可能會得到不同的結(jié)果。例如：數(shù)據(jù)集D經(jīng)過某個聚類算法聚類后得到聚類結(jié)果Pi=[1,2,3,4]，即D的類簇標簽是[1，2，3，4]；不失一般性，假設再次使用該聚類算法對D進行聚類得到的類簇標簽是Pj=[4,3,2,1]，雖然Pi≠Pj，但它們指代的是相同的聚類結(jié)果，因此需要將Pj重置為[1，2，3，4]，或?qū)i重置為[4，3，2，1]后才能正確地對聚類結(jié)果進行投票。本文將基于最直接的數(shù)據(jù)相似度完成重標簽步驟。下面先給出相似度的定義，并提出改進策略。

定義1（Jaccard距離）

集合S1和S2的Jaccard距離定義為：其中#表示集合中的元素個數(shù)。

直接使用Jaccard距離獲取的是兩個集合元素的重疊程度，可能會造成信息遺漏。例如，給定兩個數(shù)據(jù)子集 S1={d1,d3,d5,d6,d7}和 S2={d1,d3,d8,d9,d10}，其中di代表樣本點的序號。顯然，Jaccard(S1,S2)=0.25。然而，經(jīng)過數(shù)據(jù)相似度計算發(fā)現(xiàn)，d5和d9對應的樣本點之間的相似度大于規(guī)定的閾值，可認為d5=d9，從而Jaccard(S1,S2)=(2+1)/(8-1)=3/7。

可見，為避免遺漏信息，還需要檢查集合的差集，從中找到符合相似度閾值的元素對的個數(shù)。因此，本文提出改進的Jaccard距離的計算方法如下：

算法 2（J2）

其中，{S1-S2}表示屬于S1不屬于S2的元素集合，E代表相似度計算函數(shù)。

由此，給出重標簽的具體步驟如下：給定數(shù)據(jù)集D，設PA={CA1,CA2,…,CAN}和PB={CB1,CB2,…,CBM}為兩個單聚類結(jié)果，其中CAi表示PA中的第i個類簇標簽，CBj表示PB中的第j個類簇標簽。記SAi,SBj分別表示屬于類簇CAi，CBj的數(shù)據(jù)子集，則有：

若以PA為基準進行重標簽，則對PA中的每個類簇CAi及其對應的數(shù)據(jù)子集SAi，遍歷PB中的每個元素CBj及其對應的數(shù)據(jù)子集SBj，將J2(SAi,SBj)最大的SBj對應的CBj重新標簽為CAj即可。需要注意，集合PA,PB的元素個數(shù)不一定相等，且PA中某個元素對應的數(shù)據(jù)子集可能和PB中的若干個元素對應的數(shù)據(jù)子集相似度相同或相近，因此重標簽時會出現(xiàn)一對多的情況，如，CB1重標簽的結(jié)果是{CA1,CA2}，CB2重標簽的結(jié)果是{CA2,CA3}。最后唯一的重標簽結(jié)果可通過最終的加權(quán)投票確定。

5 基于特征關系的聚類準則

5.1 基本流程

重標簽后，要對不同的單聚類算法的結(jié)果進行加權(quán)投票，得到最終的聚類標簽。

通用的加權(quán)投票算法框架如算法3所述，其中M為數(shù)據(jù)集D的條目總數(shù)，聚類成員集合中的每個元素P是一個由聚類標簽構(gòu)成的M維列向量，即，向量的每個元素為對應序號的數(shù)據(jù)點的聚類標簽。

算法3（加權(quán)投票）

將label中最大的value對應的key作為第i個樣本點的最終標簽

其中，label={?,?}是一個由key，value組成的二元組集合，key為標簽，value為權(quán)重。

加權(quán)投票的權(quán)重對聚類融合結(jié)果影響很大。本文結(jié)合聚類評價準則和特征選擇方法，分別采用DBI、信息增益、RELIEF以及兩種新方法作為單聚類結(jié)果的權(quán)重計算準則。

5.2 幾種權(quán)重計算方法

5.2.1 Davies-Bouldin-Index評價準則

Davies-Bouldin-Index（DBI）[18]是一種經(jīng)典的聚類評價準則。它不需要借助外部標簽，主要考慮類簇之間的關系和類簇內(nèi)數(shù)據(jù)點離類簇中心的距離。

定義2（DBI）：

其中，N代表聚類數(shù)，Si表示第i個類簇中所有數(shù)據(jù)點和其質(zhì)心距離的均值，Mij代表第i和j個類簇質(zhì)心之間的距離。不難看出，Mij值越大，Si值越小，DBI的值越小，即類簇之間的距離越大、同一類簇內(nèi)的數(shù)據(jù)點越集中，聚類的質(zhì)量越好。因此，DBI的值越小，聚類的質(zhì)量越好。本文直接使用weight=eDBI-1作為單聚類結(jié)果的權(quán)重，e為自然底數(shù)。

DBI依據(jù)“類簇之間差異最大，類簇內(nèi)差異最小”的聚類標準，通過質(zhì)心以及樣本點之間的距離定量分析類簇之間的差異。但是，它非常依賴類簇的質(zhì)心，因此主要適用于評價球狀類簇。

5.2.2 信息增益

信息增益[19]是最重要的特征選擇方法之一，其核心是信息熵。假設特征F有k個取值 f1,f2,…,fk，p(fi)為特征F取值 fi的概率，則代表特征F的信息熵。在聚類問題中，特征F相對于聚類結(jié)果即類簇集合C={c1,c2,…,ck}的信息熵為：

定義3（相對信息熵）：

同樣，可定義特征F對類簇集合C的信息增益：

定義4（信息增益）：

其中信息增益IG表示由于特征F而使得類簇集合C的不確定性減少的程度。F的信息增益越大，它在C的各個類簇中的區(qū)分度就越大，因此信息增益大的特征越多，聚類的質(zhì)量就越好。使用信息增益來計算單聚類結(jié)果權(quán)重的方法如下：

其中，D代表整個數(shù)據(jù)集，F(xiàn)代表某個特征，col(D)表示特征個數(shù)，CTN是一個可選函數(shù)，當特征為連續(xù)值時，可將其轉(zhuǎn)換為離散特征。

信息增益基于信息熵來評價特征與類別標簽之間的相關性。當特征是離散值時，通過統(tǒng)計特征不同取值的頻數(shù)來近似得到特征的離散概率分布。當特征為連續(xù)值時，一般有兩種處理方法：（1）假設特征符合某種概率分布，在此基礎上計算連續(xù)概率獲得熵值分布。（2）將連續(xù)特征轉(zhuǎn)換為離散特征再進行處理。為了統(tǒng)一計算，本文采取特征離散化的方法，將連續(xù)特征等距劃分為離散值?；谛畔⒃鲆娴姆椒ㄍㄟ^熵值差異來計算特征和類簇之間的相關性，理論上可以處理各種形狀類簇的數(shù)據(jù)。

5.2.3 RELIEF

RELIEF[20]算法是一種用于特征選擇的經(jīng)典方法，其形式化描述如下：

算法 4（RELIEF）

該算法的基本思想是：盡量使每一個樣本點和同一類別內(nèi)距離其最近的樣本點的間距最小，和不同類別內(nèi)距其最近的樣本點間距最大，因此它可以非常自然地作為聚類算法的評價標準。

從應用的角度來看，RELIEF考慮的是樣本的密度，即使數(shù)據(jù)集的類簇形狀是不規(guī)則的，只要每個類簇內(nèi)的數(shù)據(jù)具有一定的密度，類簇之間有明顯的間隔，RELIEF算法的效果就很好。

5.2.4 特征取值差異

本文基于特征之間的關系提出一種基于特征分布差異的權(quán)重計算方法。在理想情況下，當聚類結(jié)果的質(zhì)量最好時，大部分特征在結(jié)果類簇中的區(qū)分度應最大，即當特征F的k個取值{f1,f2,…,fk}正好各自落在k個類簇{c1,c2,…,ck}中時，相對于特征F而言的聚類結(jié)果質(zhì)量是最好的，但實際上特征的不同取值不會正好對應不同的類簇。一種直接的考慮是：特征F的取值在不同類簇間的頻數(shù)差異越大，它在C個類簇中的區(qū)分度也就越大。于是，定義如下：

定義5（特征取值差異法）：

其中abs是絕對值函數(shù)，nc表示類簇的個數(shù)，nf表示特征F取值的種數(shù)，freqik表示特征F的第k種取值在類簇Ci中出現(xiàn)的次數(shù)?；谧畲箢l數(shù)差異的聚類成員權(quán)重計算方法如下：

其中，CTN是一個將連續(xù)特征進行離散化的可選函數(shù)，col(D)表示D的特征個數(shù)，getFreq(F,C)獲取特征F的不同取值在不同類簇中出現(xiàn)的次數(shù)。

特征取值差異法只考慮每個特征的不同取值在不同類簇中出現(xiàn)的次數(shù)，并不直接計算特征和類簇的關系。

5.2.5 基本統(tǒng)計量差異

在評價聚類結(jié)果時，聚類后的每一個類簇一般都有一個代表性的特征，如使用DBI準則進行評價時，類簇代表是質(zhì)心。以質(zhì)心為基礎的評價方法計算準確，但由于涉及每一個樣本點和質(zhì)心之間以及兩兩質(zhì)心之間的距離，計算代價較大。本文使用更一般的統(tǒng)計量來代表每個類簇。具體定義如下：

定義6（基本統(tǒng)計量差異法）：

其中，C表示所有類簇集合，F(xiàn)表示所有特征集合，nf代表特征個數(shù)，nc代表類簇個數(shù)；分母表示所有類簇方差的均值，該值越小，說明類簇內(nèi)數(shù)據(jù)聚合度越高；分子diff定義如下：

其中，abs是絕對值函數(shù)，max(Cfi),min(Cfi),avg(Cfi)分別表示特征f在類簇Ci中的最大、最小和均值。易見，diff表示屬于不同類簇兩兩之間的均值、最值的差，差值越大，類簇之間的距離越大。因此，基本統(tǒng)計量MS的值越大，表明聚類效果越好，從而可用于計算聚類結(jié)果權(quán)重。

6 聚類集成框架

整個加權(quán)投票的聚類集成框架如下：

步驟1初始聚類成員集合P={}，權(quán)重集合W={}

步驟2

for i=1 to特征數(shù)：

1.用最小相關法選擇特征子集Subi

2.用某種聚類算法對Subi進行聚類，得到結(jié)果pi，用算法5修正pi，并將修正后的pi加入集合P

3.用某種權(quán)重方法計算pi的權(quán)重wi，將wi加入集合W

步驟3對權(quán)重集合W進行0-1標準化

步驟4

for p1in P：

cand={p1}

for p2in P-{p1}：

以p1為基準將p2進行重標簽并將更新后的p2加入集合cand用算法3對cand加權(quán)投票，得到最終聚類標簽L用算法5修正L并用聚類準則計算L的準確率輸出聚類準確率最高的L

基于加權(quán)投票的聚類集成在限制類簇個數(shù)的情況下，有時會出現(xiàn)一種包含樣本點很少且離其他類簇較近的噪聲類簇，如圖1所示。

圖1 噪聲類簇

圖1包含3個類簇，但·代表的類簇樣本點很少，且和其他兩個類簇距離很近，因此應該將其與其他兩個類簇進行合并，最終的聚類數(shù)為2。這一合并思路可通過下列算法實現(xiàn)：

算法5（噪聲簇合并）

for c in所有類簇：

如果 c的容量＜=容量閾值：

for d in c：

dn=距d最近的類簇的質(zhì)心

avg=距d最近類簇中所有點到質(zhì)心的平均距離

if E（dn，d）＜=avg

將d指派到dn對應的類簇中

其中c代表一個類簇，d代表類簇c中的一個數(shù)據(jù)點，E是一種相似度計算函數(shù)。

7 實驗

7.1 實驗數(shù)據(jù)及評價標準

本文從UCI Machine Learning Repository[21]選取了具有一定特征數(shù)的6個球狀類簇數(shù)據(jù)集和4個不規(guī)則類簇數(shù)據(jù)集，見表1。

表1（a） 球狀類簇數(shù)據(jù)集

表1（b） 不規(guī)則類簇數(shù)據(jù)集

本文使用經(jīng)典的聚類評價標準DBI[18]和SDBW[22]來評價實驗結(jié)果。這兩種標準不需借助類標簽信息，是無監(jiān)督性質(zhì)的評價準則，并且在常用的無監(jiān)督評價準則中，SDBW的可信度是最高的[22]。但是這兩種標準只能用于具有球狀類簇的數(shù)據(jù)集。針對有真實類別信息的數(shù)據(jù)集，由于每個類別的實例數(shù)大致相同，即數(shù)據(jù)集是平衡的，因此直接使用分類準確性來評價。

DBI和SDBW的核心思想是類內(nèi)距離和類間距離的比值，它們的值越小說明聚類效果越好；分類準確性為聚類正確的標簽個數(shù)和數(shù)據(jù)集實例數(shù)的比值，值越大說明聚類效果越好。

為了更加全面地比較單次聚類和聚類集成的效果差異，本文基于上述三種評價標準定義如下評價方法：

定義7（單權(quán)重相對評價）：

（1）對于DBI和SDBW，其相對評價定義為：

（單次評價值－集成評價值）/單次評價值

（2）分類準確率的相對評價定義為：

（集成準確率－單次準確率）/單次準確率

其中單次或者集成評價值是根據(jù)某一權(quán)重計算方法的單次聚類或者聚類集成結(jié)果計算的，如果考慮所有權(quán)重計算方法，則評價方法如下：

定義8（多權(quán)重相對評價）：

7.2 實驗結(jié)果

7.2.1 不同數(shù)據(jù)子集選擇策略的對比

假設數(shù)據(jù)集一共有M個特征，為了分析最小相關特征選擇法的效果，設計如下實驗：設定M個聚類成員，之后：

（1）針對數(shù)據(jù)集的每一個特征，用算法1確定K個特征作為每個聚類成員的輸入，進行加權(quán)聚類集成。

（2）對數(shù)據(jù)集隨機抽樣M次，每次抽出K個特征作為每個聚類成員的輸入，進行加權(quán)聚類集成。

其中K值的大小經(jīng)過之后的實驗確定為特征總數(shù)M的70%～80%。

針對每一種數(shù)據(jù)子集選擇方法，分別使用定義8計算該方法下聚類集成的效果，可以得到圖2所示的實驗結(jié)果，實驗使用6個具有球狀類簇的數(shù)據(jù)集，其中每個數(shù)據(jù)集的聚類數(shù)取其實際類別數(shù)。對于剩下的4個具有不規(guī)則類簇的數(shù)據(jù)集，DBI和SDBW不再適用，因此只比較它們的分類準確率。

從實驗結(jié)果可知，最小相關特征法在大部分數(shù)據(jù)集上的相對評價都比隨機抽樣法高。它的DBI相對評價在5個數(shù)據(jù)集上高于隨機抽樣，SDBW的相對評價在4個數(shù)據(jù)集上高于隨機抽樣，分類準確度的相對評價在8個數(shù)據(jù)集上都高于隨機抽樣。因此，相對隨機抽樣而言，最小特征相關法不僅具有更少的不確定參數(shù)，用于聚類集成時的效果也比前者好。 使用最小特征相關法作為數(shù)據(jù)子集選擇方法時，需要為每一個聚類成員選擇K個特征，本文以每個數(shù)據(jù)集的分類準確性為依據(jù)，觀察K取不同值時對分類準確性產(chǎn)生的影響，結(jié)果如圖3。

圖3中每一條折線代表一個數(shù)據(jù)集，分析可知，當使用最小相關特征法作為數(shù)據(jù)子集選擇方法并進行聚類集成后，每個數(shù)據(jù)子集的特征數(shù)K取特征總數(shù)的70%～80%時，大部分數(shù)據(jù)集的聚類準確率都是最高的，當K大于特征總數(shù)的80%時，分類準確率不再提升。

7.2.2 球狀類簇數(shù)據(jù)集的聚類集成實驗

針對6個球狀類簇數(shù)據(jù)集，將聚類數(shù)設定為數(shù)據(jù)集的真實類別數(shù)，分別使用K-Means和基于層次聚類的Agglomerative（AL）這兩種聚類算法進行加權(quán)聚類集成，實驗結(jié)果如表2所示，其中ACC、DBI、SDBW分別代表分類準確率、DBI評價值和SDBW評價值。每一行數(shù)據(jù)為某一數(shù)據(jù)集上分別使用五種權(quán)重計算方法聚類后得到的評價值的均值。

圖2 兩種數(shù)據(jù)子集選擇方法的對比

圖3 分類準確率和K值的關系

表2 兩種算法下單聚類和聚類集成的對比

表2顯示，聚類集成的真實分類準確率在所有數(shù)據(jù)集上都優(yōu)于單聚類，且聚類集成的DBI和SDBW值在大部分數(shù)據(jù)集上也都優(yōu)于單聚類。

接下來，基于DB Index（DBI）、信息增益（IG）、RELIEF（RF）、特征取值差異（MF）、基本統(tǒng)計量差異（MS）這五種權(quán)重計算方法，表3給出了每種權(quán)重計算方法下單聚類和聚類集成的效果。因為涉及所有數(shù)據(jù)集的評價值，權(quán)重計算方法的評價值的計算如下：對該權(quán)重計算方法在6個數(shù)據(jù)集和2種聚類算法（KMEANS，AL）下的各評價值（ACC/DBI/SDBW）構(gòu)成的列表進行0-1標準化，將標準化后的均值作為最終評價值。進行標準化是因為評價值在不同數(shù)據(jù)集（相同聚類數(shù)）上的取值差異較大。

從表3可以看出，在五種權(quán)重計算方法下聚類集成的效果都好于單次。使用定義7對表3的數(shù)據(jù)計算發(fā)現(xiàn)，基于信息增益（IG）和基本統(tǒng)計量差異（MS）的方法在分類準確性上提升較高，為9.4%和8.8%?；谔卣魅≈挡町悾∕F）和基本統(tǒng)計量差異（MS）的方法在DBI上提升較高，為15.0%和15.2%?；诨窘y(tǒng)計量差異（MS）和RELIEF（RF）的方法在SDBW上提升較高，為52.1%和53.5%。綜合來看，基于基本統(tǒng)計量差異法的權(quán)重計算方法性能較好。

表3 不同權(quán)重計算方法的效果對比

圖4給出了基于五種權(quán)重計算方法的聚類集成在不同數(shù)據(jù)集上的相對評價差異。從圖中可看出，基于這五種權(quán)重計算方法的聚類集成在大部分數(shù)據(jù)集上的相對評價都大于0，且DBI相對評價在所有數(shù)據(jù)集上的趨勢基本一致，基于特征取值差異（MF）的權(quán)重計算方法的SDBW相對評價在大部分數(shù)據(jù)集上高于其他權(quán)重方法，基于信息增益（IG）的權(quán)重計算方法的分類準確性相對評價在大部分數(shù)據(jù)集上高于其他權(quán)重方法。

圖5給出了五種權(quán)重計算方法的平均執(zhí)行時間。由此可見，基于RELIEF算法的權(quán)重計算方法時間消耗最大，而基于基本統(tǒng)計量差異（MS）的計算方法的時間性能最好，基于DBI的方法次之。綜合考慮五種權(quán)重計算方法的效果和時間性能，基于DBI和基本統(tǒng)計量差異（MS）的權(quán)重計算方法較優(yōu)。

7.2.3 球狀類簇數(shù)據(jù)集不同聚類數(shù)的聚類集成

圖4 不同權(quán)重計算方法的相對評價

圖5 五種權(quán)重方法在各數(shù)據(jù)集上的執(zhí)行時間

盡管數(shù)據(jù)集都有真實類別數(shù)，但在現(xiàn)實問題中聚類數(shù)往往不確定。因此，本文進一步考慮了不同聚類數(shù)下單聚類和聚類集成的差異。每一行數(shù)據(jù)取五種權(quán)重計算方法下聚類評價值的均值。實驗結(jié)果如表4所示。從實驗數(shù)據(jù)來看，在聚類數(shù)為4，6，8，10的條件下，基于不同權(quán)重計算方法的聚類集成在兩種聚類算法下的DBI和SDBW的平均值都優(yōu)于單次聚類。

針對每一種權(quán)重計算方法，類似7.2.2小節(jié)的實驗，分別計算它在所有聚類算法（K-Means和AL）下所有數(shù)據(jù)集上的DBI和SDBW評價值經(jīng)過0-1標準化后的均值，結(jié)果如表5所示。從實驗數(shù)據(jù)來看，無論使用哪種權(quán)重計算方法，在不同聚類數(shù)下的集成效果都比單聚類好。

表4（a） K-Means算法下不同聚類數(shù)目下的DBI和SDBW對比

表4（b） Agglomerative算法下不同聚類數(shù)目下的DBI和SDBW對比

表5 不同聚類數(shù)目下不同權(quán)重計算方法在所有數(shù)據(jù)集上的DBI和SDBW對比

進一步，依然使用定義7（相對評價）分析不同權(quán)重計算方法在不同數(shù)據(jù)集上集成效果的差異，結(jié)果如圖6所示?？梢钥闯?，五種權(quán)重計算方法隨聚類數(shù)增加而變化的趨勢大致一致，其中DBI相對評價隨聚類數(shù)的增加有所降低，SDBW的相對評價在聚類數(shù)為6時最高，之后也隨聚類數(shù)增加而下降。并且基于信息增益（IG）和基于DBI的權(quán)重計算方法在的相對評價在大部分聚類數(shù)上都高于其他權(quán)重計算方法。

圖6 不同權(quán)重方法下相對評價隨聚類數(shù)的變化

圖7 4個不規(guī)則數(shù)據(jù)集降到三維的可視化結(jié)果

7.2.4 不規(guī)則類簇數(shù)據(jù)集的聚類集成實驗

為比較五種權(quán)重計算方法在不規(guī)則類簇數(shù)據(jù)集上的效果，本文使用表1（b）所示的數(shù)據(jù)集進行實驗，圖7是4個數(shù)據(jù)集降維后的可視化結(jié)果。

不規(guī)則數(shù)據(jù)的質(zhì)心是沒有意義的，因此使用分類準確性作為評價標準，并用可處理任意簇類形狀的DBSCAN（基于密度的聚類）和SPECTRAL（譜聚類）算法作為單聚類算法，分別計算五種權(quán)重計算方法下集成和單次聚類的準確率。結(jié)果如表6所示。

從表6的結(jié)果來看，基于RELIEF的權(quán)重計算方法在每一個數(shù)據(jù)集上的分類準確率都比基于DBI的方法高，這種差異在數(shù)據(jù)集synt3和synt4上尤為明顯?；谛畔⒃鲆妫↖G）和特征取值差異（MF）的方法在前3個數(shù)據(jù)集上的效果也比基于DBI的方法好?？傮w來看，對具有不規(guī)則類簇的數(shù)據(jù)進行聚類集成，IG、MF、RELIEF這三種基于特征選擇的權(quán)重計算方法效果很好。

7.2.5 權(quán)重計算方法的比較

本文分析的五種權(quán)重計算方法，主要在數(shù)據(jù)集的適用范圍、時間性能上有一定的差異。

基于信息增益（IG）的方法依賴于特征和聚類結(jié)果之間概率分布的差異，基于RELIEF的方法考慮依賴于樣本的密度，而基于特征取值差異（MF）的方法則根據(jù)特征在不同類簇不同取值頻數(shù)的差異進行區(qū)分，因此，這三種方法不受數(shù)據(jù)在空間中分布的影響，能處理具有任意形狀類簇的數(shù)據(jù)。而其他兩種方法需要有一個能代表類簇中心的量作為基礎，因此它們只能處理類簇形狀接近球狀的數(shù)據(jù)集。

表6 synt1、synt2、synt3、synt4上的分類準確率

從時間性能來看，基于RELIEF的方法性能最差，基于基本統(tǒng)計量差異的方法性能最好，基于DBI的方法次之，因此當數(shù)據(jù)量較小時可以選擇RELIEF方法。從聚類的準確率來看，當數(shù)據(jù)集具有球狀類簇時，五種權(quán)重計算方法在所有數(shù)據(jù)集上的差別不是很大，但是對于類簇形狀不規(guī)則的數(shù)據(jù)，基于RELIEF、IG、MF的權(quán)重計算方法效果更好。

因此，針對具體的數(shù)據(jù)集，為了選擇合適的權(quán)重計算方法，可以先對數(shù)據(jù)集進行可視化確定它的類簇形狀，對于維數(shù)較高的數(shù)據(jù)集，可以使用基于主成分分析的方法將其降到三維后進行可視化，之后按照如表7規(guī)則選擇權(quán)重計算方法。

表7 權(quán)重計算方法的選擇方案

8 結(jié)束語

本文針對加權(quán)投票的聚類集成，提出了一種基于特征最小相關性的數(shù)據(jù)子集選擇方法，提高了聚類集成的準確度；此外，分析比較了五種權(quán)重計算方法，其聚類集成的準確率均優(yōu)于單聚類，且基于RELIEF的方法可用于任何類簇形狀的數(shù)據(jù)集，基于基本統(tǒng)計量差異的方法的時間復雜度最小。

[1]Vega-Pons S，Ruiz-Shulcloper J.A survey of clustering ensemble algorithms[J].International Journal of Pattern Recognition and Artificial Intelligence，2011，25（3）：337-372.

[2]Régnier S.Sur quelques aspects mathématiques des problèmes de classification automatique[J].Mathématiques et Sciences Humaines，1983，82：13-29.

[3]Fischer B，Buhmann J M.Bagging for path-based clustering[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2003，25（11）：1411-1415.

[4]Weingessel A，DimitriadouE，HornikK.Anensemble method for clustering[C]//International Workshop on Distributed Statistical Computing，2003.

[5]Fred A L N，Jain A K.Combining multiple clusterings using evidence accumulation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2005，27（6）：835-850.

[6]Strehl A，Ghosh J.Cluster ensembles-a knowledge reuse framework for combining partitionings[C]//Eighteenth National Conference on Artifical Intelligence，2002：93-99.

[7]Karypis G，Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM Journal on Scientific Computing，1998，20（1）：359-392.

[8] Mirkin B.Mathematicalclassification and clustering：From how to whatand why[M]//Classification，data analysis，and data highways.Berlin Heidelberg：Springer，1998：172-181.

[9]K?ivánek M，Morávek J.NP-hard problems in hierarchicaltree clustering[J].Acta Inform，1986，23（3）：311-323.

[10]Wakabayashi Y.Aggregation of binary relations：algorithmic and polyhedral investigations[D].University of Augsburg，1986.

[11]Filkov V，Skiena S.Integrating microarray data by consensus clustering[J].International Journal of Artificial Intelligence Tools，2004，13（4）：863-880.

[12]Kuhn H W.The Hungarian method for the assignment problem[J].Naval Research Logistics，1955，2（1/2）：83-97.

[13]Ayad H G，Kamel M S.Cumulative voting consensus method for partitions with variable number of clusters[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2008，30（1）：160-173.

[14]Vega-Pons S，Correa-Morris J，Ruiz-Shulcloper J.Weighted cluster ensemble using a kernel consensus function[C]//Iberoamerican Congress on Pattern Recognition，2008：195-202.

[15]陽琳赟，周海京，卓晴，等.基于屬性重要性的加權(quán)聚類融合[J].計算機科學，2009，36（4）：243-245.

[16]Devi K N V R，Rao M S.Attribute and information gain based feature selection technique for cluster ensemble：Hybrid majority voting based variable importance measure[J].International Journal of Innovative Technology and Research，2013，1（6）：607-610.

[17]潘俊，王瑞琴.基于選擇性聚類集成的客戶細分[J].計算機集成制造系統(tǒng)，2015，21（6）：1662-1668.

[18]Davies D L，Bouldin D W.A cluster separation measure[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，1979（2）：224-227.

[19]李航.統(tǒng)計學習方法[M].北京：清華大學出版社，2012.

[20]Kira K，Rendell L A.A practical approach to feature selection[C]//International Workshop on Machine Learning，1992：249-256.

[21]Bache K，Lichman M.UCI Machine learning repository[D].Irvine，CA：University of California，2013.

[22]Liu Y，Li Z，Xiong H，et al.Understanding of internal