【人工智能基础】构造性覆盖下不完整数据修正填充方法

第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201906015 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190902.1033.002.html 构造性覆盖下不完整数据修正填充方法 严远亭，吴亚亚，赵姝，张燕平 (安徽大学计算机科学与技术学院，安徽合肥230601) 摘要：不完整数据处理是数据挖掘、机器学习等领域中的重要问题，缺失值填充是处理不完整数据的主流方 法。当前已有的缺失值填充方法大多运用统计学和机器学习领域的相关技术来分析原始数据中的剩余信息， 从而得到较为合理的值来替代缺失部分。缺失值填充大致可以分为单一填充和多重填充，这些填充方法在不 同的场景下有着各自的优势。但是，很少有方法能进一步考虑样本空间分布中的邻域信息，并以此对缺失值的 填充结果进行修正。鉴于此，本文提出了一种可广泛应用于诸多现有填充方法的框架用以提升现有方法的填 充效果，该框架由预填充、空间邻域信息挖掘和修正填充三部分构成。本文对7种填充方法在8个UCI数据集 上进行了实验，实验结果验证了本文所提框架的有效性和鲁棒性。 关键词：不完整数据；缺失值填充：邻域信息：数据挖掘；机器学习；填充方法；单一填充；多重填充 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)06-1225-08 中文引用格式：严远亭，吴亚亚，赵蛛，等.构造性覆盖下不完整数据修正填充方法[J.智能系统学报，2019,14(6)： 1225-1232. 英文引用格式：YAN Yuanting,WU Yaya,ZHAO Shu,et al.Improving missing data recovery with a constructive covering al- gorithmJ].CAAI transactions on intelligent systems,2019,14(6):1225-1232. Improving missing data recovery with a constructive covering algorithm YAN Yuanting,WU Yaya,ZHAO Shu,ZHANG Yanping (School of Computer Science and Technology,Anhui University,Hefei 230601,China) Abstract:Incomplete data processing is one of the most active avenues in the fields of data mining,machine learning, etc.Missing value imputation is the mainstream method used to deal with incomplete data.At present,most existing missing value imputation methods utilize relevant techniques in the field of statistics and machine learning to analyze surplus information from original data to replace the missing attributes with plausible values.Missing value imputation can be roughly divided into single imputation and multiple imputation,which have their own advantages in different scenarios.However,there are few methods that can further consider neighborhood information in the spatial distribu- tion of samples and modify the filling results of missing values.In view of this,this paper proposes a new framework that can be widely used in many existing imputation methods to enhance the imputation effect of existing methods.It is composed of three modules,called pre-filling,spatial neighborhood information mining,and modification of the results of pre-filling separately.In this paper,seven existing imputation methods were evaluated on eight UCI datasets.Experi- mental results verified the validity and robustness of the framework proposed in this paper. Keywords:incomplete data;missing value imputation;neighborhood information;data-mining;machine learning;im- putation method;single imputation;multiple imputation 收稿日期：2019-06-06.网络出版日期：2019-09-02 机器学习、数据挖掘等技术在诸如生物特征 基金项目：国家自然科学基金项目(61806002,61872002 61673020,61876001.61602003):安徽省自然科学基 识别、文本分类和医学诊断等领域得到了广泛应 金项目(1708085QF143,1808085MF197):安徽大学博 用。近年来，随着传感器技术、信息技术等科 士科研启动基金项目(J01003253). 通信作者：张燕平.E-mail:zhangyp.2@gmail.com 学技术的迅猛发展，数据获取的途径日益丰富

DOI: 10.11992/tis.201906015 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190902.1033.002.html 构造性覆盖下不完整数据修正填充方法 严远亭，吴亚亚，赵姝，张燕平 （安徽大学 计算机科学与技术学院，安徽 合肥 230601） 摘 要：不完整数据处理是数据挖掘、机器学习等领域中的重要问题，缺失值填充是处理不完整数据的主流方 法。当前已有的缺失值填充方法大多运用统计学和机器学习领域的相关技术来分析原始数据中的剩余信息， 从而得到较为合理的值来替代缺失部分。缺失值填充大致可以分为单一填充和多重填充，这些填充方法在不 同的场景下有着各自的优势。但是，很少有方法能进一步考虑样本空间分布中的邻域信息，并以此对缺失值的 填充结果进行修正。鉴于此，本文提出了一种可广泛应用于诸多现有填充方法的框架用以提升现有方法的填 充效果，该框架由预填充、空间邻域信息挖掘和修正填充三部分构成。本文对 7 种填充方法在 8 个 UCI 数据集 上进行了实验，实验结果验证了本文所提框架的有效性和鲁棒性。 关键词：不完整数据；缺失值填充；邻域信息；数据挖掘；机器学习；填充方法；单一填充；多重填充 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)06−1225−08 中文引用格式：严远亭, 吴亚亚, 赵姝, 等. 构造性覆盖下不完整数据修正填充方法 [J]. 智能系统学报, 2019, 14(6): 1225–1232. 英文引用格式：YAN Yuanting, WU Yaya, ZHAO Shu, et al. Improving missing data recovery with a constructive covering al￾gorithm[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1225–1232. Improving missing data recovery with a constructive covering algorithm YAN Yuanting，WU Yaya，ZHAO Shu，ZHANG Yanping (School of Computer Science and Technology, Anhui University, Hefei 230601, China) Abstract: Incomplete data processing is one of the most active avenues in the fields of data mining, machine learning, etc. Missing value imputation is the mainstream method used to deal with incomplete data. At present, most existing missing value imputation methods utilize relevant techniques in the field of statistics and machine learning to analyze surplus information from original data to replace the missing attributes with plausible values. Missing value imputation can be roughly divided into single imputation and multiple imputation, which have their own advantages in different scenarios. However, there are few methods that can further consider neighborhood information in the spatial distribu￾tion of samples and modify the filling results of missing values. In view of this, this paper proposes a new framework that can be widely used in many existing imputation methods to enhance the imputation effect of existing methods. It is composed of three modules, called pre-filling, spatial neighborhood information mining, and modification of the results of pre-filling separately. In this paper, seven existing imputation methods were evaluated on eight UCI datasets. Experi￾mental results verified the validity and robustness of the framework proposed in this paper. Keywords: incomplete data; missing value imputation; neighborhood information; data-mining; machine learning; im￾putation method; single imputation; multiple imputation 机器学习、数据挖掘等技术在诸如生物特征 识别、文本分类和医学诊断等领域得到了广泛应 用 [1-6]。近年来，随着传感器技术、信息技术等科 学技术的迅猛发展，数据获取的途径日益丰富， 收稿日期：2019−06−06. 网络出版日期：2019−09−02. 基金项目：国家自然科学基金项 目 (61806002， 61872002， 61673020，61876001，61602003)；安徽省自然科学基 金项目 (1708085QF143，1808085MF197)；安徽大学博 士科研启动基金项目 (J01003253). 通信作者：张燕平. E-mail：zhangyp2@gmail.com. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019

·1226· 智能系统学报 第14卷 这给机器学习等技术带来了极大的发展机遇。然 时不需要建立明确的模型（如决策树模型或诸多 而在实践中，通常会因为存储设备损坏、数据采 其他繁琐的填充规则)，无论使用何种方法对数据 集设备能力有限等多种因素导致数据出现缺失的 进行分析，总能找到距缺失样本最近的若干个样 情况，我们称其为不完整数据问题。此类问题普 本用于填充。因此，基于该方法的很多改进方法 遍存在于众多领域中，如：微阵列数据、移动电 也被相继提出，如WKNN等，它们通常使用某 话数据、可视化数据o、工业数据、软件项目 种度量指标（如皮尔逊相关系数、距离函数等）来 数据1等。然而，传统机器学习的方法往往都是 衡量样本间的相似度大小或采用特征提取等手段 针对完整数据而设计的，因此缺失数据给这些方 来对重要属性进行加权后再进行填充，取得了较 法带来了极大挑战。 好的填充效果；聚类填充方法如：CKNNI根据 目前已有不少学者针对不完整数据提出了一 样本间的相似度大小将所有样本聚类得到若干个 些解决策略，大致可以分为三类，其一为替代法， 簇，簇内样本间的相似度较高，再针对缺失样本， 即用同一数据集内其他样本的完整部分替代缺失 利用其所在簇内的其他样本对缺失部分进行填 值，有时甚至会将众多缺失属性补以统一的固定 充。虽然这类方法也在一定程度上考虑了样本在 值。这种策略虽然简单，但众多研究表明，绝大 空间分布中的信息，但由于聚类是无监督的，因 多数原始数据集的样本属性间都不是相互独立 此无法知悉经过聚类操作后会得到怎样的聚类结 的，因此单一的替换策略直接忽略了属性间的关 果，同时聚类算法初始中心个数也很难确定。此 系，并不可取；其二为删除法，例如在许多统计软 外，还有一些其他的机器学习算法被应用于缺失 件如：SPSS、SAS中，默认采用Listwise deletion(LD) 值填充领域，如结合期望最大化方法(EM)用于 策略处理缺失值，直接删除带有缺失项的样本。 最大似然估计的方法、基于支持向量机的填充方 然而，这种策略是以减少原始数据为代价换取数 法等，但是这些方法在时间复杂度方面都非常庞 据完整，在信息获取代价较大时会造成严重的资 大，收敛速度极慢，对于某些数据集甚至达到了 源浪费和重要信息的损失。因此，解决不完整数 指数级别。 据问题的第3种策略，即在多数现有的机器学习 上述所提方法大多为单一填充法（如均值填 算法被应用到实际问题之前，将缺失数据填充完 充、KNN填充等)，往往会降低估计量的方差。针 整的策略更为主流一些。 对这一缺陷，Rubin在1987年提出了多重填充的 当前的缺失值填充方法大多运用统计学和机 思想。单一填充往往针对每个缺失值产生一个可 器学习领域的相关技术，对不完整数据的剩余部 能的值用以填充，而多重填充（如MICE1、M- 分进行建模和分析，从而产生较为合适的值用以 LC8奶是指在对填充值的预测分布中，通过一 填充。最常用的统计学填充法是均值填充)，它 组(m>l)合理的值来替代所有缺失值的过程s20。 简单快速，但是无法较好地拟合原始数据，因此 数据经过多重填充处理后，会得到m个完整的数 通常适用于快速填充或者只有极少数属性缺失的 据集，每一个数据集都可以运用分析完整数据的 情况；同样基于统计学的回归填充通常基于数据 方法对其分析，然后再融合这些不同数据集的分 的完整部分来建立回归模型，对于包含缺失值的 析结果，给出综合估计，显著缩小了由单一填充 样本，将已知属性值代入方程来估计未知属性 所导致的偏差，可获得更好的填充效果。 值。除此以外，在过去的十年里，许多机器学习 尽管现有的这些填充方法都具有各自的优 填充方法也被相继提出，在机器学习填充法中， 势，某些方法能较好地实现对缺失数据的恢复。 缺失的属性通常被视为一个训练模型的目标输 但是研究表明，目前还没有哪一种填充方法可以 出，剩余其他完整属性是用于训练和测试的输入 在任意给定的数据集和所有场景下都取得最佳的 特性，算法通常根据数据集的完备部分使用一些 填充效果2四。此外，现有的绝大多数方法仍缺乏 诸如KNN、决策树(DT)、多层感知器(MLP)、自 对样本空间分布信息的考虑，忽略了空间邻域信 组织映射(SOM①等机器学习方法来训练相关模 息对数据恢复的影响。因此，本文提出了一种新 型，在模型中对不完整属性进行估计。 的框架，可用于诸多现有的填充方法以进一步提 当前最常用的机器学习填充方法有K最近邻 升填充效果。框架由3部分组成，分别为预填 填充(KNNI、聚类填充(CKNN等。其中， 充、空间邻域信息挖掘和修正填充。首先利用传 K最近邻填充的一个最大的特点在于KNN是一 统的填充方法对数据集进行预填充，得到完整数 种懒惰式的学习方法，在应用到缺失值填充问题 据；然后构造性的对预填充后的数据集构造覆

这给机器学习等技术带来了极大的发展机遇。然 而在实践中，通常会因为存储设备损坏、数据采 集设备能力有限等多种因素导致数据出现缺失的 情况，我们称其为不完整数据问题。此类问题普 遍存在于众多领域中，如：微阵列数据[7-8] 、移动电 话数据[9] 、可视化数据[10] 、工业数据[11] 、软件项目 数据[12] 等。然而，传统机器学习的方法往往都是 针对完整数据而设计的，因此缺失数据给这些方 法带来了极大挑战。 目前已有不少学者针对不完整数据提出了一 些解决策略，大致可以分为三类，其一为替代法， 即用同一数据集内其他样本的完整部分替代缺失 值，有时甚至会将众多缺失属性补以统一的固定 值。这种策略虽然简单，但众多研究表明，绝大 多数原始数据集的样本属性间都不是相互独立 的，因此单一的替换策略直接忽略了属性间的关 系，并不可取；其二为删除法，例如在许多统计软 件如：SPSS、SAS 中，默认采用 Listwise deletion(LD) 策略处理缺失值，直接删除带有缺失项的样本。 然而，这种策略是以减少原始数据为代价换取数 据完整，在信息获取代价较大时会造成严重的资 源浪费和重要信息的损失。因此，解决不完整数 据问题的第 3 种策略，即在多数现有的机器学习 算法被应用到实际问题之前，将缺失数据填充完 整的策略更为主流一些。 当前的缺失值填充方法大多运用统计学和机 器学习领域的相关技术，对不完整数据的剩余部 分进行建模和分析，从而产生较为合适的值用以 填充。最常用的统计学填充法是均值填充[13] ，它 简单快速，但是无法较好地拟合原始数据，因此 通常适用于快速填充或者只有极少数属性缺失的 情况；同样基于统计学的回归填充通常基于数据 的完整部分来建立回归模型，对于包含缺失值的 样本，将已知属性值代入方程来估计未知属性 值。除此以外，在过去的十年里，许多机器学习 填充方法也被相继提出，在机器学习填充法中， 缺失的属性通常被视为一个训练模型的目标输 出，剩余其他完整属性是用于训练和测试的输入 特性，算法通常根据数据集的完备部分使用一些 诸如 KNN、决策树 (DT)、多层感知器 (MLP)、自 组织映射 (SOM) 等机器学习方法来训练相关模 型，在模型中对不完整属性进行估计。 当前最常用的机器学习填充方法有 K 最近邻 填充 (KNNI)[14] 、聚类填充 (CKNNI[15] ) 等。其中， K 最近邻填充的一个最大的特点在于 KNN 是一 种懒惰式的学习方法，在应用到缺失值填充问题 时不需要建立明确的模型 (如决策树模型或诸多 其他繁琐的填充规则)，无论使用何种方法对数据 进行分析，总能找到距缺失样本最近的若干个样 本用于填充。因此，基于该方法的很多改进方法 也被相继提出，如 WKNNI[16] 等，它们通常使用某 种度量指标 (如皮尔逊相关系数、距离函数等) 来 衡量样本间的相似度大小或采用特征提取等手段 来对重要属性进行加权后再进行填充，取得了较 好的填充效果；聚类填充方法如：CKNNI[15] 根据 样本间的相似度大小将所有样本聚类得到若干个 簇，簇内样本间的相似度较高，再针对缺失样本， 利用其所在簇内的其他样本对缺失部分进行填 充。虽然这类方法也在一定程度上考虑了样本在 空间分布中的信息，但由于聚类是无监督的，因 此无法知悉经过聚类操作后会得到怎样的聚类结 果，同时聚类算法初始中心个数也很难确定。此 外，还有一些其他的机器学习算法被应用于缺失 值填充领域，如结合期望最大化方法 (EM) 用于 最大似然估计的方法、基于支持向量机的填充方 法等，但是这些方法在时间复杂度方面都非常庞 大，收敛速度极慢，对于某些数据集甚至达到了 指数级别。 上述所提方法大多为单一填充法 (如均值填 充、KNN 填充等)，往往会降低估计量的方差。针 对这一缺陷，Rubin 在 1987 年提出了多重填充的 思想。单一填充往往针对每个缺失值产生一个可 能的值用以填充，而多重填充 (如 MICE[17] 、MI￾LC[18-19] ) 是指在对填充值的预测分布中，通过一 组 (m>1) 合理的值来替代所有缺失值的过程[5, 20]。 数据经过多重填充处理后，会得到 m 个完整的数 据集，每一个数据集都可以运用分析完整数据的 方法对其分析，然后再融合这些不同数据集的分 析结果，给出综合估计，显著缩小了由单一填充 所导致的偏差，可获得更好的填充效果。 尽管现有的这些填充方法都具有各自的优 势，某些方法能较好地实现对缺失数据的恢复。 但是研究表明，目前还没有哪一种填充方法可以 在任意给定的数据集和所有场景下都取得最佳的 填充效果[21]。此外，现有的绝大多数方法仍缺乏 对样本空间分布信息的考虑，忽略了空间邻域信 息对数据恢复的影响。因此，本文提出了一种新 的框架，可用于诸多现有的填充方法以进一步提 升填充效果。框架由 3 部分组成，分别为预填 充、空间邻域信息挖掘和修正填充。首先利用传 统的填充方法对数据集进行预填充，得到完整数 据；然后构造性的对预填充后的数据集构造覆 ·1226· 智 能 系 统 学 报 第 14 卷

第6期 严远亭，等：构造性覆盖下不完整数据修正填充方法 ·1227· 盖，挖掘样本的空间邻域信息；最后利用邻域内 学习样本的特征用超平面切割球面形成“球形领 样本的有效信息对预填充的结果进行修正，从而 域”作为神经元来构造神经网络，基于超球面上的 得到最终的完整数据集。 样本来构造每个类别的覆盖。该算法可以处理海 量样本，适用于多分类问题且分类能力强、运算 1相关工作 速度快2。 1.1缺失机制和缺失模式 2基于空间邻域信息的修正填充方法 根据Rubin的总结，共有3种类型的缺失机 制会导致一个不完整数据集的产生，分别为完全 2.1预填充 随机缺失、随机缺失和非随机缺失。 给定不完整数据集DS=(x,yi=1,2,…,m),令 完全随机缺失：样本的某一属性出现缺失的 F={F四，F2,…,F。其中，m表示的是样本个 概率和其他样本以及该属性本身的值无关。即当 数；F表示的是输入空间的特征集合； 某属性值发生缺失的可能性与其他样本无关且与 x=(xx,…x);x9表示的是第i个样本的第 该样本属性自身也无关时称作完全随机缺失。 j维属性，若第i个样本的第j维缺失，则记 随机缺失：当某样本属性缺失的可能性与模 x=NaW。定义所有缺失值的集合： 型中某些观测样本有关而与该样本自身无关时称 其为随机缺失。 IND =((i,j)x NaN) (1) 非随机缺失：当样本属性中存在缺失值的可 利用经典的填充算法对DS进行填充，在本 能性仅与其自身相关时则称为非随机缺失。 文中称为预填充。预填充后得到完整数据集 除此之外，还有两种缺失模式，分别为单调缺 DS。分别选用以下7种填充方法实现预填充： 失和非单调缺失。前者指的是针对同一个记录或 1)均值填充(ME) 者变量的缺失，后者指的是针对任何记录、任何 = 变量的缺失，本文的实验是以非单调缺失模式为 「e&p,noap (2) 前提进行的。 式中：I(comp)表示的是所有第j维属性不缺失的 1.2构造性覆盖算法 属性索引集合；而neop表示的是所有第j维属性 张铃等提出的基于覆盖的构造性机器学习 不缺失的样本总数。 方法主要是以M-P模型的几何表示为理论基础， 2)中值填充(MEDD) 针对样本自身的特点来构造神经网络。构造性覆 令2={W"k∈I(comp)小：2表示集合2中所有 盖算法可以看作一个3层网络分类器。 元素的升序存放；2=21=n;则： 输入层：共n个神经元，每个神经元对应样本 = 2+1p nmod2≠0 (2a+2a+i)/2,nmod2=0 (3) 的一维，即样本的特征属性，x=(x,x2,…,x"),该 层神经元只负责接收外部信息，自身无信息处理 3)KNNI4 能力。 (4) 隐藏层：共s个神经元。初始时，隐层神经元 d:dist() 为0个，每求得一个球形覆盖，增加一个神经元， 直到将所有的样本都被覆盖，从而求得一组覆盖： x≠NaN (5) C={Cl,C2,…,Cm,C2,C22,…C2,…,Cm,…Cm"}, 式中：表示第i个样本和第j个样本之间的欧式 其中C表示第i类样本的第j个覆盖，是隐层中 距离：N表示距离第ⅰ个样本最近的k个第j维属 的一个神经元，隐层共有s=∑”：个覆盖，第1类 性不缺失的样本集合；W=k表示的是N,集合中 有n,个覆盖，i=1,2,…m。神经元的权值是覆盖 的个数。 的中心，阈值为覆盖的半径。 4)WKNNI161 输出层：共m个神经元，第1个神经元的输入人 为同类的一组覆盖，输出为该覆盖的类别。 =∑w,w,= 1/d (6) 0,=(01=0,02=0,…,0,=1,…,0m=0)表示第1类 1/d 1 样本的输出。该层神经元向外部输出处理信息。 式中：N,表示距离第i个样本最近的k个第j维属 构造性覆盖算法属于有监督学习。 性不缺失的样本集合；ω，表示第1个样本的权值； 构造性覆盖算法针对样本自身的特点，根据 d表示第i个样本和第j个样本之间的欧式距离；

盖，挖掘样本的空间邻域信息；最后利用邻域内 样本的有效信息对预填充的结果进行修正，从而 得到最终的完整数据集。 1 相关工作 1.1 缺失机制和缺失模式 根据 Rubin 的总结，共有 3 种类型的缺失机 制会导致一个不完整数据集的产生，分别为完全 随机缺失、随机缺失和非随机缺失。 完全随机缺失：样本的某一属性出现缺失的 概率和其他样本以及该属性本身的值无关。即当 某属性值发生缺失的可能性与其他样本无关且与 该样本属性自身也无关时称作完全随机缺失。 随机缺失：当某样本属性缺失的可能性与模 型中某些观测样本有关而与该样本自身无关时称 其为随机缺失。 非随机缺失：当样本属性中存在缺失值的可 能性仅与其自身相关时则称为非随机缺失。 除此之外，还有两种缺失模式，分别为单调缺 失和非单调缺失。前者指的是针对同一个记录或 者变量的缺失，后者指的是针对任何记录、任何 变量的缺失，本文的实验是以非单调缺失模式为 前提进行的。 1.2 构造性覆盖算法 张铃等[22] 提出的基于覆盖的构造性机器学习 方法主要是以 M-P 模型的几何表示为理论基础， 针对样本自身的特点来构造神经网络。构造性覆 盖算法可以看作一个 3 层网络分类器。 xi = ( xi 1 , xi 2 ,··· , xi n ) 输入层：共 n 个神经元，每个神经元对应样本 的一维，即样本的特征属性， ，该 层神经元只负责接收外部信息，自身无信息处理 能力。 C = { C1 1 ,C1 2 ,··· ,C1 n1 ,C2 1 ,C2 2 ,···C2 n2 ,··· ,C1 m ,···Cm nm } C j i s = ∑ ni i = 1,2,···m 隐藏层：共 s 个神经元。初始时，隐层神经元 为 0 个，每求得一个球形覆盖，增加一个神经元， 直到将所有的样本都被覆盖，从而求得一组覆盖： ， 其中 表示第 i 类样本的第 j 个覆盖，是隐层中 的一个神经元，隐层共有 个覆盖，第 i 类 有 ni 个覆盖， 。神经元的权值是覆盖 的中心，阈值为覆盖的半径。 Ot = (O1 = 0,O2 = 0,··· ,Ot = 1,··· ,Om = 0) 输出层：共 m 个神经元，第 t 个神经元的输入 为同类的一组覆盖，输出为该覆盖的类别。 表示第 t 类 样本的输出。该层神经元向外部输出处理信息。 构造性覆盖算法属于有监督学习。 构造性覆盖算法针对样本自身的特点，根据 学习样本的特征用超平面切割球面形成“球形领 域”作为神经元来构造神经网络，基于超球面上的 样本来构造每个类别的覆盖。该算法可以处理海 量样本，适用于多分类问题且分类能力强、运算 速度快[23]。 2 基于空间邻域信息的修正填充方法 2.1 预填充 DS = (xi , yi |i = 1,2,··· ,m) F = { F (1) ,F (2) ,··· ,F (n) } xi= (x (1) i ,x (2) i ,···,x (n) i ) x (j) i x (j) i = NaN 给定不完整数据集 ,令 。其中， m 表示的是样本个 数 ； F 表示的是输入空间的特征集合； ； 表示的是第 i 个样本的第 j 维属性，若 第 i 个样本的 第 j 维缺失，则记 。定义所有缺失值的集合： IND = {(i, j)|x (j) i = NaN} (1) 利用经典的填充算法对 DS 进行填充，在本 文中称为预填充。预填充后得到完整数据集 DSc。分别选用以下 7 种填充方法实现预填充： 1) 均值填充 (MEI)[13] x (j) i = ∑ k∈I(comp) x (j) k n|I(comp)| (2) I(comp) nI(comp) 式中： 表示的是所有第 j 维属性不缺失的 属性索引集合；而 表示的是所有第 j 维属性 不缺失的样本总数。 2) 中值填充 (MEDI)[13] Ω = { x (j) k |k ∈ I(comp)} Ω ∗ Ω |Ω| = |Ω ∗ | = n 令 ； 表示集合 中所有 元素的升序存放； ；则： x j i = { Ω ∗ [n+1/2] , n mod 2 , 0 ( Ω ∗ [n/2] +Ω ∗ [n+1/2] ) /2, n mod 2 = 0 (3) 3) KNNI[14] d t i = dist(xi , xt) = vt∑n p=1 ( x p i − x p t )2 (4) x j i =   ∑ ∀xt∈Ni x j t   / |Ni |, x j t , NaN (5) d t i Ni |Ni | =k Ni 式中： 表示第 i 个样本和第 j 个样本之间的欧式 距离； 表示距离第 i 个样本最近的 k 个第 j 维属 性不缺失的样本集合； 表示的是 集合中 的个数。 4) WKNNI[16] x j i = ∑ ∀xt∈Ni x j tωt , ωt = 1/d t i ∑k t=1 1/d t i (6) ωt d t i 式中：Ni 表示距离第 i 个样本最近的 k 个第 j 维属 性不缺失的样本集合； 表示第 t 个样本的权值； 表示第 i 个样本和第 j 个样本之间的欧式距离； 第 6 期 严远亭，等：构造性覆盖下不完整数据修正填充方法 ·1227·

·1228· 智能系统学报 第14卷 k表示最近邻的个数。 二类样本的覆盖的个数。 5)Soft-impute(Sof2:通过对SVD分解的迭 对于x∈CA(位，)eND,使用式(13)对x 代软阈值处理来填充不完整数据。 进行修正填充。 6)Matrix-Factorization-impute(MF)2:将不完 (Σ(x)/M,≠0 整数据用矩阵形式表示并直接将其分解为低秩 (13) =0 的U和V,然后对U中的元素采用L1稀疏惩罚， 对V中的元素采用L2稀疏惩罚，通过梯度下降 =Ct-x(s.j)IND (14) 法求解。 式中：y表示在C覆盖集合内，除样本：以外的 7)MCE:利用链式方程实现多重填充。 所有第j维不缺失的属性值集合。M为满足条件 2.2挖掘空间邻域信息 (14)的所有属性的数量。 在对不完整数据进行填充的过程中，最关键 在极少数情况下会出现覆盖内除：以外，其 的问题在于如何通过对数据集中样本的剩余完整 他所有样本对应的第j维属性在预填充步骤前均 信息进行分析。在这一节中，我们利用一种有监 是缺失的，即出现式(13)中的M值为零的情况， 督的空间邻域信息挖掘方法，挖掘与缺失样本具 这表明这些属性在预填充阶段都已被填充，算法 有更高相似性的某邻域内样本的有效信息。 采用预填充的结果x替代x,其中(p,)∈ND。 1)通过式(2)变换将DS。中的样本点投射到 算法针对所有的缺失属性依次进行判断和修 S*1球面上并使得投影后的样本向量等长。 正填充，最终得到修正填充后的完整数据集 DSc。修正填充方法的流程图如图1所示，其中， T:DS。→S,T)=xVR-lf (7) MR表示缺失率。 式中R≥maxd,x∈DS} /NRMSE sum=0/ 2)随机选取一个未被标记的样本：作为覆 开始 N=0 MR=0.01 盖中心并计算覆盖半径R。 随机缺失得到 x0x+…+x*x+,ie{l,2,…,m(8) 不完整数据 d1=max{《xk,xh,ie{l,2,…,m (9) 某行（列）刀 d2=min{xk,x)Ix,x〉>d},i∈{1,2，…，m(10) 全部缺失 N R=(d+d2)/2 (11) 删除该行（列预填充 式中：表示样本与x之间的内积；d表 4=1 示异类样本间的最小距离，等价于最大内积； 预填充完整数据集 NRMSE sum+=NRMSE 表示同类样本间的最大距离，等价于最小内积； R表示覆盖半径。 构造性覆盖算法 3)构造一个以x为球形领域的中心，R为半 径的球形领域C,其中C表示第v类样本的第 覆盖1 覆盖2一覆盖n k个覆盖，并将该领域内的所有样本都标记成“已 利用缺失样本所在覆盖中的 学习”。若全部已被标记则会得到一组覆盖集合 邻域信息修正填充缺失值 C={C,C,…,C,CC经，…，C,…,C,…},否则返 MR+=0.01 计算NRMSE值 回2)。 经过1)~3)得到的覆盖集合C能够很好地刻 N≤500 画样本空间的空间邻域信息。 N 2.3利用空间邻域信息修正预填充结果 NRMSE=NRMSE sum/N 为方便起见，本文以二分类问题为例，描述如 何利用空间邻域信息进行缺失值的填充。 NRMSE 令C1和C2为经过2.2节所得到的两类样本 的覆盖集合为 MR≤0.2 结束 C1={C1,C,…,C}C2={C2,C3,…,C}(12) 图1算法流程图 式中：k表示第一类样本的覆盖的个数，k表示第 Fig.1 The flow chart of the proposed method

k 表示最近邻的个数。 5) Soft-impute(SoftI)[24] ：通过对 SVD 分解的迭 代软阈值处理来填充不完整数据。 6) Matrix-Factorization-impute(MFI)[25] ：将不完 整数据用矩阵形式表示并直接将其分解为低秩 的 U 和 V，然后对 U 中的元素采用 L1 稀疏惩罚， 对 V 中的元素采用 L2 稀疏惩罚，通过梯度下降 法求解。 7) MICE[20] ：利用链式方程实现多重填充。 2.2 挖掘空间邻域信息 在对不完整数据进行填充的过程中,最关键 的问题在于如何通过对数据集中样本的剩余完整 信息进行分析。在这一节中，我们利用一种有监 督的空间邻域信息挖掘方法，挖掘与缺失样本具 有更高相似性的某邻域内样本的有效信息。 DSc S n+1 1) 通过式 (2) 变换将 中的样本点投射到 球面上并使得投影后的样本向量等长。 T : DSc → S n+1 ,T (x) = ( x, √ R2 −|x| 2 ) (7) 式中 R ⩾ max{|x|, x ∈ DS c} 2) 随机选取一个未被标记的样本 xk 作为覆 盖中心并计算覆盖半径 R。 x (1) k x (1) i +···+ x (n+1) k x (n+1) i , i ∈ {1,2,··· ,m} (8) d1 = max yk,yi {⟨xk , xi⟩}, i ∈ {1,2,··· ,m} (9) d2 = min yk=yi {⟨xk , xi⟩|⟨xk , xi⟩ > d1}, i ∈ {1,2,··· ,m} (10) R = (d1 +d2)/2 (11) xk xi d1 d2 式中： 表示样本 与 之间的内积； 表 示异类样本间的最小距离，等价于最大内积； 表示同类样本间的最大距离，等价于最小内积； R 表示覆盖半径。 xk Cv C k v C = {C 1 1 ,C 2 1 ,··· ,C k1 1 ,C 1 2 ,C 2 2 ,··· ,C k2 2 ,··· ,C 1 i ,··· } 3) 构造一个以 为球形领域的中心，R 为半 径的球形领域 ，其中 表示第 v 类样本的第 k 个覆盖，并将该领域内的所有样本都标记成“已 学习”。若全部已被标记则会得到一组覆盖集合 ，否则返 回 2)。 经过 1)~3) 得到的覆盖集合 C 能够很好地刻 画样本空间的空间邻域信息。 2.3 利用空间邻域信息修正预填充结果 为方便起见，本文以二分类问题为例，描述如 何利用空间邻域信息进行缺失值的填充。 令 C1 和 C2 为经过 2.2 节所得到的两类样本 的覆盖集合为 C1 = { C 1 1 ,C 2 1 ,··· ,C k1 1 } ;C2 = { C 1 2 ,C 2 2 ,··· ,C k2 2 } (12) 式中：k1 表示第一类样本的覆盖的个数，k2 表示第 二类样本的覆盖的个数。 ∀xi ∈ C k v ∧(i, j) ∈ IND x (j) 对于 ，使用式 i (13) 对 进行修正填充。 x (j) i =    ( ∑ |ψ| t=1 (x (j) s )t )/ |ψ|, |ψ| , 0 x (j) p , |ψ| = 0 (13) ψ = { x (j) s |xs ∈ { C k v − xi } ∧(s, j) < IND} (14) C k v xi |ψ| 式中：ψ 表示在 覆盖集合内，除样本 以外的 所有第 j 维不缺失的属性值集合。 为满足条件 (14) 的所有属性的数量。 xi |ψ| x (j) p x (j) i (p, j) ∈ IND 在极少数情况下会出现覆盖内除 以外，其 他所有样本对应的第 j 维属性在预填充步骤前均 是缺失的，即出现式 (13) 中的 值为零的情况， 这表明这些属性在预填充阶段都已被填充，算法 采用预填充的结果 替代 ，其中 。 DSf c 算法针对所有的缺失属性依次进行判断和修 正填充，最终得到修正填充后的完整数据集 。修正填充方法的流程图如图 1 所示，其中， MR 表示缺失率。 开始 NRMSE_sum=0 N=0 MR=0.01 随机缺失得到 不完整数据 某行（列） 全部缺失 删除该行（列） 预填充 构造性覆盖算法 覆盖 1 覆盖 2 ... 覆盖 n 利用缺失样本所在覆盖中的 邻域信息修正填充缺失值 计算NRMSE值 N≤500 NRMSE=NRMSE_sum/N NRMSE MR≤0.2 MR+=0.01 N+=1 NRMSE_sum+=NRMSE Y N N Y N Y 结束 预填充完整数据集 图 1 算法流程图 Fig. 1 The flow chart of the proposed method ·1228· 智 能 系 统 学 报 第 14 卷

第6期 严远亭，等：构造性覆盖下不完整数据修正填充方法 ·1229· 3 实验与分析 表1数据集简介 Table 1 The introduction of the datasets 3.1 实验设计 数据集 样本数 属性数 类别数 本小节中，本文提出的框架分别与2.1节提 balance-s 625 4 3 出的7种当前已有的缺失值填充方法对比。由于 BCC 116 10 2 本文的方法是对已有填充方法得到的填充结果进 dba 1372 5 2 一步的修正。因此，这7种经典的方法也是本文 glass 214 10 > 预填充阶段所选取的填充方法。另外，本文使用 haberman 306 3 2 lenses 24 4 3 一种常见的度量缺失值填充效果的指标NRMSE) lym 148 18 4 来量化填充效果，进一步验证方法的有效性。 wine 178 13 实验首先在UCI上的完整数据集上，以随机 缺失的方式得到不完整数据，缺失率从小到大依 3.3 不完整数据填充性能的评价标准 次为0.01、0.02、0.03、0.04、0.05、0.10、0.15和 本文采用的评价不完整数据填充性能的指标 0.20:然后用现有的填充方法与本文提出的框架 是归一化均方根误差，定义如下： 结合后对得到的不完整数据进行处理；最后根据 mean(xguess-o)2 修正填充前的原始数据集和修正填充后得到的最 NRMSE= (15) std (xon) 终完整集得出不同缺失率下的NRMSE值及其变 式中：xues和xm分别代表填充后的属性值以及在 化趋势。为了避免因单次填充而导致的误差对实 原始数据集中被填充前的属性值；std(x)表示的 验结果的影响，实验在每种缺失率下均重复随机 是被填充前的所有属性值的标准差。NRMSE 缺失多次，最终得到的NRMSE值为多次重复缺 值越小，意味着填充后的值与填充前的值差异越 失后得到的均值。 小，即填充效果越好。 3.2实验数据集 3.4实验结果与分析 本文从UCI中选取了8个数据集进行实验的 本小节中，通过NRMSE度量指标对本文所 比较和分析，表1给出了8个数据集的基本信息， 提框架与当前已有的缺失值填充方法所产生的结 包括数据集名称、样本个数、属性个数以及类别 果进行对比和分析，研究在不同的缺失率下，框架 个数，其中balance-s、BCC、dba和lym分别是bal, 对于现有填充方法的提升效果呈现出何种趋势。 ance-scale,Breast Cancer Coimbra,data banknote 图2分别展示了7组填充方法在不同数据集上以 authentication和ymphography数据集的简写。 及不同缺失率下对应的NRMSE值的变化趋势。 0.5 0.35 0.50 04 0.30 0.45 0.25 0.40 0.3 0.20 0.35 02 0.15 0.30 0.10 0.25 0.05 0.10 0.15 0.20 0 0.05 0.10 0.15 0.20 0.05 0.10 0.15 0.20 缺失率 缺失率 缺失率 (a)haberman (b)BCC (c)balance-s 04 0.4 1.0 0.3 0.3 0.8 0.2 02 0.6 4 0.1 0.2 0.05 0.10 0.15 0.20 0.05 0.100.15 0.20 0.050.100.150.20 缺失率 缺失率 缺失率 (d)dba (e)glass (f)lenses

3 实验与分析 3.1 实验设计 本小节中，本文提出的框架分别与 2.1 节提 出的 7 种当前已有的缺失值填充方法对比。由于 本文的方法是对已有填充方法得到的填充结果进 一步的修正。因此，这 7 种经典的方法也是本文 预填充阶段所选取的填充方法。另外，本文使用 一种常见的度量缺失值填充效果的指标 (NRMSE) 来量化填充效果，进一步验证方法的有效性。 实验首先在 UCI 上的完整数据集上，以随机 缺失的方式得到不完整数据，缺失率从小到大依 次为 0.01、0.02、0.03、0.04、0.05、0.10、0.15 和 0.20；然后用现有的填充方法与本文提出的框架 结合后对得到的不完整数据进行处理；最后根据 修正填充前的原始数据集和修正填充后得到的最 终完整集得出不同缺失率下的 NRMSE 值及其变 化趋势。为了避免因单次填充而导致的误差对实 验结果的影响，实验在每种缺失率下均重复随机 缺失多次，最终得到的 NRMSE 值为多次重复缺 失后得到的均值。 3.2 实验数据集 本文从 UCI 中选取了 8 个数据集进行实验的 比较和分析，表 1 给出了 8 个数据集的基本信息， 包括数据集名称、样本个数、属性个数以及类别 个数，其中 balance-s、BCC、dba 和 lym 分别是 bal￾ance-scale、Breast Cancer Coimbra、data_banknote_ authentication 和 lymphography 数据集的简写。 表 1 数据集简介 Table 1 The introduction of the datasets 数据集 样本数 属性数 类别数 balance-s 625 4 3 BCC 116 10 2 dba 1 372 5 2 glass 214 10 7 haberman 306 3 2 lenses 24 4 3 lym 148 18 4 wine 178 13 3 3.3 不完整数据填充性能的评价标准 本文采用的评价不完整数据填充性能的指标 是归一化均方根误差，定义如下： NRMSE = √ mean(xguess − xori) 2 std(xori) (15) xguess xori std(xori) 式中： 和 分别代表填充后的属性值以及在 原始数据集中被填充前的属性值； 表示的 是被填充前的所有属性值的标准差。NRMSE 值越小，意味着填充后的值与填充前的值差异越 小，即填充效果越好。 3.4 实验结果与分析 本小节中，通过 NRMSE 度量指标对本文所 提框架与当前已有的缺失值填充方法所产生的结 果进行对比和分析，研究在不同的缺失率下，框架 对于现有填充方法的提升效果呈现出何种趋势。 图 2 分别展示了 7 组填充方法在不同数据集上以 及不同缺失率下对应的 NRMSE 值的变化趋势。 0 0.05 0.10 0.15 0.20 缺失率 0.1 0.2 0.3 0.4 0.5 NRMSE (a) haberman 0 0.05 0.10 0.15 0.20 缺失率 0.10 0.15 0.20 0.25 0.30 0.35 NRMSE (b) BCC 0 0.05 0.10 0.15 0.20 缺失率 0.25 0.30 0.35 0.40 0.45 0.50 NRMSE (c) balance-s 0 0.05 0.10 0.15 0.20 缺失率 0.1 0.2 0.3 0.4 NRMSE (d) dba 0 0.05 0.10 0.15 0.20 缺失率 0.1 0.2 0.3 0.4 NRMSE (e) glass 0 0.05 0.10 0.15 0.20 缺失率 0.2 0.4 0.6 0.8 1.0 NRMSE (f) lenses 第 6 期 严远亭，等：构造性覆盖下不完整数据修正填充方法 ·1229·

·1230· 智能系统学报 第14卷 0.50 0.30 0.45 0.25 A一MEI -MEI+CCA 0 0 KNNICCA 0.40 KNNI WKNNI WKNNI+CCA 0.20 MEDI MEDI+CCA 0.35 Softl Softl+CCA MFI MFI+CCA 0.30 0.15 MICE -MICE+CCA 0.25 0.10 0 0.050.100.150.20 0.050.100.150.20 缺失率 缺失率 (g)lym (h)wine 图27组填充方法在8个数据集上以及在不同缺失率下对应的NRMSE值 Fig.2 The NRMSE values corresponding to 7 groups of imputation methods on 8 datasets and at different missing rates 除此之外，图3更为直观地展示了7种现有 数据样本较少的数据集而言，当缺失率较小时， 填充方法分别在与本文所提框架结合后填充效果 对应缺失率下的缺失属性的数量也十分接近，在 的提升。其中，MR表示的是缺失率。从实验结 这种情况下，可能会出现缺失率略大反而填充效 果中不难发现，由于数据的随机缺失导致缺失值 果略好的情况，但从经过多次重复实验的结果来 的分布具有一定的随机性，同时因缺失场景的不 看可知NRMSE指标的总体变化呈上升趋势。 同和缺失数据本身的特点共同决定了没有任何一 从BCC和balance-s数据集上的实验结果中 种现有的填充方法可以在所有数据集上都能取得 可以看出，尽管有少数对比算法在缺失率较小的 最好的填充效果。但是本文所提框架应用于多数 时候呈现出的填充效果要优于本文的方法，但 现有填充方法和数据集上所呈现出来的填充效果 是，随着缺失率的不断增长，本文方法所展现出 均优于对比算法，如haberman、BCC等数据集。 来的优势逐渐明显。如MICE+CCA在balance-s 从总体上来看，针对一些特征（维）数较少而样本 数据集上，当缺失率达到5%以及在glass数据集 数较多的数据集而言，当缺失率较小时，对应的 上达到10%以后，填充效果开始逐渐优于对比算 NRMSE值也较小，当缺失率达到最小时， 法。此外，我们发现一些现有的单一填充方法在 NRMSE值往往也达到最小，意味着填充效果最 用本文框架修正填充后，填充效果更加逼近效果 好，但是随着缺失率的不断增大，对应的NRMSE 较好的多元填充方法，如：WKNNI+CCA在 逐渐呈现出增长的趋势。这是因为缺失率越小， lenses数据集上当缺失率达到20%时，几乎取得 出现缺失的属性数就越少，而当样本数远大特征 了等同于MICE的填充效果。这表明了通过和本 (维)数时，例如dba数据集的特征（维）数是5，但 文所提框架结合后可以更加有效地提升现有填充 却拥有1372个样本，当缺失率为1%时，出现缺 方法所产生的效果。 失的属性数是13，而该数据本身具有1372个样 当然，也有方法与框架结合后的提升效果不 本，故可用于填充的剩余完整样本数还有很多， 这对于数据的恢复十分有利。随着缺失率的增 佳，如：MICE+CCA在dba和wine数据集上的填 长，剩余完整样本逐渐变少，对应的NRMSE值也 充效果较对比方法差。这是因为MICE本身就运 呈现出上升的趋势。当然，也会出现极少数的特 用了多重填充的思想，已经在一定程度上规避了 殊情况，如：MEI方法在haberman数据集上当缺 因单一填充而引入的误差，因此，在通常情况下 失率为2%时，对应的NRMSE值略小于缺失率等 都会取得十分不错的填充效果。但是，MICE+ 于1%时对应的值，即随着缺失率的增大，NRMSE CCA在BCC、glass、haberman和lym等数据集上 值却在减小，类似的情况还有MEDI方法在 随着缺失率的不断增大，对于MICE方法的提升 glass数据集上以及SoftI方法在balance-s数据集 效果逐渐明显。此外，同样是在dba和wine数据 上等。这种情况出现的原因是实验所得的不完整 集上，本文所提出的用于修正填充其他现有方法 数据是通过随机缺失的方式得到的，且在挖掘空 的效果相对于对比算法的效果而言仍具有较大优 间邻域信息的过程中也采用了多次覆盖，因此具 势，如：KNNI+CCA、MFI+CCA等。 有一定的随机性，尽管重复随机缺失了很多次， 从lenses数据集和lym数据集上的实验结果 最后取多次实验所得的NRMSE度量值的均值为 来看，一方面，除了MICE方法在lenses上的填充 最终结果，但也只能在一定程度上较为稳定地反 效果比MICE+CCA好以外，其他几组对比算法 映出NRMSE值的总体变化趋势，此外，针对一些 的效果均没有本文提出的方法好，尤其是Sof+

除此之外，图 3 更为直观地展示了 7 种现有 填充方法分别在与本文所提框架结合后填充效果 的提升。其中，MR 表示的是缺失率。从实验结 果中不难发现，由于数据的随机缺失导致缺失值 的分布具有一定的随机性，同时因缺失场景的不 同和缺失数据本身的特点共同决定了没有任何一 种现有的填充方法可以在所有数据集上都能取得 最好的填充效果。但是本文所提框架应用于多数 现有填充方法和数据集上所呈现出来的填充效果 均优于对比算法，如 haberman、BCC 等数据集。 从总体上来看，针对一些特征 (维) 数较少而样本 数较多的数据集而言，当缺失率较小时，对应的 NRMS E 值也较小，当缺失率达到最小时， NRMSE 值往往也达到最小，意味着填充效果最 好，但是随着缺失率的不断增大，对应的 NRMSE 逐渐呈现出增长的趋势。这是因为缺失率越小， 出现缺失的属性数就越少，而当样本数远大特征 (维) 数时，例如 dba 数据集的特征 (维) 数是 5，但 却拥有 1 372 个样本，当缺失率为 1% 时，出现缺 失的属性数是 13，而该数据本身具有 1 372 个样 本，故可用于填充的剩余完整样本数还有很多， 这对于数据的恢复十分有利。随着缺失率的增 长，剩余完整样本逐渐变少，对应的 NRMSE 值也 呈现出上升的趋势。当然，也会出现极少数的特 殊情况，如：MEI 方法在 haberman 数据集上当缺 失率为 2% 时，对应的 NRMSE 值略小于缺失率等 于 1% 时对应的值，即随着缺失率的增大，NRMSE 值却在减小，类似的情况还 有 MEDI 方 法 在 glass 数据集上以及 SoftI 方法在 balance-s 数据集 上等。这种情况出现的原因是实验所得的不完整 数据是通过随机缺失的方式得到的，且在挖掘空 间邻域信息的过程中也采用了多次覆盖，因此具 有一定的随机性，尽管重复随机缺失了很多次， 最后取多次实验所得的 NRMSE 度量值的均值为 最终结果，但也只能在一定程度上较为稳定地反 映出 NRMSE 值的总体变化趋势，此外，针对一些 数据样本较少的数据集而言，当缺失率较小时， 对应缺失率下的缺失属性的数量也十分接近，在 这种情况下，可能会出现缺失率略大反而填充效 果略好的情况，但从经过多次重复实验的结果来 看可知 NRMSE 指标的总体变化呈上升趋势。 从 BCC 和 balance-s 数据集上的实验结果中 可以看出，尽管有少数对比算法在缺失率较小的 时候呈现出的填充效果要优于本文的方法，但 是，随着缺失率的不断增长，本文方法所展现出 来的优势逐渐明显。如 MICE+CCA 在 balance-s 数据集上，当缺失率达到 5% 以及在 glass 数据集 上达到 10% 以后，填充效果开始逐渐优于对比算 法。此外，我们发现一些现有的单一填充方法在 用本文框架修正填充后，填充效果更加逼近效果 较好的多元填充方法，如： WKNNI+CCA 在 lenses 数据集上当缺失率达到 20% 时，几乎取得 了等同于 MICE 的填充效果。这表明了通过和本 文所提框架结合后可以更加有效地提升现有填充 方法所产生的效果。 当然，也有方法与框架结合后的提升效果不 佳，如：MICE+CCA 在 dba 和 wine 数据集上的填 充效果较对比方法差。这是因为 MICE 本身就运 用了多重填充的思想，已经在一定程度上规避了 因单一填充而引入的误差，因此，在通常情况下 都会取得十分不错的填充效果。但是，MICE+ CCA 在 BCC、glass、haberman 和 lym 等数据集上 随着缺失率的不断增大，对于 MICE 方法的提升 效果逐渐明显。此外，同样是在 dba 和 wine 数据 集上，本文所提出的用于修正填充其他现有方法 的效果相对于对比算法的效果而言仍具有较大优 势，如：KNNI+CCA、MFI+CCA 等。 从 lenses 数据集和 lym 数据集上的实验结果 来看，一方面，除了 MICE 方法在 lenses 上的填充 效果比 MICE+ CCA 好以外，其他几组对比算法 的效果均没有本文提出的方法好，尤其是 SoftI+ 0 0.05 0.10 0.15 0.20 缺失率 0.25 0.30 0.35 0.40 0.45 0.50 NRMSE (g) lym 0 0.05 0.10 0.15 0.20 缺失率 0.10 0.15 0.20 0.25 0.30 NRMSE (h) wine MEI KNNI WKNNI MEDI SoftI MFI MICE MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SoftI+CCA MFI+CCA MICE+CCA 图 2 7 组填充方法在 8 个数据集上以及在不同缺失率下对应的 NRMSE 值 Fig. 2 The NRMSE values corresponding to 7 groups of imputation methods on 8 datasets and at different missing rates ·1230· 智 能 系 统 学 报 第 14 卷

第6期 严远亭，等：构造性覆盖下不完整数据修正填充方法 ·1231· CCA在lenses数据集上以及KNNI+CCA、MFI+ 的效果更好一些，但是与本文提出的MICE+ CCA等方法在Iym数据集上的填充效果均显著 CCA的效果相比较，差距并不是很大，而后者表 优于对比算法；另一方面，尽管MICE在lenses上 现出的算法稳定性更高。 ■0.01☐0.02☐0.03☐0.04☐0.05☐0.10☐0.15☐0.20 0.20 0.10 0.08 0.15 0.08 0.06 0.10 0.10 0.06 0.04 0.05 0.05 0.02 0.02 0 0 0 -0.05 -0.02 0.02 009 KNNI+CCA CCA NNI+CCA CA MEI+CCA +CCA MEI+CCA CA A MICE MICE M WK MEDI SO (a)haberman (b)BCC (c)balance-s (d)dba 0.10 0.3 006 0.04 0.08 0.2 0.04 0.02 0.06 0.1 002 0.04 -0.02 0.02 房-0.02 0 -0.1 -0.04 0.04 -0.0 -0.2 -006 -0.06 MEI+CCA CA ● MIC SOF (e)glass (f)lenses (g)lym (h)wine 图37组现有填充方法经修正后的填充效果提升图 Fig.3 The improvement of the imputation effect by using proposed method 4结束语 此之外，本文所提框架还可以将一些效果较差的 单一填充方法的填充效果提升至更好的多重填充 针对当前已有的大多数填充方法忽视了样本 方法所取得的效果。 空间分布信息对数据恢复的影响，本文提出了一 种可广泛应用于现有填充方法的框架，旨在对利 参考文献： 用现有方法得到的填充结果进行修正，从而提升 [1]LARRANAGA P,CALVO B,SANTANA R,et al.Ma- 填充效果。该框架由预填充、空间邻域信息挖掘 chine learning in bioinformatics[J].Briefings in bioinform- 和修正填充3部分构成，首先利用现有填充方法 atics,.2006.7(1):86-112 对样本进行预填充；再通过引入一种空间邻域信 [2]HARPER P R.A review and comparison of classification 息挖掘方法来找到与待填样本具有更高相似度的 algorithms for medical decision making[J].Health policy. 若干个空间邻域：最后利用待填样本的空间邻域 2005,71(3):315-331 内的有效信息对现有填充方法产生的填充结果进 [3]SEBASTIANI F.Machine learning in automated text cat- 行修正。 egorization[J].ACM computing surveys,2002,34(1): 实验选取了7种经典的填充方法（包括单一 1-47 填充和多重填充)，在8个UCI数据集上进行了对 [4]KONG S G.HEO J.ABIDI B R.et al.Recent advances in 比。结果表明，本文提出的框架确实能够在大多 visual and infrared face recognition-a review[J].Com- 数数据集上有效提升现有填充方法的填充效果。 puter vision and image understanding,2005,97(1): 103-135 尽管在少数数据集上的提升效果不佳，但是从实 [5]FU Xiao,REN Yinzi,YANG Guiqiu,et al.A computation- 验所得的不同缺失率下的NRMSE度量值的变化 al model for heart failure stratification[Cl//Proceedings of 趋势来看，多数与框架结合后的填充方法通常呈 2011 IEEE Computing in Cardiology.Hangzhou,China, 现出较为平稳的填充趋势，不会随着缺失率的不 2011:385-388 断增长而出现较大波动，而且在某些数据集上呈 [6]FIALHO A S,KAYMAK U,ALMEIDA R J,et al.Prob- 现出一个重要规律，即随着缺失率的不断增大， abilistic fuzzy prediction of mortality in intensive care 框架对于现有填充方法的提升效果逐渐明显。除 units[C]//Proceedings of 2012 IEEE International Confer-

CCA 在 lenses 数据集上以及 KNNI+CCA、MFI+ CCA 等方法在 lym 数据集上的填充效果均显著 优于对比算法；另一方面，尽管 MICE 在 lenses 上 的效果更好一些，但是与本文提出的 MICE+ CCA 的效果相比较，差距并不是很大，而后者表 现出的算法稳定性更高。 (a) haberman MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.05 0 0.05 0.10 0.15 0.20 精度提升 0.01 0.02 0.03 0.04 0.05 0.10 0.15 0.20 (b) BCC MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.02 0 0.02 0.04 0.06 0.08 0.10 精度提升 (c) balance-s MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.02 0 0.02 0.04 0.06 0.08 精度提升 (d) dba MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.05 0 0.05 0.10 0.15 精度提升 (e) glass MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.02 0 0.02 0.04 0.06 0.08 0.10 精度提升 (f) lenses MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.2 −0.1 0 0.1 0.2 0.3 精度提升 (g) lym MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.06 −0.04 −0.02 0 0.02 0.04 0.06 精度提升 (h) wine MEI+CCA KNNI+CCA WKNNI+CCA MEDI+CCA SOFTI+CCA MFI+CCA MICE+CCA −0.06 −0.04 −0.02 0 0.02 0.04 精度提升 图 3 7 组现有填充方法经修正后的填充效果提升图 Fig. 3 The improvement of the imputation effect by using proposed method 4 结束语 针对当前已有的大多数填充方法忽视了样本 空间分布信息对数据恢复的影响，本文提出了一 种可广泛应用于现有填充方法的框架，旨在对利 用现有方法得到的填充结果进行修正，从而提升 填充效果。该框架由预填充、空间邻域信息挖掘 和修正填充 3 部分构成，首先利用现有填充方法 对样本进行预填充；再通过引入一种空间邻域信 息挖掘方法来找到与待填样本具有更高相似度的 若干个空间邻域；最后利用待填样本的空间邻域 内的有效信息对现有填充方法产生的填充结果进 行修正。 实验选取了 7 种经典的填充方法 (包括单一 填充和多重填充)，在 8 个 UCI 数据集上进行了对 比。结果表明，本文提出的框架确实能够在大多 数数据集上有效提升现有填充方法的填充效果。 尽管在少数数据集上的提升效果不佳，但是从实 验所得的不同缺失率下的 NRMSE 度量值的变化 趋势来看，多数与框架结合后的填充方法通常呈 现出较为平稳的填充趋势，不会随着缺失率的不 断增长而出现较大波动，而且在某些数据集上呈 现出一个重要规律，即随着缺失率的不断增大， 框架对于现有填充方法的提升效果逐渐明显。除 此之外，本文所提框架还可以将一些效果较差的 单一填充方法的填充效果提升至更好的多重填充 方法所取得的效果。 参考文献： LARRAÑAGA P, CALVO B, SANTANA R, et al. Ma￾chine learning in bioinformatics[J]. Briefings in bioinform￾atics, 2006, 7(1): 86–112. [1] HARPER P R. A review and comparison of classification algorithms for medical decision making[J]. Health policy, 2005, 71(3): 315–331. [2] SEBASTIANI F. Machine learning in automated text cat￾egorization[J]. ACM computing surveys, 2002, 34(1): 1–47. [3] KONG S G, HEO J, ABIDI B R, et al. Recent advances in visual and infrared face recognition—a review[J]. Com￾puter vision and image understanding, 2005, 97(1): 103–135. [4] FU Xiao, REN Yinzi, YANG Guiqiu, et al. A computation￾al model for heart failure stratification[C]//Proceedings of 2011 IEEE Computing in Cardiology. Hangzhou, China, 2011: 385–388. [5] FIALHO A S, KAYMAK U, ALMEIDA R J, et al. Prob￾abilistic fuzzy prediction of mortality in intensive care units[C]//Proceedings of 2012 IEEE International Confer- [6] 第 6 期 严远亭，等：构造性覆盖下不完整数据修正填充方法 ·1231·

·1232· 智能系统学报 第14卷 ence on Fuzzy Systems.Brisbane,Australia,2012:1-8. nonresponse in surveys[J].Statistical papers,1990,31(1): [7]AITTOKALLIO T.Dealing with missing values in large- 180. scale studies:microarray data imputation and beyond[J]. [20]SIM J M,KWON O,LEE K C.Adaptive pairing of clas- Briefings in bioinformatics,2010,11(2):253-264. sifier and imputation methods based on the characterist- [8]DE SOUTO MC P,JASKOWIAK P A,COSTA I G.Im- ics of missing values in data sets[J].Expert systems with pact of missing data imputation methods on gene expres- applications,2016,46:485-493. sion clustering and classification[J].BMC bioinformatics, [21]张铃，张钹.M-P神经元模型的几何意义及其应用]， 2015,16:64 软件学报，1998.9(5)：334338. [9]LIU Siyuan,CHEN Lei,NI L M.Anomaly detection from ZHANG Ling,ZHANG Bo.A geometrical representation incomplete data[J].ACM transactions on knowledge dis- of M-P neural model and its applications[J].Journal of covery from data,2014,9(2):11. software,.1998,9(5):334-338. [10]LIU Ji,MUSIALSKI P,WONKA P,et al.Tensor com- [22]张燕平，张铃.机器学习理论与算法M.北京：科学出 pletion for estimating missing values in visual data[J]. 版社.2012：56-66. IEEE transactions on pattern analysis and machine intelli- [23]JORNSTEN R,WANG Huiyu,WELSH W J,et al.DNA gence,2013,35(1):208-220. microarray data imputation and significance analysis of [11]LAKSHMINARAYAN K.HARP S A.SAMAD T.Im- differential expression[J].Bioinformatics,2005,21(22): putation of missing data in industrial databases[J].Ap- 4155-4161. plied intelligence,1999,11(3):259-275. [24]MAZUMDER R,HASTIE T,TIBSHIRANI R.Spectral [12]SONG Qinhao,SHEPPERD M,CHEN Xiangru,et al. regularization algorithms for learning large incomplete Can k-NN imputation improve the performance of C4.5 matrices[J].The journal of machine learning research, with small software project data sets?A comparative 2010,11:2287-2322. evaluation[J].Journal of systems and software,2008. [25]RANJBAR M,MORADI P,AZAMI M,et al.An imputa- 81(12):2361-2370. tion-based matrix factorization method for improving ac- [13]DONDERS A R T,VAN DER HEIJDEN GJ M G. curacy of collaborative filtering systems[J].Engineering STIJNEN T,et al.Review:a gentle introduction to im- putation of missing values[J].Journal of clinical epidemi- applications of artificial intelligence,2015,46:58-66. ology,2006,59101087-1091. 作者简介： [14]TROYANSKAYA O,CANTOR M,SHERLOCK G,et 严远亭，男，1986年生，讲师，博 al.Missing value estimation methods for DNA microar- 士，中国人工智能学会会员，主要研究 rays[J].Bioinformatics,2001,17(6):520-525. 方向为机器学习、粒计算和生物信息 [15]KEERIN P.,KURUTACH W,BOONGOEN T.Cluster- 学。主持国家自然科学基金青年项目 1项，发表学术论文10余篇。 based KNN missing value imputation for DNA microar- ray data[Cl//Proceedings of 2012 IEEE International Con- ference on Systems,Man,and Cybernetics.Seoul,South Korea,2012:445-450. 吴亚亚，男，1995年生，硕士研究 [16]VAN BUUREN S.GROOTHUIS-OUDSHOORN K. 生，中国人工智能学会会员，主要研究 方向为机器学习和不完整数据处理。 Mice:Multivariate imputation by chained equations in R[J].Journal of statistical software,2011,45(3):75765. [17]GEBREGZIABHER M,DESANTIS S M.Latent class based multiple imputation approach for missing categoric- al data[J].Journal of statistical planning and inference, 2010,140(11:3252-3262. 赵蛛，女，1979年生，教授，博士 [18]VERMUNT J K,VAN GINKEL JR,VAN DER ARK L 生导师，博土，中国人工智能学会粒计 算与知识发现专委会委员，安徽省人 A,et al.9.Multiple imputation of incomplete categorical 工智能学会常务理事，主要研究方向 data using latent class analysis[J].Sociological methodo- 为机器学习、粒计算。获得发明专利 1ogy,2008.38(1):369-397. 和软件著作权多项，发表学术论文 [19]TOUTENBURG H.Rubin,D.B.:multiple imputation for 60余篇

ence on Fuzzy Systems. Brisbane, Australia, 2012: 1–8. AITTOKALLIO T. Dealing with missing values in large￾scale studies: microarray data imputation and beyond[J]. Briefings in bioinformatics, 2010, 11(2): 253–264. [7] DE SOUTO M C P, JASKOWIAK P A, COSTA I G. Im￾pact of missing data imputation methods on gene expres￾sion clustering and classification[J]. BMC bioinformatics, 2015, 16: 64. [8] LIU Siyuan, CHEN Lei, NI L M. Anomaly detection from incomplete data[J]. ACM transactions on knowledge dis￾covery from data, 2014, 9(2): 11. [9] LIU Ji, MUSIALSKI P, WONKA P, et al. Tensor com￾pletion for estimating missing values in visual data[J]. IEEE transactions on pattern analysis and machine intelli￾gence, 2013, 35(1): 208–220. [10] LAKSHMINARAYAN K, HARP S A, SAMAD T. Im￾putation of missing data in industrial databases[J]. Ap￾plied intelligence, 1999, 11(3): 259–275. [11] SONG Qinhao, SHEPPERD M, CHEN Xiangru, et al. Can k-NN imputation improve the performance of C4.5 with small software project data sets? A comparative evaluation[J]. Journal of systems and software, 2008, 81(12): 2361–2370. [12] DONDERS A R T, VAN DER HEIJDEN G J M G, STIJNEN T, et al. Review: a gentle introduction to im￾putation of missing values[J]. Journal of clinical epidemi￾ology, 2006, 59(10): 1087–1091. [13] TROYANSKAYA O, CANTOR M, SHERLOCK G, et al. Missing value estimation methods for DNA microar￾rays[J]. Bioinformatics, 2001, 17(6): 520–525. [14] KEERIN P, KURUTACH W, BOONGOEN T. Cluster￾based KNN missing value imputation for DNA microar￾ray data[C]//Proceedings of 2012 IEEE International Con￾ference on Systems, Man, and Cybernetics. Seoul, South Korea, 2012: 445-450. [15] VAN BUUREN S, GROOTHUIS-OUDSHOORN K. Mice: Multivariate imputation by chained equations in R[J]. Journal of statistical software, 2011, 45(3): 75765. [16] GEBREGZIABHER M, DESANTIS S M. Latent class based multiple imputation approach for missing categoric￾al data[J]. Journal of statistical planning and inference, 2010, 140(11): 3252–3262. [17] VERMUNT J K, VAN GINKEL J R, VAN DER ARK L A, et al. 9. Multiple imputation of incomplete categorical data using latent class analysis[J]. Sociological methodo￾logy, 2008, 38(1): 369–397. [18] [19] TOUTENBURG H. Rubin, D.B.: multiple imputation for nonresponse in surveys[J]. Statistical papers, 1990, 31(1): 180. SIM J M, KWON O, LEE K C. Adaptive pairing of clas￾sifier and imputation methods based on the characterist￾ics of missing values in data sets[J]. Expert systems with applications, 2016, 46: 485–493. [20] 张铃, 张钹. M-P 神经元模型的几何意义及其应用 [J]. 软件学报, 1998, 9(5): 334–338. ZHANG Ling, ZHANG Bo. A geometrical representation of M-P neural model and its applications[J]. Journal of software, 1998, 9(5): 334–338. [21] 张燕平, 张铃. 机器学习理论与算法 [M]. 北京: 科学出 版社, 2012: 56–66. [22] JÖRNSTEN R, WANG Huiyu, WELSH W J, et al. DNA microarray data imputation and significance analysis of differential expression[J]. Bioinformatics, 2005, 21(22): 4155–4161. [23] MAZUMDER R, HASTIE T, TIBSHIRANI R. Spectral regularization algorithms for learning large incomplete matrices[J]. The journal of machine learning research, 2010, 11: 2287–2322. [24] RANJBAR M, MORADI P, AZAMI M, et al. An imputa￾tion-based matrix factorization method for improving ac￾curacy of collaborative filtering systems[J]. Engineering applications of artificial intelligence, 2015, 46: 58–66. [25] 作者简介： 严远亭，男，1986 年生，讲师，博 士，中国人工智能学会会员，主要研究 方向为机器学习、粒计算和生物信息 学。主持国家自然科学基金青年项目 1 项，发表学术论文 10 余篇。 吴亚亚，男，1995 年生，硕士研究 生，中国人工智能学会会员，主要研究 方向为机器学习和不完整数据处理。 赵姝，女，1979 年生，教授，博士 生导师，博士，中国人工智能学会粒计 算与知识发现专委会委员，安徽省人 工智能学会常务理事，主要研究方向 为机器学习、粒计算。获得发明专利 和软件著作权多项，发表学术论文 60 余篇。 ·1232· 智 能 系 统 学 报 第 14 卷