PCA算法推导

2019-05-26 本文已影响0人 zealscott

PCA理解与应用。

Motivation

PCA与Factor analysis非常相似，都是主要用于reduction data dimensions。但PCA的想法相比于Factor analysis更简单，实现起来也更加直观和容易（只需要算特征值）。
PCA tries to identify the subspace in which the data approximately lies.
一个很简单的例子是，我们的数据中可能存在很多属性是高度相关的，那么这些属性实际上是有冗余的，如果我们直接用原始数据进行训练，有可能会受到Curse of dimensionality，同时增大计算量，增加模型过拟合的程度。

算法流程

数据预处理

首先，我们需要对数据进行标准化：
$\begin{array}{l}{\text { 1. Let } \mu=\frac{1}{m} \sum_{i=1}^{m} x^{(i)}} \\ {\text { 2. Replace each } x^{(i)} \text { with } x^{(i)}-\mu} \\ {\text { 3. Let } \sigma_{j}^{2}=\frac{1}{m} \sum_{i}\left(x_{j}^{(i)}\right)^{2}} \\ {\text { 4. Replace each } x_{j}^{(i)} \text { with } x_{j}^{(i)} / \sigma_{j}}\end{array}$
这里让数据的每个维度的期望变为0，方差变为1，使得不同维度具有可比性。

推导

PCA有多种推导方式，最直观的方式是最大方差和最小平方误差。

最大方差理论

在信号处理中认为信号具有较大的方差，噪声有较小的方差，信噪比就是信号与噪声的方差比，越大越好。

一个直观的想法是，我们从 $m$ 维的feature space投影到 $m-1$ 维到feature subspace时，希望使得其方差能最大化的得到保留（也就是数据之间的差异性保留越多越好）

设投影到新的单位向量 $u$ 中，那么投影点和原点的距离是 $x^Tu$ 。我们的目标是求最佳的 $u$ ，使得投影后的样本点方差最大。

由于这些样本点（样例）的每一维特征均值都为 0，因此投影到 u 上的样本点（只有一个到原点的距离值）的均值仍然是 0。

因此我们只需要方差最大化，而方差就是投影点到原点的距离的平方和：
$\begin{aligned} \frac{1}{m} \sum_{i=1}^{m}\left(x^{(i)^{T}} u\right)^{2} &=\frac{1}{m} \sum_{i=1}^{m} u^{T} x^{(i)} x^{(i) T} u \\ &=u^{T}\left(\frac{1}{m} \sum_{i=1}^{m} x^{(i)} x^{(i)^{T}}\right) u \end{aligned}$
可以通过简单的Lagrange变换，得到目标函数的最大值就等于求最大的特征向量。

因此，我们只需要对协方差矩阵进行特征值分解，得到的前 k 大特征值对应的特征向量就是最佳的 k 维新特征，而且这 k 维新特征是正交的。得到前 k 个 u 以后，样例 $X^{(i)}$ 通过以下变换可以得到新的样本。
$y^{(i)}=\left[ \begin{array}{c}{u_{1}^{T} x^{(i)}} \\ {u_{2}^{T} x^{(i)}} \\ {\vdots} \\ {u_{k}^{T} x^{(i)}}\end{array}\right] \in \mathbb{R}^{k}$
通过选取最大的 k 个 u，使得方差较小的特征（如噪声）被丢弃。

最小平方误差理论

回想我们最开始学习的线性回归等，目的也是求一个线性函数使得直线能够最佳拟合样本点，那么我们能不能认为最佳的直线就是回归后的直线呢？回归时我们的最小二乘法度量的是样本点到直线的坐标轴距离。

我们打算选用另外一种评价直线好坏的方法，使用点到直线的距离 d’来度量。

将样本点 $x_k$ 在直线上的投影记为 $x_k^{'}$ ，那么我们就是要最小化
$\sum_{\mathrm{k}=1}^{n}\left\|\left(\mathrm{x}_{k}^{\prime}-x_{\mathrm{k}}\right)\right\|^{2}$
这个公式称作最小平方误差（Least Squared Error）。

而确定一条直线，一般只需要确定一个点，并且确定方向即可。（推导可参考这里）

应用

PCA 将 n 个特征降维到 k 个，可以用来进行数据压缩，如果 100 维的向量最后可以用 10 维来表示，那么压缩率为 90%。同样图像处理领域的 KL 变换使用 PCA 做图像压缩。但 PCA 要保证降维后，还要保证数据的特性损失最小。
可用于数据预处理，减少feature space的大小，从而减少运算，减少overfitting。
可用于noise reduction algorithm。
Match/define better calculation
- 例如在人脸相似度匹配中，一个图像中属于人脸的并不是主要部分，而大部分都是噪声，因此我们可以使用PCA降维，使得某些维度能够衡量脸的形状大小等等。
- 在计算相似度时，将两个图像通过PCA投影到子空间，再通过距离度量。

总结

PCA 的思想是将 n 维特征映射到 k 维上（k<n），这 k 维是全新的正交特征。这 k 维特征称为主元，是重新构造出来的 k 维特征，他们能从方差的角度最大化的保留数据存在的差异，并减少维度。
PCA 技术的一个很大的优点是，它是完全无参数限制的。在 PCA 的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。
- 但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。
有时数据的分布并不是满足高斯分布。如图表 5 所示，在非高斯分布的情况下，PCA 方法得出的主元可能并不是最优的。在寻找主元时不能将方差作为衡量重要性的标准。

Reference

A TUTORIAL ON PRINCIPAL COMPONENT ANALYSIS
CS229 notes10
http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/PCAMissingData.pdf