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

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

關(guān)鍵詞：數(shù)據(jù)缺失;機(jī)器學(xué)習(xí);缺失值插補(bǔ);隨機(jī)森林

中圖分類號：TP399 ? ? 文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

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

國外有關(guān)缺失數(shù)據(jù)的插補(bǔ)研究相對較早，提出了一些經(jīng)典的數(shù)據(jù)缺失填補(bǔ)算法，如KNN插補(bǔ)算法、MICE[3]（基于鏈?zhǔn)降亩嘀夭逖a(bǔ)）算法、MissForest[4]算法、FAMD因子分析填補(bǔ)算法、matrix completion[5]算法等。

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

2 相關(guān)算法研究

2.1 MissForest算法原理

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

①用均值填補(bǔ)等簡單填補(bǔ)算法對缺失值進(jìn)行初始填補(bǔ)。

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

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

2.2 K折交叉驗證

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

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

4 試驗與分析

4.1 試驗環(huán)境

本研究中所做試驗的開發(fā)環(huán)境部署于虛擬機(jī)之上，處理器4核心3.6 GHz、8 GB內(nèi)存、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‰。為進(jìn)行缺失填補(bǔ)測試，本研究模擬隨機(jī)缺失的情況。首先隨機(jī)生成與數(shù)據(jù)集大小相同的0-1矩陣，將矩陣中“0”位置對應(yīng)的數(shù)據(jù)集位置置空，0-1矩陣中0的數(shù)量即缺模式數(shù)據(jù)缺失值的比例。由于本研究用于測試的數(shù)據(jù)集相對較小，K折驗證算法中K的取值<3，且判定當(dāng)K折分段數(shù)據(jù)集小于缺失數(shù)據(jù)集記錄數(shù)時將不再拆分;將填補(bǔ)數(shù)據(jù)與原完整數(shù)據(jù)集進(jìn)行根方誤差（RMSE）的對比分析。

4.3 試驗結(jié)果比較

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

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

[2]岳勇，田考聰.數(shù)據(jù)缺失及其填補(bǔ)方法綜述[J].預(yù)防醫(yī)學(xué)情報雜志，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ī)學(xué)，2018（4）：8-10，80.

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

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

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

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

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

[12] 劉琚，杜若畫，吳強(qiáng)，等.一種基于張量分解的醫(yī)學(xué)數(shù)據(jù)缺失模態(tài)的補(bǔ)全算法[J].數(shù)據(jù)采集與處理，2021（1）：45-52.

[13] 殷振滔. 隨機(jī)缺失值填補(bǔ)及其效果研究[D].上海：上海師范大學(xué)，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.