由于感知设备硬件资源有限、抵制干扰性差等固有限制,感知网络在数据获取过程中经常存在数据缺失现象.目前,一般对缺失数据的处理办法分为3大类:(1) case deletion,即直接丢弃缺失数据元组;(2) learning without handling of missing data,即不做处理,直接将缺失数据元组传递给上层应用;(3) data imputation,对缺失数据进行填补.当数据集中包含大量缺失数据时,若直接将其丢弃会造成原始数据信息的失真,导致上层应用得到的结果与预期偏差较大.若不对缺失数据进行处理,现有的用于聚类(clustering)、统计分析(statistical analysis)、机器学习(machine learning)等上层应用中的分析工具无法处理含有缺失值的数据集.因此,当缺失数据的规模对整个数据集来说不可忽视时,对缺失数据进行填补是非常必要的.

由于感知网络主要通过部署大量的感知设备对真实环境中的目标从多个维度进行监测,因此,感知数据通常具有一定的时间相关性、空间相关性以及属性相关性,本文称这3方面相关性为多维度相关性.目前,已有的缺失数据填补算法本质上均利用了数据在时间或空间或属性上的相关性,如:连续多元回归填补^{[1, 2, 3, 4]}通过衡量数据源在空间或属性上的相似度来获取用于估计缺失值的数据元组;时间序列填补^[5]利用数据的时间相关性进行填补;加权k近邻填补^[6]利用数据的属性相关性进行填补.但这些已有方法均未同时考虑感知数据的多维度相关性,而只考虑某一方面的相关性通常具有一定的局限性.

例1:图 1是伯克利研究实验室提供的室内54个传感器的分布图,利用这54个传感器可对室内温度、湿度和光强数据进行采集.

表 1为图 1中数据源s₄₂~s₅₁在t₁~t₇时刻对室内温度、湿度信息进行获取得到的感知数据矩阵.表中第1行代表时间戳,第1列代表数据源,其余单元格内为相应数据源在对应时刻的温度、湿度感知数据对,加粗的数字的表示该数据在真实数据集中是缺失的.根据各个传感器的位置分布可知,传感器s₄₆的空间3NN为s₄₅,s₄₇,s₄₈,但t₇时刻s₄₅,s₄₇,s₄₈的温度数据均为缺失状态,即:若只利用空间相关性,将无法对传感器s₄₆进行填补.而根据各个感知节点的历史数据,可计算得到传感器s₄₆在时间相关性上的3NN为s₄₇,s₅₀,s₅₁.由于s₅₀,s₅₁在t₇时刻为完整数据元组,可利用时间相关性上的近邻节点对传感器s₄₆的温度值进行填补.因此,同时考虑感知数据的多维度相关性,将更加有利于缺失数据的填补,且3个方面的相关性具有相辅相成的作用.

另一方面,与待填补数据源相似度较高的数据源是否包含缺失数据,将对填补值的准确性有很大的影响,尤其是在缺失数据较为密集的情况下.因此,本文将已填补的缺失值作为观测值用于后续填补,此时,不同的缺失数据填补顺序将得到不同甚至差异很大的填补结果.

例2:在对表 1中的缺失数据进行填补过程中,根据不同的填补顺序会得到不同的填补结果,如填补顺序为(46,48,45,49,44,47)时,填补结果为(17.10,17.214,16.905,16.904,17.291,17.22);当填补顺序为(49,47,48,46,44,45)时,填补结果为(17.151,17.248,16.906,16.964,17.327,17.248).由此可知,不同填补顺序得到的填补结果不同.此外,根据表 1给出的各个缺失值的真值,可计算得到第1个填补顺序的平均填补误差为0.290,第2个填补顺序的平均填补误差为0.293.由此说明,不同填补结果对应不同的填补误差.如何确定一个最优的填补顺序,从而得到填补误差最小的填补结果,是本文重点要解决的问题.

基于以上描述,本文提出了面向多源感知数据的、基于多维度相关性且顺序敏感的缺失值填补框架OMSMVI.该框架首先利用感知数据的多维度相关性,提出对缺失数据源与其他数据源间相似度度量的新方法;其次,OMSMVI构建能够充分刻画缺失数据源之间以及缺失数据源与完整数据源间相关关系的相似图,进而在相似图基础上提出缺失数据填补顺序的决策算法;最后对KNN填补算法进行改进,提出一种新的基于近邻的缺失值填补方法NI.本文的主要贡献点主要有:

· 面向感知数据的缺失值填补问题,提出一种新的顺序敏感的缺失值填补框架OMSMVI;

· 充分利用感知数据的多维度相关性对数据源间的相似度进行衡量,并构建以缺失数据源为中心的相似图;

· 针对缺失数据较为密集的情况,考虑不同填补顺序对填补精度的影响,提出填补顺序决策问题,并通过精确和近似算法对其进行求解;

· 对现有的KNN填补算法进行改进,提出基于近邻的缺失值填补算法,该算法解决了KNN填补过程中K值难以确定的问题;并通过利用缺失数据源周围的所有近邻节点对缺失值进行填补,提高了在缺失值较为密集情况下填补值的准确性;

· 利用两个真实数据集,通过大量实验验证了本文算法的准确性及有效性.

本文第1节对已有的缺失数据填补算法进行总结,并指出已有工作与本文的不同.第2节给出问题描述及相关定义.第3节详细介绍缺失数据源的近邻筛选方法.第4节提出缺失数据填补顺序决策问题,给出精确及近似求解方法,并提出一种新的缺失值填补算法NI.第5节给出实验结果及数据分析.最后,在第6节进行总结.

1 相关工作

目前已有的填补算法很多,常用的算法有hot-deck填补、回归填补、KNN填补、多重填补.Hot-deck填补主要包含两个步骤:(1) 对不包含缺失值且与待填补值相关的完整数据进行分类;(2) 从每个分类中按照完整数据与缺失数据的相关性大小选择合适的完整数据作为donor用于填补^[7].文献^[8]在文献^[7]的基础上,在donors选取计算中加入权重,并提出每个donor用于缺失值填补的次数与权重成正比.回归填补是一种条件性的均值填补,该方法基于完整数据集建立缺失值与已知值间的回归模型,进而依据历史数据学习得到的参数来估计缺失变量值.当变量不是线性相关或高度相关时,会导致填补值与真实值间的偏差较大.文献^{[3, 4]}利用一系列线性和非线性回归模型对缺失值进行填补,文献^{[1, 2]}利用核函数建立回归模型.回归填补的优点是既适用于分类型数据又适用于连续型数据,缺点是模型的参数确定比较复杂,填补准确性不容易保证.KNN填补的主要思想是,利用缺失值的K个近邻的加权均值替代缺失值.文献^[6]针对基因数据,利用欧式距离找出数据矩阵中与缺失值最相似的K个近邻进而进行缺失值填补.文献^[9]基于灰色关联度对缺失数据的K近邻进行查找,进而对缺失值进行填补.文献^[10]提出基于KNN的部分填补,该方法利用机器学习和数据挖掘异常点检测技术来探测缺失值是否可填补:若缺失值不可填补,则放弃填补;若缺失值可填补,则利用缺失值的左右近邻进行加权KNN填补.由此可知,该填补方法并不是对每个缺失值均进行填补.为了进一步提高填补的精度,文献^[11]提出了基于EM的非参数缺失数据填补方法,类似于EM算法,不同的是,利用非参数模型如KNN或核函数回归来代替EM算法中的有参模型.多重填补^{[12, 13, 14]}利用m(m>1)个能够反映数据本身分布概率的值来代替缺失值,以反映缺失数据的不确定性.多重填补通过模拟缺失数据的分布,较好地保持了变量之间的关系,但其处理过程较为复杂.

以上算法均针对静态数据进行填补,文献^{[15, 16]}研究了感知流上的缺失值估计问题.Gruenwald等人^[15]采用数据挖掘技术,提出了WARM算法,当某一数据源节点a产生的流数据出现缺失时,该算法首先找到与a相关联的另一数据源节点b,然后用b的相应数据作为a的填补值.Jiang等人^[16]对WARM算法进行了改进,提出了CARM算法,该算法通过对流数据进行关联规则计算,找到多个数据源节点的频繁模式,并用该频繁模式来估计缺失值.然而这两个算法具有很大的局限性,无法被广泛应用:首先,这两个算法只能处理离散型数据,无法处理连续型数据;另一方面,这两个算法对缺失值的计算能力和估计准确性依赖于关联规则中用户指定的支持度阈值和置信度阈值,而实际应用中,用户很难知道数据之间的关联程度及数据变化规律,因此很难给出恰当的阈值.此外,如果缺失值所对应的数据元组不出现在频繁模式中,则这两个算法无法对缺失值进行估计计算.文献^[17]提出了针对缺失数据流进行并行填补的框架Pythia,该框架主要解决的问题是:如何将包含缺失值的大数据划分到多台机器上进行并行处理,从而提高填补效率.框架用到的填补方法为已有的加权KNN填补及连续多元回归填补,因此侧重点和本文不同.

另一方面,由于数据类型限制或处理速度的制约,目前针对感知数据,同时考虑其在时间、空间、属性这3方面相关性的缺失值填补方法鲜少.文献^[18]基于稀疏真实数据,利用机器学习方法对细粒度的空气质量数据进行填补.该工作从大量交通流量、气象等数据集中提取出与空气质量相关的特征属性,并将这些特征属性分为空间相关的和时间相关的两类,进而分别对其利用半监督机器学习方法并结合已有的历史数据进行缺失值的填补.该方法的局限性在于:只能处理分类型数据,针对连续型数据,只能先对其进行离散化处理才能在机器学习过程中对其进行打标签操作,因此不适用于连续型数据.

最后,以上相关工作均未考虑在缺失值较为密集的情况下,不同的填补顺序对填补结果的影响.目前,针对顺序敏感的缺失数据填补的方法还比较少,Kim等人^[19]提出了顺序KNN填补算法,该算法针对gene数据,根据每个基因中包含缺失值的多少对其进行排序,先填补包含缺失值最少的数据,并将填补后的gene作为完整数据用于后续缺失值的填补.算法只是通过简单的规则定义缺失值的填补顺序,并未对不同填补顺序对填补结果的影响进行量化.文献^[20]在确定填补顺序的策略方面与文献^[19]完全相同,只是在判定不同gene间相似度的方法上不同.

2 问题描述

设感知网络中有N个数据源$\mathbb{S}=\left\{ {{S}_{1}},{{S}_{2}},\ldots ,{{S}_{N}} \right\},t$时刻N个数据源的感知数据集合为${{\mathbb{D}}^{t}}=\{D_{1}^{t},D_{2}^{t},...,D_{N}^{t}\}$,其中每条感知数据为包含m维属性的多模态数据,如数据源S_i在t时刻的感知数据为$D_{i}^{t}=(d_{i1}^{t},d_{i2}^{t},...,d_{im}^{t})$.下面是文中要用到的一些定义.

定义1(缺失数据元组). 若多模态感感知数据$D_{i}^{t}$在某一维上的属性值缺失,则称$D_{i}^{t}$为缺失数据元组.

定义2(完整数据元组). 若多模态感知数据$D_{i}^{t}$在每一维属性上观测值均存在,则称$D_{i}^{t}$为完整数据元组.

定义3(相对完整数据元组). 对于缺失数据$D_{i}^{t}$的待填补维$d_{ij}^{t}$,若多模态感知数据$D_{k}^{t}$在待填补维上的观测数据$d_{kj}^{t}$存在,则称$D_{k}^{t}$为$D_{i}^{t}$的相对完整数据元组.

定义4(时间邻域). t时刻,对于待填补缺失数据$d_{ij}^{t}$,其前s个时刻的感知数据元组集合称为$d_{ij}^{t}$的时间邻域,表示为$\mathbb{D}_{ij}^{TN}=\{D_{ij}^{t-s},D_{ij}^{t-(s-1)},...,D_{ij}^{t-1}\}.$

定义5(属性邻域). t时刻,对于待填补缺失数据$d_{ij}^{t}$,其属性邻域为数据元组$D_{i}^{t}$中与待填补维j具有相关性的属性组成的新的元组,表示为$\mathbb{D}_{ij}^{AN}=\{d_{ik}^{t}|k\in [1,m],k\ne j\}.$

定义6(空间近邻). t时刻,数据源S_i的空间近邻为与其欧式距离小于等于给定阈值d_d的数据源集合,表示为

$S{{N}_{i}}=\{{{S}_{j}}|j\hat{I}\left[ 1,N \right],j{}^\text{1}i,dis\left( {{S}_{i}},{{S}_{j}} \right)\le {{d}_{d}}\}.$

为了简便起见,不失一般性,本文利用数据元组中只包含一维数据缺失的情况进行说明.对于包含多维缺失数据的元组,可将其看作多条只包含一维缺失数据的元组进行处理.设t时刻到达的N个数据源的感知数据集中包含n条缺失数据元组,对应的缺失数据源集合为MS={S₁,S₂,…,S_n}.本文最终的目的是要对n个缺失数据源的缺失数据进行填补,利用的基本思想是:对于缺失数据源S_i,若用于填补的数据源与缺失数据源间的相似度越高,则填补值的准确性越高;同时,两个缺失数据源间的相似度越高,则在数据填补过程中,他们之间的相互影响越大.由于每个缺失数据源的近邻分布不同,在缺失数据分布较为密集的情况下,不同的填补顺序会得到不同的填补结果,因为已填补的缺失值将作为观测值用于后续填补过程.因此,在对缺失数据进行填补前,需确定最优的填补顺序.本文提出的顺序敏感的缺失值填补框架OMSMVI的基本流程如图 2所示.

对于t时刻感知数据中包含的n条缺失数据,首先计算每个缺失数据源与剩余数据源在时间、空间、属性上的相关性,进而确定数据源间的多维度相关性;其次,依据数据源间的多维度相似性确定每个缺失数据源的近邻节点,进而基于近邻节点构建以缺失数据源为中心的相似图,由于相似图中有边连接的两点间的相似度需大于给定阈值,因此构建出的相似图可能是一个包含所有缺失数据源的大图,也可能是多个互不连通的小图;最后,基于相似图对缺失数据的填补顺序进行决策,选择最优的填补顺序,进而利用适用的缺失数据填补方法对缺失数据依次进行填补.

3 缺失数据源近邻筛选

本节将详细介绍缺失数据源的近邻节点筛选算法,其主要思想是:综合缺失数据源与剩余数据源在时间、空间、属性这3方面的相似度,筛选出每个缺失数据源的近邻节点,近邻节点与缺失数据源间的相似度需在某一维度上大于相应阈值.为了能最大限度地找出所有近邻点,时间、空间、属性这3方面的相关性相互互补,即,近邻节点只需满足某一方面的相似度即可.

3.1 多维度相关性模型

多维度相关性是指感知数据特有的时间相关性、空间相关性以及属性相关性.时间相关性是指感知数据随时间的变化具有一定的趋势性,若两个数据源在历史时间内的数据比较相似,则下一时刻二者之间的观测值相差不大,即:t时刻对第j维缺失数据进行填补过程中,若数据源S_i和S_k的时间邻域$\mathbb{D}_{ij}^{TN},\mathbb{D}_{kj}^{TN}$相似度较高,则$d_{ij}^{t}$与$d_{kj}^{t}$也较为相似.本文利用数据源在时间邻域上的相似度来衡量当前时刻两数据源间的时间相似性.感知数据的空间相关性是指物理位置上相近的感知节点采集到的数据往往比较相似或存在某种函数关系.直观上,若两个数据源相距很远,它们将不具有空间相关性.因此对于缺失数据源S_i,只需计算其空间近邻内的数据源与S_i的相似性即可.此外,由于数据源的位置通常是相对固定或是成组移动的,因此可周期性地对各个数据源间的空间相似性进行更新,而不必每一时刻均对其进行计算.属性相关性是指不同维度间的感知数据具有一定的相关性,如海水的温度和盐度、空气的能见度和风速均存在一定的正相关关系.在t时刻对第j维缺失数据进行填补过程中,若$d_{ij}^{t}$与$d_{kj}^{t}$的属性邻域具有较高的相似度,则$d_{ij}^{t}$与$d_{kj}^{t}$相差不大.基于此,本文通过待填补维度的属性邻域的

相似性来衡量不同数据源在待填补维上的属性相似性.

综上,基于对不同数据源在时间、空间、属性上相似性度量的介绍,本文采用平均欧式距离来度量数据源间多维度的相似度.假设当前时刻第j维属性存在数据缺失,则数据源S_i和S_k间的多维度相似度为

$Si{{m}_{ik}}=\frac{1}{1+\min \{d_{ik}^{T},d_{ik}^{S},d_{ik}^{A}\}}$

(1)

其中,$d_{ik}^{T},d_{ik}^{S},d_{ik}^{A}$分别表示数据源S_i和S_k在时间、空间、属性上的距离,具体计算公式如下所示:

$d_{ik}^{T}=\frac{{{h}_{T}}}{s}\sqrt{\sum\limits_{d_{ij}^{{{t}'}}\in \mathbb{D}_{ij}^{TN},d_{kj}^{{{t}'}}\in \mathbb{D}_{kj}^{TN}}{{{(d_{ij}^{{{t}'}}-d_{kj}^{{{t}'}})}^{2}}}}$

(2)

$d_{ik}^{S}=\frac{{{h}_{S}}}{|loc|}\sqrt{\sum\limits_{{{l}_{i}}\in lo{{c}_{i}},{{l}_{j}}\in lo{{c}_{j}}}{{{({{l}_{i}}-{{l}_{k}})}^{2}}}}$

(3)

$d_{ik}^{A}=\frac{{{h}_{A}}}{|\mathbb{D}_{ij}^{AN}|}\sqrt{\sum\limits_{d_{ij}^{t}\in \mathbb{D}_{ij}^{AN},d_{kj}^{t}\in \mathbb{D}_{kj}^{AN}}{{{(d_{ij}^{t}-d_{kj}^{t})}^{2}}}}$

(4)

其中,loc表示数据源的位置信息;|loc|表示位置的维数,如感知设备位置信息用二维空间点表示,则|loc|=2;$|\mathbb{D}_{ij}^{AN}|$为属性邻域的维数,h_T,h_S,h_A为每一维度上的归一化因子.根据公式(1)可知,两个数据源间的多模态相似度为它们在时间、空间、属性上相似度的最大值.这样的定义能够保证在缺失数据源近邻节点筛选过程中更多的节点被保留,并保证相似度值最大.也由此说明感知数据在时间、空间、属性这3方面的相似度相互互补,从而缓解在缺失数据分布较密集情况下近邻节点均为数据缺失导致无法给出填补值的情况.此外,对于相似性度量方法的选取并不局限于欧式距离,可根据具体应用选择合适的相似度度量方法.

3.2 缺失数据源近邻节点筛选

根据第3.1节介绍的多维度相关性模型,可求得每个缺失数据源与剩余数据源间的多维度相似度.由于缺失数据源的近邻节点将用于填补顺序的确定以及缺失值填补过程中,而相似度较低的节点对填补顺序及填补值的确定影响较小,为了降低相似图构建的计算量,首先对每缺失数据源的近邻节点进行筛选,筛选规则很简单,即,相似度小于给定多维度相似度阈值d_s的节点将被删除.

例3:仍以表 1中给定数据为例,根据第3.1节对多维度相似度计算的定义,可得到每个缺失数据源与剩余数据源的多维度相似性见表 2,假设d_s=0.8,则每个缺失数据源的近邻节点列表如图 3所示.

4 缺失数据填补顺序决策及缺失值填补

在缺失数据分布较为密集的情况下,缺失数据源的近邻节点也可能数据缺失,此时,利用已有的缺失数据填补方法会导致填补值的准确性降低,甚至无法对缺失值进行填补.基于此,本文将已填补的缺失值作为观测值用于后续填补过程,但填补值具有一定的不确定性,当前填补值的准确性将直接影响后续与其相关的填补值的精度,由此便引发填补顺序的问题.如引言中例2的介绍,不同的填补顺序会得到不同甚至差异很大的填补结果,因此,如何确定一个最优的填补顺序以提高填补值的准确性,成为一个具有挑战性并亟待解决的问题.本文首先将缺失数据源集合构建为一个相似图结构,进而在相似图基础上,将填补顺序决策问题转化为一个最优化问题并对其进行求解.

4.1 缺失数据源相似图构建

根据第3节对缺失数据源近邻节点筛选策略的介绍,可得到t时刻n个缺失数据源的近邻节点列表以及缺失数据源与各个近邻节点间的相似度,本节将根据这些数据信息构建以缺失数据源为中心的相似图.由于相似图的构建主要用于缺失数据源填补顺序的确定,因此,图的顶点只包含缺失数据源.顶点权重为该缺失数据源与其所有相对完整近邻节点间相似度融合后的结果.边表示两个缺失数据源互为近邻节点,边权重为二者的相似度.由此构建出能够直观反映缺失数据源间依赖关系的无向加权相似图,并且通过边权重反映两个缺失数据源间相似度的大小,通过顶点权重反映每个缺失数据源的所有相对完整近邻节点的分布情况,计算公式见公式(5).

${{w}_{{{s}_{i}}}}=1-\prod\limits_{{{s}_{k}}\in N({{s}_{i}})}{(1-Si{{m}_{ik}})}$

(5)

其中,N(s_i)表示缺失顶点s_i的相对完整近邻节点集合,Sim_ik为数据源s_i与s_k间的多维度相似性.根据公式(5)可知:缺失数据源s_i的相对完整近邻节点个数越多,且每个近邻节点与s_i的相似度越大,则s_i顶点的权重值越大.

例4:以例3中缺失数据源近邻点的计算结果为例进行相似图构建,得到的缺失数据源相似图如图 4(a)所示.

需要注意的是:t时刻,由n个缺失数据源构建出的相似图可能是一个包含所有节点的大图,也可能是多个互不连通的子图.例如:当例3中的多维度相似性阈值d_s=0.9时,缺失数据源相似图则由3个子图构成(如图 4(b)所示).在对缺失数据源进行填补顺序确定过程中,每个子图之间是相互独立的.

4.2 填补顺序决策

基于第4.1节构建的缺失数据源相似图,本节主要要解决的问题是对缺失数据源填补顺序的决策.根据第4.1节,相似图的顶点权重反映的是可用于填补该缺失数据源的相对完整近邻节点的个数以及近邻节点与之的相似度.权重值越大,表明其周围可用于填补的相对完整数据越多且相似度越高,进而反映了其缺失近邻节点在填补过程中的贡献量相对越小.而边权重反映的是两个缺失数据源间的相似度,该相似度越高,表明数据填补过程中两个数据源间的相互影响越大.

当给定一个填补顺序时,每对互为近邻节点(即由一条边相连)的两个缺失数据源的填补优先级即可被确定,进而相应的无向加权相似图即可转化为一个有向加权相似图.

例5:针对例4中的缺失数据源相似图 4(a),假设填补顺序为(44,46,47,49,48,45),则图 4(a)可转化为一个有向加权图,如图 5所示.

对于一个包含n个缺失数据源的可能的填补顺序seq,本文将其对应的有向加权相似图看作一个贝叶斯网络,顶点权重为贝叶斯网络中每个顶点的先验概率,边权重为两个顶点间的条件概率,该贝叶斯网络的联合概率为相应填补顺序的置信度,计算公式见公式(6).

$b(seq)=\prod\limits_{i=1}^{n}{p({{s}_{i}}|{{s}_{N(i)}})}$

(6)

其中,s_N(i)为可用于缺失数据源s_i填补的缺失近邻节点集合.当一个缺失数据源被填补后,可将其视为观测值并用于后续缺失值填补过程中.因此在填补顺序确定后,后填补的缺失数据源的近邻节点是动态变化的,顶点的权重也是动态更新的,p(s_i|s_N(i))为顶点s_i在可用于填补的近邻节点列表中加入s_N(i)后更新的顶点权重值.若s_N(i)为空,则p(s_i|s_N(i))可表示为p(s_i),即,缺失数据源s_i的初始顶点权重$p({{s}_{i}})={{w}_{{{s}_{i}}}};$若s_N(i)不为空,结合公式(5),可得p(s_i|s_N(i))见公式(7).

$p({{s}_{i}}|{{s}_{N(i)}})=1-(1-{{w}_{{{s}_{i}}}})\prod\limits_{{{s}_{j}}\in N(i)}{(1-Si{{m}_{ij}})}$

(7)

引理1. 对于缺失数据源s_i,p(s_i|s_N(i))越大,填补误差越小.

证明:目前已有的基于统计学的缺失值填补算法均遵循一个共同的填补思想:通过与缺失数据源较为相似的完整数据源对其进行填补,并认为完整数据源的个数越多且与缺失源间的相似度越高,则填补精度越高.本引理将基于此基本填补思想给出证明.

根据p(s_i|s_N(i))的定义可知:s_N(i)为空时,$p({{s}_{i}}|{{s}_{N(i)}})=p({{s}_{i}})={{w}_{{{s}_{i}}}}$.结合公式(5)可知:${{w}_{{{s}_{i}}}}$反映的是缺失数据源的完整近邻节点分布,完整近邻节点与缺失节点间的相似度越高且完整近邻节点个数越多,公式(5)的后半部分越小,即p(s_i|s_N(i))越大,则根据缺失值的基本填补思想,其填补误差越小.s_N(i)不为空时,根据公式(7)可知:可用于缺失值填补的填补近邻节点个数越多且二者间的相似度越大,$\prod\limits_{{{s}_{j}}\in N(i)}{(1-Si{{m}_{ij}})}$越小,相应的p(s_i|s_N(i))越大,则填补误差越小.

综上,引理1得证. □

定理1. 给定一个填补顺序,其置信度越高,填补误差越小.

证明:对于一个给定的填补顺序,根据公式(6)的定义可知:p(s_i|s_N(i))越大,该填补顺序对应的置信度越高.再结合引理1,不难得出定理1的结论. □

例5:基于构建好的相似图,可通过枚举计算每个可能填补顺序的置信度,表 3显示的是与例4中图 4(a)相似图对应的部分填补顺序及置信度以及填补误差.

从表中可见:不同填补顺序的置信度是不同的,填补误差也不同,置信度越高的填补顺序,填补误差越小.

基于以上介绍,最优填补顺序决策问题即转化为置信度最高的贝叶斯网络选取问题.设n个缺失数据源所有可能的填补顺序集合为SEQ={seq₁,seq₂,seq₃,…,},填补顺序seq_i的置信度为b(seq_i),则填补顺序决策问题即转化为求SEQ中置信度最大的序列:

$se{{q}^{*}}=arg\text{max}\left( b\left( se{{q}_{i}} \right) \right),se{{q}_{i}}\in SEQ.$

对于上述问题,可通过枚举所有可能的填补顺序,选取置信度最大的序列作为最优填补顺序得到最优解,见算法1.

算法1. 填补顺序决策精确算法.

输入:缺失数据源相似图集合G={G₁,G₂,…};

输出:缺失数据源最优填补顺序seq.

1. foreach similarity graph G_i∈G

2. all possible imputation sequences SEQ_i is

3. SEQ_i=Enumerate(G_i)={seq₁,seq₂,…}

4. foreach imputation sequence seq_j∈SEQ_i

5. calculate its confidence b(seqj) according to Eq.(6)

6. end

7. select the best imputation sequence $seq_{i}^{*}$whose confidence is the maximum,and then $se{{q}^{*}}=seq_{1}^{*}\cup seq_{2}^{*}\cup ...$

8. end

9. return seq^*

根据算法1可知,最优填补顺序精确解法的时间复杂度为指数级O(n!),n为一个相似图中缺失数据源的个数.当n较小时,可通过枚举法得到精确的最优填补顺序;但当数据量较大且缺失数据分布较为密集(即n较大)时,算法的复杂度将呈指数级增长,精确求解问题也随之成为NP难问题.为了降低算法的时间复杂度,本文利用启发式算法对其进行近似求解.算法的基本思想是:对于两个具有依赖关系的缺失数据源来说,先填补顶点标签值较高的缺失数据源得到的最终填补结果相对较为准确.这是因为顶点标签值越高,表明该缺失数据源的近邻完整数据源与之的相似度越高,也就意味着填补值相对来说更加准确.基于此,本文采用启发式算法对最优填补顺序进行决策,主要包含3个步骤.

1) 对每个相似图中的顶点标签值进行排序,选择顶点标签值最高的节点作为优先填补对象;

2) 对与该缺失数据源有边相连的顶点标签值进行更新,因为该缺失数据源填补完成后即作为完整数据用于后续填补过程,也就是说,该已完成填补的缺失数据源对于与之相连的缺失数据源来说是完整数据元组;

3) 重复步骤1)进行下一次最优填补对象选取.

具体算法见算法2.根据算法2可知:在基于启发式算法的填补顺序决策过程中,每次最优填补对象选取的时间复杂度为O(n),重复n次的时间复杂度为O(nlogn),因为每完成一次最优填补对象的选取,下一次选取过程中的可选择对象范围即减1.

算法2. 填补顺序决策启发式算法.

输入:缺失数据源相似图集合G={G₁,G₂,…};

输出:缺失数据源最优填补顺序seq.

1. foreach similarity graph G_i∈G

2. the vertexes contained in G_i is V={v₁,v₂,…}

3. while (V!=null)

4. Current loop max vertex confidence ${{c}_{{{v}^{*}}}}=0$

5. foreach vertex v_j∈V

6. If (${{c}_{{{v}_{j}}}}>{{c}_{{{v}^{*}}}}$),then

7. ${{c}_{{{v}^{*}}}}={{c}_{{{v}_{j}}}},{{v}^{*}}={{v}_{j}}$

8. $seq_{i}^{*}\leftarrow \{{{v}^{*}}\}$

9. Delete v from V

10. end

11. $se{{q}^{*}}\leftarrow \{seq_{i}^{*}\}$

12. end

13. return seq^*

此外,根据本节对填补顺序决策的详细介绍可知:当缺失数据源构建的相似图包含多个互不连通的子图时,各个子图之间是相互独立的,没有填补顺序上的依赖关系.即:只需对每个子图确定最优填补顺序,进而将所有填补顺序进行随机组合即可.因此,最优填补顺序是不唯一的.

4.3 缺失数据填补

当缺失数据源填补顺序确定后,即可对缺失数据依次进行填补.由于OMSMVIF填补框架的核心思想是利用感知数据的多维度相关性对缺失值近邻节点进行查找,进而对缺失数据进行填补,因此在本质上,利用了数据在时间、空间、属性一方面或几方面相似性的填补方法均适用于本框架,如KNN填补、回归填补以及基于这两种填补的改进方法.在基于KNN的填补方法中,需为每个缺失数据源选取K个近邻节点用于缺失值的填补,但由于每个缺失数据源的近邻节点分布不均匀,K值的确定比较困难:K值过小,会导致由于填补结果对噪音敏感引起的填补精度下降;K值过大,会导致近邻节点集合包含大量与待填补点相似度很低的节点,造成填补精度的下降及计算量的增加.基于回归的填补方法需通过对历史数据进行学习构建回归模型,填补结果对学习得到的参数依赖较大,且复杂度更高.基于此,本文对KNN填补进行改进,提出一种新的近邻填补方法NI (neighbor-based imputation).该方法不限定K值大小,而是基于第4.1节构建的缺失数据源相似图,利用与待填补数据源相似度高于给定阈值的所有近邻节点进行填补.其优点是针对每个待填补数据,考虑其近邻节点的分布情况,找出适用于填补的近邻节点,而非针对所有待填补数据源找出固定的K个近邻节点.对于待填补数据源S_i,设其近邻节点集合为$N{{S}_{i}}=\{{{S}_{1}},{{S}_{2}},...,{{S}_{|N{{S}_{i}}|}}\}$,则S_i的填补值${{\hat{d}}_{i}}$见公式(8).

${{\hat{d}}_{i}}=\frac{\sum\limits_{{{S}_{j}}\in N{{S}_{i}}}{Si{{m}_{ij}}\cdot {{d}_{j}}}}{\sum\limits_{{{S}_{j}}\in N{{S}_{i}}}{Si{{m}_{ij}}}}$

(8)

此外,与已有KNN填补或回归填补算法不同的是,NI填补算法中对缺失数据源近邻的查找是依据感知数据的多维度相似性,而非某一维相似性,因此,用于缺失数据源填补的近邻节点更加全面,也能够进一步提高填补值的准确性.

5 实验

本节将通过大量实验对算法的准确性和高效性进行了验证.采用两个真实数据集:SENSOR和WEATHER,SENSOR(http://db.lcs.mit.edu/labdata/labdata.html)数据集是由部署在Intel Berkeley实验室的54个Mica2传感器节点在36天内对室内温度、湿度、光强和节点电压每隔30s进行一次采集得到的连续型数据.WEATHER数据集是由AccuWeather(http://www.accuweather.com/zh/us/united-states-weather)网站提供的美国30个城市在一周内的天气数据,包含的监测属性有温度、湿度、气压、风速等.针对以上两个数据集,本文选取温度和湿度两个属性,并且按小时对数据进行聚合后用于本文的实验.此外,本文在WEATHER数据基础上生成了一组模拟数据集用于后文第5.4节对算法执行时间的验证.对于缺失值的选取,本文在温度属性上随机删除部分观测值,进而将其看作缺失值用于填补.此外,缺失率的计算以元组为单位,即:对于一条数据元组,若其在温度属性上的观测值为缺失的,则称该元组为缺失数据元组.数据缺失率即为缺失数据元组条数占总元组数的比例.本文利用 平均相对误差来度量填补值的准确性,假设有n个缺失值,第i个缺失值的填补值为${{\hat{d}}_{i}}$,真值为d_i,则平均相对误差avg_relerr为

$avg\_relerr=\frac{1}{n}\sum\limits_{i=1}^{n}{\left| \frac{{{{\hat{d}}}_{i}}-{{d}_{i}}}{{{d}_{i}}} \right|}$

本文采用KNN与多元线性回归(linear regression)^[21]作为基本的缺失值填补算法,与本文提出的近邻填补(NI)算法进行对比.依据近似度计算中考虑到的空间或时间或属性等3方面的相关性,分别利用MKNN,SKNN,TKNN,AKNN表示考虑多维度相关性、只考虑空间相关性、只考虑时间相关性、只考虑属性相关性的KNN填补算法.同理,利用MLR,SLR,TLR,ALR和MNI,SNI,TNI,ANI来分别表示考虑多维度相关性和只考虑空间、时间、属性上某一维相关性的回归填补和近邻填补算法.另一方面,基于是否考虑填补顺序,可将填补算法分为顺序(sequential)填补和随机(random)填补两大类,在具体填补算法前加S表示顺序填补,加R表示随机填补,如SMKNN表示基于多模态相关性的顺序KNN填补算法,RMKNN表示基于多模态相关性的随机KNN填补算法.

本文在Inter(R) Core(TM) i7-2600 CPU @3.4GHz,8.00GB内存和64位Windows 7操作系统运行环境下,利用Java语言进行实验验证.实验过程中,设定时间邻域长度s=10,空间近邻距离阈值d_d=50,近邻节点筛选过程中多模态相似度阈值d_s=0.9.基于KNN填补算法中,K值取5.这些参数的设定不是固定的,可根据具体的数据集和应用背景由用户给定.

5.1 单维度和多维度相关性对填补准确性的影响

根据第3节的介绍可知:本文利用感知数据的多维度相关性对缺失数据源近邻节点进行筛选,进而利用近邻节点对缺失值进行填补.图 6和图 7给出了利用多维度相关性和单维度相关性进行缺失值填补时的准确性对比.图 6(a)和图 7(a)是基于KNN,NI,LR的随机填补算法,图 6(b)和图 7(b)是基于KNN,NI,LR的顺序填补算法.

从图中可以看出,利用多维度相关性的缺失值填补准确性普遍高于利用单维度相关性的缺失值填补准确性.这是由于在缺失数据较为密集的情况下,利用单维度相关性得到的缺失数据源的近邻节点较少,或在限定近邻点个数(KNN中K值)情况下得到的近邻节点与缺失数据源本身的相似度不高,从而导致填补准确性下降.并且从图中可以看出,随着数据缺失率的增加,填补值的平均相对误差相应增大.这是由于随着数据缺失率的增加,可用于填补的完整数据相对减少,即使在顺序填补过程中将已填补值作为观测值用于后续填补,但在实际应用中填补值本身也存在一定误差,填补精度也会相应降低.从图 6和图 7可以看出,SENSOR数据集的平均相对误差较小.这是由于SENSOR数据集由54个sensor对一个房间的温度、湿度进行测量,每个sensor的观测值相差都不大,其感知数据的单维度相关性也更强,因此得到的填补结果更为准确.对比之下,WEATHER数据是美国30个不同城市的温度和湿度气象数据,由于各个城市间距离相对较远,且各个城市的感知数据在时间和属性上的波动相对较大,因此即使根据多维度相关性得到的填补值,平均相对误差较大.

5.2 单维度和多维度相关性对填补准确性的影响

本节通过图 8和图 9给出了在两个数据集上,基于KNN,NI,LR这3种填补算法,利用多维度相关性进行顺序填补和随机填补时得到的填补结果准确性的对比.

从图中可以看出,顺序填补的准确性高于随机填补.这是由于顺序填补考虑了每个缺失数据源近邻的分布,先填补近邻中完整数据相对较多且近似度较高的缺失数据源,由此得到的填补值能更好地为后续缺失值填补所用,得到的填补值准确性也更高.极端情况下,对于近邻节点均为数据缺失的待填补数据源来说,无法利用相关性对其进行填补,只能根据待填补维度的数值变化区间进行随机填补,由此得到的填补值的准确性无疑是很低的.

5.3 各填补算法间的准确性对比

本文在该节给出了基于近邻(NI)的填补算法与基于KNN(K=5)和多元线性回归(LR)填补算法的准确性比较结果.从图 10中可以看出,本文提出的NI算法准确性最高.这是由于KNN填补算法中固定的K值无法满足所有缺失数据源的具体情况.对于近邻节点较多的缺失数据源来说,K值过小会导致由于没有充分利用与待填补数据源相似度较高的近邻节点而引起填补值精度下降;对于近邻节点较少的缺失数据源来说,K值过大会导致在缺失值估计过程中由于利用了与待填补数据源相似度过低的近邻节点而影响填补精度.因此,固定的K值很难同时满足所有缺失数据源的需求.在利用多元线性回归对缺失值进行估计的过程中包含矩阵求逆的运算,而当缺失数据源周围的近邻节点较多时,根据近邻节点及历史数据组成的求逆矩阵很容易是奇异矩阵,因而导致回归模型建立失败.因此,基于LR的填补算法在3种填补算法中准确性最低.

5.4 各填补算法的执行时间

最后,本文给出了基于顺序的3种填补算法的执行时间随着数据量以及数据缺失率增长的变化情况.图 11给出的是3种算法的执行时间随数据量的变化,其中,纵坐标为对数刻度,数据缺失率设定为50%.从图中可以看出,算法的执行时间随着数据量的增加呈线性增长.这是由于随着数据量的成倍增加,缺失数据源的个数也成倍增加.图 12给出的是随着数据缺失率的增加,3种基于顺序的填补算法的执行时间,其数据量设定为10K.从图中可以看出:随着数据缺失率的增加,3种缺失值填补算法的执行时间也随着增加,并且基于回归的填补算法执行时间最长,基于NI的填补算法执行时间最短.这是由于基于回归的填补算法需根据历史数据对线性填补模型的参数进行学习,而NI填补算法只需根据相似度阈值对近邻节点进行筛选.此外,通过图 11和图 12的实验结果可以看出:当数据量较大时,算法的执行时间较长.例如:当数据缺失率为50%、数据量为10M(43万条数据)的情况下,其执行时间大约需要10min.因此,在对感知数据流进行实时填补过程中,如何设计有效的增量填补算法以提高执行效率,是一个很有挑战的问题,我们将在未来的工作中对其进行研究.