机器学习 | 线性方法降维（理论篇）

科幻名著《三体》里有句犀利的台词——降低维度用于攻击。不过，这个“降维”绝对不只是科幻界的专用名词。

在机器学习中，降维同样重要。很多人把降维（Dismensionality reduction），特征选择（feature selection），以及特征提取（feature extraction）混为一谈，因为这三者都削减了进入模型的变量个数。

降维是一个更为宽泛的概念，它包括特征选择和特征提取。

• 特征选择
  降维过后，最终使用的变量个数减少了，但特征选择挑选的是特征子集，也就是说，保留下来的所有特征都在原来的特征集中可以找到。
• 特征提取
  而特征提取所提取的是不再是特征子集，而是原来特征的线性（或者非线性）组合，我们经过特征提取后的变量都是新的变量，它的本质是将原始高维空间向低维空间投影，我们所使用的特征不仅少了，而且不再是原来的特征。

我们引入一个更为重要的概念------距离。

• 距离
  每个样本可以表示为一个向量，也就是高维空间的一个点，距离可以用来衡量样本之间的相似度。但是在高维空间，距离的计算会变得非常困难，而我们关心的问题可能在低维空间就会得到很好的解决。但这不意味着低维空间只是对高维空间的近似，有些问题中，高维空间会增加很多噪声，而在低维空间中会得到比高维空间更好的性能。

因此，我们讨论一下降维的几种方法，特征选择的方法会在后续文章中更新，在本文中降维特指“特征提取”。降维有两种分类方法：其一，根据目标值（target）的参与与否，分为有监督降维和无监督降维；其二，根据高维空间与低维空间的关系，分为线性降维和非线性降维。

我们对每种方法分举一例：

线性\监督	无监督	监督
线性	PCA	LDA
非线性	ISOMAP	KLDA

• PCA（Principal component analysis）主成分分析

数学准备

1. 协方差矩阵： 随机变量组成的向量，每组随机变量的协方差构成的一个对称矩阵，其对角元是每组随机变量的方差

2. 矩阵的对角化：对于矩阵M，有可逆矩阵V，使得

成为对角矩阵，而M的特征值对应的特征向量组成了该可逆矩阵V。（换而言之，矩阵V的每一列对应着M的特征向量）

3.正交矩阵：转置矩阵等于其逆矩阵，构成矩阵的列向量彼此正交。

4.数据中心化：对每组随机变量减去均值，再除以标准差。本质是将每组随机变量变为标准的高斯分布。

PCA(Principal component analysis）是用投影的方法将高维空间压缩到低维。

想象一下，此时你站在路灯下面，你本身是三维的（此时此刻除去了时间维度），你的影子却在一个二维平面上。

如图，我们将二维空间的点投影到一条直线上

如图，我们将二维空间的点投影到一条直线上。

但是，我们有无数个投影的方向，就像上图我们可以找出无数条直线来进行投影，那么哪条直线，哪个方向才是最好的呢？PCA的目标就是，找一条直线，使得投影之后的点尽可能的远离彼此，因为点之间的互相远离而不是相互重叠，就意味着某些距离信息被保留了下来。

在高维空间（维数D）的所有的样本可以被表示为一个向量:

在投影之后的低维空间（维数d），样本也是一个向量：

向量的变化可以通过一个矩阵联系起来，这个矩阵我们把它叫做投影矩阵，它的作用是将一个高维向量投影到低维空间得出一个低维向量：

此时，中心化数据的优势就体现了出来，因为经过中心化的数据， ，这就意味着数据的协方差矩阵就成了 ，投影之后的协方差矩阵就成为了 ,我们的目标是使其方差最大，而协方差矩阵的对角元正是方差，所以我们只需要对其求迹（主对角线上的各元素之和）： 换而言之，我们需要找的投影矩阵W其实是一个使 对角化的可逆矩阵，而它的转置等于它的逆 。所以我们寻找W的过程，就是寻找 的特征向量的过程，而方差最大化的过程，也就是寻找 最大特征值的过程。 所以，我们只需要对

做特征值分解，将其特征值排序，取到前面的d个特征向量，彼此正交，构成了投影矩阵W，而它们所张成的低维空间，就是使得投影点方差最大的低维空间。

如图，这是对一个二元高斯分布用PCA进行降维后的结果，这个平面就是由两个最大的特征值对应的特征向量所张成，可以看出，特征向量彼此正交，且首先找到的是最大的特征值对应的特征向量，逐步寻找第二个，第三个.....如果我们的目标空间是n维，就会取到前n个。

• LDA（Linear Discriminant Analysis）线性判别分析

数学准备：

1.均值准备:由多组随机变量组成的向量，对每一组随机变量取均值所构成的向量。
2.厄米矩阵（Hermitan）：转置等于其本身的矩阵，

3.广义瑞利熵（Rayleigh quotient ）：若x为非零向量，则

为A,B的广义瑞利熵，它的最大值是

的最大特征值。

4.矩阵的奇异值分解：
任何实矩阵M都可以被分解成为

这三个矩阵的乘积。U和V均为正交矩阵。U的列向量是 的特征向量，V的列向量是 的特征向量，同时奇异值的大小 是的特征值的平方根。

LDA（Linear Discriminant Analysis）的基本思想也是将高维空间的样本投影到低维空间，使信息损失最少。

与PCA不同在于，PCA只针对样本矩阵，希望投影到低维空间之后，样本投影点的方差最大；但LDA不仅针对样本矩阵，还使用了类别信息，它希望投影到低维空间后，相同样本的方差最小（相同样本的集中化），不同样本的距离最大（不同样本离散化）。

如图所示，将二维空间投影到一维空间，即一条直线。图2相比于图1，类间样本距离更大，类内样本方差更小。
以二分类问题为例，我们用 表示两类样本，用 表示两类样本的均值向量，用 来表示两类样本的协方差矩阵，与PCA一样，我们假设存在一个投影矩阵W，这些量会在低维空间变成：

其中 分别为低维空间的样本，均值向量和协方差矩阵。在投影空间的相同样本的方差最小，意味着
最小；而不同样本的距离最大，意味着 最大。 我们定义原始空间的样本协方差矩阵之和为

,类内散度矩阵（whithin-class scatter matrix），用来刻画原始空间上相同样本的方差：

同时定义类间散度矩阵（between-class scatter matrix） ,用来刻画原始空间上不同样本的距离:
将以上的原则结合起来，我们的目的就变成了：

根据广义瑞利熵的形式，我们寻求最大值就变成了对

进行奇异值分解，然后选取最大的奇异值和相应的特征向量。这些特征向量所张成的低维空间，就是我们的目标空间。

Tips:

• 降维在表示论中属于低维表示，本质是将原本空间压缩到更小的空间，在这个过程中保证信息损失的最小化。与之相对的是稀疏表示，它是将原本的空间嵌入到更大的空间，在这过程中保证信息损失的最小化。

• PCA有多种理解方式，除了在低维空间使得样本方差最大化，也可以理解为最小重构均方误差，将问题转化为所选低维空间重构的数据与实际数据的差。引入贝叶斯视角，还可以将PCA理解为最小化高斯先验误差。如果从流形的角度看，就是把数据看作一个拓扑空间的点集，在高斯概率空间内找到一个对应的线性流形。

• PCA和LDA的优化目标均可以用拉格朗日乘子法解决。PCA同样也可以通过奇异值分解来解决。奇异值分解方法可以理解为是特征值分解的推广，因为特征值分解要求矩阵为一个方阵，但奇异值分解并无此要求。

【参考阅读】

• 微信公众平台------读芯术