机器学习算法原理篇之PCA主成分分析

2018-10-26 本文已影响39人 TuringWong

首先要特别感谢刘建平Pinard老师(https://www.cnblogs.com/pinard/)，刘建平Pinard老师是个大神，本文是在他主成分分析（PCA）原理总结这篇博文的基础上加了一些自己的理解以及部分细节的推导而成。

1. PCA概述

1.1 什么是主成分分析？

主成分分析（Principal components analysis，以下简称PCA）是最重要的降维方法之一。在数据压缩消除冗余和数据噪音消除等领域都有广泛的应用。主成分分析的好处是使要分析的数据的维度降低了，但是数据的主要信息还能保留下来，并且，这些变换后的维两两不相关！

1.2 PCA的思想

对于任意给定的一组多维数据，它所代表的信息量是一定。数据代表的信息总量等于数据在各位维度分量上的信息之和，而与所选取的坐标系无关。但是同一组数据在维数相同的不同的坐标系下，各维度所代表的信息量的分布却存在差异。主成分分析的目的是通过转换坐标空间，使得数据所代表的的信息尽可能集中地分布在较少数量的维度上，从而可以只选择占有较多信息的坐标维度，达到数据降维的目的。

PCA顾名思义，就是找出数据里最主要的方面，用数据里最主要的方面来代替原始数据。具体的，假如我们的数据集是n维的，共有m个数据 $(x(1),x(2),...,x(m))$ 。我们希望将这m个数据的维度从n维降到n'维，希望这m个n'维的数据集尽可能的代表原始数据集。我们知道数据从n维降到n'维肯定会有损失，但是我们希望损失尽可能的小。

我们先看看最简单的情况，也就是 $n=2$ ， $n^{'}=1$ ,也就是将数据从二维降维到一维。数据如下图。我们希望找到某一个维度方向，它可以代表这两个维度的数据。

二维数据方向

接下来，我们面临两个问题：

如何找到最优的维度方向？

对于这点，我想好多人都有经验，这不就是以前用最小二乘法拟合数据时做的事情吗！对，最小二乘法求出来的直线（二维）的方向就是 $u_1$ 的方向！那 $u_2$ 的方向呢？因为这里是二维情况，所以 $u_2$ 方向就是跟 $u_1$ 垂直的方向，对于高维数据，怎么知道 $u_1$ 、 $u_2$ 的方向？
为什么最优维度方向比其它方向好？

从直观上也可以看出， $u_1$ 比 $u_2$ 好。为什么 $u_1$ 比 $u_2$ 好呢？可以有两种解释，第一种解释是样本点到这个直线的距离足够近，第二种解释是样本点在这个直线上的投影能尽可能的分开。

2. PCA推导

如何找到最优维度方向是主成分分析要解决的问题，对于维度方向优劣的衡量指标可以从上节问题二得到启发，这里我们主要从第二种解释入手，即对样本点在这个直线上的投影能尽可能的分开来量化。我们知道方差一定程度上反映了数据的分散程度，而数据分散程度从一定程度也代表了数据所携带的信息量，因此我们可以考虑比较数据在不同维度上的投影方差来选择最优维度方向。

2.1 PCA推导：基于最大投影方差

假设给定m个n维数据 $Y=(y_1,y_2,...,y_m)$ ,投影变换后新的坐标系空间为 $W=(w_1,w_2,...,w_n)$

2.1.1 数据中心化

一方面，不同特征量纲的差异会导致不同特征的方差存在先天差异，而数据中心化在一定程度上可以消除这种先天差异；另一方面数据中心化不会改变数据本身的形状，但可以大大降低计算量。数据中心化具体操作如下：
$X=(x_1,x_2,...,x_m)=(y_1-\mu,y_2-\mu,...,y_m-\mu)$
其中 $\mu=\frac{1}{m}\sum_{i=1}^{m}y_i$ ,从而 $\sum_{i=1}^{m}x_i=0$

变换坐标空间，数据在新坐标系W下的坐标如下：
$W^TX=(W^Tx_1,W^Tx_2,...,W^Tx_m)$
样本点 $x_i$ 在新的坐标系中的坐标为 $z_i=(w_1^Tx_i,w_2^Tx_i,...,w_n^Tx_i,)$

则数据在新坐标空间下也是中心化的，具体如下：
$\sum_{i=1}^{m}w_j^Tx_i=w_j^T\sum_{i=1}^{m}x_i=0$
其中 $j={1,2...,n}$

2.1.2 求解第一主轴（投影方差最大的维度方向）

不失一般性，假设 $w_1$ 为第一主轴方向，由于数据在 $w_1$ 轴下是中心化了的，因此样本数据在 $w_1$ 上的均值为0，即样本数据在 $w_1$ 轴的投影方差表达式如下：
$Var_{w_1}=\frac{1}{m}\sum_{i=1}^{m}(w_1^Tx_i)^2=\frac{1}{m}\sum_{i=1}^{m}x_i^Tw_1w_1^Tx_i=\frac{1}{m}\sum_{i=1}^{m}w_1^Tx_ix_i^Tw_1$
由于求和项与 $w_1$ 无关，所以
$Var_{w_1}=\frac{1}{m}w_1^T(\sum_{i=1}^{m}x_ix_i^T)w_1$
注意，其实括号里面是一个矩阵乘以自身的转置,即：
$\sum_{i=1}^{m}x_ix_i^T=XX^T$
所以
$Var_{w_1}=\frac{1}{m}w_1^TXX^Tw_1$
如果没有前面的1/n，那就是就是一个标准的二次型！可以证明 $XX^T$ 为一个半正定矩阵（证明略：证明所有特征值大于等于0即可），半正定矩阵存在最大值！

到此，主轴投影方差最大化问题可以抽象为以下模型：
$max Var_{w_1}=w_1^TXX^Tw_1\\ s.t. w_1^Tw_1=1$

2.1.3 模型求解

方法1：拉格朗日乘数法

等式约束的极值问题可以通过拉格朗日乘数法求解，构造拉格朗日函数如下：
$f(w_1,\lambda) = w_1^TXX^Tw_1+\lambda(1-w_1^Tw_1)$
上式对 $w_1$ 求导（涉及到矩阵求导的相关知识，请自行补充相关的知识点）如下：
$df(w_1,\lambda)=d(w_1^TXX^Tw_1)+d(\lambda(1-w_1^Tw_1))=dw_1^T(XX^Tw_1)+w_1^Td(XX^Tw_1)-\lambda{d(w_1^Tw_1)}$
$\Downarrow$
$df(w_1,\lambda)=<dw_1,XX^Tw_1>+<XX^Tw_1,dw_1>+\lambda(<dw_1,w_1>+<w_1,dw_1>)$
$\Downarrow$
$df(w_1,\lambda)=<2XX^Tw_1-2\lambda{w_1},dw_1>$
$\Downarrow$
$\frac{\partial f}{\partial w_1}=2XX^Tw_1-2\lambda{w_1}=0$
显然， $w_1$ 即为 $XX^T$ 特征值对应的特征向量！ $XX^T$ 的所有特征值和特征向量都满足上式，那么将上式代入目标函数表达式即可得到
$Var_{w_1}=\frac{1}{m}w_1^TXX^Tw_1=\frac{1}{m}\lambda{w_1^Tw_1}=\frac{1}{m}\lambda$
所以，第一主轴方向即为第一大特征值对应的特征向量方向。第二主轴方向为第二大特征值对应的特征向量方向，以此类推，证明类似。
求出 $\lambda$ 之后，顺序可求得相应的坐标维度，具体策略如下：
1）对于重根 $\lambda$ ，对应的特征向量需要先进行Schimidt正交，然后再进行单位化；
2）对于单根 $\lambda$ ，对应的特征向量直接进行单位化即可；
方法2：奇异值法
具体见引用文章2

2.2 PCA推导：基于小于投影距离

具体见引用文章1

3. PCA算法流程

从上面两节我们可以看出，求样本 $x(i)$ 的 $n^{'}$ 维的主成分其实就是求样本集的协方差矩阵(注意协方差矩阵只和 $XX^T$ 隔了1/m)的前n'个特征值对应特征向量矩阵,并将其标准正交化，得到正交矩阵W，然后对于每个样本 $x_i$ ,做如下变换 $z_i=W^Tx_i$ ，即达到降维的PCA目的。

下面我们看看具体的算法流程。
输入：n维样本 $D=(x_1,x_2,...,x_m)$ ，要降维到的维数 $n^{'}$
输出：降维后的n维样本 $D^{'}$

对所有的样本进行中心化： $x_i=x_i−\frac{1}{m}\sum_{i=1}^{m}x_i$
计算样本的协方差矩阵 $\frac{1}{m}XX^T$
求解矩阵 $\frac{1}{m}XX^T$ 的特征值、
取出最大的n'个特征值对应的特征向量(w1,w2,...,wn′), 将所有的特征向量标准化后，组成特征向量矩阵W。
对样本集中的每一个样本 $x_i$ ,转化为新的样本 $z_i=W^Tx_i$
得到输出样本集 $D^{'}=(z_1,z_2,...,z_m)$

有时候，我们不指定降维后的n'的值，而是换种方式，指定一个降维到的主成分比重阈值t。这个阈值t在（0,1]之间。假如我们的n个特征值为λ1≥λ2≥...≥λn,则n'可以通过下式得到:
$\frac{\sum_{i=1}^{n^{'}}\lambda_i}{\sum_{i=1}^{n}\lambda_i}\geq{t}$

4. PCA算法总结

这里对PCA算法做一个总结。作为一个非监督学习的降维方法，它只需要特征值分解，就可以对数据进行压缩，去噪。因此在实际场景应用很广泛。为了克服PCA的一些缺点，出现了很多PCA的变种，比如为解决非线性降维的KPCA，还有解决内存限制的增量PCA方法Incremental PCA，以及解决稀疏数据降维的PCA方法Sparse PCA等。

优点
1. 仅仅需要以方差衡量信息量，不受数据集以外的因素影响。
2. 各主成分之间正交，可消除原始数据成分间的相互影响的因素。
3. 计算方法简单，主要运算是特征值求解，易于实现。
缺点
1. 主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强。
2. 方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。

5. 参考文章

1. 刘建平-主成分分析（PCA）原理总结
 2. 止战-主成分分析(PCA)原理及推导
 3. 倚楼-矩阵求导浅析（一）