摘  要：實(shí)際應(yīng)用中大量的不完整的數(shù)據(jù)集,，造成了數(shù)據(jù)中信息的丟失和分析的不方便,，所以對(duì)缺失數(shù)據(jù)的處理已經(jīng)成為目前分類領(lǐng)域研究的熱點(diǎn)。由于EM方法隨機(jī)選取初始代表簇中心會(huì)導(dǎo)致聚類不穩(wěn)定,，本文使用樸素貝葉斯算法的分類結(jié)果作為EM算法的初始使用范圍,，然后按E步M步反復(fù)求精，利用得到的最大化值填充缺失數(shù)據(jù),。實(shí)驗(yàn)結(jié)果表明,，本文的算法加強(qiáng)了聚類的穩(wěn)定性，具有更好的數(shù)據(jù)填充效果,。
關(guān)鍵詞：數(shù)據(jù)填充,；EM算法；樸素貝葉斯算法

　在數(shù)據(jù)泛濫的今天,，迫切地需要一種將數(shù)據(jù)轉(zhuǎn)換成有用的信息和知識(shí)的數(shù)據(jù)挖掘技術(shù),。然而，由于信息無法獲取或者在操作過程中被遺漏等原因,，現(xiàn)實(shí)中的數(shù)據(jù)往往存在大量的缺失[1],。數(shù)據(jù)缺失對(duì)數(shù)據(jù)挖掘的過程和結(jié)果有嚴(yán)重的影響：首先，系統(tǒng)丟失了大量有用的信息,；其次,，系統(tǒng)中所表現(xiàn)出的不確定性更加顯著，系統(tǒng)中蘊(yùn)涵的確定性成分更難把握[2],；第三,，包含空值的數(shù)據(jù)會(huì)使挖掘過程陷入混亂，導(dǎo)致不可靠的輸出,；第四,，可能直接影響到數(shù)據(jù)挖掘模式發(fā)現(xiàn)的準(zhǔn)確性和運(yùn)行性能，甚至導(dǎo)致錯(cuò)誤的挖掘模型[3],。因此,，在數(shù)據(jù)預(yù)處理過程中，缺失數(shù)據(jù)的處理是一個(gè)重要的環(huán)節(jié),。
    目前,，國外對(duì)數(shù)據(jù)缺失問題的研究取得了很多成果，提出了最近似值替換方法,、隨機(jī)回歸填補(bǔ)法,、神經(jīng)網(wǎng)絡(luò)、貝葉斯網(wǎng)絡(luò)等理論來解決缺失數(shù)據(jù)填充問題。國內(nèi)對(duì)填充缺失數(shù)據(jù)的研究還處在一個(gè)開始的階段,，只有銀行,、保險(xiǎn)業(yè)等在針對(duì)其自身具體的應(yīng)用進(jìn)行了缺失數(shù)據(jù)處理的研究。
    總體上說,，對(duì)缺失值的處理分為三大類：刪除元組,、數(shù)據(jù)填充和不處理[4]。其中,，處理數(shù)據(jù)缺失最簡單的方法是刪除元組,，當(dāng)缺少類標(biāo)號(hào)時(shí)通常這樣做（假定挖掘任務(wù)設(shè)計(jì)分類），但是當(dāng)每個(gè)屬性缺少值的百分比變化很大時(shí),，該方法性能特別差[5],。處理數(shù)據(jù)缺失的有效方法是使用最可能的值填充缺失值，可以用回歸,、貝葉斯形式化的基于推理的工具或決策樹歸納確定[6],。近年來，學(xué)術(shù)界提出了很多數(shù)據(jù)填充算法,。宮義山提出了基于貝葉斯網(wǎng)絡(luò)的缺失數(shù)據(jù)處理方法[7],，彭紅毅針對(duì)數(shù)據(jù)之間存在相關(guān)性且為非高斯分布這種情況提出了ICA-MDH數(shù)據(jù)估計(jì)方法[8]，Hruschkaetal.使用貝葉斯算法對(duì)實(shí)例中的缺失值進(jìn)行估計(jì)[9],。
    在眾多算法中,，EM算法能通過穩(wěn)定、上升的步驟可靠地找到全局最優(yōu)值,，算法適應(yīng)性更強(qiáng),。盡管Gibbs抽樣(Gibbs samplig)[10]、GEM(Generalized EM)算法,、Monte Carlo EM算法都改進(jìn)了EM算法,，但EM算法收斂速度慢的缺點(diǎn)仍然沒有得到很好的解決?；诖?，本文提出結(jié)合樸素貝葉斯分類改進(jìn)傳統(tǒng)EM算法的方法填充缺失數(shù)據(jù)的新算法。給EM初始值界定了范圍,，提高了EM算法的收斂速度和算法的穩(wěn)定性,，克服了邊緣值造成EM算法結(jié)果偏差大的缺點(diǎn)，實(shí)現(xiàn)了良好的缺失數(shù)據(jù)填充效果,。
1 樸素貝葉斯分類的EM數(shù)據(jù)填充算法及其改進(jìn)
1.1 符號(hào)定義
    首先對(duì)算法中使用到的符號(hào)進(jìn)行定義,，如表1。

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

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

    實(shí)驗(yàn)設(shè)計(jì)具體步驟如下：
    （1） 將原始數(shù)據(jù)集準(zhǔn)備二份，一份作為原始集,，一份作為測試集,。用MCAR（missing completely at random，完全隨機(jī)缺失）方法隨機(jī)去掉測試集的不同比率的屬性值,，并剔除原有類標(biāo),；
    （2） 使用本文算法對(duì)（1）后的測試集的屬性值和類標(biāo)進(jìn)行預(yù)測，填充缺失值和類標(biāo)志,；
    （3） 反復(fù)進(jìn)行試驗(yàn)20次,；
    （4） 本文使用填充數(shù)據(jù)與真實(shí)數(shù)據(jù)的平均絕對(duì)離
     由上述三表可以看出，在缺失率不同的情況下與經(jīng)典EM算法相比,，本文算法穩(wěn)定,，且減少了與真實(shí)數(shù)值的偏差，這樣使得實(shí)際運(yùn)用中的填充數(shù)據(jù)值更真實(shí)地反映數(shù)據(jù)信息,。EM算法提出較早,，GEM算法、Monte Carlo EM算法和界定折疊法等都改進(jìn)了EM算法,，相比較于這些算法,，本文充分利用了EM算法容易實(shí)現(xiàn)局部最優(yōu)的特點(diǎn)，將EM初始范圍界定在一個(gè)類內(nèi),，使得EM算法很好地聚類和收斂,，使得填充值更接近于真實(shí)數(shù)值,。
    數(shù)據(jù)缺失是數(shù)據(jù)預(yù)處理中亟須解決的問題，本文為填充缺失數(shù)據(jù)提出了基于樸素貝葉斯的EM數(shù)據(jù)填充算法,。該算法使用樸素貝葉斯分類算法的結(jié)果作為EM算法的初始范圍,，然后按E步M步反復(fù)求精，利用得到的最大化值填充缺失數(shù)據(jù),。該算法充分利用了EM算法容易實(shí)現(xiàn)局部最優(yōu)的特點(diǎn),，使得EM算法更好地聚類，更快地收斂,，從而得到更準(zhǔn)確的數(shù)據(jù)填充值,。實(shí)驗(yàn)結(jié)果表明，該算法得到了預(yù)期的效果,。由于本論文主要是針對(duì)數(shù)值型屬性進(jìn)行分析,，下一步的研究是考慮非數(shù)值型屬性缺失問題。
參考文獻(xiàn)
[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è)計(jì)[M]. 北京：機(jī)械工業(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 mining[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é)報(bào)，2010,32（1）：79-83.
[8] 彭紅毅,，朱思銘,，蔣春福.數(shù)據(jù)挖掘中基于ICA的缺失數(shù)據(jù)值的估計(jì)[J].計(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.