一種基于MissFroest的并行插補算法

華南　馬春萍　朱彥霞　劉惠萍　曹彥　王飛　張利鵬

摘 要：本研究針對大數據分析預處理的缺失數據值填補問題及解決方案進行了探討，提出了一種用于缺失值填充的插補算法。該算法在MissForest算法基礎上融合K折交叉驗證的思想，通過在不同缺失率下的插補試驗與分析表明：該算法的填補誤差小于傳統的CNN插補算法，運行時間復雜度優于基礎的MissForest算法，具有較強的泛化能力。

關鍵詞：數據缺失;機器學習;缺失值插補;隨機森林

中圖分類號：TP399 ? ? 文獻標志碼：A ? ? 文章編號：1003-5168（2022）3-0018-04

DOI：10.19968/j.cnki.hnkj.1003-5168.2022.03.004

A Parallel Interpolation Algorithm Based on MissFroest

HUA Nan MA Chunping ZHU Yanxia LIU Huiping CAO Yan WANG Fei

ZHANG Lipeng

（1. China Radio and Television Henan Network Co.， Ltd.， Zhengzhou 450000，China;2. The First Affiliated Hospital of? Henan University of CM，Zhengzhou 450000，China;3.Henan General Hospital，Zhengzhou 450002，China; 4. College of Information Engineering? Xuchang University， Xuchang 461000，China;5.Henan University of Animal Husbandry and Economy，Zhengzhou 450000，China）

Abstract：This study discusses the problem of missing data value filling in the preprocessing of big data analysis and its solutions， and proposes an interpolation algorithm for missing value filling. This algorithm combines the idea of K-fold cross-validation on the basis of the MissForest algorithm. Interpolation experiments and analysis under different missing rates show that the algorithm has less filling error than the traditional CNN interpolation algorithm， running time complexity is better than the basic MissForest algorithm， and has a strong generalization ability.

Keywords：missing data; machine learning; imputation of missing values; random forest

0 引言

隨著信息技術、互聯網技術、物聯網技術的迅速發展，人們已經進入了高數字化“大數據”時代，大數據的存儲、分析及有效利用成為各行各業廣泛關注的焦點。數據的采集與處理過程是數據分析的前置過程，也影響著數據分析的質量與效率。由于采集設備故障，導致調查問卷的選擇性認知程度、數據錄入過程存在錯誤，部分數據損壞或丟失等采集過程不可控因素較多，數據的“大”與缺失并存，形成了大數據中“天然的矛盾體”，數據的缺失對數據的分析會產生樣本復雜性增加、預測評估偏差、結論導向偏離等不同程度的影響[1]。如何有效處理缺失數據成為數據分析中的重點問題與挑戰。

本研究梳理了數據缺失的機制、處理方法等國內外相關研究，在隨機缺失機制下，提出了一種基于MissForest的并行缺失值插補方法，并通過模擬試驗進行了分析及效果評價，為缺失數據插補提供了一種新方法。

1 國內外研究現狀

數據的缺失機制主要分為完全隨機缺失（MCAR）、隨機缺失（MAR）、完全非隨機缺失（MANR），處理缺失的處理方法主要有刪除和插補兩種。刪除數據會造成分析數據信息量的丟失以及分析的不完整，對研究數據的采集工作也是一種巨大的浪費[2]。數據插補通常是通過計算實現對缺失值替代的一種方式，通常分為單一插補和多重插補兩種類型。

國外有關缺失數據的插補研究相對較早，提出了一些經典的數據缺失填補算法，如KNN插補算法、MICE[3]（基于鏈式的多重插補）算法、MissForest[4]算法、FAMD因子分析填補算法、matrix completion[5]算法等。

國內對數據缺失處理的研究雖然起步時間比國外晚些，但近些年的研究逐漸“升溫”。李琳等[6]基于醫學臨床數據集，比較了4種數據插補算法在不同缺失率下插補的效果與性能;楊日東等[7]在K近鄰算法的基礎上提出一種局部K近鄰插補算法，用于提升在缺失率較大情況下的數據填充性能;楊弘等[8]通過模擬缺失數據，對比分析了采用Missforest、因子分析（FAMD）、K-近鄰（KNN）、基于鏈式的多重插補算法進行數據插補的性能;石清陽等[9]論述了時效性隨機試驗過程中存在的結局缺失問題、缺失機制、可能的選擇性偏倚和處理結局缺失的方法及推薦;李業錦等[10]針對隊列研究中的數據缺失問題，用蒙特·卡羅方法模擬產生缺失數據，并對缺失數據分別采用均值填補、EM算法、KNN填補、隨機森林等缺失數據方法的填補效果進行了分析評價;黃裕[11]通過引入高斯核函數、建立回歸模型，構建了一種基于核回歸的多視角數據缺失不全算法，并進行了模擬驗證;劉琚等[12]針對醫學影像數據采集過程中可能存在的模態數據缺失問題，構建了一種基于張量分解的數據缺失模態不全算法。本研究則基于MissForest的算法并融合了K折驗證的思想，提出了一種基于MissForest的并處缺失值填充算法，并進行了試驗模擬與分析。

2 相關算法研究

2.1 MissForest算法原理

MissForest算法是由Stekhoven于2012年首次提出，是一種基于隨機森林的迭代填補算法，其主要思想是用預測值對缺失數據進行填補，其填補過程[13]如下。

①用均值填補等簡單填補算法對缺失值進行初始填補。

②將X中缺失列按缺失率從小到大重新排列，缺失列指標集標記為M。

大多數傳統的缺失插補算法僅適用于連續型數值數據或可量化為數值的分類數據等，對混合數據及變量非線性關系的負責數據表現不佳。有相關研究表明，MissForest插補對數據的條件假設較少且算法具有較強的魯棒性[14-15]，由于K-近鄰算法、EM算法等，MissForest對于大數據量處理的時間復雜度與空間復雜度較高。

2.2 K折交叉驗證

K折交叉驗證主要是為防止預測模型過于復雜而產生過擬合現象從而采取的一種方法，其基本原理如圖1所示。首先將原始數據隨機分成K份，然后每次選取其中的1份作為測試數據集，其余K-1份作為訓練數據集，重復K次交叉驗證，并取K次統計指標的均值作為模型的評價指標。

3 基于MissForest融合K折交叉驗證并行算法

4 試驗與分析

4.1 試驗環境

本研究中所做試驗的開發環境部署于虛擬機之上，處理器4核心3.6 GHz、8 GB內存、512 GB存儲。軟件：Linux發行版本CentOs 7 64bit環境，python 3.9;算法編碼測試環境：Jupter notebook，算法框基于Tensorflow 2.0。

4.2 試驗數據及方法步驟

為了驗證算法的有效性，試驗中選取了Breast cancer data數據集[16]（記為數據集D0），原始數據集缺失率<5‰。為進行缺失填補測試，本研究模擬隨機缺失的情況。首先隨機生成與數據集大小相同的0-1矩陣，將矩陣中“0”位置對應的數據集位置置空，0-1矩陣中0的數量即缺模式數據缺失值的比例。由于本研究用于測試的數據集相對較小，K折驗證算法中K的取值<3，且判定當K折分段數據集小于缺失數據集記錄數時將不再拆分;將填補數據與原完整數據集進行根方誤差（RMSE）的對比分析。

4.3 試驗結果比較

4.3.1 不同缺失比例下，插補算法性能比較。試驗過程模擬了數據缺失比例在5%、10%、15%、20%、25%、30%情況下，采取K值驗證與MissForest相融合并行插補數據的過程，并且分析了在各種情況下的根方誤差，如表1所示。同時與傳統的KNN算法插補性能進行了比較。

從表1可以看出，隨著缺失比例的增高，填補的根方誤差也隨之增加;K分段的增多對誤差率也有所影響，填補誤差優于經典的KNN算法。

4.3.2 運行時間對比。從表2可以看出，當缺失比例比較大時，基于MissForest的并行缺失填補算法運行時間性能表現良好。

5 結語

在MissForest的基礎上融合K折驗證的思想，實現了基于MisssForest的并行化數據插補，通過對算法的仿真試驗，驗證了該算法填補的效率，并行化運行在一定程度上降低了MissForest算法數據插補算法的時空復雜性、填補誤差小于傳統的KNN插補算法，具有一定的泛化能力。對于數據量較少的情況，K的選取不宜過大，同時切分后的數據一般不應小于缺失數據量。該算法分段并行用預測值填補數據的過程也為增量的數據預測提供了借鑒。

參考文獻：

[1] MANDEL J S P . A Comparison of Six Methods for Missing Data Imputation[J]. Journal of Biometrics & Biostats， 2015（1）.

[2]岳勇，田考聰.數據缺失及其填補方法綜述[J].預防醫學情報雜志，2005（6）：683-685.

[3] BUUREN S V，GROOTHUIS-OUDSHOORN K .MICE： Multivariate Imputation by Chained Equations in R[J]. Journal of statistical software， 2011（3）：1-68.

[4] STEKHOVEN D J， BüHLMANN P. Missforest nonparametric missing value imputation for mixed-type data[J]. Bioinformatics， 2011（1）：112-118.

[5] RAHUL M，TREVOR H， ROBERT T. Spectral Regularization Algorithms for Learning Large Incomplete Matrices[J].Journal of machine learning research ： JMLR，2010，11.

[6] 李琳，楊紅梅，楊日東，等.基于臨床數據集的缺失值處理方法比較[J].中國數字醫學，2018（4）：8-10，80.

[7] 楊日東，李琳，陳秋源，等.LKNNI：一種局部K近鄰插補算法[J].中國衛生統計，2019（5）：780-783.

[8] 楊弘，田晶，王可，等.混合型缺失數據填補方法比較與應用[J].中國衛生統計，2020（3）：395-399.

[9] 石清陽，李玲，任燕，等.實效性隨機對照試驗中的統計方法（Ⅱ）：解決結局缺失問題[J]. 中國循證醫學雜志，2021（6）：729-736.

[10] 李業棉，趙芃，楊崳惠，等.隊列研究中縱向缺失數據填補方法的模擬研究[J].中華流行病學雜志，2021（10）：1889-1894.

[11] 黃裕.基于多視角缺失補全算法的數據挖掘研究[J].計算技術與自動化，2018（2）：67-72.

[12] 劉琚，杜若畫，吳強，等.一種基于張量分解的醫學數據缺失模態的補全算法[J].數據采集與處理，2021（1）：45-52.

[13] 殷振滔. 隨機缺失值填補及其效果研究[D].上海：上海師范大學，2018.

[14] TANG F， ISHWARAN H.Random forest missing data algorithms[J].Statistical Analysis and Data Mining： The ASA Data Science Journal， 2017（6）：1-19.

[15] GóMEZ-MéNDEZ， IRVING， JOLY E.Regression with Missing Data， a Comparison Study of TechniquesBased on Random Forests[J]. 2021.