基于樸素貝葉斯的EM缺失數(shù)據(jù)填充算法

鄒 薇，王會進

（暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州510632）

在數(shù)據(jù)泛濫的今天，迫切地需要一種將數(shù)據(jù)轉(zhuǎn)換成有用的信息和知識的數(shù)據(jù)挖掘技術(shù)。然而，由于信息無法獲取或者在操作過程中被遺漏等原因，現(xiàn)實中的數(shù)據(jù)往往存在大量的缺失[1]。數(shù)據(jù)缺失對數(shù)據(jù)挖掘的過程和結(jié)果有嚴(yán)重的影響：首先，系統(tǒng)丟失了大量有用的信息；其次，系統(tǒng)中所表現(xiàn)出的不確定性更加顯著，系統(tǒng)中蘊涵的確定性成分更難把握[2]；第三，包含空值的數(shù)據(jù)會使挖掘過程陷入混亂，導(dǎo)致不可靠的輸出；第四，可能直接影響到數(shù)據(jù)挖掘模式發(fā)現(xiàn)的準(zhǔn)確性和運行性能，甚至導(dǎo)致錯誤的挖掘模型[3]。因此，在數(shù)據(jù)預(yù)處理過程中，缺失數(shù)據(jù)的處理是一個重要的環(huán)節(jié)。

目前，國外對數(shù)據(jù)缺失問題的研究取得了很多成果，提出了最近似值替換方法、隨機回歸填補法、神經(jīng)網(wǎng)絡(luò)、貝葉斯網(wǎng)絡(luò)等理論來解決缺失數(shù)據(jù)填充問題。國內(nèi)對填充缺失數(shù)據(jù)的研究還處在一個開始的階段，只有銀行、保險業(yè)等在針對其自身具體的應(yīng)用進行了缺失數(shù)據(jù)處理的研究。

總體上說，對缺失值的處理分為三大類：刪除元組、數(shù)據(jù)填充和不處理[4]。其中，處理數(shù)據(jù)缺失最簡單的方法是刪除元組，當(dāng)缺少類標(biāo)號時通常這樣做（假定挖掘任務(wù)設(shè)計分類），但是當(dāng)每個屬性缺少值的百分比變化很大時，該方法性能特別差[5]。處理數(shù)據(jù)缺失的有效方法是使用最可能的值填充缺失值，可以用回歸、貝葉斯形式化的基于推理的工具或決策樹歸納確定[6]。近年來，學(xué)術(shù)界提出了很多數(shù)據(jù)填充算法。宮義山提出了基于貝葉斯網(wǎng)絡(luò)的缺失數(shù)據(jù)處理方法[7]，彭紅毅針對數(shù)據(jù)之間存在相關(guān)性且為非高斯分布這種情況提出了ICA-MDH數(shù)據(jù)估計方法[8]，Hruschkaetal.使用貝葉斯算法對實例中的缺失值進行估計[9]。

在眾多算法中，EM算法能通過穩(wěn)定、上升的步驟可靠地找到全局最優(yōu)值，算法適應(yīng)性更強。盡管Gibbs抽樣(Gibbs samplig)[10]、GEM(Generalized EM)算法、Monte Carlo EM算法都改進了EM算法，但EM算法收斂速度慢的缺點仍然沒有得到很好的解決。基于此，本文提出結(jié)合樸素貝葉斯分類改進傳統(tǒng)EM算法的方法填充缺失數(shù)據(jù)的新算法。給EM初始值界定了范圍，提高了EM算法的收斂速度和算法的穩(wěn)定性，克服了邊緣值造成EM算法結(jié)果偏差大的缺點，實現(xiàn)了良好的缺失數(shù)據(jù)填充效果。

1 樸素貝葉斯分類的EM數(shù)據(jù)填充算法及其改進

1.1 符號定義

首先對算法中使用到的符號進行定義，如表1。

表1 符號定義一覽表

1.2 傳統(tǒng)EM算法介紹

EM(期望最大化)算法是一種流行的迭代求精算法，它的每一步迭代都由一個期望步（expectation step）和一個最大化步（maximization step）組成。其基本思想是，首先估計出缺失數(shù)據(jù)初值，計算出模型參數(shù)的值，然后再不斷迭代執(zhí)行E步和M步，對估計出的缺失數(shù)據(jù)值進行更新，直到收斂。EM算法的具體描述如下：

（1）隨機選擇K個對象代表簇的中心，以此猜測其他的參數(shù)；

（2）反復(fù)執(zhí)行E步和M步對參數(shù)進行求精，直到收斂。

①E(期望)步：用概率 P(Xi∈Ck)將每個對象 X指派到簇 Ck。

其中，P(Xi|Ck)表示簇 Ck中 Xi的概率，是對象 Xi的簇隸屬概率。

1.3 EM算法改進

EM算法隨機選擇對象作為簇的中心，會導(dǎo)致EM算法聚類結(jié)果的不穩(wěn)定性，以及邊緣數(shù)據(jù)對整個算法影響過大，使得填充數(shù)據(jù)正確率偏低。本文提出了基于樸素貝葉斯的EM缺失數(shù)據(jù)填充算法。本算法使用樸素貝葉斯算法對源數(shù)據(jù)進行分類，將分類結(jié)果作為EM算法使用范圍，在每個類中反復(fù)執(zhí)行E步M步直至收斂，充分利用了EM算法容易達到局部最優(yōu)的優(yōu)點，使得EM算法更好地聚類，更快地收斂，從而得到更準(zhǔn)確的數(shù)據(jù)填充值。本文算法的具體描述如下：

(1)利用樸素貝葉斯算法對源數(shù)據(jù)進行分類；

其中，P(Li)為先驗概率，等于 SCi/Sd。

P(X/Li)為Li條件下X的條件概率密度函數(shù)。假定X/Li為一整體T，該概率密度函數(shù)母體ξ是離散型，則L（θ∧；T1,T2,…，Tn）=L(θ；T1,T2,…，Tn)，滿足這個式子的 θ∧（T1,T2,…，Tn）就有可能產(chǎn)生 T1,T2,…，Tn的參數(shù) θ的值，其 相 應(yīng) 的 統(tǒng) 計量 θ∧（ξ1，ξ2，…，ξn）稱 作 θ的 極 大似然估計量。如果該概率密度函數(shù)母體ξ是連續(xù)型，則只需求出使得 L（θ∧；T1,T2,…，Tn）=∏f(Ti；θ)達到極大的θ∧（T1,T2,…，Tn），便可得到極大似然估計，即InL（θ∧；T1,T2,…，Tn）=L(θ；T1,T2,…，Tn)。

計算出P(Li/X)，分類法將預(yù)測X屬于具有最高后驗概率（條件X下）的類。即樸素貝葉斯分類預(yù)測X屬于類 Ci，當(dāng)且僅當(dāng) P(Ci/X)>P(Cj/X)1≤j

這樣就得出了每個數(shù)據(jù)元組X所屬的類，分類完成。

(2)利用（1）分類的結(jié)果分別作為新的數(shù)據(jù)集，在這些數(shù)據(jù)集中分別使用EM算法計算期望最大化值。

在類 L1，L2，…，Lw這 W 個分類中，分別選出 K個對象代表簇的均值，再反復(fù)執(zhí)行E步和M步對參數(shù)進行求精，直到收斂。

E(期望)步：用概率 P(XLi∈CLiK)分別將類 Li中的每個對象XLi指派到簇CLiK中。

算法收斂后，用計算得到的最大化值mLik作為類Li中簇k的最大化值，并使用這個值填充缺失數(shù)字。

1.4 算法偽代碼實現(xiàn)

上節(jié)描述的算法由程序?qū)崿F(xiàn)，具體的算法偽代碼如下：

(2)將樸素貝葉斯算法的分類結(jié)果分別作為EM的初始范圍。分別在每個類中使用EM算法，計算出期望最大值。

2 實驗結(jié)果及分析

從UCI機器學(xué)習(xí)數(shù)據(jù)庫中，選取4個沒有數(shù)據(jù)缺失的完整數(shù)據(jù)集，表2列出了它們的詳細信息。

表2 論文中使用的數(shù)據(jù)集

實驗設(shè)計具體步驟如下：

（1）將原始數(shù)據(jù)集準(zhǔn)備二份，一份作為原始集，一份作為測試集。用MCAR（missing completely at random，完全隨機缺失）方法隨機去掉測試集的不同比率的屬性值，并剔除原有類標(biāo)；

（2）使用本文算法對（1）后的測試集的屬性值和類標(biāo)進行預(yù)測，填充缺失值和類標(biāo)志；

（3）反復(fù)進行試驗20次；

（4）本文使用填充數(shù)據(jù)與真實數(shù)據(jù)的平均絕對離差（MAD）和標(biāo)準(zhǔn)平均離差（RMSD）作為比較標(biāo)準(zhǔn)。其中MAD=|Y填充值i-Y真實數(shù)據(jù)|/20×n，RMSD=(Y填充值i-Y真實數(shù)據(jù))2/n]1/2/20。 其中 Y填充值i表示第 i次填充的數(shù)據(jù)，Y真實數(shù)據(jù)是真值，n 表示缺失個數(shù)。

對于不同缺失率的數(shù)據(jù)集，分別使用EM算法和本文算法進行填充，比較結(jié)果如表3～表5所示。

表3 缺失率15%下MAD、RMSD比較結(jié)果

表4 缺失率30%下MAD、RMSD比較結(jié)果

表5 缺失率50%下MAD、RMSD比較結(jié)果

由上述三表可以看出，在缺失率不同的情況下與經(jīng)典EM算法相比，本文算法穩(wěn)定，且減少了與真實數(shù)值的偏差，這樣使得實際運用中的填充數(shù)據(jù)值更真實地反映數(shù)據(jù)信息。EM算法提出較早，GEM算法、Monte Carlo EM算法和界定折疊法等都改進了EM算法，相比較于這些算法，本文充分利用了EM算法容易實現(xiàn)局部最優(yōu)的特點，將EM初始范圍界定在一個類內(nèi)，使得EM算法很好地聚類和收斂，使得填充值更接近于真實數(shù)值。

數(shù)據(jù)缺失是數(shù)據(jù)預(yù)處理中亟須解決的問題，本文為填充缺失數(shù)據(jù)提出了基于樸素貝葉斯的EM數(shù)據(jù)填充算法。該算法使用樸素貝葉斯分類算法的結(jié)果作為EM算法的初始范圍，然后按E步M步反復(fù)求精，利用得到的最大化值填充缺失數(shù)據(jù)。該算法充分利用了EM算法容易實現(xiàn)局部最優(yōu)的特點，使得EM算法更好地聚類，更快地收斂，從而得到更準(zhǔn)確的數(shù)據(jù)填充值。實驗結(jié)果表明，該算法得到了預(yù)期的效果。由于本論文主要是針對數(shù)值型屬性進行分析，下一步的研究是考慮非數(shù)值型屬性缺失問題。

[1]GRZYMALA-BUSSE J W.Rough set approach to incomplete data.In∶LNAI 3070,2004∶50～55.

[2]（加）Han Jiawei,KAMBER M.數(shù)據(jù)挖掘概念與設(shè)計[M].北京：機械工業(yè)出版社,2008.

[3]LAKSHMINARAYAN K,(1999).Imputation of missing data in industrial databases[J],Applied Intelligence 11：259-275.

[4]HUANG X L.A pseudo-nearest-neighbor approach for missing data recovery on Gaussian random data sets[J].Pattern Recognition Letters，2002(23)：1613－1622.

[5]GRZYMALA-BUSSE J W,FU M,(2000).A comparison of several approaches to missing attribute values in data min-ing[C].In∶Proc of the 2nd Int’Conf on Rough Sets and Current Trends in Computing.Berlin∶Springer-Verlag,2000：378-385.

[6]ZHANG S C，QIN Y S，ZHU X F，et al.Optimized parameters for missing data imputation.PRICAI06,2006∶1010-1016.

[7]宮義山，董晨.基于貝葉斯網(wǎng)絡(luò)的缺失數(shù)據(jù)處理[J].沈陽工業(yè)大學(xué)學(xué)報，2010,32（1）：79-83.

[8]彭紅毅，朱思銘，蔣春福.數(shù)據(jù)挖掘中基于 ICA的缺失數(shù)據(jù)值的估計[J].計算機科學(xué)，2005，32(12)：203-205.

[9]HRUSCHKA E R,EBECKEN N F F.Missing values prediction with K2[J].Intelligent Data Analysis,2002,6(6)∶557-566.

[10]GEMAN S，GEMAN D.Stochastic relaxation,Gibbs distribution and the Bayesian restoration of images[J].IEEE Trans onPattern Analysis and Machine Intelligence,1984(6)∶721.