第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 algorithm[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 distribution 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. Experimental 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; imputation 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] 、MILC[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。 随机缺失得到 <x,x>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,x>表示样本与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。 < xk , xi > 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 > 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 分别是 balance-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·