基于模糊C-均值聚類的缺失數(shù)據(jù)填充方法*

黃紫成，李 影

(仰恩大學(xué)工程技術(shù)學(xué)院，福建 泉州 362014)

在加工、存儲(chǔ)數(shù)據(jù)時(shí)常發(fā)生數(shù)據(jù)丟失，這對(duì)數(shù)據(jù)挖掘的有效性會(huì)造成一定的影響.對(duì)缺失數(shù)據(jù)的處理大概分為直接刪除、填充或不處理.刪除數(shù)據(jù)往往是刪除缺失數(shù)據(jù)所在的樣本，但如果刪除的數(shù)據(jù)是至關(guān)重要的，那么對(duì)后續(xù)的操作會(huì)產(chǎn)生極大的影響.如果不處理缺失數(shù)據(jù)，因存在空值，對(duì)于有些算法就無(wú)法使用(如聚類算法).因此，有效的處理方式是對(duì)缺失數(shù)據(jù)進(jìn)行填充[1-3].學(xué)者們對(duì)數(shù)據(jù)的填充提出了許多方法，如平均值填充、k近鄰填充[4-6]、聚類填充[7-9]和粗糙集的不完備算法等.為了能得到更接近原始數(shù)據(jù)的完備數(shù)據(jù)集，筆者將使用模糊C-均值聚類算法進(jìn)行數(shù)據(jù)填充，并與k近鄰算法作比較.

1 k近鄰填充算法

k近鄰(k-Nearest Neighbor，KNN)填充算法是通過(guò)計(jì)算缺失數(shù)據(jù)樣本與完整數(shù)據(jù)樣本之間的歐式距離，選出距離最小的k個(gè)樣本作為缺失樣本的最近鄰，再通過(guò)距離的反比加權(quán)平均而得到缺少數(shù)據(jù)的填充值[10-11].KNN填充算法步驟如下:

(ⅰ)初始化數(shù)據(jù)矩陣Xm×n，m為樣本數(shù)量，n為屬性維度；

(ⅲ)從完整樣本中選出最小的k個(gè)距離作為缺失數(shù)據(jù)的k個(gè)近鄰；

2 模糊C-均值聚類填充算法

模糊C-均值聚類(FuzzyC-Means，F(xiàn)CM)算法最早由E. Ruspini提出，后來(lái)J. C. Dunn和J. C. Bezdek將該算法從硬聚類算法推廣為模糊聚類算法.模糊聚類算法是無(wú)監(jiān)督的聚類算法，其聚類結(jié)果是每個(gè)數(shù)據(jù)樣本點(diǎn)對(duì)聚類中心的隸屬度[12-13].

對(duì)于數(shù)據(jù)集X={x1,x2,…,xn},cj(j=1,2,…,k)為k個(gè)類別的聚類中心，uj(xi)為第i個(gè)樣本對(duì)應(yīng)第j個(gè)類別的隸屬度函數(shù)，則FCM算法的目標(biāo)函數(shù)可以寫成

(1)

這里隸屬函數(shù)之和為1，b為加權(quán)指數(shù)，通常取為2.對(duì)(1)式求偏導(dǎo)，得到極小值時(shí)對(duì)應(yīng)的必要條件為[12-13]

之后通過(guò)循環(huán)迭代就可計(jì)算出聚類中心和隸屬度矩陣.FCM填充算法的流程如圖1所示.得到隸屬矩陣u之后，每個(gè)樣本隸屬于某個(gè)類別的概率已經(jīng)確定.對(duì)于樣本缺失的屬性值，可通過(guò)計(jì)算每類對(duì)應(yīng)屬性的均值再乘以權(quán)重而得到.

圖1 模糊C-均值聚類填充流程Fig. 1 Flow Chart of Fuzzy C-Means Clustering Filling

算法的時(shí)間復(fù)雜度主要為計(jì)算目標(biāo)函數(shù)是否收斂于因子δ，若一直無(wú)法收斂，則可以控制循環(huán)迭代次數(shù)，如100次[14].

3 實(shí)驗(yàn)結(jié)果與討論

本實(shí)驗(yàn)利用FCM和KNN算法完成填充，選用UCI數(shù)據(jù)庫(kù)上的wine，wpbc，iono，ecoli等4組數(shù)據(jù)進(jìn)行測(cè)試.為了比較填充前后數(shù)據(jù)與原始數(shù)據(jù)的差別，在4組數(shù)據(jù)上做隨機(jī)缺失，缺失比例為5%，10%，15%，20%，25%.填充前后數(shù)據(jù)的均方根誤差(Root Mean Squard Error，RMSE)計(jì)算公式為

實(shí)驗(yàn)平臺(tái)為win10，CORE i7，內(nèi)存8 G，MATLABR2017a.KNN填充算法中近鄰k=3，F(xiàn)CM填充算法中聚類數(shù)目為6，收斂因子δ=10-6，實(shí)驗(yàn)數(shù)據(jù)見表1.

表1 數(shù)據(jù)集信息Table 1 Dataset Information

計(jì)算各數(shù)據(jù)集在FCM和KNN填充算法下的 RMSE，結(jié)果如圖2～5所示.

圖2 wine數(shù)據(jù)Fig. 2 wine Data

圖3 wpbc數(shù)據(jù)Fig. 3 wpbc Data

圖4 iono數(shù)據(jù)Fig. 4 iono Data

圖5 ecoli數(shù)據(jù)Fig. 5 ecoli Data

由圖2～5可以看出：在數(shù)據(jù)集wine，wpbc，iono中，F(xiàn)CM填充算法的RMSE都比KNN填充算法的小；在ecoli數(shù)據(jù)集中，缺失比例為5%，10%，15%，20%時(shí)FCM填充算法的RMSE較小，缺失比例為25%時(shí)KNN填充算法得到的RMSE較小，但二者較相近.缺失比例逐漸增加，RMSE也隨之增大，但相對(duì)KNN填充算法，F(xiàn)CM填充算法總體保持在較小水平，這說(shuō)明FCM填充算法在缺失值填充應(yīng)用中能達(dá)到更好的效果.

4 結(jié)語(yǔ)

利用FCM算法的隸屬度矩陣對(duì)缺失數(shù)據(jù)進(jìn)行填充，并與KNN填充算法作對(duì)比，結(jié)果表明，F(xiàn)CM填充的效果總體優(yōu)于KNN填充.由于模糊均值需要事先確定分類個(gè)數(shù)，因此筆者后續(xù)的主要研究工作是如何確定分類及分類個(gè)數(shù).