一、缺失值处理

1. 数据缺失值的产生的原因多种多样，主要分为客观原因和人为原因。

   • 客观原因：比如数据存储的失败、存储器损坏、机械故障导致某段时间数据未能收集（对于定时数据采集而言）。
   • 人为原因：由于人的主观失误（如：数据录入人员失误漏录了数据）、历史局限（如：数据在早期尚无记录）、有意隐瞒数据（如：在市场调查中被访人拒绝透露相关问题的答案，或者回答的问题是无效的）导致数据未能收集。

2. 缺失值的处理有三种方法：

   • 直接使用含有缺失值的数据。

     某些算法可以直接使用含有缺失值的情况，如决策树算法可以直接使用含有缺失值的数据。

     • 优点：直接使用原始数据，排除了人工处理缺失值带来的信息损失。
     • 缺点：只有少量的算法支持这种方式。

   • 删除含有缺失值的数据。

     最简单的办法就是删除含有缺失值的样本。

     • 优点：简单、高效。

     • 缺点：如果样本中的缺失值较少，则直接丢弃样本会损失大量的有效信息。这是对信息的极大浪费。

       如果样本中包含大量的缺失值，只有少量的有效值，则该方法可以接受。

   • 缺失值补全。

     用最可能的值来插补缺失值。这也是在实际工程中应用最广泛的技术。

     • 优点：保留了原始数据
     • 缺点：计算复杂，而且当插补的值估计不准确时，会对后续的模型引入额外的误差。

3. 缺失值补全常见有以下方法：

   • 均值插补
   • 同类均值插补
   • 建模预测
   • 高维映射
   • 多重插补
   • 压缩感知及矩阵补全

1.1 均值插补 && 同类均值插补

1. 均值插补：

   • 如果样本的属性是连续值，则该属性的缺失值就以该属性有效值的平均值来插补。
   • 如果样本的属性是离散值，则该属性的缺失值就以该属性有效值的众数（出现频率最高的值）来插补。

2. 均值插补在含有缺失值的属性上的所有缺失值都填补为同一个值。

   而同类均值插补首先将样本进行分类，然后以该类中的样本的均值来插补缺失值。

1.2 建模预测

1. 建模预测的思想是：将缺失的属性作为预测目标，通过建立模型来预测。

2. 给定数据集 。

   假设属性 含有缺失值，根据 是否缺失，将数据集划分为：

   • ：属性 有效的样本的集合。
   • ：属性 缺失的样本的集合。

   将 中的样本作为新的训练集，标签值重新定义为属性 的值，通过建模来完成属性 的学习。将 中的样本作为测试集，通过学得的模型来预测其属性 的值。

3. 这种方法的效果相对较好，但是该方法有个根本缺陷：

   • 如果其他属性和属性 无关，则预测的结果无意义。
   • 如果预测结果相当准确，则又说明属性 可以由其它属性计算得到， 于是属性 信息冗余，没有必要纳入数据集中。

   一般的情况是介于两者之间。

1.3 高维映射

1. 高维映射的思想是：将属性映射到高维空间。

2. 给定数据集 ，假设属性 的取值为离散值 一共 个值，则将该属性扩展为 个属性 ，其中：

   • 若样本在属性 上的取值为 ，则样本在新的属性 上的取值为 1，在新的属性 上的取值为 0 。
   • 若样本在属性 上缺失，则样本的新的属性 上的取值为 1,在新的属性 上取值为 0 。

3. 对于连续特征，高维映射无法直接处理。可以在连续特征离散化之后，再进行高维映射。

4. 高维映射是最精确的做法，它完全保留了所有的信息，也未增加任何额外的信息。比如广告的CTR预估模型，预处理时会把所有变量都这样处理，达到几亿维。

   • 优点：完整保留了原始数据的全部信息。
   • 缺点：计算量大大提升。而且只有在样本量非常大的时候效果才好，否则会因为过于稀疏，效果很差。

1.4 多重插补

1. 多重插补（Multiple Imputation:MI）认为待插补的值是随机的，它的值来自于已观测到的值。

   具体实践上通常是估计出待插补的值，然后再加上不同的噪声，形成多组可选插补值。然后根据某种选择依据，选取最合适的插补值。

2. 多重插补法的步骤：

   • 通过变量之间的关系对缺失数据进行预测，利用蒙特卡洛方法生成多个完整的数据集。
   • 在每个完整的数据集上进行训练，得到训练后的模型以及评价函数值。
   • 对来自各个完整的数据集的结果，根据评价函数值进行选择，选择评价函数值最大的模型，其对应的插值就是最终的插补值。

1.5 压缩感知 && 矩阵补全

1. 在现实任务中，经常希望根据部分信息来恢复全部信息。压缩感知和矩阵补全就是用于完成这个任务。

2. 假定有长度为 的离散信号 。 根据奈奎斯特采样定理，当采样频率达到 最高频率的两倍时，采样后的信号就保留了原信号的全部信息。

   假定以远小于奈奎斯特采样定理要求的采样频率进行采样，得到了长度为 的采样后信号 ， 其中 。 则有： 。

   其中 是对信号 的测量矩阵，它确定了以什么样的频率采样以及如何将采样样本组成采样后的信号。

3. 通常在已知离散信号 和测量矩阵 时要得到测量值 很容易。但是如果给定测量值 和测量矩阵 ， 要还原出原始信号 比较困难。这是由于当 时， 是一个欠定方程，无法简单的求出数值解。

   假设存在某种线性变换 ， 使得 ，其中 也和 一样是 维列向量，则有 。令 ，则 。

4. 如果能够从 中恢复 ，则能够通过 从 中恢复出 。

   从数学意义上来看，这种做法没有解决任何问题。因为根据 ， 从 中恢复 这个问题仍然是欠定的。

   但是在实际应用中发现，如果 具有稀疏性（即大量的分量为零），则该问题能够很好地求解。这是因为稀疏性使得未知因素的影响大大减少。

   此时 称作稀疏基，而 的作用类似于字典，能够将信号转换为稀疏表示。

1.5.1 压缩感知

1. 与特征选择、稀疏表示不同，压缩感知侧重的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。

2. 压缩感知分为感知测量和重构恢复两个阶段。

   • 感知测量：关注如何对原始信号进行处理以获得稀疏样本表示。常用的手段是傅里叶变换、小波变换、字典学习、稀疏编码等
   • 重构恢复：关注的是如何基于稀疏性从少量观测中恢复原信号。

3. 限定等距性Restricted Isometry Property:RIP：对于大小为 的矩阵 ，若存在常数 ，使得对于任意向量 和 的所有子矩阵 ，都有：

   

   则称 满足 限定等距性 k-RIP。

   此时通过下面的最优化问题可以近乎完美的从 中恢复出稀疏信号 ，进而恢复出 ：

   

   这里 范数表示向量中非零元素的个数。

4. 该最优化问题涉及 范数最小化，这是个 NP难问题。但是 范数最小化在一定条件下与 范数最小化问题共解，于是实际上只需要求解最小化问题：

   

   可以将该问题转化为LASSO等价形式，然后通过近端梯度下降法来求解。

1.5.2 矩阵补全

1. 矩阵补全matrix completion解决的问题是：

   

   其中

   

   • 为观测矩阵，其中有很多缺失值。
   • 为 中所有的有数值的下标的集合。
   • 为需要恢复的稀疏信号， 为矩阵 的秩。

   该最优化问题也是一个 NP 难问题。

2. 考虑到 在集合 上的凸包是 的核范数nuclear norm：

   

   其中 表示 的奇异值。于是可以通过最小化矩阵核范数来近似求解：

   

   该最优化问题是一个凸优化问题，可以通过半正定规划Semi-Definite Programming:SDP求解。

3. 理论研究表明：若 的秩为 ，则只需要观察 个元素就能够完美恢复出 。