imputing structured missing values in spatial data with clsutered adversarial matrix factorization

一种基于对抗模型用于补全带有结构性缺失信息的空间数据的矩阵分解技术

摘要:在数据分析时,缺失的数据总是会成为一个重大的挑战,因为它带来了不确定性。在许多领域中,矩阵补全技术有着出色的表现。然而,在特定的空间数据集如地理坐标点时,这种传统的矩阵补全技术有着两个主要的限制:第一,这些方法往往假设缺失的数据是随机产生的,而这种假设对于空间数据集可能并不总是成立;第二,它们可能无法运用这些空间数据集中的结构信息。为了解决这些局限性,本论文提出了一种利用先验结构信息和生成对抗模型的矩阵分解技术。这个模型使用一个对抗网络通过学习数据集的概率分布来改善补全的结果。 关键词:缺失数据估计;深度对抗网络;空间数据

前言

  很多现实生活中的应用容易面临数据缺失的问题。而对于空间数据集,造成这种情况的原因有很多种。例如,在森林监测中,因为收集成本的原因,数据的缺失很普遍。【3】过去十年许多针对数据补全的工作在开展,从基本的统计方法到复杂的模型使用。后者的典例低秩矩阵补全技术为许多领域如推荐系统或图像重构带来了可观的改善【9】。这些方法通过发现并利用数据矩阵的低秩属性来建立已有值与缺失值的联系。而在这些矩阵补全方法里,矩阵分解是最为常用的方法之一,它将输入的数据矩阵分解成两个低秩矩阵的乘积,称为“特征因子”,接着通过最小化这个乘积与已有值的误差来学习这两个特征因子,随后利用它们来补全缺失的信息。【18】其它方法还有如带门槛的矩阵奇异值分解,核心思想是迭代地使用截断奇异值分解来补全。

  这些矩阵补全的方法,往往假设缺失的数据是随机产生的。【2】然而,这个假设在空间数据上可能并不成立,因为它往往带有空间结构。例如,一项针对加拿大青少年的研究指出,家庭收入这一栏数据空缺的青少年有更低的可能性居住在富人区。【15】因此,当数据并不是随机缺失时,只是单纯地最小化两个特征因子的乘积与已有值的误差并不能保证补全数据的有效性。

  而另一个限制则是这些方法无法把数据集里的结构信息利用起来。而在补全缺失的空间数据时,这些结构信息格外重要。【12】例如,淡水湖数据就有强烈的空间结构,因为相邻的湖泊往往有相似的降水量等。【17】如果这些结构信息能够被一个矩阵补全的方法利用起来,它可以显著地提升结果,因为这些结构信息代表了一个子空间,在这个子空间里,不同湖泊之间相似的信息互相传递。

  因为为了解决这两点局限,我们提出了一种利用先验结构信息和生成对抗模型的矩阵分解技术。这个框架找到一个低维的子空间来与数据中的结构信息相符合,因此可以利用同一类中其它数据点的信息来补全某一点的缺失值。而且,估计值的概率分布也尽可能的与已有值相似,这么做的好处是它把缺失值与已有值连接起来了。如果估计值与实际值偏差太大,那么它出现的概率应该很小。然而,实际数据的概率分布往往是未知的,因此我们借鉴了生成对抗网络的思想引入了一个判别器来区分估计值与已有值。我们在合成数据集与显示数据集上均做了实验,来说明这个框架的有效性。

相关工作

  截断奇异值算法是近年来使用频率较高的一个方法,它在数据矩阵中迭代的使用截断奇异值分解接着通过保持一个较小的奇异值重构整个矩阵。矩阵分解是另一项常用的技术,关于它的过程前面部分已有讲述。

  生成对抗网络(GAN)被广泛地用于生成图像【5】【16】。在【8】【14】中,作者提出了一个想法,利用GAN的思想和整幅图片的结构来推测一幅图片中随机缺失的像素。虽然这个想法在这类问题上效果较好,但它补全图片时是将每张图片看成一个个独立的个体,而空间数据与此相反,它们之间有着强烈的依赖性。

方法

A.矩阵分解引入

  矩阵分解在推荐系统中十分常用,例如如下的一个评分矩阵,列为用户,行为物品,矩阵中的值为用户对物品的评分,如电影和书籍。现实情况中这个评分矩阵往往很稀疏,许多物品上缺少用户的评分,而推荐系统就是要预估用户在某个物品上的评分来判断用户对它的倾向程度,从而进行推荐。

  矩阵分解的方法是将原始评分矩阵$R^{m\times n}$分解成两个矩阵$P^{m\times k}$和$Q^{k\times n}$,根据评分矩阵中已有的值来判断分解是否准确,而判别标准常用均方差。如图所示。

  分解后的矩阵P和Q可以称为特征因子(latent factor),其中要求分解后$k<<min(m,n)$,即低秩要求,因为如果输入矩阵满秩,则各元素行之间线性无关,如果有线性相关关系,则某个元素行可以通过其他行的线性组合表示,相当于引入了冗余的信息,这样就可以将矩阵投影到更低维的空间,只保留非冗余信息,同时冗余信息可以用来对缺失值进行补全。

  矩阵分解的直观意义为,找出矩阵中的潜在特征,如图2中假设特征为3,特征可以是书籍作者、类型等等,而矩阵P表示用户对某个特征的喜爱程度,而矩阵Q表示某个物品与该特征的关联程度。

B.低秩补全

  给定一个带有缺失值的矩阵,矩阵补全技术旨在通过已有值的某种潜在的结构来对缺失值进行估计补全。一个常用的潜在结构是矩阵的低秩性,因为它可以将该矩阵投影到一个去除冗余信息的子空间中,低秩意味着矩阵中的值存在线性关系,因此某些值可以通过另外的值来线性表示,如同坐标系中的基底一样。在这类方法中有凸也有非凸的技术。凸方法通过对矩阵迹的约束来保证具有良好理论性的全局最优结果,而诸如矩阵分解的非凸方法进行局部搜索过程并提供更大的灵活性和效率。给定一个矩阵$X\in R^{d\times n}$,n代表样本个数,d代表特征维度,矩阵分解技术通过将X分解为两个矩阵U和V,$U\in R^{d\times n}$,$V\in R^{r\times n}$要求$r < min(d, n)$;U和V的求解可以通过对下列式子运用块坐标下降法求得:

  $\bigodot$代表哈德蒙德内积(即矩阵各元素相乘),M矩阵的大小同X一致,如果$X_{ij}$有值则$M_{ij}$为1,否则为0。局部解用$U^、V^$表示,因此,它们可以通过如下的式子来重构矩阵X:

  矩阵分解在推荐系统中使用较为普遍,它用来估计一个用户在某项新物品上的评分。

  将此方法应用于空间数据集时,矩阵分解不会包含有关数据集中空间聚类结构的先验知识信息。 然而,这些先验知识通常有助于发现需要的子空间。此外,对于结构化缺失值问题,经典矩阵补全提供较差的结果,因为缺失值不是随机的。

C.聚类对抗式矩阵分解

  为了解决上一小节中提到的矩阵分解的两个局限性,我们提出了一种新的聚类对抗矩阵分解框架。 在我们的框架中,我们找到整个样本的聚类信息,并将补全值的概率分布与已有值的分布靠近,以得到可靠的补全结果。X为输入矩阵,每一列代表一个数据样本,有些数据点有完整的特征信息,而某些数据点以结构性缺失了某些特征信息。我们将输入矩阵中完整部分记为$X_n$,而缺失部分记为$X_m$。我们假设每个数据点都符合某个概率分布$p_{data(x)}$。接下来的公式中包含两个部分:矩阵重构以及概率分布近似。

矩阵重构

  为了利用数据的低秩属性和空间聚类结构,我们决定在矩阵分解中使用l2聚类项:

  式中$v_i$代表矩阵V中第i列,$r_1,r_2,r_3$均为正则化参数,第二项和第三项加的约束是为了防止过拟合,最后一项则用来引入空间数据集中的聚类结构信息。$d_{ij}$是第i个样本和第j个样本的相似度,它可以手动设置,原则为:当$v_i$和$v_j$很靠近即在同一类时,将$d_{ij}$的值设置得较大,反之较小。$r_3$用来调整结构信息在重构时所占的比重,如果$r_3$较大,则对一个样本的缺失数据进行估计补全时会更多的参考同一类其它数据点的信息。因此当$r_3$为0时,结构信息将不被使用,这也使得这个式子变成了常规的矩阵分解方法。而对于UV矩阵直观的理解为,U为特征因子,而V为样本因子,如同推荐系统里的用户因子和物品因子,两者相互独立。

生成对抗网络思想(GAN)

  在继续讲到使用概率分布近似来优化前,先引入生成对抗网络的基本思想加深理解。GAN的非常的直观,就是生成器和判别器两个极大极小的博弈。

GAN的目标函数为:

  从判别器D的角度看,它希望自己能尽可能区分真实样本和虚假样本,因此希望 D(x)尽可能大,D(G(z))尽可能小,即 V(D,G)尽可能大。从生成器G的角度看,它希望自己尽可能骗过D,也就是希望 D(G(z))尽可能大,即 V(D,G)V(D,G) 尽可能小。两个模型相对抗,最后达到全局最优。

  图中,黑色曲线是真实样本的概率分布函数,绿色曲线是虚假样本的概率分布函数,蓝色曲线是判别器D的输出,它的值越大表示这个样本越有可能是真实样本。最下方的平行线是噪声z,它映射到了x。

  一开始, 虽然 G(z)和x是在同一个特征空间里的,但它们分布的差异很大,这时,虽然鉴别真实样本和虚假样本的模型 D性能也不强,但它很容易就能把两者区分开来,而随着训练的推进,虚假样本的分布逐渐与真实样本重合,D虽然也在不断更新,但也已经力不从心了。

  最后,黑线和绿线最后几乎重合,模型达到了最优状态,这时 判别器的输出对于任意样本都是 0.5。

GAN的最优化

  在建立好理论框架后,需要对所需要的生成器G和判别器D进行优化,在此之前先引入交叉熵的概念:它一般用来求目标与预测值之间的差距。

  在信息论与编码中,熵可以用来衡量信息量的多少,而如果我们对于同一个随机变量 x 有两个单独的概率分布 P(x) 和 Q(x),我们可以使用 KL 散度来衡量这两个分布的差异,计算式如下:

  在机器学习中,P往往用来表示样本的真实分布,比如[1,0,0]表示当前样本属于第一类。Q用来表示模型所预测的分布,比如[0.7,0.2,0.1],直观的理解就是如果用P来描述样本,那么就非常完美。而用Q来描述样本,虽然可以大致描述,但并不是那么的完美,信息量不足,需要额外的一些“信息增量”才能达到和P一样完美的描述。如果我们的Q通过反复训练,也能完美的描述样本,那么就不再需要额外的“信息增量”,此时Q就等价于P。

而对KL散度的计算式进行变形,可以得到:

等式的前一项即为P的熵,而后一项就是交叉熵的计算式:

  在机器学习中,我们需要评估labels和predictions之间的差距,可以使用KL散度,即$D_{KL}(y\mid\mid\hat{y})$,由于KL散度中的前一部分−H(y)即P的熵不变,故在优化过程中,只需要关注交叉熵就可以了。所以一般在机器学习中直接用用交叉熵做损失函数,评估模型。

  在引入交叉熵后,就可以定义最优化表达式。首先我们需要定义一个判别器 D以判别样本是不是从$p_{data(x)}$分布中取出来的,因此有:

  其中E代表取期望。这一项是根据「正类」(即辨别出 x 属于真实数据data)的对数损失函数而构建的。最大化这一项相当于令判别器 D在 x 服从于 data 的概率密度时能准确地预测 D(x)=1,即:

另外一项是企图欺骗判别器的生成器 G。该项根据「负类」的对数损失函数而构建,即

因此目标函数为:

它的含义是,对于D而言要尽量使公式最大化(识别能力强),而对于G又想使它最小(生成的数据接近实际数据)。整个训练是一个迭代过程。极小极大化博弈可以分开理解,即在给定G的情况下先最大化$V(D,G)$而来得到D,然后固定D,并最小化$V(D,G)$而得到G。其中,给定 G,最大化$V(D,G)$评估了$P_g$和$P_{data}$之间的差异或距离。

概率分布近似

  接下来,论文中就使用生成对抗网络中的对抗策略来使得推算样本具有与完整数据类似的概率分布。为了实现这一目标,我们使用鉴别器来区分推算和完整样本之间的分布差异:

  其中$p_r(x_r)$代表估计值的概率分布,它将从补全的矩阵Xr中得到;$x_r$代表从$p_r(x_r)$中选取的一个数据点;D为一个鉴别器,我们通过一个以SOFTMAX为输出层的全连接的深度神经网络来实现。D将输出一个概率值,判断输入的数据为已有值还是估计值。我们使用了负交叉熵作为损失函数,通过最大化$l_d$得到一个鉴别器D,能够有效地区分已有值与估计值

完整公式

将前节提到的两个部分进行合并,我们得到了如下的公式:

  其中λ是用来平衡矩阵重构与概率分布近似所占比例的一个参数,因此最小化该式时,不仅使得重构的矩阵与已有值所构成的矩阵的误差尽可能得小,同时通过鉴别器使得这两者的概率分布尽可能相似。这个同时最大最小化的要求就像是进行一场对抗。一方面,鉴别器尽可能地区别重构样本与已有样本的概率分布,而另一方面,重构矩阵又尽可能地逼近已有值的概率分布,以骗过鉴别器。因此当算法收敛时,重构矩阵的概率分布将会近似于已有值,训练出一个有效的鉴别器,同时重构矩阵的值也足够接近实际值以至于可以骗过这个鉴别器。在最小化部分中,我们求解出使得误差最小的矩阵U和V,接着使用它们来进行缺失值的计算。同时,这个部分也尽可能地让估计值去骗过鉴别器。而在最大化部分中,鉴别器通过区分已有值与最小化部分所得的估计值来进行更新,整个框架的流程如图所示。

最优化

然而在实际情况中,输入样本的概率分布往往是未知的,因此,我们使用如下式子来进行近似:在每次的更新迭代中,我们随机从Xn与Xr选取k个样本,来计算概率分布:


  其中r1与rk分别代表从Xn中选取的k个样本中的第一个和最后一个,q1和qk从Xr中选取的k个样本中的第一个和最后一个,$X^i_n$和$X^i_r$分别代表从Xn与Xr中所选取的第i个样本。因此,上面的合成式将变成:

算法流程如下所示:

实验