改進(jìn)的均值插補(bǔ)不完備數(shù)據(jù)聚類(lèi)算法

施 虹, 楊 鑫, 王平心

(1.江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 鎮(zhèn)江 212003)(2.江蘇科技大學(xué) 理學(xué)院, 鎮(zhèn)江 212003)

聚類(lèi)分析是數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)的重要技術(shù)之一[1],廣泛應(yīng)用于商務(wù)智能、圖像處理[2]、生物信息學(xué)[3]、安全保障[4]等多個(gè)領(lǐng)域．同時(shí)作為一種無(wú)監(jiān)督學(xué)習(xí)技術(shù),在識(shí)別無(wú)標(biāo)簽數(shù)據(jù)的隱藏結(jié)構(gòu)方面發(fā)揮了極大的作用．現(xiàn)有的聚類(lèi)算法大致可以分為兩大類(lèi):層次聚類(lèi)方法和劃分聚類(lèi)方法[5]．根據(jù)相似性度量可以將相似度高的樣本劃分到同一類(lèi)簇中,使得同一類(lèi)簇中樣本的相似度達(dá)到最大而不同類(lèi)簇中樣本的相似度達(dá)到最小[6]．

然而,在實(shí)際場(chǎng)景中,由于隨機(jī)噪音、數(shù)據(jù)丟失、數(shù)據(jù)獲取困難、數(shù)據(jù)誤讀等原因造成了一些數(shù)據(jù)值的缺失．根據(jù)文獻(xiàn)[7-8]提出的分類(lèi)法,缺失數(shù)據(jù)被分為完全隨機(jī)缺失(MCAR)、隨機(jī)缺失(MAR)以及非隨機(jī)缺失(NMAR)．由于缺失數(shù)據(jù)的出現(xiàn),傳統(tǒng)的聚類(lèi)算法無(wú)法直接處理這些數(shù)據(jù)．因此,如何解決缺失數(shù)據(jù)的聚類(lèi)問(wèn)題成為聚類(lèi)分析研究中一個(gè)亟待解決的難題．針對(duì)缺失型數(shù)據(jù),文中研究的數(shù)據(jù)對(duì)象是完全隨機(jī)缺失型數(shù)據(jù)(MCAR)．

如何對(duì)缺失數(shù)據(jù)進(jìn)行有效填充是解決不完備數(shù)據(jù)聚類(lèi)的一個(gè)關(guān)鍵之處．目前不完備數(shù)據(jù)填充方法有很多如:均值插補(bǔ)、回歸插補(bǔ)、多重插補(bǔ)、熱卡填充、冷卡填充[9];通過(guò)迭代產(chǎn)生最大似然估計(jì)值的EM算法[10];使用頻繁出現(xiàn)的屬性值替代缺失值的最常見(jiàn)屬性值法[11];由文獻(xiàn)[12]提出基于互信息的最近鄰方法評(píng)測(cè)缺失值以及文獻(xiàn)[13]通過(guò)不完備數(shù)據(jù)對(duì)象的k個(gè)鄰居的均值填充缺失數(shù)據(jù)．

國(guó)外的學(xué)者在已有聚類(lèi)算法的基礎(chǔ)上提出了不完備數(shù)據(jù)的聚類(lèi)策略，如文獻(xiàn)[14]提出了4種基于FCM算法的聚類(lèi)方法:Whole Data Strategy(WDS)、Partial Distance Strategy(PDS)、Optimal Completion Strategy(OCS)、Nearest Prototype Strategy(NPS)．同時(shí)國(guó)內(nèi)學(xué)者也探討了眾多方法如:文獻(xiàn)[15]使用區(qū)間形式來(lái)估計(jì)缺失的屬性值、在OCS-FCM算法的基礎(chǔ)上引入屬性權(quán)重的思想[16]、將遺傳算法和FCM算法相結(jié)合在得到最終聚類(lèi)結(jié)果時(shí)得到對(duì)缺失數(shù)據(jù)的最佳估計(jì)值[17];文獻(xiàn)[18]提出RFCM算法處理不完備數(shù)據(jù);文獻(xiàn)[19]提出基于q近鄰不完備數(shù)據(jù)三支決策聚類(lèi)方法;文獻(xiàn)[20]提出一種不完備混合數(shù)據(jù)集成聚類(lèi)算法．

1 相關(guān)工作

1.1 聚類(lèi)算法

James Macqueen于1967年提出k-means算法[21],是數(shù)據(jù)挖掘中的一種常用聚類(lèi)分析算法，應(yīng)用于計(jì)算機(jī)視覺(jué)、市場(chǎng)劃分、天文學(xué)以及地質(zhì)統(tǒng)計(jì)學(xué)等多個(gè)領(lǐng)域[21]．k-means算法簡(jiǎn)單快速,處理大規(guī)模數(shù)據(jù)集也能保持可伸縮性以及高效性．然而,k-means算法也存在一些不可避免的缺陷:① 類(lèi)簇?cái)?shù)k值需要事先給定;② 該算法對(duì)初始值比較敏感,不同的初始值會(huì)不產(chǎn)生不同的聚類(lèi)結(jié)果;③ 算法很容易陷入局部最優(yōu)解．具體步驟見(jiàn)算法1．

算法1:k-means算法輸入:數(shù)據(jù)集U={x1,x2,…,xn}∈Rm,聚類(lèi)數(shù)k.輸出:聚類(lèi)結(jié)果C={C1,C2,…,Ck}.Step1:從U中隨機(jī)選擇k個(gè)數(shù)據(jù)對(duì)象作為初始“簇中心”向量:z1,z2,z3,…,zk,其中k

原始的k-means算法易于收斂到局部最優(yōu)解并且對(duì)初始數(shù)據(jù)敏感．為了能在任意形狀樣本空間聚類(lèi)并收斂到全局最優(yōu)解,提出了譜聚類(lèi)方法[22]．它是基于圖論的無(wú)監(jiān)督學(xué)習(xí)方法,其實(shí)質(zhì)是將聚類(lèi)問(wèn)題轉(zhuǎn)化為圖的最優(yōu)分割問(wèn)題．算法2中為譜聚類(lèi)算法的詳細(xì)過(guò)程．

算法2:譜聚類(lèi)算法輸入:S={s1,s2,…,sn}∈Rm,聚類(lèi)數(shù)k,參數(shù)σ.輸出:聚類(lèi)結(jié)果C={C1,C2,…,Ck}.Step1:構(gòu)造對(duì)應(yīng)的相似矩陣A,其中Aii=0,Aij=exp(-‖si-sj‖2/2σ2)(i≠j);Step2:定義對(duì)角矩陣D,其中元素dii的值等于矩陣A第i行元素的和(i=1,2,…,n),構(gòu)造矩陣L=D-12AD-12;Step3:求解矩陣L的前k個(gè)最大特征值以及與之對(duì)應(yīng)的特征向量,構(gòu)造矩陣X={x1,x2,…,xk}∈Rn×k;Step4:單位化X得到矩陣Z,Zij=Xij/(∑jX2ij)1/2;Step5:將矩陣Z中的每一行看成是Rk空間中的樣本點(diǎn),使用k-means聚類(lèi)算法進(jìn)行聚類(lèi);Step6:最后,樣本點(diǎn)si聚類(lèi)于類(lèi)j中當(dāng)且僅當(dāng)矩陣Z的第i行被聚于類(lèi)j中;Step7:返回聚類(lèi)結(jié)果C={C1,C2,…,Ck}.

1.2 不完備信息系統(tǒng)

信息系統(tǒng)(Information System)也稱(chēng)知識(shí)表達(dá)系統(tǒng)(Knowledge Representation System)．它用一個(gè)四元組來(lái)表示S={U,A,V,f}也可以簡(jiǎn)寫(xiě)成S={U,A}．U={x1,x2,…,xn}是有限非空數(shù)據(jù)集稱(chēng)為論域,n為論域中的樣本個(gè)數(shù);A={a1,a2,…,am}是有限非空屬性集,m表示數(shù)據(jù)對(duì)象的屬性個(gè)數(shù);V={V1,V2,…,Vm}為屬性的值域集,Vi是屬性ai的值域;f是信息函數(shù),f:Vik=f(xi,ak)∈Vk,Vik為數(shù)據(jù)對(duì)象xi在屬性ak上的取值．例如,xi表示論域中的第i個(gè)數(shù)據(jù)對(duì)象有m維屬性,即xi={xi1,xi2,…,xim},其中xil(i≤n,l≤m)為樣本xi在l維屬性上的取值．

當(dāng)數(shù)據(jù)對(duì)象含有缺失數(shù)據(jù)時(shí),信息系統(tǒng)S是一個(gè)不完備信息系統(tǒng)(Incomplete Information System)，如表1,不完備信息系統(tǒng)中有8個(gè)數(shù)據(jù)對(duì)象且每個(gè)數(shù)據(jù)對(duì)象有6個(gè)屬性,表中的“*”表示缺失數(shù)據(jù)．

表1 不完備信息系統(tǒng)Table 1 An incomplete information system

2 改進(jìn)的均值插補(bǔ)不完備數(shù)據(jù)聚類(lèi)算法

該算法需要在完備數(shù)據(jù)集的聚類(lèi)結(jié)果的基礎(chǔ)上對(duì)缺失數(shù)據(jù)進(jìn)行填充聚類(lèi)．在大多數(shù)情況下,數(shù)據(jù)集中的缺失率越高,聚類(lèi)結(jié)果的準(zhǔn)確性越低．由于缺失率越高,不完備數(shù)據(jù)填充的準(zhǔn)確性也會(huì)降低,直接導(dǎo)致聚類(lèi)算法的性能下降,故對(duì)數(shù)據(jù)集的缺失率有一定的要求,即該算法僅適用缺失值較少的數(shù)據(jù)集．文中數(shù)據(jù)集的缺失率分別設(shè)置為5%、10%、15%、20%、25%、30%．

算法3:填充不完備數(shù)據(jù)聚類(lèi)算法輸入:不完備數(shù)據(jù)集U={x1,x2,…,xn},聚類(lèi)數(shù)k.輸出:聚類(lèi)結(jié)果C={C1,C2,…,Ck}.Step1:給定數(shù)據(jù)集U,根據(jù)特定缺失率(5%～30%)隨機(jī)選擇一些缺失的特征值來(lái)獲得不完備的數(shù)據(jù)集U,其中缺失值的隨機(jī)選擇受兩個(gè)條件的約束:每個(gè)原始特征向量至少保留一個(gè)分量;每個(gè)特征在不完整數(shù)據(jù)集中至少存在一個(gè)值.Step2:將數(shù)據(jù)集U劃分為兩個(gè)互不相交的子集UW和UM,其中UW∪UM=U;Step3:使用算法1或者算法2處理UW中的數(shù)據(jù)對(duì)象,獲得聚類(lèi)結(jié)果CW={C1W,C2W,…,CkW};Step4:UM中對(duì)象x通過(guò)式(1)進(jìn)行填充,獲得填充結(jié)果xl={x1l,xl2,…,xkl}(l∈{1,2,…,m});Step5:為了驗(yàn)證填充后的樣本對(duì)象對(duì)各類(lèi)簇聚類(lèi)中心值的影響程度并能獲得最佳填充值以及該樣本所屬類(lèi)簇,分別往每類(lèi)CiW中添加(|CiW|/k)個(gè)相同的樣本x,得到新的類(lèi)Ci?W;Step6:使用式(2)重新計(jì)算聚類(lèi)中心值;Step7:計(jì)算新舊聚類(lèi)中心的差值di=|zi-z?i|;Step8:選擇最小的di(i=1,2,…,k),確定樣本x的所屬類(lèi)以及缺失屬性值的填充值;Step9:重復(fù)執(zhí)行Step4～8直到UM=?;Step10:使用相應(yīng)的算法1或者算法2再次處理填充后的數(shù)據(jù)集U,獲得最終的聚類(lèi)結(jié)果;Step11:返回聚類(lèi)結(jié)果C={C1,C2,…,Ck}.

算法的第一階段,可以根據(jù)不完備信息系統(tǒng)的定義來(lái)區(qū)分完備數(shù)據(jù)對(duì)象和不完備數(shù)據(jù)對(duì)象,得出集合UW以及集合UM,其中UW∪UM=U．

算法的第二階段,通過(guò)聚類(lèi)算法1或者算法2處理集合UW獲得聚類(lèi)結(jié)果CW={CW1,CW2,…,CWk}．

算法的第三階段,填補(bǔ)集合UM中數(shù)據(jù)對(duì)象的缺失數(shù)據(jù)．例如,UM中對(duì)象x,通過(guò)式(1)插補(bǔ)缺失屬性值,得到插補(bǔ)后的結(jié)果xl={xl1,xl2,…,xlk}，即k種填充結(jié)果．填充公式為:

(1)

(2)

算法的最后一個(gè)階段,通過(guò)階段三的處理,不完備數(shù)據(jù)集U轉(zhuǎn)變成完備數(shù)據(jù)集．使用聚類(lèi)算法再次處理數(shù)據(jù)集U獲得最終聚類(lèi)結(jié)果．

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

通過(guò)給出在UCI數(shù)據(jù)集[23]上的實(shí)驗(yàn)結(jié)果來(lái)驗(yàn)證算法的性能,如表2給出了6組數(shù)據(jù)集的名稱(chēng)、大小、屬性個(gè)數(shù)和類(lèi)簇?cái)?shù)．給定數(shù)據(jù)集U,根據(jù)特定缺失率:5%、10%、15%、20%、25%、30%．隨機(jī)選擇一些缺失的特征值來(lái)獲得不完備的數(shù)據(jù)集U,其中缺失值的隨機(jī)選擇受兩個(gè)條件的約束:① 每個(gè)原始特征向量至少保留一個(gè)分量;② 每個(gè)特征在不完整數(shù)據(jù)集中至少存在一個(gè)值．

準(zhǔn)確率(Accuracy)是一種常見(jiàn)、易于理解的聚類(lèi)性能度量指標(biāo)，它表示那些被正確劃分的樣本數(shù)與總樣本數(shù)之間的比值,值越大表示被劃分正確的樣本越多,否則被正確劃分的樣本數(shù)就越少．準(zhǔn)確率(ACC)計(jì)算如下:

(3)

式中：N為數(shù)據(jù)集中的總樣本數(shù)；θi為類(lèi)i中被正確劃分的樣本個(gè)數(shù)；k為聚類(lèi)數(shù)．

表2 實(shí)驗(yàn)中使用的數(shù)據(jù)集Table 2 Datasets used in experiments

表3為UCI數(shù)據(jù)集上的ACC值,其中加粗的數(shù)據(jù)表示最好的實(shí)驗(yàn)結(jié)果．?dāng)?shù)據(jù)集在不同缺失率的條件下進(jìn)行100次的實(shí)驗(yàn)測(cè)試獲得ACC的平均值和最好值．表中的Method1、Method2、Method3、Method4分別表示基于k-means的不完備數(shù)據(jù)填充聚類(lèi)算法、基于譜聚類(lèi)的不完備數(shù)據(jù)填充聚類(lèi)算法、OCS-FCM算法、NPS-FCM算法[12]．其中,Method3和Method4是不完備數(shù)據(jù)聚類(lèi)算法中較為經(jīng)典的算法,基于FCM的大多數(shù)不完整數(shù)據(jù)聚類(lèi)方法都是在文獻(xiàn)[14]的基礎(chǔ)上實(shí)現(xiàn)的．

從表3的實(shí)驗(yàn)記錄可以看出:Method1和Method2中ACC的平均值與最好值的實(shí)驗(yàn)結(jié)果都是優(yōu)于Method3和Method4的,比如數(shù)據(jù)集WDBC、Pendigits以及Page Blocks．除了數(shù)據(jù)集Iris上的實(shí)驗(yàn)結(jié)果Method1和Method2不如Method3和Method4．分析實(shí)驗(yàn)結(jié)果不難發(fā)現(xiàn):對(duì)比方法是基于模糊C均值算法的,很難在非球形數(shù)據(jù)集上獲得良好的結(jié)果;譜聚類(lèi)算法可以在任意形狀的樣本空間中聚類(lèi),并以全局最優(yōu)解收斂,故在處理高維數(shù)據(jù)方面具有明顯的優(yōu)勢(shì)．因此,文中提出算法的ACC值高于對(duì)比算法的ACC值,尤其是基于譜聚類(lèi)的不完備數(shù)據(jù)填充聚類(lèi)算法．同時(shí),在數(shù)據(jù)集Pendigits和Page Blocks上,Method1和Method2的實(shí)驗(yàn)結(jié)果尤其優(yōu)于Method3和Method4．在大多數(shù)情況下,數(shù)據(jù)集中的缺失率越高,聚類(lèi)結(jié)果的準(zhǔn)確性越低．由于缺失率越高,不完備數(shù)據(jù)填充的準(zhǔn)確性也會(huì)降低,這直接導(dǎo)致聚類(lèi)算法的性能下降．

表3 UCI數(shù)據(jù)集上的ACC值Table 3 Experimental results of ACC on UCI datasets

4 結(jié)論

文中研究對(duì)不完備數(shù)據(jù)集填充聚類(lèi),提出了填充算法的改進(jìn)的均值插補(bǔ)方法(improved mean imputation，IMI)，該其將硬聚類(lèi)算法和改進(jìn)后的均值插補(bǔ)不完備數(shù)據(jù)算法相結(jié)合．通過(guò)比較k-means IMI、spectral clustering IMI和k-medoids IMI 3種硬聚類(lèi)算法的填充在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,可以得出如下結(jié)論:

(1) 3種算法在解決不完備數(shù)據(jù)集的填充聚類(lèi)問(wèn)題上是可行的,其中譜聚類(lèi)算法的效果更佳．

(2) 盡管算法在不完整數(shù)據(jù)填充聚類(lèi)方面是有效的，但是這種算法在某些數(shù)據(jù)集中表現(xiàn)不佳,這表明需要進(jìn)一步改進(jìn)和完善．

(3) 在接下來(lái)的工作中,要考慮如何完善不完備數(shù)據(jù)的填充和聚類(lèi)算法,而且也要思考如何將不完備數(shù)據(jù)與三支決策聚類(lèi)思想相結(jié)合．