摘  要：實際應用中大量的不完整的數據集，造成了數據中信息的丟失和分析的不方便，所以對缺失數據的處理已經成為目前分類領域研究的熱點。由于EM方法隨機選取初始代表簇中心會導致聚類不穩定，本文使用樸素貝葉斯算法的分類結果作為EM算法的初始使用范圍，然后按E步M步反復求精，利用得到的最大化值填充缺失數據。實驗結果表明，本文的算法加強了聚類的穩定性，具有更好的數據填充效果。
關鍵詞：數據填充；EM算法；樸素貝葉斯算法

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

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

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

    實驗設計具體步驟如下：
    （1） 將原始數據集準備二份，一份作為原始集，一份作為測試集。用MCAR（missing completely at random，完全隨機缺失）方法隨機去掉測試集的不同比率的屬性值，并剔除原有類標；
    （2） 使用本文算法對（1）后的測試集的屬性值和類標進行預測，填充缺失值和類標志；
    （3） 反復進行試驗20次；
    （4） 本文使用填充數據與真實數據的平均絕對離
     由上述三表可以看出，在缺失率不同的情況下與經典EM算法相比，本文算法穩定，且減少了與真實數值的偏差，這樣使得實際運用中的填充數據值更真實地反映數據信息。EM算法提出較早，GEM算法、Monte Carlo EM算法和界定折疊法等都改進了EM算法，相比較于這些算法，本文充分利用了EM算法容易實現局部最優的特點，將EM初始范圍界定在一個類內，使得EM算法很好地聚類和收斂，使得填充值更接近于真實數值。
    數據缺失是數據預處理中亟須解決的問題，本文為填充缺失數據提出了基于樸素貝葉斯的EM數據填充算法。該算法使用樸素貝葉斯分類算法的結果作為EM算法的初始范圍，然后按E步M步反復求精，利用得到的最大化值填充缺失數據。該算法充分利用了EM算法容易實現局部最優的特點，使得EM算法更好地聚類，更快地收斂，從而得到更準確的數據填充值。實驗結果表明，該算法得到了預期的效果。由于本論文主要是針對數值型屬性進行分析，下一步的研究是考慮非數值型屬性缺失問題。
參考文獻
[1] GRZYMALA-BUSSE J W. Rough set approach to incomplete data. In:LNAI 3070,2004:50~55.
[2] （加）Han Jiawei, KAMBER M. 數據挖掘概念與設計[M]. 北京：機械工業出版社,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] 宮義山，董晨.基于貝葉斯網絡的缺失數據處理[J].沈陽工業大學學報，2010,32（1）：79-83.
[8] 彭紅毅，朱思銘，蔣春福.數據挖掘中基于ICA的缺失數據值的估計[J].計算機科學，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.