李 鑫，白 亮,2

(1.山西大學(xué) 計算機與信息技術(shù)學(xué)院 山西 太原 030006；2.計算智能與中文信息處理教育部重點實驗室 山西 太原 030006)

0 引言

聚類分析是數(shù)據(jù)挖掘中的一個重要研究領(lǐng)域．它是針對給定的數(shù)據(jù)集，根據(jù)元素之間的相似性度量自動將相似的元素劃分到同一組，使得組內(nèi)元素的相似性達(dá)到最大而組間元素的相似性達(dá)到最小的過程．聚類分析已被廣泛應(yīng)用于圖像處理、信息檢索和生物信息學(xué)等研究領(lǐng)域[1]．

目前，已有多種聚類算法被提出，例如基于層次的、基于劃分的、基于密度的、基于網(wǎng)格的和基于模型的方法等．由于數(shù)據(jù)的復(fù)雜性與算法自身參數(shù)的影響，單一算法無法有效地完成聚類任務(wù)，所以將多個聚類結(jié)果進行融合是聚類分析的一個重要研究內(nèi)容．集成學(xué)習(xí)通過集成多個不同的學(xué)習(xí)器來解決同一個問題，提高了系統(tǒng)的學(xué)習(xí)能力．聚類集成利用集成學(xué)習(xí)技術(shù)，通過將數(shù)據(jù)集的多個聚類結(jié)果融合，得到一個新的聚類結(jié)果．Fred[2]和Strehl等[3]分別于2001年和2002年提出了聚類集成的概念．聚類集成主要有兩大任務(wù)：基聚類的產(chǎn)生和一致性函數(shù)的設(shè)計．為了得到更好的聚類集成效果，基聚類的成員應(yīng)具有一定的差異性．目前生成基聚類成員[4-6]主要有以下方法：對同一數(shù)據(jù)集使用不同的聚類算法；在使用相同算法時設(shè)定不同的初始化參數(shù)；使用數(shù)據(jù)集不同的特征子集；將數(shù)據(jù)集投影到子空間以及添加人工噪聲數(shù)據(jù)等．在得到具有差異性的基聚類成員后，需對其進行集成以得到最后的標(biāo)簽．集成即一致性函數(shù)[7]的設(shè)計有基于相似性度量的方法[8]、基于圖論的方法[9]、基于標(biāo)簽對齊的方法[10-12]以及基于特征轉(zhuǎn)換的方法[13]等．

雖然已有多種聚類集成算法被提出，但現(xiàn)有的聚類集成算法更多地追求最大基聚類的一致性，集成效果受到基聚類質(zhì)量的影響.當(dāng)基聚類結(jié)果很差時，最終的聚類集成效果會不理想．因此，本文在一致性函數(shù)設(shè)計時將原數(shù)據(jù)類結(jié)構(gòu)納入考慮中．將基聚類與原數(shù)據(jù)看作一個混合型數(shù)據(jù)，提出了一種基于混合型數(shù)據(jù)表示的聚類集成算法，該算法考慮了聚類集成結(jié)果對原數(shù)據(jù)類結(jié)構(gòu)和基聚類的一致性．與MCLA、HGPA、CSPA、Voting、WCT、WTQ、CSM、LWGP聚類集成算法進行了比較,結(jié)果表明，基于混合型數(shù)據(jù)表示的聚類集成算法具有較好的聚類結(jié)果．

1 基于混合型數(shù)據(jù)表示的聚類集成算法

1.1 基于混合型數(shù)據(jù)的表示

數(shù)據(jù)可分為數(shù)值型數(shù)據(jù)、符號型數(shù)據(jù)和混合型數(shù)據(jù)．例如匿名統(tǒng)計學(xué)生信息S={身高，體重，班級}時，既統(tǒng)計身高、體重等數(shù)值型信息，也統(tǒng)計班級等符號型信息，這種類型的數(shù)據(jù)被稱為混合型數(shù)據(jù)．

令X={X1,X2,…,Xn}表示具有n個樣本的數(shù)據(jù)集，其中Xi={Xi1,Xi2,…,Xim}表示第i個樣本的m個屬性，數(shù)據(jù)集表示成n×m的矩陣．對數(shù)據(jù)集進行T次聚類，Ri={Ri1,Ri2,…,RiT}表示第i個樣本在T次聚類下的結(jié)果，基聚類結(jié)果表示成n×T的矩陣．

定義1將基聚類結(jié)果看作原數(shù)據(jù)的符號型屬性，其和原數(shù)據(jù)合并成一個n×s的混合型數(shù)據(jù)．混合型數(shù)據(jù)中Xi={Xi1,…,Xim,Xi(m+1),…,Xis}表示第i個樣本的s個屬性，其中下標(biāo)為1～m的屬性為數(shù)值型屬性，下標(biāo)為m+1～s的屬性為符號型屬性，即基聚類．

1.2 基于混合型數(shù)據(jù)表示的聚類集成算法

對數(shù)據(jù)集進行T次K-Means聚類得到基聚類結(jié)果，為了將原數(shù)據(jù)類結(jié)構(gòu)考慮到集成過程中，在集成策略的選擇上將基聚類結(jié)果作為原數(shù)據(jù)的符號型屬性，將符號型數(shù)據(jù)與原數(shù)據(jù)結(jié)合，看作一個混合型數(shù)據(jù)來進行聚類.聚類方法采用K-Prototypes，對混合型數(shù)據(jù)進行T次K-Prototypes聚類,得到T個聚類集成結(jié)果．將T個聚類集成結(jié)果看作新的符號型數(shù)據(jù)集，代替原先的符號型數(shù)據(jù)再進行聚類集成，循環(huán)Q次結(jié)束，通過不斷迭代優(yōu)化,以得到更好的基聚類．在最后一次得到的T個集成結(jié)果中，將目標(biāo)函數(shù)值最小的集成結(jié)果選為最后的類標(biāo)簽．算法具體步驟如下：

Step1對數(shù)據(jù)集進行T次K-Means聚類，將基聚類結(jié)果看作數(shù)據(jù)集的符號型屬性，將原數(shù)據(jù)與其合并成一個混合型數(shù)據(jù).

Step2在混合型數(shù)據(jù)中隨機選取k個樣本作為初始類原型.

Step3對數(shù)據(jù)集中的每個樣本，根據(jù)式(1)～(3)計算其與每個類原型的相異性，并將樣本分配到與其最近的類原型所代表的類中.

(1)

(2)

(3)

Step4重新計算每個類的類原型.數(shù)值型屬性部分取類內(nèi)全部對象的均值，符號型屬性部分取出現(xiàn)次數(shù)最多的屬性組成類原型.

Step5循環(huán)Step 3、Step 4，直到每個類中的樣本不再發(fā)生變化為止.

Step6將Step 2～Step 5循環(huán)T次，用每次得到的結(jié)果矩陣替換Step 1中的基聚類.

Step7將Step 6循環(huán)Q次結(jié)束，在最終的結(jié)果矩陣中選取結(jié)果類標(biāo)簽．

算法的最大優(yōu)勢在于在集成過程中既保證了最終結(jié)果對基聚類的一致性，也考慮了原數(shù)據(jù)類結(jié)構(gòu)與結(jié)果的一致性．算法的時間復(fù)雜度為O(knstTQ)，空間復(fù)雜度為O(ns)，其中k為聚類的目標(biāo)類數(shù)；n表示數(shù)據(jù)集中的對象數(shù)；s為混合型數(shù)據(jù)的屬性個數(shù)；t為Step 5中的迭代次數(shù)；T為Step 6中的循環(huán)次數(shù)；Q為Step 7中的循環(huán)次數(shù)．

2 實驗分析

2.1 實驗數(shù)據(jù)

為了驗證所提出算法的有效性，從UCI真實數(shù)據(jù)集中選取了不同的數(shù)據(jù)集進行了測試．UCI數(shù)據(jù)集描述如表1所示．

2.2 評價指標(biāo)

表1 UCI數(shù)據(jù)集描述Tab.1 Description of UCI data sets

2.3 實驗結(jié)果分析

將本文算法與其他聚類集成算法進行了比較，選用的比較算法有MCLA[3]、HGPA[3]、CSPA[3]、Voting[10]、WCT[8]、WTQ[8]、CSM[8]、LWGP[14]，在UCI數(shù)據(jù)集中的7個真實數(shù)據(jù)集上進行測試．對本文算法進行30次K-Means聚類,生成具有差異度的基聚類，對混合型數(shù)據(jù)進行30次K-Prototypes聚類，迭代10次得到最后的結(jié)果．實驗結(jié)果是在每個數(shù)據(jù)集上運行多次,得到結(jié)果的平均值，不同算法的ARI值比較如表2所示，不同算法的NMI值比較如表3所示．每個數(shù)據(jù)集上不同方法的最優(yōu)值用黑色粗體進行標(biāo)識．

表2 不同算法的ARI值比較Tab.2 Comparison on different algorithms with respect to ARI

通過表2可知，在ARI指標(biāo)上，本文算法在7個數(shù)據(jù)集中有6個數(shù)據(jù)集都得到了最優(yōu)值，在未取得最優(yōu)值的數(shù)據(jù)集上其結(jié)果與最優(yōu)值也相差不大，均值在所有算法中是最優(yōu)的．同樣通過表3可知，在NMI指標(biāo)上，本文算法在7個數(shù)據(jù)集中也有6個數(shù)據(jù)集都得到了最優(yōu)值，且均值在所有算法中是最優(yōu)的．分析數(shù)據(jù)可知，本文設(shè)計的聚類集成算法相比其他算法有較好的聚類結(jié)果．

表3 不同算法的NMI值比較Tab.3 Comparison on different algorithms with respect to NMI

3 結(jié)束語

提出了一種基于混合型數(shù)據(jù)表示的聚類集成算法．在聚類集成過程中，不斷迭代優(yōu)化基聚類結(jié)果，在一致性函數(shù)設(shè)計時將原數(shù)據(jù)類結(jié)構(gòu)納入考慮，保證了集成結(jié)果對原數(shù)據(jù)類結(jié)構(gòu)與基聚類的一致性．在UCI數(shù)據(jù)集上與已有的聚類集成算法進行比較，實驗結(jié)果表明，本文提出的算法可以獲得較好的聚類集成結(jié)果．