概述

数据预处理和特征选择是数据挖掘与机器学习中关注的重要问题，坊间常说：数据和特征决定了机器学习的上限，而模型和算法只是逼近这个上限而已。特征工程就是将原始数据转化为有用的特征，更好的表示预测模型处理的实际问题，提升对于未知数据的预测准确性。

缺失值处理

数据缺失值的产生的原因多种多样，主要分为客观原因和人为原因。
- 客观原因：比如数据存储的失败、存储器损坏、机械故障导致某段时间数据未能收集（对于定时数据采集而言）。
- 人为原因：由于人的主观失误（如：数据录入人员失误漏录了数据）、历史局限（如：数据在早期尚无记录）、有意隐瞒数据（如：在市场调查中被访人拒绝透露相关问题的答案，或者回答的问题是无效的）导致数据未能收集。
缺失值的处理有三种方法：
- 直接使用含有缺失值的数据。
  
  某些算法可以直接使用含有缺失值的情况，如决策树算法可以直接使用含有缺失值的数据。
- 优点：直接使用原始数据，排除了人工处理缺失值带来的信息损失。
- 缺点：只有少量的算法支持这种方式。
- 删除含有缺失值的数据。
  
  最简单的办法就是删除含有缺失值的样本。
  - 优点：简单、高效。
  - 缺点：如果样本中的缺失值较少，则直接丢弃样本会损失大量的有效信息。这是对信息的极大浪费。
  如果样本中包含大量的缺失值，只有少量的有效值，则该方法可以接受。
- 缺失值补全。
  
  用最可能的值来插补缺失值。这也是在实际工程中应用最广泛的技术。
  - 优点：保留了原始数据
  - 缺点：计算复杂，而且当插补的值估计不准确时，会对后续的模型引入额外的误差。
缺失值补全常见有以下方法：

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

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

均值插补：
- 如果样本的属性是连续值，则该属性的缺失值就以该属性有效值的平均值来插补。
- 如果样本的属性是离散值，则该属性的缺失值就以该属性有效值的众数（出现频率最高的值）来插补。
均值插补在含有缺失值的属性上的所有缺失值都填补为同一个值。而同类均值插补首先将样本进行分类，然后以该类中的样本的均值来插补缺失值。

建模预测

建模预测的思想是：将缺失的属性作为预测目标，通过建立模型来预测。
给定数据集$\mathbb{D}=\left\{\left(\vec{\mathbf{x}}_{1}, \tilde{y}_{1}\right),\left(\vec{\mathbf{x}}_{2}, \tilde{y}_{2}\right), \cdots,\left(\vec{\mathbf{x}}_{N}, \tilde{y}_{N}\right)\right\}$

假设属性$j$含有缺失值，根据$x_{ij}$是否缺失，将数据集划分为：
- $\mathbb{D}_{1}=\left\{\vec{\mathbf{x}}_{i} | x_{i, j} \neq n u l l\right\}$：属性有$j$效的样本的集合。
- $\mathbb{D}_{2}=\left\{\vec{\mathbf{x}}_{i} | x_{i, j}=n u l l\right\}$：属性$j$缺失的样本的集合。
将$\mathbb{D}_{1}$中的样本作为新的训练集，标签值重新定义为属性$j$的值，通过建模来完成属性$j$的学习。将$\mathbb{D}_{2}$中的样本作为测试集，通过学得的模型来预测其属性$j$的值。
这种方法的效果相对较好，但是该方法有个根本缺陷：
- 如果其他属性和属性无关，则预测的结果无意义。
- 如果预测结果相当准确，则又说明属性可以由其它属性计算得到，于是属性信息冗余，没有必要纳入数据集中。
  
  一般的情况是介于两者之间。

高维映射

高维映射的思想是：将属性映射到高维空间。
给定数据集$\mathbb{D}$，假设属性$j$的取值为离散值$\left\{a_{1}, a_{2} \cdots, a_{K}\right\}$一共$K$个值，则将该属性扩展为$k+1$个属性$\left(j_{1}, j_{2}, \cdots, j_{K+1}\right)$，其中：
- 若样本在属性$j$上的取值为$a_k$，则样本在新的属性$j_k$上的取值为 1，在新的属性$j_{1}, \cdots, j_{k-1}, j_{k+1}, \cdots, j_{K+1}$上的取值为0 。
- 若样本在属性$j$上缺失，则样本的新的属性$j_{K+1}$上的取值为 1,在新的属性$j_{1}, \cdots, j_{K}$上取值为 0 。
对于连续特征，高维映射无法直接处理。可以在连续特征离散化之后，再进行高维映射。
高维映射是最精确的做法，它完全保留了所有的信息，也未增加任何额外的信息。比如广告的CTR 预估模
型，预处理时会把所有变量都这样处理，达到几亿维。
- 优点：完整保留了原始数据的全部信息。
- 缺点：计算量大大提升。而且只有在样本量非常大的时候效果才好，否则会因为过于稀疏，效果很差。

多重插补

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

具体实践上通常是估计出待插补的值，然后再加上不同的噪声，形成多组可选插补值。然后根据某种选择依
据，选取最合适的插补值。
多重插补法的步骤：
- 通过变量之间的关系对缺失数据进行预测，利用蒙特卡洛方法生成多个完整的数据集。
- 在每个完整的数据集上进行训练，得到训练后的模型以及评价函数值。
- 对来自各个完整的数据集的结果，根据评价函数值进行选择，选择评价函数值最大的模型，其对应的插
  值就是最终的插补值。

压缩感知 && 矩阵补全

在现实任务中，经常希望根据部分信息来恢复全部信息。压缩感知和矩阵补全就是用于完成这个任务。
假定有长度为$n$的离散信号$\vec{x}$。根据奈奎斯特采样定理，当采样频率达到$\vec{x}$最高频率的两倍时，采样后的信号就保留了原信号的全部信息。

假定以远小于奈奎斯特采样定理要求的采样频率进行采样，得到了长度为的采样后信号，其中$m \ll n$。则有：$\vec{\mathbf{y}}=\Phi \vec{\mathbf{x}}$

其中$\Phi \in \mathbb{R}^{m \times n}$是对信号$\vec{x}$的测量矩阵，它确定了以什么样的频率采样以及如何将采样样本组成采样后的信号。
通常在已知离散信号$\vec{x}$和测量矩阵$\Phi$时要得到测量值$\vec{\mathbf{y}}$很容易。但是如果给定测量值$\vec{\mathbf{y}}$和测量矩阵$\Phi$，要
还原出原始信号$\vec{x}$比较困难。这是由于当$m \ll n$时，$\vec{\mathbf{y}}=\Phi \vec{\mathbf{x}}$是一个欠定方程，无法简单的求出数值解。
假设存在某种线性变换$\Psi \in \mathbb{R}^{n \times n}$，使得$\vec{\mathbf{x}}=\Psi \vec{\mathbf{s}}$ ，其中$\vec{\mathrm{s}}$也和$\vec{x}$一样是$n$维列向量，则有$\vec{\mathbf{y}}=\Phi \vec{\mathbf{x}}=\Phi \Psi \vec{\mathbf{s}}$
。令$\mathbf{A}=\Phi \Psi \in \mathbb{R}^{m \times n}$，则$\vec{\mathbf{y}}=\mathbf{A} \vec{\mathbf{s}}$。
如果能够从$\vec{\mathbf{y}}$中恢复$\vec{\mathbf{x}}$，则能够通过$\vec{\mathbf{x}}=\Psi \vec{\mathbf{s}}$从$\vec{\mathbf{y}}$中恢复出$\vec{\mathbf{x}}$。

从数学意义上来看，这种做法没有解决任何问题。因为根据$\vec{\mathbf{y}}=\mathbf{A} \vec{\mathbf{s}}$，从$\vec{\mathbf{y}}$中恢复$\vec{\mathbf{s}}$这个问题仍然是欠定的。

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

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

压缩感知

与特征选择、稀疏表示不同，压缩感知侧重的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。
压缩感知分为感知测量和重构恢复两个阶段。
- 感知测量：关注如何对原始信号进行处理以获得稀疏样本表示。常用的手段是傅里叶变换、小波变换、字典学习、稀疏编码等
- 重构恢复：关注的是如何基于稀疏性从少量观测中恢复原信号。
限定等距性Restricted Isometry Property:RIP ：对于大小为$m \times n, m \ll n$的矩阵$\mathbf{A}$，若存在常数$\delta_{k} \in(0,1)$，使得对于任意向量$\vec{\mathbf{S}}$和$A$的所有子矩阵$\mathbf{A}_{k} \in \mathbb{R}^{m \times k}$，都有：
$\left(1-\delta_{k}\right)| | \vec{\mathbf{s}}\left\|_{2}^{2} \leq\right\| \mathbf{A}_{k} \vec{\mathbf{s}}\left\|_{2}^{2} \leq\left(1+\delta_{k}\right)\right\| \mathbf{s}\left\|_{2}^{2}\right.$
则称$A$满足$k$限定等距性k-RIP。

此时通过下面的最优化问题可以近乎完美的从$\vec{\mathbf{y}}$中恢复出稀疏信号$\vec{\mathbf{s}} $，进而恢复出$\vec{\mathbf{x}}$：
$\begin{array}{c}{\min _{\vec{\mathrm{s}}}\|\vec{\mathbf{s}}\|_{0}} \\ {\text { s.t. } \vec{\mathbf{y}}=\mathbf{A} \vec{\mathbf{s}}}\end{array}$
这里$L_0$范数表示向量中非零元素的个数。
该最优化问题涉及$L_0$范数最小化，这是个NP难问题。但是$L_1$范数最小化在一定条件下与$L_0$范数最小化

问题共解，于是实际上只需要求解最小化问题：
$\begin{array}{c}{\min _{\vec{\mathbf{s}}}\|\vec{\mathbf{s}}\|_{1}} \\ {\text { s.t. } \quad \vec{\mathbf{y}}=\mathbf{A} \vec{\mathbf{s}}}\end{array}$
可以将该问题转化为LASSO等价形式，然后通过近端梯度下降法来求解。

矩阵补全

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

其中
- $A$为观测矩阵，其中有很多缺失值。
- $\Omega$为$A$中所有的有数值的下标的集合。
- $X$为需要恢复的稀疏信号，$rank(X)$为矩阵$A$的秩。
该最优化问题也是一个NP难问题。
考虑到在集合上的凸包是的核范数nuclear norm：
$\|\mathbf{X}\|_{*}=\sum_{j=1}^{\min \{m, n\}} \sigma_{j}(\mathbf{X})$
其中$\sigma_{j}(\mathbf{X})$表示$X$的奇异值。于是可以通过最小化矩阵核范数来近似求解：
$\begin{array}{c}{\min _{\mathbf{X}}\|\mathbf{X}\|_{*}} \\ {\text {s.t.} \quad x_{i, j}=a_{i, j},(i, j) \in \Omega}\end{array}$
该最优化问题是一个凸优化问题，可以通过半正定规划Semi-Definite Programming:SDP 求解。
理论研究表明：若$A$的秩为$r$，$n \leq m$，则只需要观察$O\left(m r \log ^{2} m\right)$个元素就能够完美恢复出$A$。

特征编码

特征二元化

特征二元化的过程是将数值型的属性转换为布尔值的属性。通常用于假设属性取值为取值分布为伯努利分布
的情形。
特征二元化的算法比较简单。对属性$j$指定一个阈值$\epsilon$。
- 如果样本在属性$j$上的值大于等于$\epsilon$，则二元化之后为 1 。
- 如果样本在属性$j$ 上的值小于$\epsilon$，则二元化之后为 0 。
阈值$\epsilon$是一个超参数，其选取需要结合模型和具体的任务来选择。

one-hot

对于非数值属性，如性别：[男，女]、国籍：[中国，美国，英国] 等等，可以构建一个到整数的映射。如性
别：[男，女] 属性中，将男映射为整数 1、女映射为整数 0。

该方法的优点是简单。但是问题是，在这种处理方式中无序的属性被看成有序的。男和女无法比较大小，但是1 和0 有大小。

解决的办法是采用独热码编码One-Hot Encoding 。
One-Hot Encoding采用N位状态位来对N个可能的取值进行编码，每个取值都由独立的状态位来表示，并
且在任意时刻只有其中的一位有效。

假设属性的取值为非数值的离散集合$\left\{a_{1}, a_{2}, \cdots, a_{K}\right\}$，独热码将其扩展成$K$个属性，每个新属性代表属性$j$的一个状态位：若样本在属性$j$上的取值为$a_k$，则样本在新的属性$j_k$上的取值为 1，在新的属性$j_{1}, \cdots, j_{k-1}, j_{k+1}, \cdots, j_{K}$上的取值为 0 。
- 这种做法中，如果在$j_{1}, \cdots, j_{K}$上取值全为 0，则表示发生了缺失。
  
  缺失值也可以用第$K+1$个状态位来表示.
- 也可以扩展成个$K-1$属性，如果在$\dot{\jmath}_{1}, \cdots, j_{K-1}$上取值全为 0，则表示样本在属性$j$上的取值为$a_K$
  。
One-Hot Encoding 的优点：
- 能够处理非数值属性。
- 在一定程度上也扩充了特征。如性别是一个属性，经过独热码编码之后变成了是否男 和是否女两个属性。
- 编码后的属性是稀疏的，存在大量的零元分量。
在决策树模型中，并不推荐对离散特征进行one-hot 。主要有两个原因：
- 产生样本切分不平衡的问题，此时且分增益会非常小。
  
  如：国籍这个离散特征经过独热码编码之后，会产生是否中国、是否美国、是否英国、...等一系列特征。在这一系列特征上，只有少量样本为1 ，大量样本为0 。
  
  这种划分的增益非常小，因为拆分之后：
  - 较小的那个拆分样本集，它占总样本的比例太小。无论增益多大，乘以该比例之后几乎可以忽略。
  - 较大的那个拆分样本集，它几乎就是原始的样本集，增益几乎为零。

影响决策树的学习。

决策树依赖的是数据的统计信息。而独热码编码会把数据切分到零散的小空间上。在这些零散的小空间上，统计信息是不准确的，学习效果变差。

本质是因为独热码编码之后的特征的表达能力较差的。该特征的预测能力被人为的拆分成多份，每一份与其他特征竞争最优划分点都失败。最终该特征得到的重要性会比实际值低。

离散化

离散化用于将连续的数值属性转化为离散的数值属性。
是否使用特征离散化，这背后是：使用“海量离散特征+简单模型”，还是“少量连续特征+复杂模型”。
- 对于线性模型，通常使用“海量离散特征+简单模型”。
- 优点：模型简单。
  - 缺点：特征工程比较困难。但是一旦有成功的经验就可以推广，并且可以很多人并行研究。
- 对于非线性模型（如深度学习），通常使用“少量连续特征+复杂模型”。
  - 优点是：不需要进行复杂的特征工程.
  - 缺点是：模型复杂。
    分桶
离散化的常用方法是分桶。
- 将所有样本在连续的数值属性$j$的取值从小到大排列$\left\{a_{0}, a_{1}, \cdots, a_{N}\right\}$。
- 然后从小到大依次选择分桶边界$b_{1}, b_{2}, \cdots, b_{M}$。其中：
  - $M$为分桶的数量，它是一个超参数，需要人工指定。
  - 每个桶的大小$b_{k+1}-b_{k}$也是一个超参数，需要人工指定。
- 给定属性$j$的取值$a_i$，对其进行分桶：
  - 如果$a_{i}<b_{1}$，则分桶编号为 0。分桶后的属性的取值为 0 。
  - 如果$b_{k} \leq a_{i}<b_{k+1}$，则分桶编号为$k$。分桶后的属性的取值为$k$。
  - 如果$a_{i} \geq b_{M}$，则分桶编号为$M$。分桶后的属性的取值为$M$。
分桶的数量和边界通常需要人工指定。一般有两种方法：
- 根据业务领域的经验来指定。如：对年收入进行分桶时，根据2017年全国居民人均可支配收入约为 2.6万元，可以选择桶的数量为5。其中：
- 年收入小于 1.3 万元（人均的0.5倍），则为分桶 0 。
  - 年收入在 1.3万元～5.2 万元（人均的0.5～2倍），则为分桶 1 。
  - 年收入在 5.3万元～26万元（人均的2倍～10倍），则为分桶 2 。年收入在 26万元～260万元（人均的10倍～100倍），则为分桶 3 。
  - 年收入超过 260万，则为分桶 4 。
- 根据模型指定。根据具体任务来训练分桶之后的数据集，通过超参数搜索来确定最优的分桶数量和分桶边界。
选择分桶大小时，有一些经验指导：
- 分桶大小必须足够小，使得桶内的属性取值变化对样本标记的影响基本在一个不大的范围。
  
  即不能出现这样的情况：单个分桶的内部，样本标记输出变化很大。
- 分桶大小必须足够大，使每个桶内都有足够的样本。
  
  如果桶内样本太少，则随机性太大，不具有统计意义上的说服力。
- 每个桶内的样本尽量分布均匀。

特性

在工业界很少直接将连续值作为逻辑回归模型的特征输入，而是将连续特征离散化为一系列 0/1 的离散特征。

其优势有：
- 离散化之后得到的稀疏向量，内积乘法运算速度更快，计算结果方便存储。
- 离散化之后的特征对于异常数据具有很强的鲁棒性。
  
  如：销售额作为特征，当销售额在 [30,100) 之间时，为1，否则为 0。如果未离散化，则一个异常10000 会给模型造成很大的干扰。由于其数值较大，它对权重的学习影响较大。
- 逻辑回归属于广义线性模型，表达能力受限，只能描述线性关系。特征离散化之后，相当于引入了非线性，提升模型的表达能力，增强拟合能力。
  
  假设某个连续特征$j$，它离散化为$M$个 0/1 特征$j_{1}, j_{2}, \cdots, j_{M}$。则：
  
  $w_{j} x_{j} \rightarrow w_{j_{1}} x_{j_{1}}^{\prime}+w_{j_{2}} x_{j_{2}}^{\prime}+\cdots+w_{j_{M}} x_{j_{M}}^{\prime}$。其中$x_{j_{1}}^{\prime}, \cdots, x_{j_{M}}^{\prime}$是离散化之后的新的特征，它们的取值空间都是${0,1}$。
  
  上式右侧是一个分段线性映射，其表达能力更强。
- 离散化之后可以进行特征交叉。假设有连续特征$j$，离散化为$N$个 0/1 特征；连续特征$k$，离散化为$M$个 0/1 特征，则分别进行离散化之后引入了$M+N$个特征。
  
  假设离散化时，并不是独立进行离散化，而是特征$j,k$联合进行离散化，则可以得到$M \times N$个组合特征。这会进一步引入非线性，提高模型表达能力。
- 离散化之后，模型会更稳定。
  
  如对销售额进行离散化，[30,100) 作为一个区间。当销售额在40左右浮动时，并不会影响它离散化后的特征的值。
  
  但是处于区间连接处的值要小心处理，另外如何划分区间也是需要仔细处理。
特征离散化简化了逻辑回归模型，同时降低模型过拟合的风险。能够对抗过拟合的原因：经过特征离散化之后，模型不再拟合特征的具体值，而是拟合特征的某个概念。因此能够对抗数据的扰动，更具有鲁棒性。

另外它使得模型要拟合的值大幅度降低，也降低了模型的复杂度。

数据标准化、正则化

数据标准化

数据标准化是将样本的属性取值缩放到某个指定的范围。
数据标准化的两个原因：
- 某些算法要求样本数据的属性取值具有零均值和单位方差。
- 样本不同属性具有不同量级时，消除数量级的影响。如下图所示为两个属性的目标函数的等高线。
  - 数量级的差异将导致量级较大的属性占据主导地位。
    
    从图中看到：如果样本的某个属性的量级特别巨大，将原本为椭圆的等高线压缩成直线，从而使得目标函数值仅依赖于该属性。
  - 数量级的差异将导致迭代收敛速度减慢。
    
    原始的特征进行梯度下降时，每一步梯度的方向会偏离最小值（等高线中心点）的方向，迭代次数较多，且学习率必须非常小，否则非常容易引起宽幅震荡。
    
    标准化后进行梯度下降时，每一步梯度的方向都几乎指向最小值（等高线中心点）的方向，迭代次数较少。
  - 所有依赖于样本距离的算法对于数据的数量级都非常敏感。
    
    如$k$近邻算法需要计算距离当前样本最近的$k$个样本。当属性的量级不同时，选取的最近的$k$个样本也会不同。
设数据集$D=\left\{\left(\vec{\mathbf{x}}_{1}, \tilde{y}_{1}\right),\left(\vec{\mathbf{x}}_{2}, \tilde{y}_{2}\right), \cdots,\left(\vec{\mathbf{x}}_{N}, \tilde{y}_{N}\right)\right\}, \vec{\mathbf{x}}_{i}=\left(x_{i, 1}, \cdots, x_{i, n}\right)^{T}$。常用的标准化算法有：
- min-max 标准化：对于属性$j$，设所有样本在属性$j$上的最大值为$j_{max}$，最小值为$j_{min}$ 。则标准化后的属性值为: $\hat{x}_{i, j}=\frac{x_{i, j}-j_{\min }}{j_{\max }-j_{\min }}$

z-score 标准化：对于属性，设所有样本在属性上的均值为，方差为。则标准化后的属性值为： $\hat{x}_{i, j}=\frac{x_{i, j}-j_{\min }}{j_{\max }-j_{\min }}$

注意：如果数据集分为训练集、验证集和测试集，则：训练集、验证集、测试集使用相同标准化参数，该参数的值都是从训练集中得到。
- 如果使用min-max标准化，则属性$j$的标准化参数$j_{max}、j_{min}$都是从训练集中计算得到。
- 如果使用z-score 标准化，则属性$j$的标准化参数$\mu_{j}, \sigma_{j}$都是从训练集中计算得到。

数据正则化

数据正则化是将样本的某个范数（如$L_1$范数）缩放到单位1。

设数据集$D=\left\{\left(\vec{\mathbf{x}}_{1}, \tilde{y}_{1}\right),\left(\vec{\mathbf{x}}_{2}, \tilde{y}_{2}\right), \cdots,\left(\vec{\mathbf{x}}_{N}, \tilde{y}_{N}\right)\right\}, \vec{\mathbf{x}}_{i}=\left(x_{i, 1}, x_{i, 2}, \cdots, x_{i, n}\right)^{T}$。则样本$\vec{\mathbf{x}}_{i}$正则化后的结果为：
$\hat{\vec{\mathbf{x}}}_{i}=\left(\frac{x_{i, 1}}{L_{p}\left(\vec{\mathbf{x}}_{i}\right)}, \frac{x_{i, 2}}{L_{p}\left(\vec{\mathbf{x}}_{i}\right)}, \cdots, \frac{x_{i, n}}{L_{p}\left(\vec{\mathbf{x}}_{i}\right)}\right)^{T}$
其中$L_p$为范数：$L_{p}\left(\vec{\mathbf{x}}_{i}\right)=\left(\left|x_{i, 1}\right|^{p}+\left|x_{i, 2}\right|^{p}+\cdots+\left|x_{i, n}\right|^{p}\right)^{1 / p}$
正则化的过程是针对单个样本的，对每个样本将它缩放到单位范数。

标准化是针对单个属性的，需要用到所有样本在该属性上的值。
通常如果使用二次型（如点积）或者其他核方法计算两个样本之间的相似性时，该方法会很有用。

特征选择

对于一个学习任务，给定了属性集，其中某些属性可能对于学习来说是很关键的，但是有些属性可能就意义不大。
- 对当前学习任务有用的属性称作相关特征relevant feature 。
- 对当前学习任务没有用的属性称作无关特征irrelevant feature 。
从给定的特征集合中选出相关特征子集的过程称作特征选择feature selection。
特征选择可能会降低模型的预测能力。因为被剔除的特征中可能包含了有效的信息，抛弃了这部分信息会一定程度上降低预测准确率。

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

特征选择原理

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

进行特征选择的原因：
- 首先，在现实任务中经常会遇到维数灾难问题，这是由于属性过多造成的。如果能从中选择出重要的特征，使得后续学习过程仅仅需要在一部分特征上构建模型，则维数灾难问题会大大减轻。
  
  从这个意义上讲，特征选择与降维技术有相似的动机。事实上它们是处理高维数据的两大主流技术。
- 其次，去除不相关特征往往会降低学习任务的难度。
特征选择过程必须确保不丢失重要特征，否则后续学习过程会因为重要信息的缺失而无法获得很好的性能。
- 给定数据集，如果学习任务不同，则相关特征很可能不同，因此特征选择中的无关特征指的是与当前学习任务无关的特征。
- 有一类特征称作冗余特征redundant feature ，它们所包含的信息能从其他特征中推演出来。
  
  冗余特征在很多时候不起作用，去除它们能够减轻学习过程的负担。
- 但如果冗余特征恰好对应了完成学习任务所需要的某个中间概念，则该冗余特征是有益的，能降低学习任务的难度。
  
  这里暂且不讨论冗余特征，且假设初始的特征集合包含了所有的重要信息。
要想从初始的特征集合中选取一个包含了所有重要信息的特征子集，如果没有任何领域知识作为先验假设，则只能遍历所有可能的特征组合。

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

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

子集搜索

如何根据评价结果获取下一个候选特征子集？这是一个子集搜索subset search问题。
解决该问题的算法步骤如下：
- 给定特征集合$\mathbb{A}=\left\{A_{1}, A_{2}, \cdots, A_{d}\right\}$，首先将每个特征看作一个候选子集（即每个子集中只有一个元
  素），然后对这$d$个候选子集进行评价。
  
  假设$A_2$最优，于是将$A_2$作为第一轮的选定子集。
- 然后在上一轮的选定子集中加入一个特征，构成了包含两个特征的候选子集。
  
  假定$A_{2}, A_{5}$最优，且优于$A_{2}$，于是将$A_{2}, A_{5}$作为第二轮的选定子集。
- ……
- 假定在第$k+1$轮时，本轮的最优的特征子集不如上一轮的最优的特征子集，则停止生成候选子集，并
  将上一轮选定的特征子集作为特征选择的结果。
这种逐渐增加相关特征的策略称作前向forward搜索。

类似地，如果从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减小特征的策略称作后向
backward搜索。
也可以将前向和后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续迭代中确定不会被去

除）、同时减少无关特征，这样的策略被称作双向bidirectional搜索。
该策略是贪心的，因为它们仅仅考虑了使本轮选定集最优。但是除非进行穷举搜索，否则这样的问题无法避

免。

子集评价

如何评价候选特征子集的好坏？这是一个子集评价subset evaluation问题。
给定数据集$\mathbb{D}$，假设所有属性均为离散型。对属性子集$A$，假定根据其取值将$\mathbb{D}$分成了$V$个子集：$\left\{\mathbb{D}_{1}, \mathbb{D}_{2}, \cdots, \mathbb{D}_{V}\right\}$

于是可以计算属性子集$A$的信息增益：
$g(\mathbb{D}, \mathbb{A})=H(\mathbb{D})-H(\mathbb{D} | \mathbb{A})=H(\mathbb{D})-\sum_{v=1}^{V} \frac{\left|\mathbb{D}_{v}\right|}{|\mathbb{D}|} H\left(\mathbb{D}_{v}\right)$
其中$|\cdot|$为集合大小，$H(\cdot)$为熵。

信息增益越大，则表明特征子集包含的有助于分类的信息越多。于是对于每个候选特征子集，可以基于训
练数据集来计算其信息增益作为评价准则。
更一般地，特征子集$A$实际上确定了对数据集$D$的一个划分规则。
- 每个划分区域对应着$A$上的一个取值，而样本标记信息$y$则对应着$D$的真实划分。
- 通过估算这两种划分之间的差异，就能对$A$进行评价：与$y$对应的划分的差异越小，则说明$A$越好。
- 信息熵仅仅是判断这个差异的一种方法，其他能判断这两个划分差异的机制都能够用于特征子集的评价
将特征子集搜索机制与子集评价机制结合就能得到特征选择方法。
- 事实上，决策树可以用于特征选择，所有树结点的划分属性所组成的集合就是选择出来的特征子集。
- 其他特征选择方法本质上都是显式或者隐式地结合了某些子集搜索机制和子集评价机制。
常见的特征选择方法大致可分为三类：过滤式filter 、包裹式wrapper 、嵌入式embedding 。

过滤式选择

上面我们已经讲到了使用特征方差来过滤选择特征的过程。除了特征的方差这第一种方法，还有其他一些统计学指标可以使用。

第二个可以使用的是相关系数。这个主要用于输出连续值的监督学习算法中。我们分别计算所有训练集中各个特征与输出值之间的相关系数，设定一个阈值，选择相关系数较大的部分特征。

第三个可以使用的是假设检验，比如卡方检验。卡方检验可以检验某个特征分布和输出值分布之间的相关性。个人觉得它比比粗暴的方差法好用。如果大家对卡方检验不熟悉，可以参看这篇卡方检验原理及应用，这里就不展开了。在sklearn中，可以使用chi2这个类来做卡方检验得到所有特征的卡方值与显著性水平P临界值，我们可以给定卡方值阈值，选择卡方值较大的部分特征。

除了卡方检验，我们还可以使用F检验和t检验，它们都是使用假设检验的方法，只是使用的统计分布不是卡方分布，而是F分布和t分布而已。在sklearn中，有F检验的函数f_classif和f_regression，分别在分类和回归特征选择时使用。

第四个是互信息，即从信息熵的角度分析各个特征和输出值之间的关系评分。在决策树算法中我们讲到过互信息（信息增益）。互信息值越大，说明该特征和输出值之间的相关性越大，越需要保留。在sklearn中，可以使用mutual_info_classif(分类)和mutual_info_regression(回归)来计算各个输入特征和输出值之间的互信息。

以上就是过滤法的主要方法，个人经验是，在没有什么思路的时候，可以优先使用卡方检验和互信息来做特征选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。
这相当于先用特征选择过程对初始特征进行过滤，再用过滤后的特征来训练模型。
Relief:Relevant Features是一种著名的过滤式特征选择方法，该方法设计了一个相关统计量来度量特征的重要性。
- 该统计量是一个向量，其中每个分量都对应于一个初始特征。特征子集的重要性则是由该子集中每个特征所对应的相关统计量分量之和来决定的。
- 最终只需要指定一个阈值$\theta$，然后选择比$\theta$大的相关统计量分量所对应的特征即可。
  
  也可以指定特征个数$k$，然后选择相关统计量分量最大的$k$个特征。
给定训练集$\mathbb{D}=\left\{\left(\vec{\mathbf{x}}_{1}, \tilde{y}_{1}\right),\left(\vec{\mathbf{x}}_{2}, \tilde{y}_{2}\right), \cdots,\left(\vec{\mathbf{x}}_{N}, \tilde{y}_{N}\right)\right\}, \tilde{y}_{i} \in\{0,1\}$。对于每个样本$\vec{\mathbf{x}}_{i}$：
- Relief 先在$\vec{\mathbf{x}}_{i}$同类样本中寻找其最近邻$\vec{\mathbf{x}}_{n h_{i}}$，称作猜中近邻near-hit 。
- 然后从$\vec{x}_{i}$的异类样本中寻找其最近邻$\vec{\mathbf{x}}_{n m_{i}}$，称作猜错近邻near-miss。
- 然后相关统计量对应于属性$j$的分量为：
  
  其中$\operatorname{diff}\left(x_{a, j}, x_{b, j}\right)$为两个样本在属性上的差异值，其结果取决于该属性是离散的还是连续的：
  - 如果属性$j$是离散的，则： $\operatorname{diff}\left(x_{a, j}, x_{b, j}\right)=\left\{\begin{array}{ll}{0,} & {\text { if } \quad x_{a, j}=x_{b, j}} \\ {1,} & {\text { else }}\end{array}\right.$

如果属性$j$是连续的，则：

$\operatorname{diff}\left(x_{a, j}, x_{b, j}\right)=\left|x_{a, j}-x_{b, j}\right|$

注意：此时$x_{a, j}, x_{b, j}$需要标准化到[0,1] 区间。

从公式 $\delta_{j}=\sum_{i=1}^{N}\left(-\operatorname{diff}\left(x_{i, j}, x_{n h_{i}, j}\right)^{2}+\operatorname{diff}\left(x_{i, j}, x_{n m_{i}, j}\right)^{2}\right)$

可以看出：

如果$\vec{\mathbf{x}}_{i}$与其猜中近邻$\vec{\mathbf{x}}_{n h_{i}}$在属性上的距离小于$\vec{\mathbf{x}}_{i}$与其猜错近邻$\vec{\mathbf{x}}_{n m_{i}}$的距离，则说明属性$j$对于区分同类与异类样本是有益的，于是增大属性$j$所对应的统计量分量。
如果$\vec{\mathbf{x}}_{i}$与其猜中近邻$\vec{\mathbf{x}}_{n h_{i}}$在属性上的距离大于$\vec{\mathbf{x}}_{i}$与其猜错近邻$\vec{\mathbf{x}}_{n m_{i}}$的距离，则说明属性$j$对于区分同类与异类样本是起负作用的，于是减小属性$j$所对应的统计量分量。
最后对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计量分量。分量值越大，则对应属性的分类能力越强。

Relief 是为二分类问题设计的，其扩展变体 Relief-F 能处理多分类问题。

假定数据集$\mathbb{D}$中的样本类别为：$c_{1}, c_{2}, \cdots, c_{K}$ 。对于样本$\vec{\mathbf{x}}_{i}$ ，假设 $\tilde{y}_{i}=c_{k}$。
- Relief-F先在类别$c_k$的样本中寻找$\vec{\mathbf{x}}_{i}$的最近邻$\vec{\mathbf{x}}_{n h_{i}}$作为猜中近邻。
- 然后在$c_k$之外的每个类别中分别找到一个$\vec{\mathbf{x}}_{i}$的最近邻$\vec{\mathbf{x}}_{n m_{i}^{l}}, l=1,2, \cdots, K ; l \neq k$作为猜错近邻。
- 于是相关统计量对应于属性$j$的分量为：
  $\delta_{j}=\sum_{i=1}^{N}\left(-\operatorname{diff}\left(x_{i, j}, x_{n h_{i}, j}\right)^{2}+\sum_{l \neq k}\left(p_{l} \times \operatorname{diff}\left(x_{i, j}, x_{n m_{i}^{\prime}, j}\right)^{2}\right)\right)$
  其中$p_{l}$为第$l$类的样本在数据集$D$中所占的比例。

包裹式选择

包装法的解决思路没有过滤法这么直接，它会选择一个目标函数来一步步的筛选特征。

最常用的包装法是递归消除特征法(recursive feature elimination,以下简称RFE)。递归消除特征法使用一个机器学习模型来进行多轮训练，每轮训练后，消除若干权值系数的对应的特征，再基于新的特征集进行下一轮训练。在sklearn中，可以使用RFE函数来选择特征。

我们下面以经典的SVM-RFE算法来讨论这个特征选择的思路。这个算法以支持向量机来做RFE的机器学习模型选择特征。它在第一轮训练的时候，会选择所有的特征来训练，得到了分类的超平面$w \dot x+b=0$后，如果有n个特征，那么RFE-SVM会选择出$w$中分量的平方值$w_i^2$最小的那个序号i对应的特征，将其排除，在第二类的时候，特征数就剩下n-1个了，我们继续用这n-1个特征和输出值来训练SVM，同样的，去掉$w_i^2$最小的那个序号i对应的特征。以此类推，直到剩下的特征数满足我们的需求为止。

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。其目的就是为给定学习器选择最有利于其性能、量身定做的特征子集。
- 优点：由于直接针对特定学习器进行优化，因此从最终学习器性能来看，效果比过滤式特征选择更好。
- 缺点：需要多次训练学习器，因此计算开销通常比过滤式特征选择大得多。
LVW:Las Vegas Wrapper是一个典型的包裹式特征选择方法。它是Las Vegas method 框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集的评价标准。
LVW 算法：
- 输入：
  - 数据集$\mathbb{D}=\left\{\left(\vec{\mathbf{x}}_{1}, \tilde{y}_{1}\right),\left(\vec{\mathbf{x}}_{2}, \tilde{y}_{2}\right), \cdots,\left(\vec{\mathbf{x}}_{N}, \tilde{y}_{N}\right)\right\}$
- 特征集$A=\{1,2, \cdots, n\}$
- 学习器 estimator
- 迭代停止条件$T$

输出：最优特征子集$A^{*}$
算法步骤：
- 初始化：令候选的最优特征子集$\tilde{\mathbb{A}}^{}=\mathbb{A}$，然后学习器 estimator在特征子集$\tilde{A}^{}$上使用交叉验证法进行学习，通过学习结果评估学习器estimator 的误差$e r r^{*}$。
- 迭代，停止条件为迭代次数到达$T$。迭代过程为：
  - 随机产生特征子集$A^{\prime}$ 。
  - 学习器 estimator在特征子集$A^{\prime}$上使用交叉验证法进行学习，通过学习结果评估学习器estimator的误差$e rr^{\prime}$。
  - 如果$e r r^{\prime}$比$e r r^{}$更小，或者$e r r^{\prime}=e r r^{}$但是$A^{\prime}$的特征数量$\tilde{A}^{}$的特征数量更少，则将$A^{\prime}$作为候选的最优特征子集$\tilde{\mathbb{A}}^{}=\mathbb{A}^{\prime} ; \quad$ err $^{*}=e r r^{\prime}$ 。
- 最终 $\mathbb{A}^{}=\tilde{\mathbb{A}}^{}$。
由于LVW算法中每次特征子集评价都需要训练学习器，计算开销很大，因此算法设置了停止条件控制参数$T$。但是如果初始特征数量很多、$T$设置较大、以及每一轮训练的时间较长，则很可能算法运行很长时间都不会停止。即：如果有运行时间限制，则有可能给不出解。

嵌入式选择

嵌入法也是用机器学习的方法来选择特征，但是它和RFE的区别是它不是通过不停的筛掉特征来进行训练，而是使用的都是特征全集。在sklearn中，使用SelectFromModel函数来选择特征。

最常用的是使用L1正则化和L2正则化来选择特征。在之前讲到的用scikit-learn和pandas学习Ridge回归第6节中，我们讲到正则化惩罚项越大，那么模型的系数就会越小。当正则化惩罚项大到一定的程度的时候，部分特征系数会变成0，当正则化惩罚项继续增大到一定程度时，所有的特征系数都会趋于0. 但是我们会发现一部分特征系数会更容易先变成0，这部分系数就是可以筛掉的。也就是说，我们选择特征系数较大的特征。常用的L1正则化和L2正则化来选择特征的基学习器是逻辑回归。

此外也可以使用决策树或者GBDT。那么是不是所有的机器学习方法都可以作为嵌入法的基学习器呢？也不是，一般来说，可以得到特征系数coef或者可以得到特征重要度(feature importances)的算法才可以做为嵌入法的基学习器。

在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别。

嵌入式特征选择是将特征选择与学习器训练过程融为一体，两者在同一个优化过程中完成的。即学习器训练过程中自动进行了特征选择。
以线性回归模型为例。

给定数据集$\mathbb{D}=\left\{\left(\vec{\mathbf{x}}_{1}, \tilde{y}_{1}\right),\left(\vec{\mathbf{x}}_{2}, \tilde{y}_{2}\right), \cdots,\left(\vec{\mathbf{x}}_{N}, \tilde{y}_{N}\right)\right\}, \tilde{y}_{i} \in \mathbb{R}$。以平方误差为损失函数，则优化目标为：如果使用范数正则化，则优化目标为：
- 如果使用$L_2$范数正则化，则优化目标为：
  $\min _{\vec{w}} \sum_{i=1}^{N}\left(\tilde{y}_{i}-\vec{\mathbf{w}}^{T} \vec{\mathbf{x}}_{i}\right)^{2}+\lambda\|\vec{\mathbf{w}}\|_{2}^{2}, \quad \lambda>0$
  此时称作岭回归ridge regression。
- 如果使用$L_1$范数正则化，则优化目标为：
  $\min _{\vec{\mathbf{w}}} \sum_{i=1}^{N}\left(\tilde{y}_{i}-\vec{\mathbf{w}}^{T} \vec{\mathbf{x}}_{i}\right)^{2}+\lambda\|\vec{\mathbf{w}}\|_{1}, \quad \lambda>0$
  此时称作LASSO:Least Absolute Shrinkage and Selection Operator回归。
引入$L_1$范数除了降低过拟合风险之外，还有一个好处：它求得的$\vec{\mathbf{w}}$会有较多的分量为零。即：它更容易获得稀疏解。

于是基于$L_1$正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，二者同时完成。
正则化问题的求解可以用近端梯度下降Proximal Gradient Descent:PGD算法求解。

对于优化目标：$\min _{\vec{\mathbf{x}}} f(\vec{\mathbf{x}})+\lambda|\vec{\mathbf{x}}|_{1}$ ，若$f(\vec{\mathbf{x}})$可导且$\nabla f$满足L-Lipschitz条件，即存在常数$L>0$使得：

则在$\vec{\mathbf{x}}_{0}$附近将$f(\vec{x})$通过二阶泰勒公式展开的近似值为：

其中$const$是与$\vec{x}$无关的常数项。
- 若通过梯度下降法对$f(\vec{\mathbf{x}})$进行最小化，则每一步梯度下降迭代实际上等价于最小化二次函数$\hat{f}(\vec{\mathbf{x}})$。
- 同理，若通过梯度下降法对$f(\vec{\mathbf{x}})+\lambda|\vec{\mathbf{x}}|_{1}$进行最小化，则每一步梯度下降迭代实际上等价于最小化函
  数：$\hat{f}(\vec{\mathbf{x}})+\lambda|\vec{\mathbf{x}}|_{1}$ 。
  
  则每一步迭代为：
  $\vec{\mathbf{x}}^{<k+1>}=\arg \min _{\mathbf{x}} \frac{L}{2}\left\|\vec{\mathbf{x}}-\left(\vec{\mathbf{x}}^{<k>}-\frac{1}{L} \nabla f\left(\vec{\mathbf{x}}^{<k>}\right)\right)\right\|_{2}^{2}+\lambda\|\vec{\mathbf{x}}\|_{1}$
  其中$\vec{\mathbf{x}}^{}$为$\vec{\mathbf{x}}$的第次$k$迭代的值。
  
  该问题有解析解，因此通过PGD 能够使得LASSO和其他基于$L_1$范数最小化的方法能够快速求解。
常见的嵌入式选择模型：
- 在Lasso 中，$\lambda$参数控制了稀疏性：
  - 如果$\lambda$越小，则稀疏性越小，则被选择的特征越多。
- 如果$\lambda$越大，则稀疏性越大，则被选择的特征越少。

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

多类分类问题

某些算法原生的支持多分类，如：决策树、最近邻算法等。但是有些算法只能求解二分类问题，如：支持向量机。
对于只能求解二分类问题的算法，一旦遇到问题是多类别的，那么可以将多分类问题拆解成二分类任务求解。即：
- 先对原问题进行拆分，然后为拆出的每个二分类任务训练一个分类器。
- 测试时，对这些二分类器的预测结果进行集成，从而获得最终的多分类结果。
多分类问题有三种拆解方式：
- 一对其余( One-vs-rest:OvR ) 。
- 一对一( one-vs-one:OvO ) 。
- 多对多( many-vs-many:MvM ) 。

one vs rest

一对其余：为每一个类别训练一个分类器。

假设类别为$\left\{c_{1}, c_{2}, \cdots, c_{K}\right\}$，则训练$K$ 个分类器：$C L F_{1}, C L F_{2}, \cdots, C L F_{K}$
- 训练$C L F_{i}$时，将类别为$c_{i}$的样本点定义为正类，将类别不是$c_{i}$的样本点定义为负类。
- 训练$C L F_{i}$不光需要给出预测结果是否属于类别$c_{i}$，还要给出置信度。
预测时，对于未知的实例，用训练出来的$K$个分类器来预测。

假设置信度最高的分类器为$C L F_{m}$，则该实例的类别预测为$c_m$。
缺点：非常容易陷入样本不平衡。

即使训练集中每一类样本都是平衡的，训练每个分类器时样本反而不平衡。

one vs one

一对一：为每一对类别训练一个分类器。
假设类别为$\left\{c_{1}, c_{2}, \cdots, c_{K}\right\}$。那么训练$\frac{K(K-1)}{2}$个分类器$C L F_{1,2}, C L F_{1,3}, \cdots, C L F_{i, j}, \cdots, C L F_{K-1, K}$。
$C L F_{i, j}, i<j$分类器从原始训练集中提取类别为$c_{i}, c_{j}$的样本点作为新的训练集，然后训练$C L F_{i, j}$。
预测时，对于未知的实例，对预测结果进行投票。
- 首先设投票结果为$s_{0}=0, s_{1}=0, \cdots, s_{K}=0$
- 然后用每个分类器$C L F_{i, j}, i<j ; i, j=1,2, \cdots, K$对未知实例进行预测：
  - 若预测结果是类别$c_i$，则$s_{i}+=1$ 。
- 若预测结果是类别$c_j$，则$s_{j}+=1$ 。

最终假设$\mathcal{S}_{m}$最大，则该未知的实例分类为$\mathcal{c}_{m}$。

缺点：需要训练的分类器数量为$O\left(K^{2}\right)$，计算量太大。

many vs many

多对多：每次都将若干个类作为正类，若干个其他类作为反类。
- 正、反类的构造必须有特殊的设计，不能随意选取。
- 通常采用纠错输出码Error Correcting Output Codes:ECOC技术。该技术将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。
ECOC 工作过程主要分两步，假设类别为$c_{1}, c_{2}, \cdots, c_{K}$：
- 编码：对$K$个类别进行 $M$次划分，每次划分都将一部分类别划分为正类，一部分类别划分为反类，从而形成一个二分类训练集。
  
  这样一个产生$M$个训练集，可以训练出 $M$个分类器。
- 解码：用$M$个分类器分别对测试样本进行预测，这些预测标记组成一个编码。
  
  将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果。

类别不平衡问题

Introduction

常用的分类算法一般假设不同类的比例是均衡的，现实生活中经常遇到不平衡的数据集，比如广告点击预测（点击转化率一般都很小）、商品推荐（推荐的商品被购买的比例很低）、信用卡欺诈检测等等。

对于不平衡数据集，一般的分类算法都倾向于将样本划分到多数类，体现在模型整体的准确率很高。

但对于极不均衡的分类问题，比如仅有1%的人是坏人，99%的人是好人，最简单的分类模型就是将所有人都划分为好人，模型都能得到99%的准确率，显然这样的模型并没有提供任何的信息。

在类别不平衡的情况下，对模型使用F值或者AUC值是更好的选择。

处理不平衡数据，可以从两方面考虑：一是改变数据分布，从数据层面使得类别更为平衡；

二是改变分类算法，在传统分类算法的基础上对不同类别采取不同的加权方式，使得模型更看重少数类。

本部分对数据层面的一些方法做一个介绍，改变数据分布的方法主要是重采样：

过采样：增加少数类样本的数量

欠采样：减少多数类样本的数量

综合采样：将过采样和欠采样结合

过采样

随机过采样

采样算法通过某一种策略改变样本的类别分布，以达到将不平衡分布的样本转化为相对平衡分布的样本的目的，而随机采样是采样算法中最简单也最直观易懂的一种方法。

随机过抽样是增加少数类样本数量可以事先设置多数类与少数类最终的数量比例在保留多数类样本不变的情况下，根据比例随机复制少数类样本，在使用的过程中为了保证所有的少数类样本信息都会被包含，可以先完全复制一份全量的少数类样本，再随机复制少数样本使得满足数量比例具体步骤如下：

首先在少数类$S_{min}$集合中随机选中一些少数类样本
然后通过复制所选样本生成样本集合$E$
将它们添加到$S_{min}$中来扩大原始数据集从而得到新的少数类集合$S_{min-new}$

$S_{\min }$中的总样本数增加了$|E|$个新样本，且$S_{m i n-n e w}$的类分布均衡度进行了相应的调整，如此操作可以改变类分布平衡度从而达到所需水平。

重复样本过多，容易造成分类器器的过拟合

SMOTE算法

在合成抽样技术方面，Chawla NY等人提出的SMOTE过抽样技术是基于随机过采样算法的一种改进方案，由于随机过采样简单复制样本的策略来增加少数类样本，这样容易产生模型过拟合的问题，即使模型学习到的信息过于特别（Specific）而不够泛化(General)。

SMOTE的主要思想是利用特征空间中现存少数类样本之间的相似性来建立人工数据，特别是，对于子集$S_{\min } \subset S$ ，对于每一个样本$x_{i} \subset S_{m i n}$使用K-近邻法，其中K-近邻被定义为考虑中的K个元素本身与的欧氏距离在n维特征空间X中表现为最小幅度值的样本。由于不是简单地复制少数类样本，因此可以在一定程度上避免分类器器的过度拟合，实践证明此方法可以提高分类器器的性能。但是由于对每个少数类样本都生生成新样本，因此容易发生生成样本重叠（overlapping）的问题。算法流程如下：

对于少数类中的每一个样本$\left(x_{i}\right)$，以欧氏距离为标准计算它到少数类样本集$S_{\min }$中所有样本的距离，得到K近邻
根据样本不平衡比例设置一个采样比例以确定采样倍率N，对于每一个少数类样本$x_i$，从其K近邻中随机选择若干个样本，假设选择的近邻为$\tilde{x}$；
对于每一个随机选出的近邻$\tilde{x}$，分别与原样本按照如下的公式构建新的样本:
$x_{n e w}=x+\operatorname{rand}(0,1) \times(\tilde{x}-x)$

Borderline-SMOTE算法

原始的SMOTE算法对所有的少数类样本都是一视同仁的，但实际建模过程中发现那些处于边界位置的样本更容易被错分，因此利用边界位置的样本信息产生新样本可以给模型带来更大的提升。Borderline-SMOTE便是将原始SMOTE算法和边界信息算法结合的算法。算法流程如下：

首先，对于每个$x_{i} \subset S_{m i n}$确定一系列K-近邻样本集，称该数据集为$S_{i-k N N}$，且$S_{i-k N N} \subset S$；

然后，对每个样本，判断出最近邻样本集中属于多数类样本的个数，即：$| S_{i-k N N} \cap S_{m a x}|$；

最后，选择满足下面不等式的$x_i$: $\frac{k}{2}<\left|S_{i-k N N} \cap S_{m a x}\right|<k$ ,将其加危险集$DANGER$

对危险集中的每一个样本点（最容易被错分的样本），采用普通的算法SMOTE成新的少数类样本。

欠采样

随机欠采样

减少多数类样本数量最简单的方法便是随机剔除多数类样本，可以事先设置多数类与少数类最终的数量比例，在保留少数类样本不变的情况下，根据比例随机选择多数类样本。

首先我们从$S_{max}$中随机选取一些多数类样本$E$

将这些样本从$S_{max}$中移除，就有$\left|S_{m a j-n e w}\right|=|S_{m a x}- E |$

优点在于操作简单，只依赖于样本分布，不依赖任何距离信息，属于非启发式方法；缺点在于会丢失部分多数类样本的信息，无法充分利用已有信息。

Tomek Links方法

定义：Tomek links被定义为相反类最近邻样本之间的一对连接。

符号约定：给定一个样本对$\left(x_{i}, x_{j}\right)$，其中$x_{i} \in S_{m a j}, \quad x_{j} \in S_{m i n}$ ，记$d\left(x_{i}, x_{j}\right)$是样本$x_i$和$x_j$之间的距离

公式表示：如果不存在任何样本$x_k$，使得$d\left(x_{i}, x_{k}\right)<d\left(x_{i}, x_{j}\right)$ ，那么样本对被称为Tomek Links

使用这种方法法，如果两个样本来自Tomek Links，那么他们中的一个样本要么是噪声要么它们都在两类的边界上。所以Tomek Links一般有两种用途：在欠采样中：将Tomek Links中属于是多数类的样本剔除；在数据清洗中，将Tomek Links中的两个样本都剔除。

NearMiss方法

NearMiss方法是利用距离远近剔除多数类样本的一类方法，实际操作中也是借助KNN，总结起来有以下几类：

NearMiss-1：在多数类样本中选择与最近的三个少数类样本的平均距离最小的样本

NearMiss-2：在多数类样本中选择与最远的3个少数类样本的平均距离最大的样本

NearMiss-3：对于每个少数类样本，选择离它最近的给定数量的多数类样本

NearMiss-1和NearMiss-2方法的描述仅有一字之差，但其含义是完全不同的：NearMiss-1考虑的是与最近的3个少数类样本的平均距离，是局部的；NearMiss-2考虑的是与最远的3个少数类样本的平均距离，是全局的。

NearMiss-1方法得到的多数类样本分布也是”不均衡“的，它倾向于在比较集中的少数类附近找到更多的多数类样本，而在孤立的（或者说是离群的）少数类附近找到更少的多数类样本，原因是NearMiss-1方法考虑的局部性质和平均距离。

NearMiss-3方法则会使得每一个少数类样本附近都有足够多的多数类样本，显然这会使得模型的精确度高、召回率低。
实验结果表明得到NearMiss-2的不均衡分类性能最优。

综合采样

目前为止我们使用的重采样方法几乎都是只针对某一类样本：对多数类样本欠采样，对少数类样本过采样。也有人提出将欠采样和过采样综合的方法，解决样本类别分布不平衡和过拟合问题，本部分介绍其中的SMOTE+Tomek Links和SMOTE+ENN。

SMOTE+Tomek Links

SMOTE+Tomek Links方法的算法流程非常简单：

利用SMOTE方法生成新的少数类样本，得到扩充后的数据集$T$
剔除T中的Tomek Links对

普通的SMOTE方法生成的少数类样本是通过线性插值得到的，在平衡类别分布的同时也扩张了少数类的样本空间，产生的问题是可能原本属于多数类样本的空间被少数类“入侵”，容易造成模型的过拟合。

Tomek Links对寻找的是那种噪声点或者边界点，可以很好地解决“入侵”的问题，下图红色加号为SMOTE产生的少数类样本，可以看到，红色样本“入侵”到原本属于多数类样本的空间，这种噪声数据由于第一步SMOTE方法已经很好地平衡了类别分布，因此在使用Tomek Links对的时候考虑剔除所有的Tomek Links对。

SMOTE+ENN

SMOTE+ENN方法和SMOTE+Tomek Links方法的想法和过程都是很类似的：

利用SMOTE方法生成新的少数类样本，得到扩充后的数据集$T$
对T中的每一个样本使用KNN（一般K取3）方法预测，若预测结果与实际类别标签不符，则剔除该样本。

概述