史倩玉　梁吉業(yè)　趙興旺

(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院　太原　030006)(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué))　太原　030006)

?

一種不完備混合數(shù)據(jù)集成聚類算法

史倩玉梁吉業(yè)趙興旺

(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院太原030006)(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué))太原030006)

(ljy@sxu.edu.cn)

集成聚類技術(shù)由于具有較好的泛化能力，目前引起了研究者的高度關(guān)注.已有研究主要關(guān)注數(shù)值型完備數(shù)據(jù)的集成聚類問(wèn)題.然而，實(shí)際應(yīng)用中面臨的數(shù)據(jù)往往是兼具數(shù)值屬性和分類屬性共同描述的混合型數(shù)據(jù)，而且通常帶有缺失值.為此，針對(duì)不完備混合數(shù)據(jù)提出了一種集成聚類算法，首先利用3種缺失值填充方法對(duì)不完備混合數(shù)據(jù)進(jìn)行完備化處理；其次在3種填充后的不同完備數(shù)據(jù)集上分別多次執(zhí)行K-Prototypes算法產(chǎn)生基聚類結(jié)果；最后對(duì)基聚類結(jié)果進(jìn)行集成.在UCI真實(shí)數(shù)據(jù)集上與傳統(tǒng)聚類算法通過(guò)實(shí)驗(yàn)進(jìn)行了比較分析，實(shí)驗(yàn)結(jié)果表明提出的算法是有效的.

集成聚類；不完備數(shù)據(jù)；混合數(shù)據(jù)；缺失值填充；K原型聚類算法

聚類分析是針對(duì)給定的數(shù)據(jù)集，根據(jù)元素之間的相似性度量自動(dòng)將相似的元素劃分到同一組，使得組內(nèi)的元素相似性達(dá)到最大而組間元素的相似性達(dá)到最小的過(guò)程.目前，聚類分析技術(shù)已經(jīng)在生物信息學(xué)、社會(huì)網(wǎng)絡(luò)、圖像處理等領(lǐng)域得到了廣泛的應(yīng)用[1].

目前，研究者針對(duì)不同應(yīng)用領(lǐng)域已經(jīng)提出了許多聚類算法[2-3]，但是已有算法存在一定的局限性.例如，針對(duì)同一數(shù)據(jù)集算法在不同參數(shù)設(shè)置下會(huì)得到不同的聚類結(jié)果，或者是傳統(tǒng)的聚類算法在復(fù)雜結(jié)構(gòu)的數(shù)據(jù)集上很難得到有效的聚類結(jié)果.

針對(duì)這些問(wèn)題，研究者提出了聚類集成的方法[4-6].聚類集成的宗旨是合并某個(gè)數(shù)據(jù)集的多重“基聚類”結(jié)果，將其轉(zhuǎn)化成統(tǒng)一的、綜合的最終聚類結(jié)果，其主要包括3個(gè)階段：生成基聚類、獲取集成關(guān)系和確定最終聚類[7].例如，文獻(xiàn)[4]介紹的CSPA算法是基于共協(xié)關(guān)系矩陣生成一個(gè)無(wú)向帶權(quán)圖，然后利用METIS算法對(duì)圖進(jìn)行分割從而得到最終的一致性聚類結(jié)果.Fred等人在文獻(xiàn)[5]中提出的EAC算法同樣基于共協(xié)關(guān)系矩陣，將該矩陣作為層次聚類算法的輸入得到最終聚類結(jié)果.文獻(xiàn)[6]構(gòu)造了一個(gè)對(duì)象和類的加權(quán)二部圖，運(yùn)用譜聚類劃分該圖確定最終聚類.然而，現(xiàn)有的方法主要針對(duì)數(shù)值型屬性或分類型屬性單一類型的完備數(shù)據(jù)進(jìn)行集成聚類.近年來(lái)，針對(duì)完備混合型數(shù)據(jù)的集成聚類問(wèn)題，國(guó)內(nèi)外學(xué)者已經(jīng)開(kāi)展了一些探索性的工作[8-10].文獻(xiàn)[8]提出的混合數(shù)據(jù)集成方法首先分別對(duì)數(shù)值型屬性和分類型屬性部分進(jìn)行聚類，然后將以上聚類結(jié)果看成是分類型數(shù)據(jù)，在其上應(yīng)用分類型數(shù)據(jù)聚類算法來(lái)進(jìn)行聚類集成并得到最終聚類結(jié)果.為了避免直接計(jì)算混合型數(shù)據(jù)間相似性的難題，文獻(xiàn)[10]利用聚類集成技術(shù)產(chǎn)生混合數(shù)據(jù)間的相似性矩陣，最后基于此矩陣應(yīng)用譜聚類算法得到混合數(shù)據(jù)聚類結(jié)果.但是，在實(shí)際應(yīng)用中，面臨的數(shù)據(jù)不僅是由數(shù)值型屬性和分類屬性共同描述的混合型數(shù)據(jù)，而且通常帶有缺失值，是一種不完備混合數(shù)據(jù).因此，如何針對(duì)不完備混合數(shù)據(jù)進(jìn)行集成聚類就顯得尤為必要.

為了解決這一問(wèn)題，本文提出了一個(gè)基于缺失值填充的不完備混合數(shù)據(jù)的集成聚類算法.1)為了產(chǎn)生基聚類數(shù)據(jù)源的多樣性，利用3種缺失值填充方法對(duì)缺失數(shù)據(jù)進(jìn)行填充;2)分別針對(duì)每種填充方法得到的完備數(shù)據(jù)多次執(zhí)行K原型(K-Prototypes)聚類算法[11]，從而形成一系列基聚類結(jié)果;3)構(gòu)造一個(gè)相似度矩陣合并基聚類，進(jìn)而通過(guò)集成技術(shù)得到最終的聚類結(jié)果.在UCI真實(shí)數(shù)據(jù)集上與傳統(tǒng)聚類算法進(jìn)行了實(shí)驗(yàn)比較分析，實(shí)驗(yàn)結(jié)果表明本文提出的算法是有效的.

1　相關(guān)工作

本節(jié)首先對(duì)本文中使用的缺失值填充方法及K-Prototypes聚類算法進(jìn)行介紹.

1.1缺失值填充方法

針對(duì)缺失數(shù)據(jù)的處理問(wèn)題，國(guó)內(nèi)外學(xué)者提出了許多不同策略，其中填充法是一種最常用的技術(shù)[12].填充法利用數(shù)據(jù)集中的完備數(shù)據(jù)對(duì)每個(gè)缺失值進(jìn)行估計(jì)，從而達(dá)到非完備數(shù)據(jù)完備化的目的.目前，研究者已經(jīng)提出了多種填充方法，其中，平均值填充法及以K最近鄰為基礎(chǔ)的填充法由于簡(jiǎn)單有效得到了廣泛的應(yīng)用[13-16].下面分別對(duì)常用的3種缺失值填充方法進(jìn)行介紹.

1) 平均值填充法

由于數(shù)值型屬性和分類型屬性的差異性，下面將分別對(duì)不同屬性下缺失值的填充方法進(jìn)行描述.如果缺失值對(duì)應(yīng)的屬性為分類型屬性，根據(jù)統(tǒng)計(jì)學(xué)中眾數(shù)(modes)的原理，用該屬性下非缺失值樣本中取值頻數(shù)最多的值來(lái)對(duì)缺失值進(jìn)行填充；如果缺失值對(duì)應(yīng)的屬性為數(shù)值型屬性，則利用該屬性下所有完備樣本取值的平均值(means)來(lái)對(duì)缺失值進(jìn)行填充.該方法利用現(xiàn)有完備數(shù)據(jù)的多數(shù)信息來(lái)推測(cè)缺失值，以最可能的取值來(lái)對(duì)缺失值進(jìn)行填充，具有簡(jiǎn)單易實(shí)現(xiàn)的優(yōu)點(diǎn).但是，由于所有的填充值都集中于眾數(shù)或均值，填充后的數(shù)據(jù)集在分布上容易形成尖峰，進(jìn)而出現(xiàn)變量分布扭曲的問(wèn)題，導(dǎo)致樣本之間差異的弱化.

2)K最近鄰填充法KNN

在K最近鄰填充法中，一個(gè)樣本的缺失值是通過(guò)找到與該樣本最相似的K個(gè)完備樣本，利用這K個(gè)完備樣本的相關(guān)信息對(duì)缺失值進(jìn)行填充.

(1)

樣本x和y在分類型屬性上的相異度DAc可表示為

(2)

樣本x和y的相異度計(jì)算如下：

(3)

其中，M(·)是一個(gè)函數(shù)，可以將樣本x和y在數(shù)值型屬性上的相異度DAr和分類型屬性上的相異度DAc有效地結(jié)合起來(lái)以度量它們之間的相異性.

基于上述距離度量公式，K最近鄰填充法主要流程描述如下：

算法1.K最近鄰填充算法KNN.

Step1. 將數(shù)據(jù)集D劃分為2個(gè)子集Dm和Dc，其中Dm表示由包括屬性值缺失的樣本組成的樣本子集，Dc表示完備樣本組成的樣本子集.

Step2. 從集合Dm中提取出一個(gè)帶有缺失值的樣本xm.

Step2.1. 將帶有缺失值的樣本xm分成屬性值完備和屬性值缺失2部分.

Step2.2. 僅使用樣本xm中屬性值完備的部分來(lái)計(jì)算該樣本和Dc集中所有樣本的相異性.假設(shè)Dc集中的一個(gè)完備樣本為xc，基于式(1)(2)，利用以下公式

D(xm,xc)=

(4)

來(lái)計(jì)算xm和xc的相異性.

Step2.3. 從完備樣本集Dc中選擇與帶有缺失值的樣本xm相異度最小的前K個(gè)完備樣本組成集合DK.

Step2.4. 如果樣本向量xm的缺失值對(duì)應(yīng)的屬性為分類型屬性，用該屬性下與xm相異度最小的K個(gè)樣本DK中眾數(shù)對(duì)缺失值進(jìn)行填充；如果缺失值對(duì)應(yīng)的屬性為數(shù)值型屬性，則取該屬性下DK中K個(gè)樣本的平均值來(lái)對(duì)缺失值進(jìn)行填充.

Step3. 重復(fù)進(jìn)行Step2，直至集合Dm中所有樣本的缺失值都填充完畢.

作為一種填充方法，K最近鄰填充法考慮了樣本之間的相關(guān)性，填充結(jié)果較為準(zhǔn)確，而且該方法具有簡(jiǎn)單易實(shí)現(xiàn)、計(jì)算高效的優(yōu)點(diǎn).然而，在屬性值缺失較多的情況下，該方法的性能和準(zhǔn)確性具有一定的缺陷.

3) 有序最近鄰填充法SKNN

有序最近鄰填充法SKNN是在KNN算法的基礎(chǔ)上做了進(jìn)一步的改進(jìn)，算法主要流程如下：

算法2. 有序最近鄰填充算法SKNN.

Step1. 將數(shù)據(jù)集D劃分為2個(gè)子集Dm和Dc，其中，Dm表示由存在屬性值缺失的樣本組成的樣本子集，Dc表示完備樣本子集.

Step2. 將集合Dm中所有帶有缺失值的樣本按照缺失率(帶有缺失值的屬性個(gè)數(shù)占樣本屬性總數(shù)的比例)由低到高的順序進(jìn)行排序.

Step3. 從集合Dm中選擇一個(gè)缺失率最低的樣本，利用K最近鄰法KNN從完備樣本子集Dc中選出與該樣本相異度最小的前K個(gè)完備樣本對(duì)其缺失值進(jìn)行填充.

Step4. 把填充后得到的完備樣本加入完備數(shù)據(jù)子集Dc中.

Step5. 重復(fù)進(jìn)行Step3～Step4，直至集合Dm中所有帶有缺失值的樣本填充完畢.

SKNN算法在填充過(guò)程中可以使用先前缺失數(shù)據(jù)填充得到的完備樣本信息.與KNN填充算法相比，SKNN填充算法明顯提高了對(duì)數(shù)據(jù)的利用率，在數(shù)據(jù)缺失率較大、完備數(shù)據(jù)樣本相對(duì)匱乏的情況下，SKNN填充算法采取邊填充邊擴(kuò)展完備數(shù)據(jù)樣本的策略，充分地利用了缺失數(shù)據(jù)的信息，使得填充效果更加符合客觀事實(shí)，填充效果更為合理.

1.2K-Prototypes算法介紹

文獻(xiàn)[11]提出的K-Prototypes聚類算法是處理混合型數(shù)據(jù)最經(jīng)濟(jì)有效的一種算法.該算法在度量對(duì)象與類中心的相異性的過(guò)程中同時(shí)考慮了分類型屬性和數(shù)值型屬性部分的貢獻(xiàn).其中，對(duì)象與類中心在分類型屬性下的相異性通過(guò)0-1簡(jiǎn)單匹配來(lái)度量，數(shù)值型屬性下的相異性由歐氏距離表示.如果對(duì)象為分類型數(shù)據(jù)，則該算法將退化為K-Modes算法[11]；類似地，如果對(duì)象為數(shù)值型數(shù)據(jù)，則該算法退化為K-Means算法[17].因此，K-Prototypes算法實(shí)質(zhì)上同時(shí)結(jié)合K-Modes算法和K-Means算法來(lái)解決現(xiàn)實(shí)世界中廣泛存在的混合型數(shù)據(jù)的聚類問(wèn)題.

假設(shè)在聚類過(guò)程中，由n個(gè)樣本組成的混合型數(shù)據(jù)集合D={x1,x2,…,xn}在當(dāng)前聚類中被劃分為k個(gè)類Ck={C1,C2,…,Ck}，類原型為Zk={z1,z2,…,zk}，基于式(1)(2)，利用以下公式

(5)

來(lái)度量樣本xi(1≤i≤n)和類原型zj(1≤j≤k)之間的相異性[18].

基于以上的相異性度量，K-Prototypes聚類算法描述如下：

算法3.K-Prototypes聚類算法.

Step1. 從數(shù)據(jù)集中隨機(jī)選取k個(gè)不同的樣本作為初始聚類中心.

Step2. 對(duì)數(shù)據(jù)集中的每個(gè)樣本，根據(jù)式(5)計(jì)算其與每個(gè)類原型的相異性，將樣本分配到與其最近的類原型所代表的類中.

Step3. 對(duì)于每個(gè)聚類結(jié)果，重新計(jì)算聚類原型.

Step4. 根據(jù)式(5)重新計(jì)算每個(gè)樣本到新的類原型之間的相異性，根據(jù)最近鄰原則重新分配樣本.

Step5. 重復(fù)進(jìn)行Step3～Step4，直到各個(gè)聚類中的樣本不再發(fā)生變化為止.

2　不完備混合數(shù)據(jù)集成聚類算法

不完備混合數(shù)據(jù)的集成聚類算法主要分為4個(gè)階段：第1階段分別使用1.1節(jié)介紹的3種不同的缺失值填充方法對(duì)缺失值進(jìn)行填充得到完備數(shù)據(jù)；第2階段分別在填充后的完備數(shù)據(jù)集上基于隨機(jī)產(chǎn)生初始類中心的方式多次進(jìn)行K-Prototypes聚類算法，從而得到基聚類結(jié)果集Π(D)；第3階段合并基聚類結(jié)果構(gòu)造相似度矩陣SMn×n；第4階段基于相似度矩陣運(yùn)用層次聚類方法進(jìn)行集成得到最終的聚類結(jié)果.本文算法的框架示意圖如圖1所示：

Fig. 1　The framework of the proposed algorithm.圖1　本文算法框架

2.1生成基聚類

2.2獲取集成關(guān)系

對(duì)于處理多個(gè)基聚類結(jié)果，現(xiàn)有的方法主要利用基聚類結(jié)果所提供的信息來(lái)得到數(shù)據(jù)集中樣本之間的關(guān)聯(lián)，構(gòu)造一個(gè)相似度矩陣，然后基于此矩陣進(jìn)行聚類集成，進(jìn)而獲得最終的聚類結(jié)果.

(6)

2) 根據(jù)所有基聚類產(chǎn)生的關(guān)系矩陣就可以得到樣本之間的相似度矩陣SMn×n，其中樣本xp和xq(1≤p,q≤n)之間的相似度表示為

(7)

該矩陣的每個(gè)元素值由所有基聚類產(chǎn)生的關(guān)系矩陣對(duì)應(yīng)元素的均值得到，反映了樣本之間的相似度.傳統(tǒng)的相似度度量方法往往完全依靠屬性值來(lái)衡量樣本之間的相似度，使得聚類結(jié)果不夠準(zhǔn)確，充分利用基聚類提供的信息來(lái)度量樣本之間的相似性具有一定的有效性.

2.3確定最終聚類

在獲取到集成關(guān)系的基礎(chǔ)上，利用層次聚類算法來(lái)確定最終聚類.本文采用層次聚類算法自底向上的策略，首先將每個(gè)樣本作為一個(gè)類，然后將2個(gè)相似度最大的類合并為一個(gè)類，重復(fù)循環(huán)此步驟，直到合并為k個(gè)類.

在層次聚類過(guò)程中假設(shè)有2個(gè)類C和C′，它們之間常用的3種相似性度量如下:

1) 單鏈(single link)方法.由2個(gè)類中相似度最大的2個(gè)樣本決定.

(8)

2) 全鏈(complete link)方法.由2個(gè)類中相似度最小的2個(gè)樣本決定.

(9)

3) 組平均(average link)方法.由2個(gè)類中所有樣本點(diǎn)相似度的平均值決定.

(10)

其中，樣本之間的相似度sim(x,x′)為相似度矩陣SMn×n中的對(duì)應(yīng)元素值.

2.4不完備混合數(shù)據(jù)的集成聚類算法

基于以上對(duì)不完備混合數(shù)據(jù)的集成聚類算法各個(gè)主要階段的介紹，本文算法描述如下：

算法4. 不完備混合數(shù)據(jù)集成聚類算法.

輸入：帶有缺失值的數(shù)據(jù)集D、聚類個(gè)數(shù)k;

輸出：最終聚類結(jié)果π*(D).

Step1. 對(duì)數(shù)據(jù)集D分別運(yùn)用平均值填充法、KNN填充法、SKNN填充法填充得到完備數(shù)據(jù)集D1，D2，D3.

Step2. 對(duì)Di(1≤i≤3)分別執(zhí)行Mi次K-Prototypes聚類算法，得到基聚類結(jié)果集Π(D).

Step3. 根據(jù)式(7)，計(jì)算樣本與樣本之間的相似度矩陣SMn×n.

Step4. 基于相似度矩陣SMn×n，分別根據(jù)式(8)(9)(10)運(yùn)行層次聚類算法得到最終的聚類結(jié)果π*(D).

3　實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文提出算法的有效性，我們從UCI真實(shí)數(shù)據(jù)集中分別選取了數(shù)值型、分類型和混合型3種不同屬性特征的不完備數(shù)據(jù)集進(jìn)行了測(cè)試.數(shù)據(jù)集的信息描述如表1所示：

Table 1　The Summary of UCI Datasets

3.2聚類有效性度量指標(biāo)

本文分別采用分類準(zhǔn)確率(classification accuracy,CA)[19]、調(diào)整蘭德系數(shù)(adjusted rand index,ARI)[19]，標(biāo)準(zhǔn)互信息(normalized mutual information,NMI)[4]三種評(píng)價(jià)指標(biāo)對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià).

(11)

其中,k為類個(gè)數(shù)，ai表示正確聚類為對(duì)應(yīng)類別Ci的樣本個(gè)數(shù)，n表示樣本總數(shù).

(12)

其中，

(13)

(14)

其中，nij表示聚類結(jié)果的第i個(gè)簇中包含原數(shù)據(jù)集類標(biāo)簽為j的樣本總數(shù)，ni表示聚類結(jié)果的第i個(gè)簇的樣本總數(shù)，nj表示原數(shù)據(jù)集類標(biāo)簽為j的樣本總數(shù)，n表示樣本總數(shù)；I和J分別表示聚類得到的簇個(gè)數(shù)和原數(shù)據(jù)集的類個(gè)數(shù).

CA，ARI，NMI的值越大，表明聚類結(jié)果越好.

在下面的實(shí)驗(yàn)中，我們將本文提出的算法根據(jù)層次聚類過(guò)程中所選取的類間相似度度量方法分為single-link集成(SLCE)、complete-link集成(CLCE)、average-link集成(ALCE).將3種集成方法分別與用平均值填充、KNN填充、SKNN填充得到的完備數(shù)據(jù)進(jìn)行單一的K-Prototypes聚類(分別簡(jiǎn)記為Mean_SK，KNN_SK，SKNN_SK)所得的聚類結(jié)果進(jìn)行比較.

在實(shí)驗(yàn)過(guò)程中，針對(duì)表1所描述的CMC和Glass兩個(gè)完備數(shù)據(jù)集，分別隨機(jī)刪除10%的屬性值作為缺失數(shù)據(jù).以下實(shí)驗(yàn)結(jié)果均為同一方法在相同的數(shù)據(jù)集上分別運(yùn)行20次的CA，ARI，NMI的平均值和方差.其中本文提出的算法分別在每種填充方法得到的完備數(shù)據(jù)上進(jìn)行50次K-Prototypes聚類算法來(lái)得到基聚類.

3.3實(shí)驗(yàn)結(jié)果分析

當(dāng)KNN和SKNN填充法選取的最近鄰個(gè)數(shù)K=5時(shí)，本文提出算法和其他聚類方法在不同評(píng)價(jià)指標(biāo)下的實(shí)驗(yàn)結(jié)果的平均值及方差如表2～4所示：

Table 2　Clustering Results of Different Algorithms with Respect to Mean±Var of CA

Table 3　Clustering Results of Different Algorithms with Respect to Mean±Var of ARI

Table 4　Clustering Results of Different Algorithms with Respect to Mean±Var of NMI

Fig. 2　The performance of different algorithms with respect to different number of neighborhood on the Dermatology dataset.圖2　數(shù)據(jù)集Dermatology上不同算法的聚類結(jié)果

其中，在每一數(shù)據(jù)集上不同方法的實(shí)驗(yàn)結(jié)果的最優(yōu)值和次優(yōu)值用粗體標(biāo)識(shí).通過(guò)表中數(shù)據(jù)分析可知，不論選取哪種指標(biāo)作為評(píng)價(jià)標(biāo)準(zhǔn)，對(duì)于UCI中7個(gè)數(shù)據(jù)集，在多數(shù)情況下average-link集成和complete-link集成的聚類準(zhǔn)確性優(yōu)于其他算法，2種方法在所有數(shù)據(jù)集上的平均值都能達(dá)到最優(yōu)值或次優(yōu)值.average-link集成的性能比complete-link集成略好，這是因?yàn)閏omplete-link集成確定類間距離時(shí)僅考慮有特點(diǎn)的數(shù)據(jù)，average-link集成考慮了類內(nèi)數(shù)據(jù)的整體特點(diǎn)，因此在多數(shù)情況下，average-link集成得到的聚類準(zhǔn)確性比較高，而complete-link集成表現(xiàn)出的性能次之.single-link集成確定類間距離時(shí)也只考慮了有特點(diǎn)的數(shù)據(jù)，而且沒(méi)有考慮類內(nèi)部的結(jié)構(gòu)，所以表現(xiàn)出的聚類結(jié)果較差.此外，average-link集成在7個(gè)數(shù)據(jù)集上的方差都幾乎為0，說(shuō)明該方法具有較強(qiáng)的穩(wěn)定性.

當(dāng)KNN和SKNN填充法選取的最近鄰個(gè)數(shù)K取不同值時(shí)，本文提出算法和其他聚類方法的實(shí)驗(yàn)結(jié)果如圖2～8所示.由圖2～8可知：

1) average-link集成和complete-link集成受到最近鄰個(gè)數(shù)變化的影響較小，它們?cè)诙鄶?shù)情況下都能取到最優(yōu)和次優(yōu)的聚類結(jié)果.average-link集成在數(shù)據(jù)集Dermatology，Credit Approval，Sponge，CMC上的聚類準(zhǔn)確度最高，在Automobile上的CA值和在Soybean上的ARI值也是較高的.complete-link集成在數(shù)據(jù)集Dermatology，Sponge，Soybean，Glass上表現(xiàn)出較高的性能，尤其在Glass上，complete-link集成的聚類性能明顯優(yōu)于average-link集成，這可能是由于Glass數(shù)據(jù)集的類結(jié)構(gòu)比較緊湊，complete-link集成是取2個(gè)類中距離最遠(yuǎn)的2個(gè)樣本點(diǎn)作為2個(gè)類的距離，這種集成方法就比較傾向于找到一些緊湊的類，所以該方法在這個(gè)數(shù)據(jù)集上的效果較優(yōu).

2) single-link集成除了在Sponge數(shù)據(jù)集上表現(xiàn)略好以外，在其他數(shù)據(jù)集上的聚類結(jié)果都不理想.這主要是由于single-link度量方法僅僅依靠距離最近的2個(gè)樣本點(diǎn)來(lái)決定類間的差異性而沒(méi)有考慮類內(nèi)部的結(jié)構(gòu)，因此聚類效果不佳.

3) Mean_SK，KNN_SK，SKNN_SK三種方法除了在Credit Approval數(shù)據(jù)集上表現(xiàn)較好外，在其他數(shù)據(jù)集上都明顯不如average-link集成或complete-link集成.這是由于average-link集成和complete-link集成不僅對(duì)多次K-Prototypes聚類算法產(chǎn)生的多個(gè)基聚類進(jìn)行集成，而且還將不同填充方法得到的完備數(shù)據(jù)集也作為產(chǎn)生基聚類的一種方法，這樣就使得基聚類結(jié)果集更具有多樣性，聚類結(jié)果的準(zhǔn)確度也越高.

4) 隨著最近鄰個(gè)數(shù)K的變化，average-link集成和complete-link集成的實(shí)驗(yàn)結(jié)果是比較穩(wěn)定的，它的性能對(duì)最近鄰個(gè)數(shù)K的變化并不敏感，算法具有一定的魯棒性.總之，average-link集成聚類方法在大多數(shù)數(shù)據(jù)集上都是較好的選擇.

Fig. 3　The performance of different algorithms with respect to different number of neighborhood on the Credit Approval dataset.圖3　數(shù)據(jù)集Credit Approval上不同算法的聚類結(jié)果

Fig. 4　The performance of different algorithms with respect to different number of neighborhood on the Automobile dataset.圖4　數(shù)據(jù)集Automobile上不同算法的聚類結(jié)果

Fig. 5　The performance of different algorithms with respect to different number of neighborhood on the Sponge dataset.圖5　數(shù)據(jù)集Sponge上不同算法的聚類結(jié)果

Fig. 6　The performance of different algorithms with respect to different number of neighborhood on the CMC dataset.圖6　數(shù)據(jù)集CMC上不同算法的聚類結(jié)果

Fig. 7　The performance of different algorithms with respect to different number of neighborhood on the Soybean dataset.圖7　數(shù)據(jù)集Soybean上不同算法的聚類結(jié)果

Fig. 8　The performance of different algorithms with respect to different number of neighborhood on the Glass dataset.圖8　數(shù)據(jù)集Glass上不同算法的聚類結(jié)果

4　結(jié)　　論

本文針對(duì)不完備混合數(shù)據(jù)首先利用3種缺失值填充方法對(duì)缺失值進(jìn)行填充得到完備數(shù)據(jù)集，有效地克服了單一填充方法帶來(lái)的缺陷；其次在3種不同的完備數(shù)據(jù)集上基于隨機(jī)產(chǎn)生初始類中心的方式多次執(zhí)行K-Prototypes算法，從而形成一系列基聚類結(jié)果；最后構(gòu)造一個(gè)相似度矩陣合并這些基聚類，進(jìn)而利用層次聚類方法進(jìn)行集成得到最終的聚類結(jié)果.在UCI真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證，與傳統(tǒng)聚類算法相比，本文提出的算法可以獲得較高的聚類質(zhì)量.

然而，目前集成聚類算法面臨著計(jì)算量大、時(shí)間復(fù)雜度較高的問(wèn)題，在未來(lái)的工作中，我們將考慮如何提高算法的計(jì)算效率來(lái)解決大數(shù)據(jù)集成面臨的挑戰(zhàn).

[1]Han Jiawei, Kamber M, Pei Jian. Data Mining: Concepts and Techniques [M]. 3rd ed. San Francisco, CA: Morgan Kaufmann, 2011[2]Sun Jigui, Liu Jie, Zhao Lianyu. Clustering algorithms research [J]. Journal of Software, 2008, 19(1): 48-61 (in Chinese)(孫吉貴, 劉杰, 趙連宇. 聚類算法研究 [J]. 軟件學(xué)報(bào), 2008, 19(1): 48-61)[3]Xu Rui, Wunsch D. Survey of clustering algorithm [J]. IEEE Trans on Neural Networks, 2005, 16(3): 645-678[4]Strehl A, Ghosh J. Cluster ensembles: A knowledge reuse framework for combining multiple partitions [J]. Journal of Machine Learning Research, 2002, 3: 583-617[5]Fred A L, Jain A K. Combining multiple clusterings using evidence accumulation [J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(6): 835-850[6]Iam-On N, Boongoen T. Comparative study of matrix refinement approaches for ensemble clustering [J]. Machine Learning, 2015, 98(12): 269-300[7]Ghosh J, Acharya A. Cluster ensembles [J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2011, 1(4): 305-315[8]He Zengyou, Xu xiaofei, Deng Shengchun. Clustering mixed numeric and categorical data: A cluster ensemble approach[OL]. ArXiv cs0509011, 2005: 1-14 [2015-09-08]. http:arxiv.orgabscs0509011[9]Shaqsi J, Wang Wenjia. A clustering ensemble method for clustering mixed data[C]Proc of the Int Joint Conf on Neural Networks. Piscataway, NJ: IEEE, 2010: 1-8[10]Luo Huilan, Wei Hui. Clustering algorithm for mixed data based on clustering ensemble technique [J]. Computer Science, 2010, 37(11): 234-274 (in Chinese)(羅會(huì)蘭, 危輝. 一種基于聚類集成技術(shù)的混合型數(shù)據(jù)聚類算法[J]. 計(jì)算機(jī)科學(xué), 2010, 37(11): 234-274)[11]Huang Zhexue. Extensions to thek-means algorithm for clustering large data sets with categorical values [J]. Data Mining and Knowledge Discovery, 1998, 2(3): 283-304[12]Wu Sen, Feng Xiaodong, Shan Zhiguang. Missing data imputation approach based on incomplete data clustering[J]. Chinese Journal of Computers, 2012, 35(8): 1726-1738 (in Chinese)(武森, 馮小東, 單志廣. 基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補(bǔ)方法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(8): 1726-1738)[13]Qiao Zhufeng, Tian Fengzhan, Huang Houkuan, et al. A comparison study of missing value datasets processing methods [J]. Journal of Computer Research and Development, 2006, 43(Suppl): 171-175 (in Chinese)(喬珠峰, 田鳳占, 黃厚寬, 等. 缺失數(shù)據(jù)處理方法的比較研究 [J]. 計(jì)算機(jī)研究與發(fā)展, 2006, 43(增刊): 171-175)

[14]Silva L O, Zárate L E. A brief review of the main approaches for treatment of missing data [J]. Intelligent Data Analysis, 2014, 18(6): 1177-1198[15]Acock A C. Working with missing values [J]. Journal of Marriage and Family, 2005, 67(4): 1012-1028[16]Batista G E, Monard M C. An analysis of four missing data treatment methods for supervised learning [J]. Applied Artificial Intelligence, 2003, 17(5): 519-533[17]Macqueen J. Some methods for classification and analysis of multivariate observations [C]Proc of the 5th Berkeley Symp on Mathematical Statistics and Probability. Berkeley, CA: University of California Press, 1967: 281-297[18]Liang Jiye, Zhao Xingwang, Li Deyu, et al. Determining the number of clusters using information entropy for mixed data [J]. Pattern Recognition, 2012, 45(6): 2251-2265[19]Liang Jiye, Bai Liang, Dang Chuangyin, et al. Thek-means-type algorithms versus imbalanced data distributions [J]. IEEE Trans on Fuzzy Systems, 2012, 20(4): 728-745

Shi Qianyu, born in 1992. Master candidate. Student member of China Computer Federation. Her main research interests include data mining and machine learning (m15735170907@163.com).

Liang Jiye, born in 1962. Professor and PhD supervisor. Distinguished member of China Computer Federation. His main research interests include granular computing, data mining and machine learning (ljy@sxu.edu.cn).

Zhao Xingwang, born in 1984. PhD candidate. Member of China Computer Federation. His main research interests include data mining and machine learning (zhaoxw84@163.com).

A Clustering Ensemble Algorithm for Incomplete Mixed Data

Shi Qianyu, Liang Jiye, and Zhao Xingwang

(SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006)(KeyLaboratoryofComputationalIntelligenceandChineseInformationProcessing(ShanxiUniversity),MinistryofEducation,Taiyuan030006)

Cluster ensembles have recently emerged a powerful clustering analysis technology and caught high attention of researchers due to their good generalization ability. From the existing work, these techniques held great promise, most of which generate the final results for complete data sets with numerical attributes. However, real life data sets are usually incomplete mixed data described by numerical and categorical attributes at the same time. And these existing algorithms are not very effective for an incomplete mixed data set. To overcome this deficiency, this paper proposes a new clustering ensemble algorithm which can be used to ensemble final clustering results for mixed numerical and categorical incomplete data. Firstly, the algorithm conducts completion of incomplete mixed data using three different missing value filling methods. Then, a set of clustering solutions are produced by executingK-Prototypes clustering algorithm on three different kinds of complete data sets multiple times, respectively. Next, a similarity matrix is constructed by considering all the clustering solutions. After that, the final clustering result is obtained by hierarchical clustering algorithms based on the similarity matrix. The effectiveness of the proposed algorithm is empirically demonstrated over some UCI real data sets and three benchmark evaluation measures. The experimental results show that the proposed algorithm is able to generate higher clustering quality in comparison with several traditional clustering algorithms.

clustering ensemble; incomplete data; mixed data; missing value imputation;K-Prototypes clustering algorithm

2015-06-19；

2015-11-16

國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61432011)；國(guó)家自然科學(xué)基金項(xiàng)目(61573229,61502289)；山西省科技基礎(chǔ)條件平臺(tái)建設(shè)項(xiàng)目(2012091002-0101)；山西省自然科學(xué)基金項(xiàng)目(201601D202039)；山西省研究生教育創(chuàng)新項(xiàng)目(2016SY002)

趙興旺(zhaoxw84@163.com)

TP391

This work was supported by the Key Program of the National Natural Science Foundation of China(61432011), the National Natural Science Foundation of China(61573229, 61502289), the Construction Project of the Science and Technology Basic Condition Platform of Shanxi Province(2012091002-0101), the Natural Science Foundation of Shanxi Province of China (201601D202039), and the Graduate Education Innovation Project of Shanxi Province (2016SY002).