擬合化處理不完整數據缺失序列插補算法仿真

姚迎樂，李 建，2，孫 濱

(1. 鄭州工業應用技術學院信息工程學院，河南 新鄭 451150；2. 河南大學數學與統計學院，河南 開封 475001)

1 引言

在大數據時代，經常會遇到因多種干擾因素而使數據呈現不完整的情況，或是數據在收集時就是缺失狀態。若丟失的是較為重要、有價值的信息，那么數據分析將變得困難，導致對信息的分析和判斷失去準確度，因此，需要對不完整數據實行缺失插補。

針對缺失數據的插補方法有很多，楊弘[1]等人研究出一種混合缺失插補法，通過模擬數據的不同缺失比例，利用不同數據填補方法，通過錯分比例形式，對缺失數據進行填補，在正則化均方誤差的基礎上，驗證數據的插補結果，對數據的填補結果較為理想，但遇到數據變量較大的情況，則會出現較大的誤差；劉佳星[2]等人研究出一種基于缺失率的數據插補算法，針對數據集合中各個樣本數據不同程度的缺失率，通過將隨機森林和馬爾科夫法相結合，計算數據的缺失平均值對數據進行缺失插補，通過驗證插補誤差，確定方法的可行性，但該方法并未考慮數據的噪聲干擾問題，因此數據插補過程中分辨數據的時間較長。

為此，利用隨機森林模型，建立決策樹來對不完整數據進行缺失預測，前期通過對數據的預處理，減少數據參數不均和噪聲現象，剔除異常數據，使數據中有效信息更加清晰，利用不完整數據內有價值信息進行預測，通過多維度和多迭代的插補計算，得到最終的數據插補值，在一定程度上提高了缺失數據插補效率和精度。

2 不完整數據缺失插補算法

2.1 隨機森林插補模型構建

將大量的已有數據去重抽樣[3]，假設原始的數據訓練樣本集包含N個數據樣本，從中隨機抓取n個數據樣本，為了方便研究，設定每一個數據樣本容量與訓練集合中樣本個數是相同的，利用提取出來的n個數據樣本構建控制決策樹分類模型，通過{h(X，θk)，k=1，2，…，n}來具體表示，將數據樣本帶入到集合中可以得到n個數據分類結果，在此基礎上，根據得出的分類結果，通過決策樹的投票機制決定最終的分類結果。隨機森林決策過程如圖1所示。

隨機森林針對不完整數據的缺失插補算法，在進行去重隨機抽樣時，如果數據訓練樣本集中包含的樣本個數N足夠多，利用重要極限推導法可以具體計算出集合中每個樣本未被隨機抓取抽中的概率是：

圖1 隨機森林示意圖

P=(1-1/N)N

(1)

經過概率收斂后得出：

1/e≈36.8

(2)

這個概率說明原始的數據訓練樣本集中約等于36.8%的數據樣本，在進行去重隨機抽樣時不會被抽取到，將這些數據樣本統稱為袋外數據，這類袋外數據可以有效降低隨機森林模型的泛化誤差[4]。

利用隨機森林模型對不完整數據進行缺失插補計算時，由于充分利用了數據集合的原始信息，基本不會受到數據分布的影響和限制，依據原始的數據訓練樣本完成相應的數據缺失預測，通過森林中多棵決策樹的聯合作用，使算法得出的插補效果更加準確有效。具體的模型構建流程如圖2所示。

圖2 數據缺失插補模型構建流程圖

2.2 數據預處理

在收集數據的過程中，不可避免地會存在一些異常數據節點，為了減少和避免這些異常數據對后續數據缺失插補結果產生影響，利用閾值函數對不同的數據特征設定對應的評估閾值，當數據中的特征超過了所設定的評估閾值時，算法認為該數據屬于異常數據，并從數據樣本集中剔除[5，6]。在此基礎上，將數據樣本集中的連續完整段數據復制，分別用于實驗和結果驗證，實驗過程中將樣本集中的數據點進行隨機連續刪除，再利用時間間隔來模擬插補段[7]。

通過遍歷法明確數據在確定時間間隔內的缺失個數，選取若干個缺失點作為隨機森林預測自變量，對訓練特征建立預測處理值，用來優化數據樣本。在采集的數據過程中，由于噪聲掩蓋了部分有效信息，使得數據缺失，假設數據{xo，y}中xo部分存在干擾噪聲，通過計算獲得數據內噪聲位置的共享特征[8]uo，可以在數據回歸的基礎上得到降噪后的數據

(3)

式中，w表示對數據干擾的降噪系數，T表示處理周期，A表示隨機變量數據。

3 不完整數據缺失插補算法

假設待插補的數據樣本集中樣本的維度為p，將第i個數據樣本在第j維的具體數據表示為xij，那么所獲得的n×p維數據樣本集合可表示為

(4)

當列向量Xs是多變量矩陣時，對不完整數據的缺失插補與單變量基本相同，針對數據樣本集合矩陣X中的缺失數據，按照數據所在不同維度，以及不同的缺失程度對數據進行升序排列，通過均值插補有效填充缺失數據，可以得到初始的填補后數據矩陣，利用偽代碼函數算法對數據進行迭代插補[9]，隨后將插補結果更新并組建新的插補矩陣。

(5)

考慮到隨機森林中的獨立決策樹在生成階段容易出現過擬合現象，利用最大生長層原則限制隨機森林中決策樹葉片節點個數，實現決策樹成長層的優化[12，13]。為了使模型對缺失數據的插補更加精確，應在一定層面上減少數據的干擾噪聲，通過融合集成算法隨機回放抓取數據樣本，隨機抽取g組數據樣本作為原始數據的插補訓練集合，對應的建立g個與數據并行但獨立的弱評估器[14]，在此過程中獨立決策樹會在各個分支節點處，對隨機變量A實行平均絕對誤差最小化處理[15]，通過計算與決策樹上任意父節點b相對應的子節點U1、U2的平均絕對誤差值，同時計算當這兩個值處于最小時所對應的父節點和變量變化，判斷具體評估結果，具體計算如下

(6)

式中，c1和c2分別表示U1、U2兩個子節點對應的輸出均值，xi表示輸入到決策樹中的樣本點，yi表示經過決策樹決策后的輸出值。

f(α)=αB

(7)

利用最小二乘估計法求解函數式可得

(8)

式中，L表示數據輸出殘差平方函數值。

數據缺失插補經過訓練得到插補權重后，利用序列插補法對數據預測點實行逐一擬合化處理，前一個數據經過擬合后將作為下一個數據的擬合輸入值，最終生成最佳的權重矩陣插補。

4 仿真研究

為驗證所研究的基于隨機森林的不完整數據缺失插補方法是否可靠有效，首先對于缺失數據的參數優化及預處理效果，進行相關的驗證，將ntree和mtry作為綜合參考因素，以標準均方根誤差數值最小作為最佳參考因素，設定隨機森林模型中子樹數量為ntree=10，20，30，…，400，一個子樹產生的分枝為mtry=2，4，6，8，在此基礎上，對缺失數據實行300次的ntree和mtry綜合因素迭代，此時可以得出隨機森林對不完整數據的插補算法中，ntree和mtry兩個綜合因素對準均方根誤差以及算法時間的具體影響關系，實驗的具體結果如圖3和圖4所示。

圖3 ntree和mtry綜合因素對標準均方根誤差的影響

從圖3和圖4中可以看出，隨機森林對不完整數據進行缺失插補的過程中產生的插補誤差，主要受到ntree參考因素的影響，隨著ntree數值的增大，隨機森林算法數據缺失插補的誤差會逐漸減小，證明插補結果在此過程中變得越來越準確。而插補算法所耗用的時間則會隨之增加，mtry參考因素對隨機森林算法的插補誤差影響并不是很大，主要影響的是算法運行時間，當ntree數值逐漸大于200時，對插補誤差產生的影響也在逐漸縮小。這一點證明了所提算法不會產生過度擬合的情況，隨著決策樹數量的不斷增加，誤差情況逐漸收斂，得到最優的算法綜合參考因素為ntree=200，mtry=2。

圖4 ntree和mtry綜合因素算法運行時間影響

令混合缺失插補法、缺失率插補法和本文方法在相同數據環境下，進行不完整數據的缺失插補計算時間對比，結果如圖5所示。

從圖5中可以看出，混合缺失插補法由于通過錯分幾種插補方法的計算比例，來實現對不完整數據的插補，其在計算數據缺失情況時，所需時間比缺失率插補法和所提算法要長，相對應的插補速度略慢；由于缺失率插補法是根據數據間不同的缺失率情況來進行插補，在對不完整是數據進行初始計算階段，需要消耗時間來分析數據的缺失程度，當掌握到缺失規律后，插補速度開始加快，但是隨著數據量的增多，插補速度仍舊不占優勢。而所提算法利用隨機森林實行不完整數據插補計算，在計算時間上耗費更少，插補速度更快，效率相對更高。

圖5 不同方法缺失數據插補計算速度

大多數情況下，不完整數據的插補是在大數據環境下完成，其數據體量相對比較龐大，并不能單純因為某個算法的計算時間短、效率高就判斷該種方法更加優秀，對不完整數據的缺失插補目的是得到相對完整的數據，便于對相關事件更好的分析和判斷，因此，數據插補的精度尤為重要，因此對三種不同算法的插補精度進行仿真對比實驗，來證明所提插補算法的性能，具體結果如圖6所示。

從圖6中可以看出，隨著數據缺失率的不斷增長，原始數據中可利用的有效信息含量越少，這對不同插補算法的影響是相同的，算法的準確度都會隨之下降，但經過比較混合缺失插補法、缺失率插補法和所提算法的仿真結果可知，當缺失率保持在30%以內時，混合缺失插補法和缺失率插補法對不完整數據的缺失插補準確度均保持在75%以上，插補效果較好，但當缺失率30%之后，這兩種方法的插補準確度下降較為明顯，無法在有效信息較少的情況下很好地預測插補值，而所提算法在數據完全缺失的情況下，插補準確度能夠保持在50%以上，對缺失數據的預測能力更好。

圖6 不同方法缺失數據插補精準度

5 結論

本文提出的基于隨機森林的不完整數據缺失插補算法，通過建立隨機森林模型并擬定獨立決策樹，經過減少數據參數不均、處理噪聲等相關預處理操作后，使原始數據不受外力干擾，能夠清晰呈現有效信息，通過多角度和多迭代的插補計算，得到最終的數據插補值，有效處理高維數據。經過仿真證明，所提算法彌補了數據的不確定性，插補準確度較高，在不影響算法準確度的同時提高了插補運算的效率，能夠提取到數據中的輔助變量信息，魯棒性好，更加適合大數據背景下的不完整數據處理和分析。