2019-03-14

机器学习基础（三）- 主成分分析（Principle Component Analysis, PCA）笔记

字数统计: 4k 字 | 阅读时长: 16 分 | 本文总阅读量: 次

引言

　　PCA，Principle Component Analysis，即主成分分析法，是特征降维的最常用手段，PCA能从冗余特征中提取主要成分，在不太损失模型质量的情况下，提升了模型训练速度，与LDA同样有降维的功能，本文主要记录一些它的知识点。

PCA思想

　　PCA如它的名字所表达的意思一样，是为了找出数据中的主要成分来代表原数据集，也就是降维，所谓降维不仅需要将数据的维度降低，减少计算量，而且要尽可能的让数据的特性不会差太多。
　　如下图所示，我们举一个二维的例子，我们可以看出$v$要$v'$更好一点，一方面因为样本点到这个个直线的距离足够近，另一方面因为样本点在这个直线上的投影能尽可能的分开（对应到图中就是协方差更大），它保持的数据的特性也更多。

　　假如我们把投影从1维推广到任意维，则我们的希望降维的标准就是，样本点在这个超平面上的投影能尽可能的分开或者样本点到这个超平面的距离足够近。
　　转化为数学问题，降维问题的优化目标就是，将一组$N$维向量降为$K$维，选择$K$个单位（模为1）正交基，使得原始数据变换到这组基上后，各字段两两间协方差为0，而字段的方差则尽可能大（在正交的约束下，取最大的$K$个方差）。
　　我们有两种思路推导出PCA的公式，一种是最大化投影方差（最大可分性），一种是最小化损失（最近重构性），我们分别介绍下。

最大化投影方差

　　我们来看第一种推导，最大化投影方差，也就是最大可分性，让样本点在这个超平面的投影能尽可能分开。
　　假设$m$个$n$维数据$\{x_1,x_2,...,x_m\}$都已经进行了中心化，即$\Sigma_{i=1}^mx_i=0$。经过投影变换后得到的新坐标系为$\{w_1,w_2,...,w_n\}$，其中$w$是标准正交基，即$||w||_2=1, w^T_i w_j=0$。
　　为了降维，我们将数据从$n$维降到$n'$维，即丢弃新坐标系中的部分坐标，则新的坐标系为$\{w_1,w_2,...,w_{n'}\}$，样本点$x_i$在$n'$维坐标系中的投影为：$z_i=(z_{i1},z_{i2},...,z_{in'})$，其中$z_{ij}=w_j^Tx_i$是$x_i$在低维坐标系里第$j$维的坐标。
　　对于任意一个样本$x_i$，在新的坐标系中的投影为$W^Tx_i$，在新坐标系中的投影方差为$W^T x_i x_i^T W$，要使所有的样本的投影方差和最大，矩阵$XX^T$作为一个协方差矩阵，其对角线的任一位置的值就是某个维度的方差，我们要优化的也恰好是方差和。因此我们的优化目标也就是最大化$\Sigma_{i=1}^m W^T x_i x_i^T W$的迹，即： \[ argmax \quad tr(W^T x_i x_i^T W) \\ s.t. W^TW=I \] 　　我们利用拉格朗日乘数得到： \[ J(W)=tr(W^TXX^TW+λ(W^TW−I)) \] 　　对$W$求导得到： \[ X X^T W = −\lambda W \] 　　我们分析一下，$W$为$XX^T$的$n'$个特征向量组成的矩阵，而$−\lambda$为$XX^T$的若干特征值组成的矩阵，特征值在主对角线上，其余位置为0。当我们将数据集从$n$维降到$n'$维时，需要找到最大的$n'$个特征值对应的特征向量。这$n'$个特征向量组成的矩阵$W$即为我们需要的矩阵。对于原始数据集，我们只需要用$z_i=W^Tx_i$，就可以把原始数据集降维到最小投影距离的$n'$维数据集。

最小化损失

　　我们来看另外一种推导，最小化的损失，即最近重构性，其实就是最小化投影距离，即让样本点到这个超平面的距离足够近，为啥这样可以保证呢，我们可以简单的推导一下。
　　假设输入数据$x$是在$n$维空间中的点，那么，我们可以用$n$个正交的$n$维向量去完全的表示这个空间（这个空间中所有的向量都可以用这$n$个向量的线性组合得到）。在$n$维空间中，有无穷多种可能找这$n$个正交的$n$维向量，哪个组合是最合适的呢？
　　假设我们已经找到了这$n$个向量，可以得到： \[ x_i = \Sigma_{j=1}^{n} a_{ij}w_j \] 　　用近似法来表示投影后的点： \[ \tilde{x}_i = \Sigma_{j=1}^{n’} z_{ij}w_j +　\Sigma_{j=n'+1}^{n} b_{j}w_j \] 　　上式表示，得到的新的$\tilde{x}$是由前$n'$个基的线性组合加上后$n-n'$个基的线性组合，注意这里的$z$是对于每个$\tilde{x}$都不同的，而$b$对于每个$\tilde{x}$是相同的，这样我们就可以用$n'$个数来表示空间中的一个点，也就是使得数据降维了。但是这样降维后的数据，必然会产生一些扭曲，我们用$J$描述这种扭曲，我们的目标是，使得$J$最小，也就是最小化损失： \[ J = \Sigma_{i=1}^m \Vert x_i - \tilde{x}_i \Vert_2^2 \] 　　我们发现这其实也就是让样本点到这个超平面的距离足够近，我们来推导一下这个式子。
　　假设$m$个$n$维数据$\{x_1,x_2,...,x_m\}$都已经进行了中心化，即$\Sigma_{i=1}^mx_i=0$。经过投影变换后得到的新坐标系为$\{w_1,w_2,...,w_n\}$，其中$w$是标准正交基，即$||w||_2=1, w^T_i w_j=0$。
　　为了降维，我们将数据从$n$维降到$n'$维，即丢弃新坐标系中的部分坐标，则新的坐标系为$\{w_1,w_2,...,w_{n'}\}$，样本点$x_i$在$n'$维坐标系中的投影为：$z_i=(z_{i1},z_{i2},...,z_{in'})$，其中$z_{ij}=w_j^Tx_i$是$x_i$在低维坐标系里第$j$维的坐标。
　　我们用$z_i$来恢复原始数据降维后的$x_i$，记$\tilde{x}_i=\Sigma_{j=1}^{n’} z_{ij}w_j=Wz_i$，$W$为标准正交基组成的矩阵。
\[ \begin{align} \Sigma_{i=1}^m \Vert x_i - \tilde{x}_i \Vert_2^2 & = \Sigma_{i=1}^m \Vert x_i - Wz_i \Vert_2^2 \\ & = \Sigma_{i=1}^m x_i^T x_i - 2\Sigma_{i=1}^m (Wz_i)^T x_i + \Sigma_{i=1}^m (Wz_i)^T (Wz_i) \\ & = \Sigma_{i=1}^m x_i^T x_i - 2\Sigma_{i=1}^m z_i^T W^T x_i + \Sigma_{i=1}^m z_i^T z_i \\ & = \Sigma_{i=1}^m x_i^T x_i - 2\Sigma_{i=1}^m z_i^T z_i + \Sigma_{i=1}^m z_i^T z_i \\ & = \Sigma_{i=1}^m x_i^T x_i - \Sigma_{i=1}^m z_i^T z_i \\ & = \Sigma_{i=1}^m x_i^T x_i - \Sigma_{i=1}^m (W^Tx_i)^T (W^Tx_i) \\ & = \Sigma_{i=1}^m x_i^T x_i - \Sigma_{i=1}^m x_i^TWW^Tx_i \\ & = \Sigma_{i=1}^m x_i^T x_i - tr(W^T(\Sigma_{i=1}^m x_i x_i^T)W) \quad (上一步到这一步用到了tr(AB)=tr(BA))\\ & = \Sigma_{i=1}^m x_i^T x_i - tr(W^T X_i X_i^T W) \\ \end{align} \] 　　推导过程中，有点需要主要，我们记$W^TW=I$，因为$W$不是方阵，所以$WW^T$不一定是单位阵$I$，例如： \[ W = \begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ \end{pmatrix} \]

\[ W^TW = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \]

\[ WW^T = \begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \] 　　所以，注意到$\Sigma_{i=1}^mx_ix_i^T$是数据集的协方差矩阵，$W$的每一个向量$w_j$是标准正交基。而$\Sigma_{i=1}^m x_i^T x_i$是一个常量。最小化上式等价于： \[ argmin \quad -tr(W^T x_i x_i^T W) \\ s.t. W^TW=I \] 　　可以看出来，这其实就和最大化投影方差最后推导出来的式子一样了，用拉格朗日乘数就可以解决了。

算法流程

　　从两种推导方式我们可以看出，求样本$x_i$的$n'$维的主成分其实就是求样本集的协方差矩阵$XX^T$的前$n'$个特征值对应特征向量矩阵$W$，然后每个样本$x_i$投射到低维上，运用变换$z_i=W^Tx_i$，即达到降维的PCA目的，算法流程可以简单的分为以下几步：

对所有的样本进行中心化： $x_i=x_i−\frac{\Sigma_{j=1}^{m}x_j}{m}$
计算样本的协方差矩阵$XX^T$
对矩阵$XX^T$进行特征值分解
取出最大的$n'$个特征值对应的特征向量$(w_1,w_2,...,w_n′)$
将所有的特征向量标准化后，组成特征向量矩阵$W$。
对样本集中的每一个样本$x_i$，转化为新的样本$z_i=W^Tx_i$

PCA与SVD

　　 PCA其实就是将一个$m \times n$的矩阵$M$变换成一个$m \times r$的矩阵，这样就会使得本来有$n$个特征的，变成了有$r$个特征了（$r \lt n$)： \[ M_{m \times n} \times P_{n \times r} = \widetilde{M}_{m \times r} \] 　　如果你熟悉SVD的话，会发现PCA其实本质上与SVD很像，SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量，我们回顾一下SVD的式子，这里只考虑实数的情况，所以可以用转置代替伴随： \[ M_{m \times n} \approx U_{m \times r} \Sigma_{r \times r} V_{r \times n}^T \] 　　在矩阵的两边同时乘上一个矩阵$V$，由于$V$是一个正交的矩阵，所以$V$转置乘以$V$得到单位阵$I$，所以可以化成后面的式子： \[ M_{m \times n} V_{r \times n} \approx U_{m \times r} \Sigma_{r \times r} V_{r \times n}^T V_{r \times n} \\ M_{m \times n} V_{r \times n} \approx U_{m \times r} \Sigma_{r \times r} \] 　　对照前面PCA的式子来看，这里$V$其实就是$P$，也就是一个变化的向量，它对列进行压缩，将一个$m \times n$的矩阵压缩到一个$m \times r$的矩阵。
　　如果我们想对行进行压缩（在PCA的观点下，对行进行压缩可以理解为，将一些相似的样本点合并在一起，或者将一些没有太大价值的样本点去掉），同样我们写出一个通用的行压缩例子： \[ P_{r \times m} \times M_{m \times n} = \widetilde{M}_{r \times n} \] 　　对SVD来说也是一样的，我们对SVD分解的式子两边乘以$U^T$： \[ U_{r \times m}^T M_{m \times n} \approx \Sigma_{r \times r} V_{r \times n}^T \] 　　可以看出，其实 PCA 几乎可以说是对 SVD 的一个包装，如果我们实现了 SVD，那也就实现了 PCA 了，而且更好的地方是，有了 SVD，我们就可以得到两个方向的PCA，如果我们对 $A^TA$ 进行特征值的分解，只能得到一个方向的 PCA。

PCA与LDA

　　LDA 也用于降维，和 PCA 有很多相同，也有很多不同的地方，我们来比较一下它们的异同。

相同点

都对数据进行降维
都在降维时使用了矩阵特征分解的思想
都假设数据符合高斯分布

不同点

LDA是有监督的降维方法，而 PCA 是无监督的降维方法
LDA 降维最大降到类别数 $ N-1$的维数，而 PCA 没有这个限制
LDA除了可以用于降维，还可以用于分类
LDA 选择分类性能最好的投影方向，而 PCA 选择样本点投影具有最大方差的方向

KPCA

　　如果要将PCA用于非线性降维，我们可以对PCA进行核化，也就是核主成分分析（Kernelized PCA, KPCA）。
　　假定我们需要在高维特征空间中将数据投影到$\mathbf{W}=(\boldsymbol{w}_1,\cdots,\boldsymbol{w}_d)$确定的超平面上，则对于$\boldsymbol{w}_j$，有之前我们通过拉格朗日乘子推出来的式子： \[ \left(\sum_{i=1}^{m} \boldsymbol{z}_{i} \boldsymbol{z}_{i}^{\mathrm{T}}\right) \mathbf{W}=\lambda \mathbf{W} \] 　　其中$\boldsymbol{z}_i$是样本点$\boldsymbol{x}_i$在高维空间中的像，移项化简得： \[ \begin{aligned} \mathbf{W} &=\frac{1}{\lambda}\left(\sum_{i=1}^{m} \boldsymbol{z}_{i} \boldsymbol{z}_{i}^{\mathrm{T}}\right) \mathbf{W}\\ &=\sum_{i=1}^{m} \boldsymbol{z}_{i} \frac{\boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}}{\lambda} \\ &=\sum_{i=1}^{m} \boldsymbol{z}_{i} \boldsymbol{\alpha}_{i} \end{aligned} \] 　　其中$\boldsymbol{\alpha}_{i}=\frac{1}{\lambda} \boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}$是$\boldsymbol{\alpha}_i$的第$j$个分量，假设$\boldsymbol{z}_{i}=\phi\left(\boldsymbol{x}_{i}\right), i=1,2, \ldots, m$，若$\phi$能被显示地表达出来，则通过它将样本映射到高维特征空间，再在特征空间中实施PCA即可，因此前式可变为： \[ \left(\sum_{i=1}^{m} \phi\left(\boldsymbol{x}_{i}\right) \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}}\right) \mathbf{W}=\lambda \mathbf{W} \\ \mathbf{W}=\sum_{i=1}^{m} \phi\left(\boldsymbol{x}_{i}\right) \boldsymbol{\alpha}_{i} \] 　　然而，一般情况下我们不知道$\phi$的具体形式，因此引入核函数： \[ \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right) \] 　　带入前式，化简得： \[ \mathbf{K} \mathbf{A}=\lambda \mathbf{A} \] 　　其中$\mathbf{K}$是核矩阵，$(\mathbf{K})_{i j}=\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right), \mathbf{A}=\left(\boldsymbol{\alpha}_{1} ; \boldsymbol{\alpha}_{2} ; \ldots ; \boldsymbol{\alpha}_{m}\right)$，上式也就变成了特征分解问题，取$\mathbf{K}$最大的$d^{'}$个特征值对应的特征向量即可。
　　对新的样本$\boldsymbol{x}$，其投影后的第$j\left(j=1,2, \dots, d^{\prime}\right)$维坐标为： \[ \begin{aligned} z_{j} &=\boldsymbol{w}_{j}^{\mathrm{T}} \phi(\boldsymbol{x}) \\ &=\sum_{i=1}^{m} \alpha_{i}^{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi(\boldsymbol{x}) \\ &=\sum_{i=1}^{m} \alpha_{i}^{j} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}\right) \end{aligned} \] 　　其中$\boldsymbol{\alpha}_i$已经规范化过了，为获得投影后的坐标，KPCA需要所有样本求和，因此它的计算开销比较大。

Conclusion

　　PCA使一些最小的特征值的特征向量被舍弃了，这也是降维导致的结果。但舍弃这部分的信息往往也是必要的，一方面舍弃这部分信息之后能使得样本的采样密度增大，这也是降维的出发点之一。另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到去噪的效果。