一种基于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.