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

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

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

關鍵詞：數(shù)據(jù)缺失;機器學習;缺失值插補;隨機森林

中圖分類號：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 引言

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

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

1 國內外研究現(xiàn)狀

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

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

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

2 相關算法研究

2.1 MissForest算法原理

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

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

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

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

2.2 K折交叉驗證

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

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

4 試驗與分析

4.1 試驗環(huán)境

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

4.2 試驗數(shù)據(jù)及方法步驟

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

4.3 試驗結果比較

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

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

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

5 結語

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

參考文獻：

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

[2]岳勇，田考聰.數(shù)據(jù)缺失及其填補方法綜述[J].預防醫(yī)學情報雜志，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] 李琳，楊紅梅，楊日東，等.基于臨床數(shù)據(jù)集的缺失值處理方法比較[J].中國數(shù)字醫(yī)學，2018（4）：8-10，80.

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

[8] 楊弘，田晶，王可，等.混合型缺失數(shù)據(jù)填補方法比較與應用[J].中國衛(wèi)生統(tǒng)計，2020（3）：395-399.

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

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

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

[12] 劉琚，杜若畫，吳強，等.一種基于張量分解的醫(yī)學數(shù)據(jù)缺失模態(tài)的補全算法[J].數(shù)據(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.