机器学习-特征选择和特征抽取

特征选择和特征抽取

特征选择和降维（特征提取）有着些许的相似点，这两者达到的效果是一样的，就是试图去减少特征数据集中的属性 (或者称为特征) 的数目；但是两者所采用的方式方法却不同：降维的方法主要是通过属性间的关系，如组合不同的属性得到新的属性，这样就改变了原来的特征空间；而特征选择的方法是从原始特征数据集中选择出子集，是一种包含的关系，没有更改原始的特征空间。

特征抽取（Feature Extraction）:Creatting a subset of new features by combinations of the exsiting features. 也就是说，特征抽取后的新特征是原来特征的一个映射。

特征选择（Feature Selection）:choosing a subset of all the features(the ones more informative)。也就是说，特征选择后的特征是原来特征的一个子集。

 

特征选择

我们希望获取尽可能小的特征子集，不显著降低分类精度、不影响分类分布以及特征子集应具有稳定、适应性强等特点。

为什么要做特征选择

在机器学习的实际应用中，特征数量往往较多，其中可能存在不相关的特征，特征之间也可能存在相互依赖，容易导致如下的后果：

• 特征个数越多，分析特征、训练模型所需的时间就越长。

• 特征个数越多，容易引起 “维度灾难”，模型也会越复杂，其推广能力会下降。

特征选择能剔除不相关 (irrelevant) 或亢余 (redundant) 的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的。另一方面，选取出真正相关的特征简化了模型，使研究人员易于理解数据产生的过程。

特征选择原理

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

进行特征选择的原因：

• 首先，在现实任务中经常会遇到维数灾难问题，这是由于属性过多造成的。如果能从中选择出重要的特征，使得后续学习过程仅仅需要在一部分特征上构建模型，则维数灾难问题会大大减轻。

  • 从这个意义上讲，特征选择与降维技术有相似的动机。事实上它们是处理高维数据的两大主流技术。

• 其次，去除不相关特征往往会降低学习任务的难度。

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

• 给定数据集，如果学习任务不同，则相关特征很可能不同，因此特征选择中的无关特征指的是与当前学习任务无关的特征。

• 有一类特征称作冗余特征redundant feature，它们所包含的信息能从其他特征中推演出来。

  • 冗余特征在很多时候不起作用，去除它们能够减轻学习过程的负担。
  • 但如果冗余特征恰好对应了完成学习任务所需要的某个中间概念，则该冗余特征是有益的，能降低学习任务的难度。

  这里暂且不讨论冗余特征，且假设初始的特征集合包含了所有的重要信息。

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

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

一个可选的方案是：

• 产生一个候选子集，评价出它的好坏。
• 基于评价结果产生下一个候选子集，再评价其好坏。
• 这个过程持续进行下去，直至无法找到更好的后续子集为止。

这里有两个问题：如何根据评价结果获取下一个候选特征子集？如何评价候选特征子集的好坏？

特征选择过程

特征选择主要有两个功能：

• 减少特征数量、降维，使模型泛化能力更强，减少过拟合
• 增强对特征和特征值之间的理解

通常来说，从两个方面考虑来选择特征：

• 特征是否发散：如果一个特征不发散，例如方差接近于 0，也就是说样本在这个特征上基本上没有差异，这个特征对于样本的区分并没有什么用。
• 特征与目标的相关性：这点比较显见，与目标相关性高的特征，应当优选选择。

特征选择的一般过程

特征选择的一般过程可用下图表示。首先从特征全集中产生出一个特征子集，然后用评价函数对该特征子集进行评价，评价的结果与停止准则进行比较，若评价结果比停止准则好就停止，否则就继续产生下一组特征子集，继续进行特征选择。选出来的特征子集一般还要验证其有效性。

综上所述，特征选择过程一般包括产生过程，评价函数，停止准则，验证过程，这 4 个部分。

(1) 产生过程 (Generation Procedure)

产生过程是搜索特征子集的过程，负责为评价函数提供特征子集

(2) 评价函数 (Evaluation Function)

评价函数是评价一个特征子集好坏程度的一个准则。

(3) 停止准则 (Stopping Criterion)

停止准则是与评价函数相关的，一般是一个阈值，当评价函数值达到这个阈值后就可停止搜索。

(4) 验证过程 (Validation Procedure)

在验证数据集上验证选出来的特征子集的有效性。

特征选择思想：特征子集搜索与评估

特征子集搜索与特征子集评估的结合即可得到特征选择方法。

子集搜索

如何根据评价结果获取下一个候选特征子集？这是一个子集搜索subset search问题。

解决该问题的算法步骤如下：

• 给定特征集合 $\mathbb A = \{A_1,A_2,\cdots,A_d\}$ ，首先将每个特征看作一个候选子集（即每个子集中只有一个元素），然后对这 $d$ 个候选子集进行评价。

  假设 $A_2$ 最优，于是将 $A_2$ 作为第一轮的选定子集。

• 然后在上一轮的选定子集中加入一个特征，构成了包含两个特征的候选子集。

  假定 $A_2,A_5$ 最优，且优于 $A_2$ ，于是将 $A_2,A_5$ 作为第二轮的选定子集。

• …

• 假定在第 $k+1$ 轮时，本轮的最优的特征子集不如上一轮的最优的特征子集，则停止生成候选子集，并将上一轮选定的特征子集作为特征选择的结果。

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

也可以将前向和后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续迭代中确定不会被去除）、同时减少无关特征，这样的策略被称作双向bidirectional搜索。该策略是贪心的，因为它们仅仅考虑了使本轮选定集最优。但是除非进行穷举搜索，否则这样的问题无法避免。

子集评价

如何评价候选特征子集的好坏？这是一个子集评价subset evaluation问题。

评判标准：Separation Criterion（类可区分性判据）

Distance based separation criterion基于距离的类可区分性判据

我们希望类内距离尽可能小，而类间距离尽可能大，这里我们用距离来衡量样本之间相似度。换言之，我们希望类与类之间的界限更清晰，或者说，聚类更内聚。

Probability distributions based separation criterion基于概率分布的类可区分性判据

跟基于距离的思路类似，我们考察类的概率分布，概率分布重叠度越小意味着不同的类被更好地进行了划分，而这正是我们所想看到的结果。如果类与类之间概率分布有很大重叠，那么说明我们划分有问题，或者说这两个类可能本身就是同一类。

Entropy based separation criterion基于熵的类可区分性判据

给定数据集 $\mathbb D$，假设所有属性均为离散型。对属性子集 $\mathbb A$ ， 假定根据其取值将 $\mathbb D$ 分成了 $V$ 个子集： $\{\mathbb D_1,\mathbb D_2,\cdots,\mathbb D_V\}$

于是可以计算属性子集 $\mathbb A$ 的信息增益：

$$g(\mathbb D,\mathbb A)=H(\mathbb D)-H(\mathbb D\mid \mathbb A)=H(\mathbb D)-\sum_{v=1}^{V}\frac{|\mathbb D_v|}{|\mathbb D|}H(\mathbb D_v)$$

其中 $|\cdot|$ 为集合大小， $H(\cdot)$ 为熵。

信息增益越大，则表明特征子集 $\mathbb A$ 包含的有助于分类的信息越多。于是对于每个候选特征子集，可以基于训练数据集 $\mathbb D$ 来计算其信息增益作为评价准则。

更一般地，特征子集 $\mathbb A$ 实际上确定了对数据集 $\mathbb D$ 的一个划分规则。

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

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

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

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

 

常见的特征选择方法

过滤式Filter

主要思想: 对每一维特征 “打分”，即给每一维的特征赋予权重，这样的权重就代表着该特征的重要性，然后依据权重排序。先进行特征选择，然后去训练学习器，所以特征选择的过程与学习器无关。相当于先对特征进行过滤操作，然后用特征子集来训练分类器。

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

• 该统计量是一个向量，其中每个分量都对应于一个初始特征。特征子集的重要性则是由该子集中每个特征所对应的相关统计量分量之和来决定的。

• 最终只需要指定一个阈值 $\tau$ ，然后选择比 $\tau$ 大的相关统计量分量所对应的特征即可。

  也可以指定特征个数 $k$ ，然后选择相关统计量分量最大的 $k$ 个特征。

给定训练集 $\mathbb D=\{(\mathbf{\vec x}_1,\tilde y_1),(\mathbf{\vec x}_2,\tilde y_2),\cdots,(\mathbf{\vec x}_N,\tilde y_N)\},\tilde y_i\in \{0,1\}$ 。 对于每个样本 $\mathbf{\vec x}_i$ :

• Relief 先在 $\mathbf{\vec x}_i$ 同类样本中寻找其最近邻 $\mathbf{\vec x}_{nh_i}$ ，称作猜中近邻near-hit 。

• 然后从 $\mathbf{\vec x}_i$ 的异类样本中寻找其最近邻 $\mathbf{\vec x}_{nm_i}$ ，称作猜错近邻near-miss 。

• 然后相关统计量对应于属性 $j$ 的分量为：

  $$\delta_j=\sum_{i=1}^{N}\left(-\text{diff}(x_{i,j},x_{nh_i,j})^2+\text{diff}(x_{i,j},x_{nm_i,j})^{2}\right)$$

  其中 $\text{diff}(x_{a,j},x_{b,j})$ 为两个样本在属性 $j$ 上的差异值，其结果取决于该属性是离散的还是连续的：

  • 如果属性 $j$ 是离散的，则：

    $$\text{diff}(x_{a,j},x_{b,j})=\begin{cases} 0,&\text{if}\quad x_{a,j}=x_{b,j}\\ 1,&else \end{cases}$$

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

    $$\text{diff}(x_{a,j},x_{b,j})=| x_{a,j}-x_{b,j}|$$

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

从公式

$$\delta_j=\sum_{i=1}^{N}\left(-\text{diff}(x_{i,j},x_{nh_i,j})^2+\text{diff}(x_{i,j},x_{nm_i,j})^{2}\right)$$

可以看出：

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

Relief 是为二分类问题设计的，其扩展变体 Relief-F 能处理多分类问题。假定数据集 $\mathbb D$ 中的样本类别为： $c_1,c_2,\cdots,c_K$ 。对于样本 $\mathbf{\vec x}_i$ ，假设 $\tilde y_i=c_k$ 。

• Relief-F 先在类别 $c_k$ 的样本中寻找 $\mathbf{\vec x}_i$ 的最近邻 $\mathbf{\vec x}_{nh_i}$ 作为猜中近邻。

• 然后在 $c_k$ 之外的每个类别中分别找到一个 $\mathbf{\vec x}_i$ 的最近邻 $\mathbf{\vec x}_{nm_i^l} ,l=1,2,\cdots,K;l\ne k$ 作为猜错近邻。

• 于是相关统计量对应于属性 $j$ 的分量为：

  $$\delta_j=\sum_{i=1}^{N}\left(-\text{diff}(x_{i,j},x_{nh_i,j})^{2}+\sum_{l\ne k}\left(p_l\times\text{diff}(x_ {i,j},x_{nm_i^l,j})^{2}\right)\right)$$

  其中 $p_l$ 为第 $l$ 类的样本在数据集 $\mathbb D$ 中所占的比例。

优点：运行速度快，是一种非常流行的特征选择方法。

缺点：无法提供反馈，特征选择的标准规范的制定是在特征搜索算法中完成，学习算法无法向特征搜索算法传递对特征的需求。另外，可能处理某个特征时由于任意原因表示该特征不重要，但是该特征与其他特征结合起来则可能变得很重要。

包裹式Wrapper

• 单变量特征选择方法独立的衡量每个特征与响应变量之间的关系，另一种主流的特征选择方法是基于机器学习模型的方法。有些机器学习方法本身就具有对特征进行打分的机制，或者很容易将其运用到特征选择任务中，例如回归模型，SVM，决策树，随机森林等等。
• 主要思想：包裹式从初始特征集合中不断的选择特征子集，训练学习器，根据学习器的性能来对子集进行评价，直到选择出最佳的子集。包裹式特征选择直接针对给定学习器进行优化。
• 主要方法：递归特征消除算法, 基于机器学习模型的特征排序

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

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

LVW算法：

• 输入：

  • 数据集 $\mathbb D=\{(\mathbf{\vec x}_1,\tilde y_1),(\mathbf{\vec x}_2,\tilde y_2),\cdots,(\mathbf{\vec x}_N,\tilde y_N)\}$
  • 特征集 $\mathbb A=\{1,2,\cdots,n\}$
  • 学习器 estimator
  • 迭代停止条件 $T$

• 输出： 最优特征子集 $\mathbb A^{*}$

• 算法步骤：

  • 初始化：令候选的最优特征子集 $\tilde {\mathbb A}^{*}=\mathbb A$，然后学习器 estimator在特征子集 $\tilde {\mathbb A}^{*}$ 上使用交叉验证法进行学习，通过学习结果评估学习器 estimator的误差 $err^{*}$。

  • 迭代，停止条件为迭代次数到达 $T$ 。迭代过程为：

    • 随机产生特征子集 $\mathbb A^{\prime}$ 。
    • 学习器 estimator在特征子集 $\mathbb A^{\prime}$ 上使用交叉验证法进行学习，通过学习结果评估学习器 estimator的误差 $err^\prime$ 。
    • 如果 $err^\prime$ 比 $err ^{*}$ 更小，或者 $err^\prime=err^{*}$ 但是 $\mathbb A^{\prime}$ 的特征数量比 $\tilde {\mathbb A}^{*}$ 的特征数量更少，则将 $\mathbb A^\prime$ 作为候选的最优特征子集：$\tilde {\mathbb A}^{*}=\mathbb A^{\prime};\quad err^{*}= err^\prime$ 。

  • 最终 $\mathbb A^{*}=\tilde {\mathbb A}^{*}$。

由于LVW算法中每次特征子集评价都需要训练学习器，计算开销很大，因此算法设置了停止条件控制参数 $T$ 。但是如果初始特征数量很多、$T$ 设置较大、以及每一轮训练的时间较长， 则很可能算法运行很长时间都不会停止。即：如果有运行时间限制，则有可能给不出解。

优点：从最终学习器的性能来看，包裹式比过滤式更好；对特征进行搜索时围绕学习算法展开的，对特征选择的标准规范是在学习算法的需求中展开的，能够考虑学习算法所属的任意学习偏差，从而确定最佳子特征，真正关注的是学习问题本身。由于每次尝试针对特定子集时必须运行学习算法，所以能够关注到学习算法的学习偏差 / 归纳偏差，因此封装能够发挥巨大的作用。

缺点：由于特征选择过程中需要多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择要大得多。

嵌入式Embedded

• 在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别。而嵌入式特征选择在学习器训练过程中自动地进行特征选择。嵌入式选择最常用的是 L1 正则化与 L2 正则化。在对线性回归模型加入两种正则化方法后，他们分别变成了岭回归与 Lasso 回归。
• 主要思想：在模型既定的情况下学习出对提高模型准确性最好的特征。也就是在确定模型的过程中，挑选出那些对模型的训练有重要意义的特征。
• 主要方法：简单易学的机器学习算法–岭回归（Ridge Regression），就是线性回归过程加入了 L2 正则项。
• L1 正则化有助于生成一个稀疏权值矩阵，进而可以用于特征选择
• L2 正则化在拟合过程中通常都倾向于让权值尽可能小，最后构造一个所有参数都比较小的模型。因为一般认为参 数值小的模型比较简单，能适应不同的数据集，也在一定程度上避免了过拟合现象。可以设想一下对于一个线性 回归方程，若参数很大，那么只要数据偏移一点点，就会对结果造成很大的影响；但如果参数足够小，数据偏移 得多一点也不会对结果造成什么影响，专业一点的说法是『抗扰动能力强』。

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

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

以线性回归模型为例。

给定数据集 $\mathbb D=\{(\mathbf{\vec x}_1,\tilde y_1),(\mathbf{\vec x}_2,\tilde y_2),\cdots,(\mathbf{\vec x}_N,\tilde y_N)\}, \tilde y_i \in \mathbb R$ 。 以平方误差为损失函数，则优化目标为：

$$\min_{\mathbf{\vec w}} \sum_{i=1}^{N}(\tilde y_i-\mathbf{\vec w}^{T}\mathbf{\vec x}_i)^{2}$$

• 如果使用 $L_2$ 范数正则化，则优化目标为：

  $$\min_{\mathbf{\vec w}} \sum_{i=1}^{N}(\tilde y_i-\mathbf{\vec w}^{T}\mathbf{\vec x}_i)^{2}+\lambda||\mathbf{\vec w}||_2^{2},\quad\lambda\gt 0$$

  此时称作岭回归ridge regression 。

• 如果使用 $L_1$ 范数正则化，则优化目标为：

  $$\min_{\mathbf{\vec w}} \sum_{i=1}^{N}(\tilde y_i-\mathbf{\vec w}^{T}\mathbf{\vec x}_i)^{2}+\lambda||\mathbf{\vec w}||_1,\quad\lambda\gt 0$$

  此时称作LASSO:Least Absolute Shrinkage and Selection Operator 回归。

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

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

$L_1$ 正则化问题的求解可以用近端梯度下降Proximal Gradient Descent:PGD算法求解。

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

$$||\nabla f(\mathbf{\vec x})-\nabla f(\mathbf{\vec x}^{\prime})||_2^{2} \le L ||\mathbf{\vec x}-\mathbf{\vec x}^{\prime} ||_2^{2},\;\forall( \mathbf{\vec x},\mathbf{\vec x}^{\prime})$$

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

$$\hat f(\mathbf{\vec x})\simeq f(\mathbf{\vec x}_0)+\nabla f(\mathbf{\vec x}_0)\cdot (\mathbf{\vec x}-\mathbf{\vec x}_0)+\frac L2|| \mathbf{\vec x}-\mathbf{\vec x}_0||_2^{2}\\ =\frac L2||\mathbf{\vec x}- (\mathbf{\vec x}_0-\frac 1L\nabla f(\mathbf{\vec x}_0) ) ||_2^{2}+const$$

其中 $const$ 是与 $\mathbf{\vec x}$无关的常数项。

• 若通过梯度下降法对 $f(\mathbf{\vec x})$ 进行最小化，则每一步梯度下降迭代实际上等价于最小化二次函数 $\hat f(\mathbf{\vec x})$。

• 同理，若通过梯度下降法对 $f(\mathbf{\vec x})+\lambda||\mathbf{\vec x}||_1$ 进行最小化，则每一步梯度下降迭代实际上等价于最小化函数：$\hat f(\mathbf{\vec x})+\lambda||\mathbf{\vec x}||_1$。

  则每一步迭代为：

  $$\mathbf{\vec x}^{}= \arg\min_{\mathbf{\vec x}}\frac L2||\mathbf{\vec x}- (\mathbf{\vec x}^{}-\frac 1L\nabla f(\mathbf{\vec x}^{}) ) ||_2^{2} +\lambda||\mathbf{\vec x} ||_1$$

  其中 $\mathbf{\vec x}^{<k>}$ 为 $\mathbf{\vec x}$的第 $k$ 次迭代的值。

  该问题有解析解，因此通过PGD能够使得LASSO和其他基于 $L_1$ 范数最小化的方法能够快速求解。

常见的嵌入式选择模型：

• 在Lasso中，$\lambda$ 参数控制了稀疏性：

  • 如果 $\lambda$ 越小，则稀疏性越小，则被选择的特征越多。
  • 如果 $\lambda$ 越大，则稀疏性越大，则被选择的特征越少。

• 在SVM和logistic-regression中，参数C控制了稀疏性

  • 如果C越小，则稀疏性越大，则被选择的特征越少。
  • 如果C越大，则稀疏性越小，则被选择的特征越多。

优点：对特征进行搜索时围绕学习算法展开的，能够考虑学习算法所属的任意学习偏差。训练模型的次数小于 Wrapper 方法，比较节省时间。

缺点：运行速度慢。

主成分分析 (Principle Components Analysis ,PCA) 和线性评判分析（Linear Discriminant Analysis,LDA）是特征抽取的两种主要经典方法。

对于特征抽取，有两种类别：

（1）Signal representation(信号表示): The goal of the feature extraction mapping is to represent the samples  accurately in a  low-dimensional space. 也就是说，特征抽取后的特征要能够精确地表示样本信息，使得信息丢失很小。对应的方法是 PCA.

（2）Signal classification（信号分类): The goal of the feature extraction mapping is toenhance the class-discriminatory  information in a low-dimensional space.  也就是说，特征抽取后的特征，要使得分类后的准确率很高，不能比原来特征进行分类的准确率低。对与线性来说，对应的方法是 LDA  .  非线性这里暂时不考虑。

可见， PCA 和 LDA 两种方法的目标不一样，因此导致他们的方法也不一样。PCA 得到的投影空间是协方差矩阵的特征向量，而 LDA 则是通过求得一个变换 W, 使得变换之后的新均值之差最大、方差最大（也就是最大化类间距离和最小化类内距离），变换 W 就是特征的投影方向。

 

降维方法（特征提取）

主成分分析（PCA）

PCA(Principal Component Analysis)，即主成分分析方法，是一种使用最广泛的数据降维算法。

降维就是一种对高维度特征数据预处理方法。降维是将高维度的数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度的目的。在实际的生产和应用中，降维在一定的信息损失范围内，可以为我们节省大量的时间和成本。降维也成为应用非常广泛的数据预处理方法。降维的算法有很多，比如奇异值分解 (SVD)、主成分分析 (PCA)、因子分析 (FA)、独立成分分析 (ICA)。

PCA 的主要思想是将 n 维特征映射到 k 维上，这 k 维是全新的正交特征也被称为主成分，是在原有 n 维特征的基础上重新构造出来的 k 维特征。

PCA 的工作就是从原始的空间中顺序地找一组相互正交的坐标轴，新的坐标轴的选择与数据本身是密切相关的。其中，第一个新坐标轴选择是原始数据中方差最大的方向，第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的，第三个轴是与第 1,2 个轴正交的平面中方差最大的。依次类推，可以得到 n 个这样的坐标轴。通过这种方式获得的新的坐标轴，我们发现，大部分方差都包含在前面 d 个坐标轴中，后面的坐标轴所含的方差几乎为 0。于是，我们可以忽略余下的坐标轴，只保留前面 d 个含有绝大部分方差的坐标轴。

算法与思想

PCA 是基于最近重构性和最大可分性而得到的方法。

• 最近重构性：样本点到这个超平面的距离都足够近

• 最大可分性：样本点在这个超平面上的投影能尽可能分开

PCA 通过协方差矩阵的特征值分解来找到这些坐标轴（特征向量），其算法描述为：

推导

数据中心化

首先，我们先对我们的数据中心化。

$$x_i = x_i - \frac{1}{m}\sum_{i=1}^mx_i$$

最近重构性

我们假定我们的数据（d 维特征）经过了一个投影变换，投影变换后，得到的新坐标系为 ${w_1,w_2,…,w_d}$ ，其中 $w_i$ 是标准正交基向量， $||w_i||_2=1$ 且 $w_i^Tw_j=0(i\ne j)$ 。

我们可以丢弃新坐标系中的部分坐标，即将维度降低到 $d’<d$ 。那么样本点 $x_i$ 在低维空间坐标系中的投影为 $z_i=(z_{i1};z_{i2};…;z_{id’})$ ，其中 $z_{ij}=w_j^Tx_i$ 是 $x_i$ 在低维坐标系下第 $j$ 维的坐标，若基于 $z_i$ 来重构 $x_i$ ，则会得到 $\hat{x_i} = \sum_{j=1}^{d’}z_{ij}w_j$ 。

考虑整个训练集，原样本点 $x_i$ 与基于投影重构的样本点 $\hat{x_i}$ 的距离为：

$$\begin{equation} \begin{split} \sum_{i=1}^m||\sum_{j=1}^{d'}z_{ij}w_j - x_i||_2^2 &=\sum_{i=1}^m[(\sum_{j=1}^{d'}z_{ij}w_j)^2 - 2\sum_{j=1}^{d'}z_{ij}w_jx_i + x_i^2]\\ &=\sum_{i=1}^m[z_i^Tz_i - 2z_i^TW^Tx_i + x_i^2]\\ &=\sum_{i=1}^mz_i^Tz_i - 2\sum_{i=1}^mz_i^TW^Tx_i + const\\ &\propto -tr(W^T(\sum_{i=1}^mx_ix_i^T)W)\\ \end{split} \end{equation}$$

其中 $W = (w_1,w_2,…,w_{d’})$ 。

根据最近重构性，上面的式子应该被最小化，我们知道 $w_j$ 是标准正交基，且 $\sum_ix_ix_i^T$ 是协方差矩阵，所以我们的目标函数为：

$$\begin{equation} \begin{split} min_W& \quad \ -tr(W^TXX^TW)\\ s.t.& \quad \ W^TW=I \\ \end{split} \end{equation}$$

最大可分性

我们知道，样本点 $x_i$ 在新空间中超平面上的投影是 $W^Tx_i$ ，若所有样本点的投影能尽可能分开，则应该使投影后样本点的方差最大化，而投影点后的方差是 $\sum_iW^Tx_ix_i^TW$ ，于是基于最大可分性，我们得到的目标函数依然是：

$$\begin{equation} \begin{split} min_W& \quad \ -tr(W^TXX^TW)\\ s.t.& \quad \ W^TW=I \\ \end{split} \end{equation}$$

特征向量求解

我们对上面的目标函数使用拉格朗日乘子法可得：

$$XX^TW = \lambda W$$

于是，我们只需要对协方差矩阵 $XX^T$ 进行特征值分解，讲求得的特征值排序: $\lambda_1 \ge \lambda_2 \ge …\lambda_d$ ，再取前 $d’$ 个特征值对应的特征向量构成 $W=(w_1,w_2,…,w_{d’})$ ，这就是主成分分析的解。

d‘的选取

降维后低维空间的维数 $d’$ 通常是由用户事先制定，我们可以设置一个阈值 $t=95$ ，使得 $d’$ 满足：

$$\frac{\sum_{i=1}^{d'}\lambda_i}{\sum_{i=1}^{d}\lambda_i} \ge t$$

降维的优点：

• 使得数据集更易使用。

• 降低算法的计算开销。

• 去除噪声。

• 使得结果容易理解。

优点：

• 仅仅需要以方差衡量信息量，不受数据集以外的因素影响。
• 各主成分之间正交，可消除原始数据成分间的相互影响的因素。
• 计算方法简单，主要运算是特征值分解，易于实现。

缺点：

• 主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强。
• 方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。

 

线性判别分析（LDA）

线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的降维方法。和主成分分析 PCA 不考虑样本类别输出的无监督降维技术不同，LDA 是一种监督学习的降维技术，数据集的每个样本有类别输出。LDA 算法的思想是将数据投影到低维空间之后，使得同一类数据尽可能的紧凑，不同类的数据尽可能分散。LDA 也是一种线性分类器，其不需要迭代式的进行训练，可以根据数据集，利用优化算法直接得到权重。

LDA 有如下两个假设:

• 原始数据根据样本均值进行分类。

• 不同类的数据拥有相同的协方差矩阵。

LDA 分类思想简单总结如下：

• 多维空间中，数据处理分类问题较为复杂，LDA 算法将多维空间中的数据投影到一条直线上，将 d 维数据转化成 1 维数据进行处理。
• 对于训练数据，设法将多维数据投影到一条直线上，同类数据的投影点尽可能接近，异类数据点尽可能远离。
• 对数据进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。
• 如果用一句话概括 LDA 思想，即 “投影后类内方差最小，类间方差最大”。

假设有红、蓝两类数据，这些数据特征均为二维，如下图所示。我们的目标是将这些数据投影到一维，让每一类相近的数据的投影点尽可能接近，不同类别数据尽可能远，即图中红色和蓝色数据中心之间的距离尽可能大。

左图和右图是两种不同的投影方式。

• 左图思路：让不同类别的平均点距离最远的投影方式。
• 右图思路：让同类别的数据挨得最近的投影方式。

从上图直观看出，右图红色数据和蓝色数据在各自的区域来说相对集中，根据数据分布直方图也可看出，所以右图的投影效果好于左图，左图中间直方图部分有明显交集。

以上例子是基于数据是二维的，分类后的投影是一条直线。如果原始数据是多维的，则投影后的分类面是一低维的超平面。

算法

对于 N 分类问题，模型输入 $x$ ，模型参数 $w$ ，模型输出 $h(x)$ (N 维向量)，预测标签 $y$

$$h(x) = w^Tx + w_0 \\ y = argmax_k\ h(x)$$

我们先以二分类任务为例，进行数学公式的推导。 $D$ 表示数据集， $D_i$ 表示类别 $i$ 的数据。

计算类别 i 数据的原始中心点：

$$\mu_i = \frac{1}{n_i}\sum_{x \in D_i} x$$

计算类别 i 数据投影后的中心点：

$$\tilde{\mu_i} = w^T·\mu_i$$

其用来衡量投影后，不同类别间的距离

得到每个数据投影后的点：

$$z = w^Tx$$

计算类别 i 数据投影后的方差（数据之间的分散程度）

$$\tilde{s_i}^2 = \sum_{z\in Z_i}(z - \tilde{\mu_i})^2$$

其用来衡量投影后，同一类别内数据的距离

最终，得到投影后的损失函数（二分类）

$$J(w) = \frac{(\tilde{\mu_1} - \tilde{\mu_2})^2}{\tilde{s_1}^2+\tilde{s_2}^2}$$

对上面的式子进行带入展开

$$J(w) = \frac{(w^T\mu_1 - w^T\mu_2)^2}{\sum_{x\in D_1}(w^Tx-w^T\mu_1)^2+\sum_{x\in D_2}(w^Tx-w^T\mu_2)^2} \\ \qquad =\frac{w^T(\mu_1 - \mu_2)(\mu_1 - \mu_2)^Tw}{\sum_{x\in D_1}(w^T(x - \mu_1)(x - \mu_1)^Tw)+\sum_{x\in D_2}(w^T(x - \mu_2)(x - \mu_2)^Tw)}$$

我们记 $S_B=(\mu_1 - \mu_2)(\mu_1 - \mu_2)^T$ , $S_i = \sum_{x\in D_i}(x-\mu_i)(x-\mu_i)^2$ ， $S_w = \sum_i^NS_i$

则上面的式子，我们可以简化为：

$$J(w) = \frac{w^TS_Bw}{w^TS_ww}$$

推广到多分类

在多分类任务中， $S_B$ 等于所有的 $\mu$ 两两相减的平方 的加和， $S_w$ 等于所有的 $S_i$ 的加和

使用拉格朗日乘子法求解权重

在拉格朗日乘子法中，我们需要对分母进行限制，限制其等于 1。这个限制条件跟 SVM 中的限制是一个道理，是为了防止权重的倍数增长而造成的有无穷多个解的问题，比如 1/1=1, 而 2/2=1，我们加了限制条件，就只有了第一种可能性，这让我们可以使用拉格朗日算法

$$c(w) = w^TS_Bw - \lambda(w^TS_ww-1) \\ \Rightarrow \frac{dc}{dw} = 2S_Bw - 2\lambda S_ww = 0 \\ \Rightarrow 2S_Bw = 2\lambda S_ww$$

我们可以利用线性代数求特征值的方法求解 w

优点

• 计算速度快
• 充分利用了先验知识

缺点

• 当数据不是高斯分布时候，效果不好，PCA 也是。
• 降维之后的维数最多为 类别数 - 1，因为在进行拉格朗日求解时，我们能够得到的特征向量的数目为 x 的秩 - 1。

 

比较这两种方法

降维的必要性：

1. 多重共线性和预测变量之间相互关联。多重共线性会导致解空间的不稳定，从而可能导致结果的不连贯。
2. 高维空间本身具有稀疏性。一维正态分布有 68% 的值落于正负标准差之间，而在十维空间上只有 2%。
3. 过多的变量，对查找规律造成冗余麻烦。
4. 仅在变量层面上分析可能会忽略变量之间的潜在联系。例如几个预测变量可能落入仅反映数据某一方面特征的一个组内。

降维的目的：

• 减少预测变量的个数。
• 确保这些变量是相互独立的。
• 提供一个框架来解释结果。相关特征，特别是重要特征更能在数据中明确的显示出来；如果只有两维或者三维的话，更便于可视化展示。
• 数据在低维下更容易处理、更容易使用。
• 去除数据噪声。
• 降低算法运算开销。

LDA 和 PCA 区别

KPCA

pass

 

参考

https://zhuanlan.zhihu.com/p/134089340

https://github.com/Vay-keen/Machine-learning-learning-notes

https://github.com/familyld/Machine_Learning

https://zhuanlan.zhihu.com/p/25994179

https://leovan.me/cn/2018/12/ensemble-learning/

https://easyai.tech/ai-definition/ensemble-learning/

https://zhuanlan.zhihu.com/p/72415675

https://www.zhihu.com/question/63492375

https://www.zhihu.com/question/27068705

https://www.zhihu.com/question/19725590/answer/241988854

https://tangshusen.me/2018/10/27/SVM/

https://www.joinquant.com/view/community/detail/a98b7021e7391c62f6369207242700b2

https://zhuanlan.zhihu.com/p/79531731

https://github.com/Charmve/PaperWeeklyAI/blob/master/03_Maiwei AI PaperWeekly/03_机器学习%26深度学习理论/机器学习算法之——K最近邻(k-Nearest Neighbor，KNN)分类算法原理讲解.md

https://blog.csdn.net/zc02051126/article/details/49618633

https://zhuanlan.zhihu.com/p/127022333

https://0809zheng.github.io/2020/03/30/ridge.html

https://www.cnblogs.com/wuliytTaotao/p/10837533.html

https://link.springer.com/referenceworkentry/10.1007/978-1-4899-7687-1_910#Sec13186

http://palm.seu.edu.cn/zhangml/files/mla11-mll.pdf

https://blog.csdn.net/zwqjoy/article/details/80431496

https://ryuchen.club/posts/0x000034/ (推荐）

https://zhuanlan.zhihu.com/p/78798251

https://zhuanlan.zhihu.com/p/622244758

https://www.biaodianfu.com/hierarchical-clustering.html

https://zhuanlan.zhihu.com/p/411533418

https://zhuanlan.zhihu.com/p/33196506

https://www.cnblogs.com/wry789/p/13125658.html

https://blog.csdn.net/qq_41485273/article/details/113178117

https://www.jianshu.com/p/7d4323c28716

http://lunarnai.cn/2019/01/02/watermelon-chap-13/

【周志华机器学习】十三、半监督学习

https://zhuanlan.zhihu.com/p/411533418

https://www.huaxiaozhuan.com/统计学习/chapters/12_semi_supervised.html

https://blog.csdn.net/tyh70537/article/details/80244490

https://zhuanlan.zhihu.com/p/37747650

7125messi.github.io

https://blog.csdn.net/qq_40722827/article/details/104515955

https://www.cnblogs.com/dyl222/p/11055756.html

https://www.zhihu.com/tardis/zm/art/392908965

https://blog.csdn.net/j123kaishichufa/article/details/7679682

https://www.cnblogs.com/heaad/archive/2011/01/02/1924088.html

https://www.cnblogs.com/stevenlk/p/6543628.html

baidinghub.github.io-PCA

baidinghub.github.io-LDA

等等