黃紫成，李 影

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

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

1 k近鄰填充算法

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

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

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

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

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

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

(1)

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

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

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

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

3 實驗結(jié)果與討論

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

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

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

計算各數(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填充算法的?。辉趀coli數(shù)據(jù)集中，缺失比例為5%，10%，15%，20%時FCM填充算法的RMSE較小，缺失比例為25%時KNN填充算法得到的RMSE較小，但二者較相近.缺失比例逐漸增加，RMSE也隨之增大，但相對KNN填充算法，F(xiàn)CM填充算法總體保持在較小水平，這說明FCM填充算法在缺失值填充應(yīng)用中能達到更好的效果.

4 結(jié)語

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