彻底理解机器学习

阿南带你理解主成分分析法

好好学习，天天向上

Posted by Nam on March 1, 2020

前言

今天要说的这个算法呢，其实之前经常有听到，但是面对算法里面的复复杂杂的矩阵公式还是有点畏难，所以一直没有提笔去写。

现在长大了，晓得 ”难事必有所得“，今天阿南就要迎难而上，带大家击败 主成分分析法！

先预告一下，今天的定理和公式可能会有点晦涩难懂。但是记住，这其中的概念和精髓一定要理解！

主成分分析法

作为一个高智商的当代智慧青年，总有一个暴富的梦想。这时候河神出现，给了你香港赛马会的历史数据，说致富的秘诀就在里面。你打开一开发现傻眼了，里面有上万条马匹的数据，而且有几千个特征：马匹年龄，血统、历史战绩、当天温度、湿度、草场硬度。。。等等。这有些特征看起来挺无关的，比如说噪音，但是你又不敢贸然剔除，面对这么高维度的数据应该怎么下手呢？

这时候发现河神走之前在沙滩上赫然写着三个大字 P！C！A！

这就是今天的主角，

主成分分析法 (Principal component analysis, PCA) (以下简称 PCA) 是利用 正交变换 把由 线性相关变量 所表示的观测数据转换为 少数几个 由 线性无关变量 所表示的数据，这几个少数的线性无关的变量称之为原始数据的 主成分。

由于新的数据维度低于原始数据维度，因此 PCA 属于 降维方法。由于新的变量维度小于原始维度，因此 PCA 也常常被用在数据分析之中用于发现各个特征之间的相互关系以及其对于总体的影响。

说到这里大家可能有点懵了，正交变换是啥？

What

定义 正交变换： 若 $\boldsymbol{A}$ 为 正交矩阵，则线性变换 $\boldsymbol{y=Ax}$ 称为正交变换。其中，满足$\boldsymbol{AA^T=E}$ 则称矩阵 $\boldsymbol{A}$ 为正交矩阵。

上面的定义用人话转述就是：对原坐标系进行旋转变换，并将数据集在新坐标系中表示。并且新坐标中坐标轴两两之间相互正交，因此我们需要上述定义中得变换矩阵 $\boldsymbol{A}$ 为正交矩阵。

现在开始处理我们的赛马数据。我们的目的就是把这令人生畏的高维度降低至一个可计算的维度，同时尽可能地保留原始数据中的大部分信息。

假设我们所拥有的原始数据形式为：$\boldsymbol{x} = (x_1,x_2,…,x_m)^T$，为 $m$ 维随机变量，$x_i$ 为第 $i$ 个随机变量，$i=1,2,…,m$，并且我们进行了 $n$ 次独立的观测 $\boldsymbol{x_1,x_2,…,x_n}$ 表示观测的样本。$x_{ij}$ 表示观测的第 $j$ 个样本的第 $i$ 个维度。样本集记作 $\boldsymbol{X}$：

\[\boldsymbol{X=} \begin{bmatrix} \boldsymbol{x_1} & \boldsymbol{x_2} & \cdots & \boldsymbol{x_n} \end{bmatrix} = \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{mn} \end{bmatrix}\]

  1. 对原始数据进行规范化，使得数据每一维度上变量的均值为 $0$，方差为 $1$ \(x_i^* = \frac{x_i-E(x_i)}{\sqrt{var(x_i)}} \tag{1}\)

    其中$E(x_i),var(x_i)$ 分别是随机变量 $x_i$ 的均值和方差，此时 $x_i^*$ 就是 $x_i$ 的规范化随机变量。显然，此时样本集 $\boldsymbol{X}$ 的协方差矩阵 $S$ 为：

    \[\Sigma = \frac{1}{n-1} \boldsymbol{XX^T} \tag{2}\]

    (由于是样本方差的估计，因此系数为 $\frac{1}{n-1}$，详情参考：阿南带你理解无偏估计)

  2. 随后对数据进行正交变换，即对原坐标系进行旋转变换，并将数据在新坐标系中表示。

    如下图所示，在新坐标系 $y_1,y_2$ 中，PCA 选择方差最大的方向作为新坐标系的第一坐标轴 $y_1$。随后选择第二第三等主成分的选取都要在已有坐标轴相互正交的条件下进行。在新坐标系中，各个维度上的变量 $y_i$ 之间都是线性无关的，即已知一个变量 $y_i$ 取值时对另一个变量 $y_k$ 的预测是完全随机的。

PCA 的主要目的就是降维，即选择的主成分的数量 $k (k<m)$ 用来代替原始数据集的 $m$ 个维度，使得高维问题在低维空间中得以简化的同时能保留原始数据的大部分信息。

那么如何尽可能的保留多的信息呢？答案就是选择能使方差达到最大的坐标轴！即让数据集在新坐标轴上的投影尽可能分散开来！

PCA

对任意正整数 $k,\ 1\le k\le m$，考虑如下正交变换：

\[\boldsymbol{y} = B^T \boldsymbol{x} \tag{3}\]

其中 $\boldsymbol{y}$ 是 $k$ 维向量， $B^T$ 是 $k\times m$ 维度的矩阵，令 $\boldsymbol{y}$ 的协方差矩阵为：

\[\Sigma_{\boldsymbol{y}} = B^T\Sigma B \tag{4}\]

则 $\Sigma_{\boldsymbol{y}}$ 的迹 $tr(\Sigma_{\boldsymbol{y}})$ 在 $B=A_k$ 时达到最大。其中 $A_k$ 为原始样本集 $\boldsymbol{x}$ 的协方差矩阵 $\Sigma$ 的特征向量矩阵 $A$ 的前 $k$ 列特征向量所构成的 $m\times k$ 维度的正交矩阵 $A_k$。

因此我们的目的就是求出原始样本集 $\boldsymbol{x}$ 的协方差矩阵 $\Sigma$ 的特征向量矩阵 $A$ 然后再取其前 $q$ 列便可以得到正交线性变换矩阵 $B$。求解协方差矩阵 $\Sigma$ 的特征向量矩阵 $A$ 有两个方法，分别是 特征值分解法 和 奇异值分解法，以下将分别介绍。

特征值分解法

首先给出特征值和特征向量的定义：

设 $\boldsymbol{A}$ 是 $n$ 阶方阵（注意，只有方阵可以求！），若存在 $n$ 维非零向量 $\boldsymbol{x}$，使得： \(\boldsymbol{Ax} = \lambda \boldsymbol{x} \tag{5}\) 则称实数 $\lambda$ 为 $\boldsymbol{A}$ 的特征值，$\boldsymbol{x}$ 是 $\boldsymbol{A}$ 在 $\lambda$ 下的特征向量。几何上的理解就是存在这么一个神奇的向量 $\boldsymbol{x}$ 它与向量左右后向量 $\boldsymbol{x}$ 方向不变，只是长度变换为原来的 $\lambda$ 倍。

通常我们通过求解特征方程来解出特征值 $\lambda$ 和特征向量 $\boldsymbol{x}$，即：

\[|A-\lambda I|=0 \tag{6}\]

传统的 PCA 通过原始数据集 $\boldsymbol{X}$ 的协方差矩阵 $S_X$ 的特征值分解以获得特征向量，具体步骤如下：

  1. 对原始数据 $\boldsymbol{X}$ 进行规范化，得到规范化数据矩阵为简洁起见仍以 $\boldsymbol{X}$ 表示。
  2. 计算相关矩阵 $\boldsymbol{R}$: \(\boldsymbol{R}= \frac{1}{n-1} \boldsymbol{XX^T} \tag{7}\)

  3. 求解相关矩阵 $\boldsymbol{R}$ 的 $k$ 个特征值和对应的 $k$ 个单位特征向量。

    具体步骤为，先求解 $\boldsymbol{R}$ 的特征方程： \(|\boldsymbol{R} - \lambda I|=0 \tag{8}\) 得到 $\boldsymbol{R}$ 的 $m$ 个特征值，并将其排序： \(\lambda_1\ge \lambda_2 \ge ... \ge \lambda_m\) 然后选出 $k$ 个特征值及其对应的单位特征向量，组成特征向量矩阵： \(A_k = [\boldsymbol{a_1} \ \ \boldsymbol{a_2} \ \ ...\ \ \boldsymbol{a_k}]\) 其中每个特征向量的形式为： \(\boldsymbol{a_i} = (a_{1i},a_{2i},...,a_{mi})\)

  4. 计算原始数据 $\boldsymbol{X}$ 在新的 $k$ 维空间中正交变换的结果 \(\boldsymbol{Y} = A_k \boldsymbol{X} \tag{9}\) 至此，我们就计算出了原始数据 $\boldsymbol{X}$ 投影至以 $k$ 个主成分为坐标轴的 $k$ 维空间中。

你可能有许多问号，比如说这里的 $k$ 我们怎么选取？

答案就是我们通过 累计方差贡献率 来辅助选择达到预定值得主成分个数 $k$:

累计方差贡献率：$k$ 个主成分 $y_1,y_2,…,y_k$ 的累计方差贡献率定义为 $k$ 个方差之和与所有方差之和的比： \(\sum_{i=1}^k \eta_i = \frac{\sum_{i=1}^k \lambda_i}{\sum_{i=1}^m \lambda_i} \tag{10}\)

通常取 $k$ 使得累计方差贡献率达到预先设定的百分比以上，例如 70%~80%。累计方差贡献率反映了主成分保留信息的比例。

以上就是通过特征值分解法求得正交变换矩阵的过程。接下来介绍的是当下最常用的奇异值分解法。

奇异值分解法

首先给出奇异值分解的定义：

若 $\boldsymbol{A}$ 为一 $m\times n$ 实矩阵，$A\in R^{m\times n}$，则 $\boldsymbol{A}$ 的奇异值分解一定存在：

\[\boldsymbol{A} = U \Sigma V^T \tag{11}\]

其中 $U$ 是 $m$ 阶正交矩阵，$V$ 是 $n$ 阶正交矩阵，$\Sigma$ 是 $m\times n$ 矩形对角矩阵，其对角线元素非负，且按照降序排列。因此，奇异值分解也可以看作是将原始坐标轴的标准正交基分别进行了 旋转变换、缩放变换以及旋转变换的变换组合，并且这个变换组合一定存在！

SVD

  1. 第一步依旧是对原始数据 $\boldsymbol{X}$ 进行规范化，得到规范化数据矩阵为简洁起见仍以 $\boldsymbol{X}$ 表示。

  2. 构造新的 $n\times m$ 矩阵: \(\boldsymbol{X^{'}} = \frac{1}{\sqrt{n-1}} \boldsymbol{X} \tag{12}\) 这样构造的目的是因为我们求解任意一个矩阵 $\boldsymbol{N}$ 的奇异值分解都可以通过求对称矩阵 $\boldsymbol{N^T N}$ 的特征值和特征向量来得到。而此处我们的目的就是要求得原始数据协方差矩阵的特征向量矩阵 $A$ 然后再取其前 $k$ 列得到 $A_k$。

    因此我们重新构建 $\boldsymbol{X^{‘}}$ 了之后，就可以在求解 $\boldsymbol{X^{‘}}$ 奇异值分解过程中得到原始数据的协方差矩阵 $\Sigma$ 的特征值矩阵，其中 $\Sigma$ 为： \(S_X = \boldsymbol{X^{'T}X^{'}} \tag{13}\)

  3. 对矩阵 $\boldsymbol{X^{‘}}$ 进行截断奇异值分解，得到： \(\boldsymbol{X^{'}} = U_k \Sigma_k V^T_k \tag{14}\) 其中 $U_k$ 是 $m\times k$ 矩阵，$V_k$ 是 $n\times k$ 矩阵， $\Sigma_k$ 是 $k$ 阶对角矩阵；$U_k,V_k$ 分别通过取 $\boldsymbol{X^{‘}}$ 的完全奇异值分解的矩阵 $U,V$ 的前 $k$ 列， $\Sigma_k$ 通过取$\boldsymbol{X^{‘}}$ 的完全奇异值分解的矩阵 $\Sigma$ 的前 $k$ 个对角元素得到。
  4. 得到原始样本集在新 $k$ 维空间中的正交变换 \(\boldsymbol{Y} = V^T_k \boldsymbol{X} \tag{15}\)

到这里，关于原始数据集 $\boldsymbol{X}$ 通过奇异值分解从高维度 $m$ 降至低维度 $k$ 的正交变换方法也叙述完毕啦~

总结

PCA 的本质是将方差最大的方向作为主要特征，并且在各个正交方向上去除各个维度上的相关性，也就是让它们在不同正交方向上没有相关性。

因此，PCA 也存在一些限制：尽管它能很好的解除线性相关，但是对于高阶相关它就没有办法了。对于高阶相关的数据可以考虑加入 核方法 的 Kernel PCA。

另外，PCA 的假设是原始数据 $\boldsymbol{X}$ 的各个主特征是分布在正交方向上。因此，如果在非正交方向上存在几个方差交大的方向，那就意味着 PCA 的效果将大打折扣。

最后，PCA 是无参数方法。也就是说对于同样的数据，没有主观参数的介入。因此 PCA 便于通用实现，但是本身无法实现个性化的优化。

好滴~ 谢谢大家的观看！希望收到大家的意见或建议~

:)

CATALOG
    FEATURED TAGS
    彻底理解机器学习