Spark環境下不完整數據集成填充方法

鄒萌萍，彭敦陸

(上海理工大學 光電信息與計算機工程學院，上海 200093)

1 引 言

自進入大數據時代以來，數據日益極速增長和積累，對工業、金融等各個行業都有著無比重要的應用價值.如何高效且精準地從這大量數據資源中挖掘出有價值的信息已成為了當今研究者們廣泛關注的焦點.而現實中，由于數據采集過程中的丟失或網絡傳輸過程中的錯誤，數據不完整已成為一個常見且不容忽視的嚴重問題.基于不完整數據的挖掘工作嚴重影響著信息的準確性和可利用性，更對后續深度學習和模型建立等工作有著直接或間接的深遠影響.因此，不完整數據的填充應運而生，為大數據的分析帶來了巨大的挑戰.

直至今日，國內外學者已經提出了許多對不完整數據進行填充的方法.雖然一些方法在特定條件下都有著很好的填充效果，但都局限于單一類型的缺失數據填充，或適宜于連續型缺失變量，或適宜于分類型，未充分考慮數據對象的類型特征，對于真實數據中多種缺失類型共存的情況，易忽略不同類型對象之間的相互作用，嚴重影響填充結果的準確性.鑒于集成學習中的隨機森林能有效地處理混合型變量的數據，Daniel等將其引入到對不完整數據填充的研究，構建了MissForest[1]，并取得了很好的填充效果.這也意味著集成學習在混合類型的不完整數據填充問題上有著明顯的優越性.但實踐也表明，MissForest在運算效率上有著很大的不足，極易產生過擬合的現象，這對數據量龐大的真實數據而言，無疑也是不推薦的.

針對大數據的缺失值處理，運算效率自然是學者們廣泛關注的焦點之一.分布式和并行化技術的發展為大數據研究提供了有效提升運算效率的環境.其中，Apache Spark(1)http://spark.apache.org作為一款基于內存快速處理大數據的計算框架，與機器學習算法和交互式數據挖掘的結合成效卓著.Chen等人提出的Spark平臺大數據的并行隨機森林算法[2]在分類精度和運算效率上都有著很大的優勢，可見機器學習算法和Spark技術的結合在效率方面的優越性顯而易見.因此，如何最大限度地利用Spark框架的并行計算優勢來解決不完整大數據的填充問題可見尤為重要.

針對以上問題，本文提出了一種在Spark分布式環境下基于集成學習的不完整數據集成填充方法.該方法引入XGBoost[3]算法，保留了對多種數據類型的處理特性，解決了基于隨機森林模型的過擬合問題，從而實現對混合數據類型的有效填充.同時，優化XGBoost算法以將其多級并行化，將同一類缺失劃分到相同的簇中，并在Spark環境下進行了模型實現和驗證，以解決運算效率的不足.實驗結果表明，本文所提出的填充技術能夠實現對混合型缺失變量的快速填充，不僅保證了缺失數據的填充精度，同時滿足了大數據背景下對數據處理的要求.

2 相關工作

2.1 不完整數據填充

目前國內外學者已經提出了不少解決不完整數據的充填方法.最樸素的填充方法莫過于用統計值(均值、中位數等)或頻率最高的數據進行插補.方法雖然簡單，但是誤差比較大，精確度也較低.后續，無論是基于統計學的填充方法，還是基于機器學習的填充方法，都可以根據其填充的數據類型分為三種：連續型、分類型以及混合型.在已有填充方法中，回歸方法和支持向量機較為常用，對于連續型變量，可以利用線性回歸和支持向量回歸法來擬合估計其取值；而對于分類型變量，則可以利用邏輯回歸或支持向量機來估計其取值.此外，期望值最大化和基于貝葉斯的填補方法也常被用于處理不完整數據的填充，但都局限于單一類型的缺失.

當前，關于混合類型數據填充的文獻相對較少.對混合型變量的考量最早出現在魯賓(1978)提出的多重填補理論[4]中.基于K近鄰估計的充填方法(KNNI，K-Nearest Neighbor Imputation)[5]是實際應用中較為常見且效果很好的，其基于最靠近的k個觀測樣本進行缺失值的預測，分別用投票法和平均法處理分類型和連續型變量.基于決策樹的填充方法，是利用已有數據構建樹模型，常與EM算法結合以便于處理混合類型變量.但決策樹的訓練過程可能會出現過擬合現象，容易導致分類精度不高、決策時間過長.MissForest使用隨機森林作為回歸方法來估計缺失值，不需要假設數據的分布情況，對不同數據類型的填充都有著較高的準確度.

2.2 XGBoost集成學習算法

集成學習[6]通過結合多個學習算法來達到更好的預測表現，其使用多個學習器共同決策比使用單個學習器的預測更加準確.其次，集成學習器在大幅度提高基學習器精確率的同時，保證了基學習器的多樣性，這在處理混合類型不完整數據填充問題上有著明顯的優越性[7].

XGBoost(Extreme Gradient Boosting)由華盛頓大學的陳天奇博士于2016年提出，是集成學習中梯度算法的高度實現.其本質上是一個多輪迭代的過程.每輪迭代后產生一個弱學習器，然后基于該學習器的殘差訓練下一輪的學習器，最終的集成學習器則由每輪訓練所得的弱學習器加權求和而獲得.在傳統梯度提升算法的基礎上，XGBoost做了如下優化：

1)引入了正則化項來控制模型復雜度，優化目標函數；

2)對損失函數進行二階泰勒展開，提升最優解的收斂速度；

3)采用列采樣策略來減少訓練時間；

4)采用交叉驗證機制在每次迭代中運行交叉驗證，以便一次運行即可獲得精確的最優增強迭代數.

此外，XGBoost同隨機森林(RF，Random Forest)一樣能很好地處理混合類型的數據，同樣具備處理缺失值的內置例程，也允許交互和非線性(回歸)效應.實際運用中，基于RF的缺失值填充技術有著過擬合與運算效率上的不足.相比之下，上文1)3)兩項措施的應用避免了過擬合現象的發生.其次，XGBoost采用加權分位數法來搜索近似最優分裂點，并利用CPU多線程實現了并行計算，有效地彌補了運算效率上的不足.

因此，采用XGBoost對不完整數據進行填充，更能滿足大數據背景下對運算效率的需要，也能避免過擬合的發生.

2.3 Spark計算框架

由于MapReduce計算框架[8]的中間結果集緩存在外置存儲系統中，且結構過于簡單，不適宜于機器學習等高復用、高迭代的場景.因此，加州大學伯克利大學AMPLab實驗室發布了Spark分布式計算框架[9].Spark是一種基于內存的通用高性能并行化計算工具.相比于MapReduce，Spark主要有著以下幾點優勢：

1)Shuffle過程中的中間結果緩存于內存中，相較于外部存儲設備，內存RAM的IO讀寫速度能有效地提升計算效率；

2)作為分布式程序的邏輯結構，DAG模式的引入，有效增強了自己結果集的復用性和靈活性，解決了機器學習算法中的高迭代運算問題;

3)Spark在程序啟動時即申請資源池，直至計算全部完成才釋放，計算過程中每個線程按需從資源池獲取資源，這一線程級別的資源分配方式，大幅減少了各階段申請資源的時間消耗[10].

因此Spark能更好地適用于數據挖掘與機器學習等需要迭代的分布式算法.

3 SXGBI—基于Spark的XGBoost填充模型

本節主要介紹基于XGBoost的數據填充算法在Spark平臺上的實現.SXGBI填充不完整數據的過程如圖1所示.填充模型的實現主要包括3個階段：預處理、模型構建和缺失值填充.

3.1 預處理

預處理過程主要是對模型的并行化設計，并為后續的模型構建提供準備工作.

3.1.1 并行化設計

為了充分發揮分布式框架的計算性能優勢，本文主要從兩個方面考慮對算法進行并行化設計：數據并行化和任務并行化.

1)數據并行化：在物理層面上對數據進行劃分，將計算所需數據分配到集群中各個Slave計算節點的機器上，各節點完成計算再將結果提交給Master節點.

2)任務并行化：XGBoost算法本身即支持并行處理，這也是選擇XGBoost作為基填充器的原因之一.不過XGBoost的并行并不是在模型上的并行，它也是一種串行的結果，需要不斷迭代的過程，它的并行是在特征粒度上的.結合這一特性，本文在以下兩方面進行并行化處理：

圖1 SXGBI模型框架Fig.1 Framework of SXGBI

一是預排序并行化：在訓練填充模型之前，XGBoost預先對數據進行了基于數據塊的預排序，采用壓縮技術將數據集切割成多個塊，并在每個數據塊中按照各特征值排序后對樣本的索引進行存儲，并行操作每個數據塊；

其次是分裂節點并行化：在進行節點分裂時，并行多線程計算每個特征的熵，以選擇增益最大的特征進行分割.

3.1.2 數據預處理

RDD(Resilient Distributed Dataset)是Spark提出的彈性分布式數據集.因此，模型一開始先要使用parallelize算法將原數據集轉化為Spark能處理的RDD形式.RDD是一種數據的集合，這個數據集合被劃分成為許多個數據分區.結合XGBoost基于數據塊(Block)的存儲結構，RDD形式的原數據按照不同的塊進行分區，并被分布式地存儲到不同的節點上.

3.2 模型構建

模型構建的主要任務是訓練各基學習器，并結合并行化處理，集成成為準確率和執行效率都較高的組合學習模型.

3.2.1 模型訓練

模型訓練過程主要是基于XGBoost的訓練，其過程中主要有以下幾個方面：

1)稀疏自適應分割策略：鑒于訓練集含有部分缺失值，開始模型訓練后，先采用默認值的方式忽略含有缺失值的數據(即稀疏數據)，然后利用那些不含缺失的樣本(即完整樣本)來選擇最優分裂點，以自動處理稀疏數據的方式構建初始樹模型.

對于缺失值的處理，如果某個樣本在特征Ak上的值tk缺失，則對于該特征上含有缺失值的所有樣本做如下處理：全部分到左子節點，或全部分到右子節點.因此，根據不同的選擇方向即可以得到兩個不同的模型，將這兩個模型中較優模型對含有缺失數據的樣本(不完整樣本)分裂方向作為最優分裂方向.這樣，通過訓練數據自動學習來確定不完整樣本的分裂方向避免了預填充可能帶來的偏差，更利于保留原始數據的特性.

2)基組合學習器的訓練：如圖1的模型構建流程所示，m為Spark集群的計算節點數量.SXGBI在Spark的各計算節點上分別執行一個集成學習器的迭代訓練，得到m個基組合學習器.單個Slave節點上基組合學習器的訓練是串行迭代的過程，SXGBI將數據預處理后的訓練集分成n份后，迭代執行n輪基學習器的訓練.其中，子訓練集i(1≤i≤n)用于執行第i輪基學習器的訓練，且每一輪的訓練都要基于上一輪的訓練結果.比如，已知基學習器p和q(1≤p

此外，由4.3節實驗2各對比方法對缺失率的敏感度可知，隨著缺失量的增加，填充結果的偏差逐漸增大，所以在每一輪迭代的訓練過程中，對于每一個缺失屬性Ai={A1，A2，…，Al}，本文根據其缺失量由少到多依次計算.

3)組合學習器的訓練：執行上一步驟后可得到m個基組合學習器.分別用驗證集驗證各基組合學習器的預測能力.結合驗證結果，SXGBI采用投票的方法來獲得最終的組合學習器.

通過以上流程，SXGBI將學習器的訓練并行化，實現了在不降低執行效率的同時還能提升組合學習器的精確性.

3.2.2 參數設置

XGBoost模型中涉及多種參數，已有一些學者對其調優做了進一步的研究.根據朱明等[11]在其文章中采用遍歷方法確定的參數取值，本文中對參數的設置見表1.

表1 XGBoost參數設置Table 1 Parameter settings of XGBoost

3.3 缺失值填充

算法1給出了缺失值填充的偽代碼.對于原數據中的缺失值Mi，首先根據數據集所給定的特征屬性類別標注及統計學變量分類規則來判斷Mi是屬于分類型變量還是連續型變量.若Mi?contibuous，即Mi為連續型變量，則將使用基于回歸樹模型的XGBoost方法進行預測填充；若Mi?categorical，即Mi為分類型變量，則將使用基于分類樹模型的XGBoost方法進行預測填充.

算法1.基于XGBoost的缺失值填充

輸入：D:不完整數據集：

M{M1,…,Mi,…,Mn}:特征屬性集合：

Mi?{continuous,categorical}

輸出：D′:填充后的完整數據集

1.Begin:

2.fori in 1:ndo

3.ifMi?continuousthen

5.endif

6.ifMi?categoricalthen

8.endif

9.endfor

10.returnR′

4 實驗及分析

實驗環境為1個Master、7個Slave節點的spark分布式集群.每個節點的配置如下：操作系統為Ubuntu 16.04，64位，處理器為2.6Hz六核Intel Core i7，16GB內存；在Hadoop 2.7.1上構建的集群環境Spark 2.1.0；編程語言采用的是Scala 2.11.8.

4.1 數據集及實驗設置

為了全面控制本文使用的數據庫中的缺失值，本文選擇的所有實驗數據集均為沒有缺失記錄的完整數據集.為了評估本文所提模型對不完整數據集填充問題的有效性及對大數據處理的有效性，采用了Abalone、KDD99[12]和URL Reputation[13]等3個數據集，每個數據集都同時包含連續型和分類型特征屬性.表2列舉了上述數據集的實例個數和屬性個數.

表2 數據集Table 2 Datasets

為了證明本文方法的性能，實驗部分將本文方法SXGBI與KNNI、基于C4.5的決策樹填充方法(DTI，Decision Tree Imputation)和基于隨機森林的填充算法(MissForest)等常見的混合類型填充方法進行了對比.

4.2 評估指標

鑒于缺失變量有分類型和連續型兩種數據類型，所以實驗也需要從這兩個方面對填充結果進行評估.本文采用均方根誤差(RMSE，the Root Mean Squared Error)、標準化均方根誤差(NRMSE)和平均絕對百分誤差(MAPE，Mean Absolute Percent Error) 來評估連續型變量的性能，用F1值F1[14]和誤分類比率(PFC，the Proportion of Falsely Classified entities)[1]來評估分類型變量.

(1)

(2)

(3)

(4)

其中，TP表示當預測為真時，預測正確的數量；FP表示當預測為真時，預測錯誤的數量；FN表示預測為假時，預測錯誤的個數.

(5)

NfalseC表示預測中分類錯誤的個數，而NtrueC表示分類正確的個數.

對于以上5種情況，RMSE、NRMSE和MAPE越小表示性能越好，偏差越小，且MAPE是用來評估同一組數據上的不同模型.如，在同一組數據集上，模型a比模型b的MAPE大可以說明模型b的效果比a好，如果只說某一模型的MAPE=20%，并不能判斷該模型的好壞；PFC越接近0效果越好；而F1越接近1表示性能越好.

此外，算法加速比作為一個常見的評價程序并行化效果的指標，是算法在單機環境下和分布式環境下執行所消耗時間的比率值.后續實驗中將采用算法加速比來評估執行效率.

4.3 實驗結果分析

實驗過程中，SXGBI默認是在3個計算節點的Spark集群環境上實現的，而其它對比方法默認在單機模式上實現.MissForest-s是在3個計算節點的Spark集群環境上實現的MissForest算法.

實驗1.不同填充方法準確率的比較

本部分實驗選用KDD99網絡入侵檢測數據集作為實驗數據集.KDD99是從一個林肯實驗室模擬的美國空軍局域網上采集來的9個星期的網絡連接和系統審計數據，共計500萬條記錄，每個連接記錄包含了41個固定的特征屬性和1個類標識，標識用來表示該條連接記錄是正常的，或是某個具體的攻擊類型.在41個固定的特征屬性中，9個特征屬性為分類型，其他均為連續型.本文僅使用其中完整的訓練數據500000條作為原始完整數據集KDD99.實驗開始前，在KDD99完整數據集上使用隨機生成器刪除15%的記錄，生成本部分實驗的模擬數據集KDD99′.

圖2 不同方法在KDD99′數據集上的填充結果Fig.2 Results of different methods on KDD99′

為了驗證實驗中各方法對混合類型不完整數據的填充效果，本文用KNNI、DTI、MissForest、MissForest-s以及SXGBI分別對KDD99′進行缺失數據的填充，并分別采用NRMSE、MAPE和F1計算每個方法所填充連續型數據和分類型數據與原完整數據集KDD99的偏差和準確性.

對比圖2中的結果，本文方法SXGBI無論是對連續型還是分類型數據的填充上都優于其它4種填充方法.結合圖(a)、(c)可見，DTI準確度僅次于本文的SXGBI，但F1卻是最低的.結合3個指標，對比MissForest和MissForest-s可見，加入Spark并行化計算框架能夠有效地提升不完整數據的填充效果；比較MissForest-s和SXGBI，由于XGBoost對過擬合現象的有效解決，SXGBI取得了更小的NRMSE、MAPE、PFC值及更高的F1值，這也進一步證明了本文選擇XGBoost作為集成填充方法基填充器的優越性.

實驗2.缺失程度對填充效果的影響

為了評估每個方法對缺失程度的敏感度，本部分用SXGBI在不同缺失程度的Abalone模擬數據集上進行填充實驗，并分別使用RMSE、F1和PFC評估每個模擬數據集上的填充精確度.如圖3所示.

圖3 不同缺失程度下對Abalone的填充結果Fig.3 Results of imputing Abalone under different degrees of missing

1)當完整比相同時，缺失率的增長會極大影響填充的準確性.完整比一致時，隨著缺失率的增長，RMSE和PFC 不斷增大，F1不斷降低，填充準確度逐漸下降.實驗中的方法對缺失率的敏感度都較高，但相比而言，SXGBI在缺失率較高的情況下仍可以達到相對其它方法更好的填充效果.

2)在缺失率相同但完整比不同的情況下，完整比高的填充效果明顯更佳，因為完整數據占比多更有益于模型的自主學習與訓練.隨著完整比的下降，如實驗中的其它方法一樣，SXGBI的填充效果也隨之減弱，但SXGBI減弱的幅度相對較小.

實驗3.不同方法在大數據集上的執行效率

為了驗證本文所提出的Spark平臺上集成填充模型的計算效率，本實驗就所提方法SXGBI與KNNI、MissForest兩種單機填充方法在URL Reputation數據集上進行了填充實驗對比，并記錄了各方法執行過程的運行時間.運行時間比，是方法執行所消耗時間與當前已知最短運行時間的比率值.表3顯示了各方法執行的運行時間比.SXGBI的計算時間明顯短于其它兩個方法，執行效率高，這對于大數據的處理明顯有著運行效率上的優勢.

表3 不同方法的運行時間比對比Table 3 Run times ratios of different methods

為了深入探究SXGBI的分布式處理優勢，本文進一步測試了SXGBI的加速比隨集群點數量的變化情況.實驗仍在URL Reputation數據集上進行，分布式集群節點的數量依次取{1，2，3，4，5，6，7}，并記錄各節點數量時的算法加速比.由圖4中SXGBI算法的加速比實驗結果可知，隨著Spark分布式集群節點數量的增加，SXGBI加速比呈線性增長，但同時其增長趨勢逐漸減緩.這也表明，在Spark分布式環境下訓練的XGBoost有著更好的運行效率.面對海量不完整大數據時，可以通過增加Spark分布式集群中計算節點的數量來大大提升SXGBI的填充效率.

圖4 不同集群點數量的加速比Fig.4 Speed-up ratio of different cluster points

5 總 結

Spark環境下不完整數據集成填充方法的提出，對于大數據時代中數據的缺失問題有著十分重要的作用.本文綜合考慮了真實數據中混合類型變量及數據集龐大兩方面問題，在XGBoost集成填充缺失數據的基礎上，通過結合分布式并行化的設計，提出了在Spark平臺上改進的XGBoost填充方法—SXGBI.一系列實驗結果表明，相比已有的填充算法，SXGBI無論對連續型還是分類型缺失變量都有著較高的填充準確度，同時也能適應大數據時代，滿足快速處理大數據的需求.在下一階段的工作中，我們將對不完整數據集進行深入分析，綜合考慮樣本不同缺失程度與不同類別的權重，改進采樣方法；同時對算法進行優化和拓展，以獲得更好的填充效果.