↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』原创

作者：华校专

作者信息：

华校专，曾任阿里巴巴资深算法工程师、智易科技首席算法研究员，现任腾讯高级研究员，《Python 大战机器学习》的作者。

编者按：

算法工程师必备系列更新啦！继上次推出了算法工程师必备的数学基础后，小编继续整理了必要的机器学习知识，全部以干货的内容呈现，哪里不会学哪里，老板再也不用担心你的基础问题!

数据预处理

在获取的数据中经常会遇到唯一属性，这些属性通常是人为添加的一些id属性，如存放在数据库中的自增的主键。
对于这些属性，它并不能刻画样本自身的分布规律。所以只需要简单的删除这些属性。
对于数据中的某个属性，如果其方差很小，则意味着其识别能力较弱。极端情况下其方差为0，这意味着该属性在所有样本上的值都是恒定的。
因此可以设定一个阈值（如），将方差小于该阈值的属性直接剔除。

一、缺失值处理

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

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

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

直接使用含有缺失值的数据。
某些算法可以直接使用含有缺失值的情况，如决策树算法可以直接使用含有缺失值的数据。
a. 优点：直接使用原始数据，排除了人工处理缺失值带来的信息损失。
b. 缺点：只有少量的算法支持这种方式。
删除含有缺失值的数据。
最简单的办法就是删除含有缺失值的样本。
a. 优点：简单、高效。
b. 缺点：如果样本中的缺失值较少，则直接丢弃样本会损失大量的有效信息。这是对信息的极大浪费。
如果样本中包含大量的缺失值，只有少量的有效值，则该方法可以接受。
缺失值补全。
用最可能的值来插补缺失值。这也是在实际工程中应用最广泛的技术。
a. 优点：保留了原始数据
b. 缺点：计算复杂，而且当插补的值估计不准确时，会对后续的模型引入额外的误差。

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

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

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

均值插补：

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

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

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

1.2 建模预测

建模预测的思想是：将缺失的属性作为预测目标，通过建立模型来预测。
给定数据集。
假设属性含有缺失值，根据是否缺失，将数据集划分为：

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

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

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

1.3 高维映射

高维映射的思想是：将属性映射到高维空间。
给定数据集，假设属性 j 的取值为离散值一共个值，则将该属性扩展为个属性，其中：

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

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

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

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

1.4 多重插补

多重插补（Multiple Imputation:MI）认为待插补的值是随机的，它的值来自于已观测到的值。
具体实践上通常是估计出待插补的值，然后再加上不同的噪声，形成多组可选插补值。然后根据某种选择依据，选取最合适的插补值。
多重插补法的步骤：

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

1.5 压缩感知 && 矩阵补全

在现实任务中，经常希望根据部分信息来恢复全部信息。压缩感知和矩阵补全就是用于完成这个任务。
假定有长度为 n 的离散信号。根据奈奎斯特采样定理，当采样频率达到最高频率的两倍时，采样后的信号就保留了原信号的全部信息。
假定以远小于奈奎斯特采样定理要求的采样频率进行采样，得到了长度为的采样后信号，其中。则有：。
其中是对信号的测量矩阵，它确定了以什么样的频率采样以及如何将采样样本组成采样后的信号。
通常在已知离散信号和测量矩阵时要得到测量值很容易。但是如果给定测量值和测量矩阵，要还原出原始信号比较困难。这是由于当时，是一个欠定方程，无法简单的求出数值解。
假设存在某种线性变换，使得，其中也和一样是维列向量，则有。令，则。
如果能够从中恢复，则能够通过从中恢复出。
从数学意义上来看，这种做法没有解决任何问题。因为根据，从中恢复这个问题仍然是欠定的。
但是在实际应用中发现，如果具有稀疏性（即大量的分量为零），则该问题能够很好地求解。这是因为稀疏性使得未知因素的影响大大减少。
此时称作稀疏基，而的作用类似于字典，能够将信号转换为稀疏表示。

1.5.1 压缩感知

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

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

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

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

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

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

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

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

1.5.2 矩阵补全

矩阵补全matrix completion解决的问题是：
其中

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

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

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

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

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

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

二、数据标准化、正则化

2.1. 数据标准化

数据标准化是将样本的属性取值缩放到某个指定的范围。
数据标准化的两个原因：

某些算法要求样本数据的属性取值具有零均值和单位方差。
样本不同属性具有不同量级时，消除数量级的影响。如下图所示为两个属性的目标函数的等高线。
a. 数量级的差异将导致量级较大的属性占据主导地位。
从图中看到：如果样本的某个属性的量级特别巨大，将原本为椭圆的等高线压缩成直线，从而使得目标函数值仅依赖于该属性。
b. 数量级的差异将导致迭代收敛速度减慢。
原始的特征进行梯度下降时，每一步梯度的方向会偏离最小值（等高线中心点）的方向，迭代次数较多，且学习率必须非常小，否则非常容易引起宽幅震荡。
标准化后进行梯度下降时，每一步梯度的方向都几乎指向最小值（等高线中心点）的方向，迭代次数较少。
c. 所有依赖于样本距离的算法对于数据的数量级都非常敏感。
如 k 近邻算法需要计算距离当前样本最近的 k 个样本。当属性的量级不同时，选取的最近的 k 个样本也会不同。

设数据集

常用的标准化算法有：

min-max标准化：对于属性，设所有样本在属性上的最大值为，最小值为。则标准化后的属性值为：标准化之后，所有样本在属性 j 上的取值都在 [0,1] 之间。
z-score标准化：对于属性，设所有样本在属性上的均值为，方差为。则标准化后的属性值为：
标准化之后，样本集的所有属性的均值都为 0，标准差均为 1。

注意：如果数据集分为训练集、验证集和测试集，则：训练集、验证集、测试集使用相同标准化参数，该参数的值都是从训练集中得到。

如果使用min-max 标准化，则属性的标准化参数都是从训练集中计算得到。
如果使用z-score 标准化，则属性的标准化参数都是从训练集中计算得到。

2.2. 数据正则化

数据正则化是将样本的某个范数（如范数）缩放到单位1。
设数据集则样本正则化后的结果为：

其中为范数：
正则化的过程是针对单个样本的，对每个样本将它缩放到单位范数。
标准化是针对单个属性的，需要用到所有样本在该属性上的值。
通常如果使用二次型（如点积）或者其他核方法计算两个样本之间的相似性时，该方法会很有用。

三、特征选择

对于一个学习任务，给定了属性集，其中某些属性可能对于学习来说是很关键的，但是有些属性可能就意义不大。

对当前学习任务有用的属性称作相关特征relevant feature 。
对当前学习任务没有用的属性称作无关特征irrelevant feature 。
从给定的特征集合中选出相关特征子集的过程称作特征选择feature selection。

特征选择可能会降低模型的预测能力。因为被剔除的特征中可能包含了有效的信息，抛弃了这部分信息会一定程度上降低预测准确率。

这是计算复杂度和预测能力之间的折衷：

如果保留尽可能多的特征，则模型的预测能力会有所提升，但是计算复杂度会上升。
如果剔除尽可能多的特征，则模型的预测能力会有所下降，但是计算复杂度会下降。

3.1 特征选择原理

特征选择是一个重要的数据预处理（data preprocessing）过程。在现实机器学习任务中，获取数据之后通常首先进行特征选择，然后再训练学习器。
进行特征选择的原因：

首先，在现实任务中经常会遇到维数灾难问题，这是由于属性过多造成的。如果能从中选择出重要的特征，使得后续学习过程仅仅需要在一部分特征上构建模型，则维数灾难问题会大大减轻。
从这个意义上讲，特征选择与降维技术有相似的动机。事实上它们是处理高维数据的两大主流技术。
其次，去除不相关特征往往会降低学习任务的难度。

特征选择过程必须确保不丢失重要特征，否则后续学习过程会因为重要信息的缺失而无法获得很好的性能。

给定数据集，如果学习任务不同，则相关特征很可能不同，因此特征选择中的无关特征指的是与当前学习任务无关的特征。
有一类特征称作冗余特征redundant feature，它们所包含的信息能从其他特征中推演出来。
a. 冗余特征在很多时候不起作用，去除它们能够减轻学习过程的负担。
b. 但如果冗余特征恰好对应了完成学习任务所需要的某个中间概念，则该冗余特征是有益的，能降低学习任务的难度。
这里暂且不讨论冗余特征，且假设初始的特征集合包含了所有的重要信息。

要想从初始的特征集合中选取一个包含了所有重要信息的特征子集，如果没有任何领域知识作为先验假设，则只能遍历所有可能的特征组合。

这在计算上是不可行的，因为这样会遭遇组合爆炸，特征数量稍多就无法进行。

一个可选的方案是：

产生一个候选子集，评价出它的好坏。
基于评价结果产生下一个候选子集，再评价其好坏。
这个过程持续进行下去，直至无法找到更好的后续子集为止。
这里有两个问题：如何根据评价结果获取下一个候选特征子集？如何评价候选特征子集的好坏？

3.1.1 子集搜索

如何根据评价结果获取下一个候选特征子集？这是一个子集搜索subset search问题。
解决该问题的算法步骤如下：

给定特征集合，首先将每个特征看作一个候选子集（即每个子集中只有一个元素），然后对这个候选子集进行评价。
假设最优，于是将作为第一轮的选定子集。
然后在上一轮的选定子集中加入一个特征，构成了包含两个特征的候选子集。
假定最优，且优于，于是将作为第二轮的选定子集。
....
假定在第 k+1 轮时，本轮的最优的特征子集不如上一轮的最优的特征子集，则停止生成候选子集，并将上一轮选定的特征子集作为特征选择的结果。

这种逐渐增加相关特征的策略称作前向forward搜索。

类似地，如果从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减小特征的策略称作后向backward搜索。

也可以将前向和后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续迭代中确定不会被去除）、同时减少无关特征，这样的策略被称作双向bidirectional搜索。

该策略是贪心的，因为它们仅仅考虑了使本轮选定集最优。但是除非进行穷举搜索，否则这样的问题无法避免。

3.1.2 子集评价

如何评价候选特征子集的好坏？这是一个子集评价subset evaluation问题。
给定数据集，假设所有属性均为离散型。对属性子集，假定根据其取值将分成了个子集：
于是可以计算属性子集的信息增益：
其中为集合大小，为熵。
信息增益越大，则表明特征子集包含的有助于分类的信息越多。于是对于每个候选特征子集，可以基于训练数据集来计算其信息增益作为评价准则。
更一般地，特征子集实际上确定了对数据集的一个划分规则。

每个划分区域对应着上的一个取值，而样本标记信息则对应着的真实划分。
通过估算这两种划分之间的差异，就能对进行评价：与对应的划分的差异越小，则说明越好。
信息熵仅仅是判断这个差异的一种方法，其他能判断这两个划分差异的机制都能够用于特征子集的评价。

将特征子集搜索机制与子集评价机制结合就能得到特征选择方法。

事实上，决策树可以用于特征选择，所有树结点的划分属性所组成的集合就是选择出来的特征子集。
其他特征选择方法本质上都是显式或者隐式地结合了某些子集搜索机制和子集评价机制。

常见的特征选择方法大致可分为三类：过滤式filter、包裹式wrapper、嵌入式embedding 。

3.2 过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。
这相当于先用特征选择过程对初始特征进行过滤，再用过滤后的特征来训练模型。
Relief:Relevant Features是一种著名的过滤式特征选择方法，该方法设计了一个相关统计量来度量特征的重要性。

该统计量是一个向量，其中每个分量都对应于一个初始特征。特征子集的重要性则是由该子集中每个特征所对应的相关统计量分量之和来决定的。
最终只需要指定一个阈值，然后选择比大的相关统计量分量所对应的特征即可。
也可以指定特征个数，然后选择相关统计量分量最大的个特征。

给定训练集

对于每个样本 :

Relief 先在
同类样本中寻找其最近邻，称作猜中近邻near-hit 。
然后从的异类样本中寻找其最近邻
，称作猜错近邻near-miss 。
然后相关统计量对应于属性的分量为：
其中为两个样本在属性 j 上的差异值，其结果取决于该属性是离散的还是连续的：

a. 如果属性 j 是离散的，则：
b. 如果属性 j 是连续的，则：
注意：此时需要标准化到 [0,1] 区间。

3.3 包裹式选择

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。其目的就是为给定学习器选择最有利于其性能、量身定做的特征子集。

优点：由于直接针对特定学习器进行优化，因此从最终学习器性能来看，效果比过滤式特征选择更好。
缺点：需要多次训练学习器，因此计算开销通常比过滤式特征选择大得多。

LVW:Las Vegas Wrapper 是一个典型的包裹式特征选择方法。它是Las Vegas method框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集的评价标准。

LVW算法：

输入：
a. 数据集
b. 特征集

c. 学习器 estimator
d. 迭代停止条件 T
输出：最优特征子集
算法步骤：
a. 初始化：令候选的最优特征子集，然后学习器 `estimator`在特征子集上使用交叉验证法进行学习，通过学习结果评估学习器 estimator的误差。
b. 迭代，停止条件为迭代次数到达
c. 最终。

由于LVW算法中每次特征子集评价都需要训练学习器，计算开销很大，因此算法设置了停止条件控制参数。

但是如果初始特征数量很多、设置较大、以及每一轮训练的时间较长，则很可能算法运行很长时间都不会停止。即：如果有运行时间限制，则有可能给不出解。

3.4 嵌入式选择

在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别。
嵌入式特征选择是将特征选择与学习器训练过程融为一体，两者在同一个优化过程中完成的。即学习器训练过程中自动进行了特征选择。
以线性回归模型为例。给定数据集以平方误差为损失函数，则优化目标为：

如果使用范数正则化，则优化目标为：
此时称作岭回归ridge regression `。
如果使用范数正则化，则优化目标为：
此时称作LASSO:Least Absolute Shrinkage and Selection Operator 回归。

引入 L_1 范数除了降低过拟合风险之外，还有一个好处：它求得的会有较多的分量为零。即：它更容易获得稀疏解。

于是基于正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，二者同时完成。

正则化问题的求解可以用近端梯度下降Proximal Gradient Descent:PGD算法求解。对于优化目标：，若可导且满足L-Lipschitz条件，即存在常数使得：

则在附近将通过二阶泰勒公式展开的近似值为：

其中是与无关的常数项。

若通过梯度下降法对进行最小化，则每一步梯度下降迭代实际上等价于最小化二次函数。
同理，若通过梯度下降法对进行最小化，则每一步梯度下降迭代实际上等价于最小化函数：。
则每一步迭代为：

其中为的第次迭代的值。
该问题有解析解，因此通过PGD能够使得LASSO 和其他基于范数最小化的方法能够快速求解。

常见的嵌入式选择模型：

在Lasso中，参数控制了稀疏性：
a. 如果越小，则稀疏性越小，则被选择的特征越多。
b. 如果越大，则稀疏性越大，则被选择的特征越少。
在SVM和logistic-regression中，参数C控制了稀疏性
a. 如果C越小，则稀疏性越大，则被选择的特征越少。
b. 如果C越大，则稀疏性越小，则被选择的特征越多。

四、类别不平衡问题

通常在机器学习中都有一个基本假设：不同类别的训练样本数目相当。

如果不同类别的训练样本数目稍有差别，通常影响不大。
如果不同类别的训练样本数目差别很大（极端情况下，如正类样本只有十个，反类样本一百万个），则会对学习过程造成影响。这就是类别不平衡问题(class-imbalance)。
这里讨论中，假设正类样本偏少、反类样本偏多。

对于类别不平衡问题，常用的有三种方法：

基于再缩放策略进行决策，称之为阈值移动threshold-moving 。
直接对训练集里的反类样本进行欠采样undersampling。
直接对训练集里的正类样本进行过采样oversampling。

对于正负样本极不平衡的场景，可以完全换一个不同的角度来看问题：将它看作一分类One Class Learning或者异常检测Novelty Detection问题。

此时可以用One-class SVM模型。

4.1 再缩放

假设对样本进行分类时，预测为正类的概率为。常规的做法是将与一个阈值，比如 0.5 ，进行比较。如果 p>0.5 时，就判别该样本为正类。
概率 p 刻画了样本为正类的可能性，几率刻画了正类可能性与反类可能性的比值。
当存在类别不平衡时，假设表示正类样本数目，表示反类样本数目，则观测几率是。
假设训练集是真实样本总体的无偏采样，因此可以用观测几率代替真实几率。于是只要分类器的预测几率高于观测几率就应该判断为正类。即如果，则预测为正类。
通常分类器都是基于概率值来进行预测的，因此需要对其预测值进行调整。在进行预测的时候，令：
然后再将跟阈值比较。这就是类别不平衡学习的一个基本策略：再缩放rescalling 。
再缩放虽然简单，但是由于“训练集是真实样本总体的无偏采样”这个假设往往不成立，所以无法基于训练集观测几率来推断出真实几率。

4.2 欠采样

欠采样会去除一些反类使得正、反类数目接近。
欠采样若随机抛弃反类，则可能丢失一些重要信息。
常用方法是将反类划分成若干个集合供不同学习器使用，这样对每个学习器来看都是欠采样，但是全局来看并不会丢失重要信息。

4.3 过采样

过采样会增加一些正类使得正、反类数目接近。
过采样不能简单的对原始正类进行重复采样，否则会导致严重的过拟合。
通常在原始正类之间插值来生成额外的正类。
常见的有以下过采样策略：

SMOTE方法：对于每个正类样本，从它的近邻中随机选取一个样本点，然后生成一个新的正类样本：该方法有两个问题：
a. 增加了正类样本之间重叠的可能性。
b. 生成了一些没有提供有益信息的样本。
Borderline-SMOTE方法：它类似SMOTE，但是对于每个正类样本，首先要评估：是否应该为该正类样本生成新的样本点。
a. 评估准则是：如果的近邻中，有超过一半以上的反类样本，则为该正类样本生成新样本。
反类样本超过一半，则说明该正类样本位于正类与反类的边界。如果的近邻中正类样本比较多，则该正类样本很可能就是处于一群正类样本的内部。
b. 该方法生成新样本的算法与SMOTE方法相同。