针对目前数据挖掘任务中广泛存在的缺失值问题，缺失值插补(missing value imputation，MVI)是解决该问题的重要方法，MVI利用被观察到的原始完整值估算缺失值。因为人为记录数据具有信息被遗漏、数据采集失误、机器故障等缺点，所以现实数据集往往存在大量的缺失值。数据不完整会使系统丢失大量有用信息，而数据的完整性恰是实现数据分析、数据挖掘以及机器学习任务的先决条件。MVI通过合理可靠的插补值代替缺失值，为系统提供完整数据，从而减少数据缺失对后续数据分析算法性能的影响。有效的MVI算法能显著提高数据的利用效率，在处理包含缺失数据的实际应用中具有重要意义。例如，统计人口基因数据并推断缺失基因型及估计染色体单倍型阶段^[1]，医学领域中插补乳腺癌患者数据并预测患者是否复发^[2]，对空气污染物时间序列的缺失数据进行插补以提高PM2.5浓度预测精度^[3]等等。

MVI算法主要有多重插补算法^[4-5]、逻辑回归(logistic regression，LR)插补算法^[6-8]、基于核函数的插补算法^[9-10]、基于奇异值分解(single value decomposition，SVD)的插补算法^[11-13]、基于最近邻(K-nearest neighbor，KNN)的插补算法^[14-15]、基于人工神经网络的插补算法^[16-18]、基于深度学习的插补算法^[19-20]等。这些算法大多针对小规模数据集的缺失问题进行研究。然而，随着数据传输和存储技术发展，数据量呈爆炸式增长，大规模数据的缺失值问题日益凸显，为数据分析带来巨大挑战。

大规模数据缺失值的产生原因，可归纳总结为内因和外因2方面。一方面，随着数据特征和样本量增加，数据出现缺失值的概率会提高，有些数据本来就含有无法测量、无法收集的部分，特别是生物信息学领域的数据、与时间序列相关的数据等，如单细胞测序技术的局限性使基因和细胞的测量值中零的比例高达80%，导致基因后续分析困难^[21]；多个空间和时间维度上的传感器无法完全覆盖时空交通数据，造成收集的数据稀疏，不足以支持后续交通预测的问题等^[22]。另一方面，数据的存储转换也会使数据产生缺失值，即外因有以下3种情况：

1) 数据增加速度快于数据存储速度，短时间内数据采集设备因无法处理快速增加的数据而死机。在数据存储过程中，数据流一般具有持续不间断、速度快且规模巨大的特点，因此不会对所有的数据进行永久化存储^[23]，从而造成数据缺失。

2) 数据存储设备损坏。大规模数据的实时处理对存储设备的要求很高，因此需要高性能、高吞吐率、大容量的存储设备。若无法在短时间内解决存储设备的性能局限、维护或损坏等问题，则硬件发生故障将是常态，而数据缺失问题也将时常存在且不可避免。

3) 跨平台跨区域数据存储方式的不统一。规模效应使数据必须采用分布式存储和多级存储^[24]，跨平台跨区域的数据存在异构性，对其进行整合预处理的难度很高。再者，多样性是大规模数据的特点之一，这表明数据的来源多种多样且质量无法保证，因此数据出现缺失值的概率也不低。

大规模数据通常含有大量信息，同时数据噪声的影响也随之增大，即使是小比例的数据缺失也会对后续的数据处理分析产生不利影响，增加数据挖掘过程的难度。尽管当前研究显示多数MVI算法具有良好的插补性能，然而大规模数据本身的复杂性使现有的MVI算法难以应用，具体原因可从数据层面和算法层面分析。在数据层面上，已有的工作^[25]证实Hadoop分布式文件系统(Hadoop distributed file system)^[26]会破坏数据本身的分布，传统且简单的MVI算法无法解决由数据缺失率过高导致的数据分布偏差问题，加剧属性关系的模糊性，在此情况下，MVI算法过于复杂甚至会使数据之间的联系更加混乱。在数据缺失率高、规模大的情况下，一个能保留数据分布和数据之间潜在联系的MVI算法一定程度上能弥补当前缺失数据插补存在的缺陷。在算法层面上，大规模数据集的并行运算(如Google公司提出的MapReduce架构^[27])增加了输入、输出和通信成本，由于大多数有效的MVI算法依赖耗时的迭代和递归操作，存在时间复杂度较高的缺点，这些算法的MapReduce化将使数据插补的成本大幅增加。

针对上述大规模数据插补的不足，本文以数据分布为导向，提出一种基于数据分布一致性的缺失值插补(distribution consistency-based MVI，DC-MVI)算法，该算法根据原始完整值与插补值的最大均值差异(maximum mean discrepancy，MMD)推导插补规则，实现对大规模数据缺失值的有效插补。利用随机数初始化缺失值，通过最小化插补值与原始完整值的MMD和方差来迭代优化插补值，最大限度还原数据分布。为实现对大规模数据缺失值的高效插补，DC-MVI算法使用随机样本划分(random sample partition，RSP)分布式数据模型^[25]，将大规模数据划分成多个小块，并行优化多个小块的缺失值，以提高对大规模数据缺失值的插补效率。通过详实的仿真实验对DC-MVI算法的可行性和有效性进行验证。实验结果表明：DC-MVI算法在还原数据分布上具有显著优势，能获得明显优于被比较方法的插补效果，从而证明DC-MVI算法是解决大规模数据缺失值插补问题的一种可行手段。

1 相关工作

MVI是以信息保留为导向的缺失值处理方法^[12]，与简单删除缺失值样本^[28]的方法相比，MVI丢失的信息少；与不处理缺失值的方法(如Zhang等^[29]提出不估算缺失值而构建决策树)相比，MVI能根据已有的数据和观测到的值推测已缺失的值，可有效提高未经处理的含有缺失值数据集的使用效率。随着插补理论的不断发展，研究人员采用了多种技术处理缺失数据，现有的数据插补算法大多应用于小规模数据，也有少部分研究专注于大规模数据的插补，但都有一定的局限性。本节以针对小规模数据和大规模数据的插补算法为出发点，分别介绍传统插补算法和先进插补算法。

1.1 小规模数据插补方法

在Little等^[30]对缺失值插补问题进行系统定义前，一些简单的统计方法已被尝试用于插补缺失值，如均值(mean)插补、条件均值插补、特殊值插补等。这些方法是早期使用最广泛的MVI，可大幅减少由缺失值导致的数据处理和分析方法效率低下问题。自2014年以来，也有学者将均值插补进行改进，如Morris等^[31]提出利用预测均值匹配进行多重插补，但该方法易使属性变量的分布发生改变。

随着数据插补要求的提高，一些复杂的统计MVI算法被提出。Zhang等^[6]利用逻辑回归插补临床数据；Li等^[32]通过模糊C-均值聚类算法(fuzzy C-means algorithm)进行混合数据插补；Khosravi等^[7]提出一种朴素构想学习算法，通过在使用几何规划学习朴素Bayes分布后嵌入LR分类器来预测缺失数据，但容易忽视随机误差导致的高偏置问题，且该问题会随数据量增大而更加严重。多重插补是当前应用最为广泛的统计插补框架，在大多数研究中，效果最好的多重插补为链式方程的多元插补算法(multiple imputation by chained equation，MICE)^[33]，该算法在构建插补模型时，用户需要做多项决策，如函数、变量、分类和非正态连续变量估算的方式等，且不同模型插补效果不一，插补模型对建模决策的敏感性是当前学界较为关注的研究点^{[5, 34]}。

2008—2021年，一些基于机器学习的插补算法获得的关注日益增加。基于KNN的插补算法^[35]采用相似样本的距离加权平均值进行插补，具有代表性的KNN插补算法如下：Keerin等^[36]将KNN结合聚类提出CKNN(cluster-based KNN)算法处理微阵列测量的基因表达数据集；Huang等^[14]利用交叉验证方案来优化每个缺失值的参数；GP-KNN(genetic programming imputation and KNN)^[15]结合遗传编程和KNN进行插补。尽管KNN以易于理解和实现简单的特点在实际应用中获得广泛认可，但寻找最优的近邻值依旧非常困难。同时该方法计算复杂度较高，因为每出现一个缺失值，该方法便需要搜索整个数据集。人工神经网络是机器学习领域的研究热点，常应用于数据插补的方法有生成式对抗性网络^[17]、去噪自动编码器^{[16, 37-38]}、极限学习机插补^[39-40]、遗传算法^[41]等。研究证明，在大多情况下，人工神经网络应用于数据插补的性能明显优于其他机器学习算法，但时间复杂度会随网络层数增加而增加。Gondara等^[38]使用去噪自动编码器的多重插补框架(multiple imputation using denoising autoencoders，MIDA)插补数据。Zhang等^[42]提出的端到端生成对抗网络是指在标准生成对抗性网络框架中引入一个编码器网络，该方法对生成对抗性网络的训练难度高和生成过程不稳定的特性进行了改进，而其特有的多层网络结构，使该方法不适用于大规模数据的MVI。

1.2 大规模数据插补方法

对于大规模数据MVI的研究，在满足插补效果要求的同时，还需考虑插补算法对数据分布的还原和时间成本的控制。

部分传统插补算法在大规模数据插补上具有天然优势。mean插补在时间复杂度上是其他插补算法无法超越的，但其假设变量之间的相关性为零，将所有的缺失值当作无差别的属性值，即忽略插补过程中的误差和不确定性，强行改变了变量之间的关系。最大期望(expectation maximization，EM)插补算法^[43-44]适用于大规模数据的插补。有效且大量的样本能保证极大似然估计渐近无偏并服从正态分布^[45]，但需迭代更新参数和插补值才能完成插补。这种算法易陷入局部极值，且收敛速度慢，因此计算复杂度很高。基于SVD的MVI^[46-47]算法通过挑选特征建立原矩阵，将原矩阵中的缺失值与非缺失值分离，使用SVD填充缺失值，如Zhu等^[12]利用低秩矩阵将缺失问题转换为矩阵完整问题，Mazumder等^[47]提出软阈值SVD(soft-thresholded SVD，SOFT)插补算法，Chen等^[11]提出了一种低秩矩阵分解插补模型，等等。尽管基于SVD的MVI算法对大规模数据具有很好的插补效果，但对数据类型和缺失率非常敏感^[48]。同时，特征的挑选也非常重要，在高维数据的情况下，若特征挑选得不好，计算密集矩阵的低秩矩阵SVD会非常困难。再者，由于大规模数据大多存在数据稀疏、缺失率高的问题，因此基于SVD的MVI算法在低阶真实值和高信噪比情况下效果并不好。

2018年，有学者将先进插补算法引入分布式系统中，寻求以较低的时间代价插补大规模数据，如Petrozziello等^[49]将误差反传(back propagation，BP)神经网络引入分布式系统中以对大规模数据进行插补，但该算法未考虑数据分块对插补值分布的影响。

上述用于处理大规模数据MVI问题的算法，在时间复杂度和还原数据分布等方面尚有改进余地。鉴于此，本文在大数据RSP模型框架下提出了分布式的MVI策略，即利用DC-MVI算法插补缺失数据，以处理大规模数据的MVI问题。

2 最大均值差异

MMD是一种基于核函数的分布度量指标，用于检验2个不同分布的距离差^[50]。设x、u是定义在特征空间O上的随机变量，给定M个变量x_i和N个变量u_j对应的观察值矩阵X={x₁，x₂，…，x_M }和Y={u₁，u₂，…，u_N }，i=1，2，…，M，j=1，2，…，N。MMD的定义为

$ \begin{gathered} \operatorname{MMD}(\mathcal{F}, \boldsymbol{X}, \boldsymbol{Y})= \\ \sup _{f \in \mathcal{F}}\left(\frac{1}{M} \sum\limits_{i=1}^M f\left(x_i\right)-\frac{1}{N} \sum\limits_{j=1}^N f\left(u_j\right)\right). \end{gathered} $

(1)

其中：$ \mathcal{F}$为O映射到实数空间R所有函数f的集合。该定义主要表示X和Y经过函数f: O→R高维映射后的差值上确界。由于$ \mathcal{F}$是有条件的，即既要能唯一地标识X和Y，又应具有足够的限制性来提供样本估计，再生核Hilbert空间(reproducing kernel Hilbert space，RKHS)被证明满足以上2个条件^[51]。RKHS可用空间内的点积表示f→f(x)的映射，

$ \boldsymbol{f} (x)=\langle f, \phi(x)\rangle_{\mathcal{H}} . $

(2)

其中：该式将变量x在Hilbert空间中映射成向量f(x)；$ \mathcal{H}$为一个RKHS；ϕ(x)表示特征映射，该特征映射采用规范形式ϕ(x)=k(x，·)，k(x，·)表示内核有一个固定在x的参数，第2个参数是不定的。特别注意的是，$ \langle\phi(x), \phi(u)\rangle_{\mathcal{H}}=k(x, u)$，通常情况下，用ϕ(x)能更简洁地表示特征映射，但在某些情况下，k(x，·)的表示更为清晰。设$\mathcal{F} $为RKHS，MMD可被推导为

$ \operatorname{MMD}(\mathcal{H}, p, q)=\left\|\mu_p-\mu_q\right\|_{\mathcal{H}} \cdot $

(3)

其中：p和q分别为X和Y的分布，μ_p=E_p[f(x)]和μ_q=E_q[f(u)]分别为X和Y经过映射f后的期望。将式(1)两边平方可得

$ \begin{gathered} \operatorname{MMD}^2[\mathcal{H}, p, q]=\left\langle\mu_p-\mu_q, \mu_p-\mu_q\right\rangle_{\mathcal{H}}= \\ \left\langle\mu_p, \mu_p\right\rangle_{\mathcal{H}}+\left\langle\mu_q, \mu_q\right\rangle_{\mathcal{H}}-2\left\langle\mu_p, \mu_q\right\rangle_{\mathcal{H}}= \\ E_p\left\langle\phi(x), \phi\left(x^{\prime}\right)\right\rangle_{\mathcal{H}}+E_q\left\langle\phi(u), \phi\left(u^{\prime}\right)\right\rangle_{\mathcal{H}}- \\ 2 E_{p, q}\langle\phi(x), \phi(u)\rangle_{\mathcal{H}} . \end{gathered} $

(4)

其中：x′为X中与x不同的变量，u′为Y中与u不同的变量。将期望由均值代替，式(4)可表示为

$ \begin{gathered} \operatorname{MMD}^2[\mathcal{H}, p, q]=\frac{1}{M^2} \sum\limits_{i=1}^M \sum\limits_{j=1}^M \phi\left(x_i\right) \phi\left(x_j\right)+ \\ \frac{1}{N^2} \sum\limits_{i=1}^N \sum\limits_{j=1}^N \phi\left(u_i\right) \phi\left(u_j\right)-\frac{2}{M N} \sum\limits_{i=1}^M \sum\limits_{j=1}^N \phi\left(x_i\right) \phi\left(u_j\right) . \end{gathered} $

(5)

其中：x_j和u_i分别为X和Y中的另一个变量；x_i和x_j在RKHS中的内积ϕ(x_i)ϕ(x_j)等于在原始空间中通过核函数计算得出的结果，ϕ(u_i)ϕ(u_j)与ϕ(x_i)ϕ(u_j)同理。因为MMD的数学性质取决于RKHS核函数的选取，而RKHS通常为高维或无限维空间，所选核大多为Gauss核，从而将MMD的计算表达式进一步转化为

$ \begin{gathered} \operatorname{MMD}^2[\mathcal{H}, p, q]=\frac{1}{M^2} \sum\limits_{i=1}^M \sum\limits_{j=1}^M k\left(x_i, x_j\right)+ \\ \frac{1}{N^2} \sum\limits_{i=1}^N \sum\limits_{j=1}^N k\left(u_i, u_j\right)-\frac{2}{M N} \sum\limits_{i=1}^M \sum\limits_{j=1}^N k\left(x_i, u_j\right) . \end{gathered} $

(6)

其中：$ k\left(x_i, u_j\right)=\exp \left[-\frac{\left\|x_i-u_j\right\|^2}{2 \sigma^2}\right]$; σ为核函数带宽，用以控制Gauss核函数的局部作用范围。

3 针对大规模数据的分布一致缺失值插补算法

MMD是对2个分布相似性的度量，本文以MMD的计算公式为基础，推导用于确定最优插补值的优化规则，提出针对大规模数据插补问题的DC-MVI算法。首先，在分布式环境下对大规模数据进行随机样本划分，获得多个相同规模的数据块；其次，用所提出的DC-MVI算法对各个数据块的缺失值进行并行随机初始化插补，构建一个网络，利用优化规则对插补值进行更新迭代，获得一组与原始完整数据块分布一致程度最大的插补值，完成插补；最后，将各个数据块进行整合，获得一个完整数据集。

3.1 目标函数

给定一个具有D个条件属性A₁，A₂，…，A_D的数据集G，其对应的原始完整数据输入矩阵X和包含缺失数据矩阵E分别为：

$ \begin{gathered} \boldsymbol{X}=\left[\begin{array}{cccc} x_{11} & x_{12} & \cdots & x_{1 D} \\ x_{21} & x_{22} & \cdots & x_{2 D} \\ \vdots & \vdots & & \vdots \\ x_{M 1} & x_{M 2} & \cdots & x_{M D} \end{array}\right], \\ \boldsymbol{E}=\left[\begin{array}{ccccc} u_{11} & \cdots & \text { null } & \cdots & u_{1 D} \\ u_{21} & \cdots & \text { null } & \cdots & u_{2 D} \\ \vdots & & \vdots & & \vdots \\ u_{N 1} & \cdots & \text { null } & \cdots & u_{N D} \end{array}\right] . \end{gathered} $

其中：M和N为X和E的行数，null为缺失值；x_id为X第i个样本第d个属性值，i=1，2，…，M，d=1，2，…，D；u_jd为Y第j个样本第d个属性插补值，j=1，2，…，N。假设由于人为错误或设备故障导致E中属性A_d的值缺失，d∈{1，2，…，D}，则通过DC-MVI算法生成一系列与E中缺失值一一对应的插补值u_1d，u_2d，…，u_Nd，得到插补后，输出数据矩阵Y，

$ \boldsymbol{Y}=\left[\begin{array}{ccccc} u_{11} & \cdots & u_{1 d} & \cdots & u_{1 D} \\ u_{21} & \cdots & u_{2 d} & \cdots & u_{2 D} \\ \vdots & & \vdots & & \vdots \\ u_{N 1} & \cdots & u_{N d} & \cdots & u_{N D} \end{array}\right]. $

考虑到数据缺失的随机性，DC-MVI算法对E中的缺失值进行随机初始化，以随机值u′_1d，u′_2d，…，u′_Nd替代E中丢失的值。为迭代更新插补值，设计如下目标函数，

$ L=L_1+\lambda L_2 \text {. } $

(7)

其中：L₁为插补数据集Y和原始完整数据集X的分布一致性度量，使最优Y获得与X近似一致的概率分布；L₂为对插补数据集Y和原始完整数据集X的方差度量，使算法获取方差最为接近X的Y；λ为正则化系数。

式(7)中的L₁是对Y的一个全局性统计。本文使用MMD来评估X和Y的分布一致性，由式(6)可知，MMD是对2个概率密度差异的度量。在实际应用中，通常无法获得X和Y的概率，相反能够获得分别来自分布p和q的独立样本数据X={x₁，x₂，…，x_M }和Y={u₁，u₂，…，u_N }。Gretton等^[51]证明利用X和Y可获得1个MMD的无偏估计，且MMD越小，分布越相似。为方便后续推导，将L₁分为L₁₁、L₁₂和L₁₃ 3部分，则有：

$ \begin{gathered} L_1=\operatorname{MMD}^2[\mathcal{F}, \boldsymbol{X}, \boldsymbol{Y}]=L_{11}+L_{12}-L_{13}, \\ L_{11}=\frac{1}{M^2} \sum\limits_{i=1}^M \sum\limits_{j=1}^M k\left(x_i, x_j\right), \\ L_{12}=\frac{1}{N^2} \sum\limits_{i=1}^N \sum\limits_{j=1}^N k\left(u_i, u_j\right), \\ L_{13}=\frac{2}{M N} \sum\limits_{i=1}^M \sum\limits_{j=1}^N k\left(x_i, u_j\right) . \end{gathered} $

(8)

式(7)中的L₂是对Y的局部统计，通过计算S_xd²和S_ud²的偏离，有：

$ \begin{gathered} L_2=\left(S_{x d}^2-S_{u d}^2\right)^2, \\ S_{x d}^2=\frac{1}{M-1} \sum\limits_{i=1}^M\left(x_{i d}-\bar{x}_d\right)^2, \\ S_{u d}^2=\frac{1}{N-1} \sum\limits_{j=1}^N\left(u_{j d}-\bar{u}_d\right)^2 . \end{gathered} $

(9)

其中：S_xd²为X完整值x_1d，x_2d，…，x_Md与属性A_d均值x_d的离散程度，即X的A_d属性值方差；S_ud²为Y的每一个插补值u_1d，u_2d，…，u_Nd与属性A_d均值u_d的离散程度，即Y的插补值方差。

3.2 优化规则推导

通过调整插补值u_1d，u_2d，…，u_Nd从而最小化目标函数L，取得与S_xd²最为相近、分布最为一致的插补数据集Y。通过求解$ \frac{\partial L}{\partial u_{j d}}=0$，难以得出u_jd的最优解，但根据梯度下降法，可推导一种u_jd的迭代更新规则：

$ u_{j d}^{v+1} \leftarrow u_{j d}^v-\alpha \Delta u_{j d}^v . $

(10)

其中：α>0，表示学习率；u_jd^v为第v次迭代的插补值，v=0，1，2，…, iteration，iteration为最大更新迭代次数；u_jd^v+1为第v+1次迭代的插补值；Δu_jd^v为第v次更新迭代时目标函数L^v对u_jd^v的梯度：

$ \Delta u_{j d}^v=\frac{\partial L^v}{\partial u_{j d}^v} . $

(11)

为计算梯度Δu_jd^v，式(7)中的目标函数L可简化为

$ L\left(u_{1 d}, u_{2 d}, \cdots, u_{N d}\right)=L_{12}-L_{13}+\lambda L_2 \text {. } $

(12)

其中，L(u_1d，u_2d，…，u_Nd)仅由L中包含插补值u_1d，u_2d，…，u_Nd的部分组成。进一步将式(7)和(9)代入式(12)，用链式法则求解Δu_jd^v：

$ \Delta u_{j d}^v=\frac{\partial L_{12}^v}{\partial u_{j d}^v}-\frac{\partial L_{13}^v}{\partial u_{j d}^v}+\lambda \frac{\partial L_2^v}{\partial u_{j d}^v}, $

(13)

$ \begin{gathered} \frac{\partial L_{12}^v}{\partial u_{j d}^v}=\frac{1}{N^2} \sum_{i=1}^N \exp \left[-\frac{\sum\limits_{d=1}^D\left(u_{i d}-u_{j d}^v\right)^2}{2 \sigma^2}\right] \cdot \\ {\left[-\frac{1}{\sigma^2}\left(u_{j d}^v-u_{i d}\right)\right],} \\ \frac{\partial L_{13}^v}{\partial u_{j d}^v}=\frac{2}{M N} \sum_{i=1}^M \exp \left[-\frac{\sum\limits_{d=1}^D\left(x_{i d}-u_{j d}^v\right)^2}{2 \sigma^2}\right] \cdot \\ {\left[-\frac{1}{\sigma^2}\left(u_{j d}^v-x_{i d}\right)\right],} \\ \frac{\partial L_2^v}{\partial u_{j d}^v}=\frac{4}{N(N-1)} \cdot\left(S_{x d}^2-S_{u d}^2\right) \cdot\left(u_{j d}^v-\bar{u}_d\right) . \end{gathered} $

利用梯度下降算法对u_jd进行更新迭代，当Δu_jd^v趋于收敛，即目标函数值稳定时，更新迭代停止。具体算法流程如图 1所示，在此算法中，通过设定迭代次数，使算法在达到最大迭代次数iteration之后停止运行。下述实验将验证算法的收敛性。

3.3 算法流程

为满足大规模数据应用场景的插补需要，本文将DC-MVI算法拓展到分布式框架中，提出针对大规模数据的DC-MVI算法，实现大规模数据的并行插补。由于大规模数据的复杂性，Hadoop分布式文件系统易对数据本身分布造成影响，区别于其他大规模数据划分框架，RSP模型框架不仅考虑到大规模数据的统计属性，且耗时少、可拓展性强。重要的是，RSP框架将一个大规模数据集分成多组不相交的RSP数据块，每个数据块都跟整个数据集有相同的分布，通过挖掘数据块分布和原始数据之间原有的潜在联系，使数据插补还原缺失的数据分布。算法的具体流程框架如图 2所示。

在针对大规模数据的DC-MVI算法中，给定一个大规模数据集B，有K个样本。首先，使其基于RSP框架生成S个较大的数据块(B₁，B₂，…，B_S)，$ \sum\limits_{w=1}^S \boldsymbol{B}_S=K$，且B_S含有[K/S]个样本；然后，再将各个数据块分别随机切分打乱成T个更小的数据块(B_w1，B_w2，…，B_wT)，w=1，2，…，S，生成S个RSP集合；接着将每个RSP集合中对应顺序的RSP块(B_1t，B_2t，…，B_St)，t=1，2，…，T，合并生成T个全新的RSP数据块；之后，分别在各个RSP数据块上分离原始完整数据矩阵X和缺失数据矩阵E，运用DC-MVI算法并行插补E得到Y，组合X和Y得到插补后的RSP块得到B′_t；最后，将各个RSP块整合，完成插补。具体算法流程如图 3所示。

4 实验评估

本节基于7个基准数据集，对针对大规模数据的DC-MVI算法进行实验评估及分析。首先，对实验设置和数据集进行介绍；然后，通过验证DC-MVI算法目标函数值的收敛性和插补值的分布一致性证明DC-MVI算法的可行性；最后，利用直接评估、间接评估和运行平均时间对DC-MVI、EM、KNN、随机森林(random forest，RF)^[52]、mean、MICE、SOFT、生成式对抗插补网络(generative adversarial imputation nets，GAIN)^[17]、MIDA等插补算法进行对比，验证DC-MVI算法的有效性。其中，KNN、MICE、EM、GAIN和MIDA是使用Python的ycimpute^[53]库实现的；SOFT是使用Python的fancyimpute^[54]库实现的。

4.1 实验设置

本文实验选取7个真实数据集作为实验对象，这些数据集主要来自加州大学欧文分校(University of California，Irvine)UCI数据库^[55]和KEEL(knowledge extraction based on evolutionary learning)数据库^[56]，详细信息如表 1所示。数据集缺失属性的选择主要使用卡方验证方法，即选择类别属性卡方值最大的条件属性作为缺失值属性。选择这种条件属性的主要考虑因素是：条件属性越重要，对插补值质量的要求越高，从而使DC-MVI算法的性能更有说服力。值得注意的是，本文在实验前需要采用最小-最大值标准化(min-max normalization)方法对数据集条件属性进行归一化处理，即将数据映射到0~1。为便于有针对性地验证分布一致对MVI的影响，数据集飞行着陆器和扑克只选取3个样本数较多的类别数据进行实验。

本文主要选择3个指标对DC-MVI算法进行有效性评估。当前评估MVI技术主要分为直接评估插补结果和间接评估插补结果^[19]。直接评估策略主要是将插补后的数据与真实数据进行对比，本文选取原始完整数据和插补数据的分类一致性进行直接评估，包括MMD和JS散度(Jensen-Shannon divergence，JSD)。不同于直接评估策略，间接评估策略主要以分类精度评估插补质量，先将数据集划分为训练集和测试集，仅训练集包含缺失值，之后使用插补完成后的训练集训练一个特定分类器，最后用测试集对其分类性能进行测试。由于对相同的不完整数据集使用不同的MVI可能会产生不同的插补结果，因此其训练和数据集的插补质量越高，则分类精度越好。考虑到大规模数据插补的时间代价，还需将MVI运行时间作为指标进行对比评测。

在可行性、分布一致有效性、运行时间验证实验中，每个数据集的缺失率设为50%，即随机划分成50%的原始完整数据集和50%的缺失数据集。而在分类有效性实验中，每个数据集被随机分成了70%的训练集和30%的测试集，其中训练集被进一步划分成原始完整数据集和缺失数据集，缺失率依旧为50%，原始完整数据集和缺失数据集用以训练DC-MVI算法，测试集用以测试原始完整数据集和插补数据集组合训练的分类器的泛化能力。

实验在配置了6个节点的集群上运行，该集群包括一个Master节点和5个Worker节点，其中每个节点拥有2 TB的硬盘、128 GB的内存和12核的CPU(Intel(R)Xeon(R)CPU E5-2630 v2 @2.60 GHz)。本实验涉及的程序均运行于Python 3.7的环境，其他MVI算法从开源库中导入或根据参考文献给出的算法自行实现。

4.2 可行性验证

可行性实验验证了目标函数值的收敛性以及DC-MVI算法还原数据分布的能力。DC-MVI算法对插补值的优化规则如式(10)所示，如果该规则能实现目标函数的收敛，则证明是有效的。DC-MVI算法的参数包括式(7)中的正则化系数、式(6)中的核函数的带宽和迭代次数，其中正则化系数和核函数带宽的设定对DC-MVI算法性能影响不大，在本实验中将其固定为0.05和1。在数据集甲状腺疾病上，DC-MVI算法使用10个不同的原始完整数据块和缺失数据块独立训练10次，目标函数值的收敛图如图 4所示。由图 4可知，随着迭代次数增加，曲线均呈现先下降后稳定的趋势，即式(7)描述的目标函数L及其分布一致性度量和方差度量均逐步趋于收敛。该实验结果表明：DC-MVI算法的目标函数具有有效性；式(10)推导出的优化规则具有可行性，可使目标函数逐渐收敛，以及使插补值在优化调整过程中更加稳定。

对于DC-MVI算法还原数据分布的验证，本实验基于戒指和二范式数据集，验证了原始完整数据和插补数据的分布一致性，所选数据集由随机样本划分为10个RSP数据块，缺失率为50%，利用核密度估计器估计原始完整数据集和插补数据集的缺失属性值对应的概率密度函数。图 5和6分别为这2个数据集随机抽取3个RSP块的概率密度函数曲线。由图 5和6可知，原始完整数据集和插补数据集的缺失属性值的概率密度函数曲线几乎重合，这表明利用DC-MVI算法确定的插补值能够保持与原始完整值近似一致的概率分布，证实了该算法的可行性。

4.3 有效性验证

有效性实验通过分布一致性、分类精度和运行平均时间3个指标来评估DC-MVI算法的插补结果，并对比EM^[45]、KNN^[35]、mean、RF、MICE^[57]、SOFT^[48]、GAIN^[17]以及MIDA^[38]等MVI算法来验证DC-MVI算法的有效性。

由于DC-MVI算法是通过MMD对插补值进行迭代调整的，为保证对比方法的公平，除MMD外还添加了JSD指标。JSD是用来衡量2个概率分布p和q之间相似性的对称性度量，取值范围为0~1，表示为

$ \begin{gathered} \mathrm{JSD}(p \| q)=\frac{1}{2} \int_{x \in \bf{R}}\left[p(x) \log _2 \frac{p(x)}{\frac{p(x)+q(x)}{2}}\right] \mathrm{d} x+ \\ \frac{1}{2} \int_{x \in \bf{R}}\left[q(x) \log _2 \frac{q(x)}{\frac{p(x)+q(x)}{2}}\right] \mathrm{d} x . \end{gathered} $

当p和q分布完全相同时，即当变量取值为x时，概率分布为p(x)=q(x)，JSD(p‖q)=0；当p和q分布无重叠时，即$\forall x \in \bf{R} $，p(x)+q(x)=0，此时JSD(p‖q)=1。对于插补值和原始完整值，很难通过计算真正获得其概率分布p(x)和q(x)，因此需要使用必要的近似计算策略衡量p和q之间的JSD。本文使用Python的第三方库Scipy库来实现JSD的计算。因为该数据库能很好地衡量2个分布之间的关系，从而评估插补值和原始完整值之间的分布一致性，JSD越小，分布越一致，所以本文将其作为衡量分布一致性的度量。

表 2和表 3分别为DC-MVI算法与其他8种算法插补值和原始完整值的JSD和MMD对比结果。其中，KNN和MICE 2种算法由于运行内存不足无法处理飞行着陆器、加速度计和扑克3个数据集。实验表明DC-MVI算法在全部数据集上都取得了最小的JSD和MMD指标，这表明DC-MVI算法实现的插补值与原始完整值的分布最为一致，直接验证了DC-MVI算法对MVI以及分布还原的有效性。

表 4为DC-MVI算法与其他8种算法的运行平均时间对比结果，分别进行10次独立运行。由表 4可知，DC-MVI算法的训练时间总体上低于KNN、MICE、RF、MIDA等复杂插补算法的训练时间，表明DC-MVI算法具备处理大规模数据插补问题的能力。

此外，本文还利用scikit-learn库中的MLP分类器来评估不同插补算法的插补性能。该分类器基于原始完整数据集经各个插补算法的插补数据集进行训练，然后用于预测测试数据集的类别。实验结果是经过10次独立训练测试后的平均值和标准差，如表 5所示。可知，利用DC-MVI算法插补的训练集训练的分类器精度比其他插补算法的更高，这表明DC-MVI能够生成高质量的插补值，从而有利于后续数据挖掘分析。基于此，本文对DC-MVI算法之所以能获得较好JSD、MMD和分类精度的原因进行了简要分析。DC-MVI算法基于“有缺失值数据与无缺失值数据之间概率分布一致”的假设对缺失值进行插补，同时令插补值方差与原始完整值方差之间的差异最小，既保证了插补值的可靠性(分布一致)，又增强了插补值的稳定性(方差近似)，从而降低了由插补值导致的数据不确定性，进而使基于插补数据集训练的分类器获得较好的泛化表现。

5 结论

本文提出一种针对大规模数据的分布一致缺失值插补算法，将随机样本划分的思想引入插补算法的设计中，并以还原数据分布为目标，推导了插补值的优化规则，实现对大规模数据的有效插补。通过一系列实验评估验证了DC-MVI算法的目标函数和优化规则的可行性，能够很好地还原原始完整数据的分布。除此之外，将DC-MVI算法与其他8种插补算法进行对比，实验结果及分析表明，DC-MVI算法在分布一致性和插补质量上具有明显优势，从而证明DC-MVI算法是解决大规模数据插补问题的一种可行手段。下一步，本研究团队将对DC-MVI算法的稳定性和健壮性进行进一步提升，并将运用该算法解决实际应用中的大规模数据插补问题。