PCA and Its Applications

书接上回,讲一下PCA。 PCA（Principal Components Analysis）,主成分分析。它是人脸识别、图像压缩中一项重要的工具技巧，作用是在高维（多属性）数据集中找到隐含的模式，利用这些隐含的模式来代表原来的高维数据，从而达到数据简化的目的。首先明确一点，PCA的数据集是无标签的，也就是无所谓分类，属于无监督学习，这一点跟LDA还是有区别的。

对于PCA的原理，有两种解释，也就有两个数学推导。一是找到一个线性投影，使投影后的维数下降，且数据差异最大（保留原数据的多样性）;二是保证投影损失最小，即原数据点与投影后的数据点距离平方和最小。下面，介绍下一。

1.简述

数据的多样性在统计上的对应便是方差。假定我们找到了投影向量$u_{1}$，简单起见，它还是一单位向量,也即$u_{1}u_{1}^T = 1$.

那么投影前后的方差为

$$\frac{1}{N}\sum_{n=1}^N\left\{u_{1}^Tx_n-u_{1}^T\bar{x}\right\}^2 = u_{1}^TSu_1$$

其中S为

$$ S = \frac{1}{N}\sum_{n=1}^N(x_n - \bar{x})(x_n - \bar{x})^T $$

在加上单位向量与其转置乘积为1的限定，考虑使用拉格朗日算子

$$ U_{1}^TSu_1 + \lambda_1(1-u_{1}^Tu_1)$$

对其求导，这样便成为一个线性代数上求特征根的问题：$Su_1 = \lambda_1(1-u_{1}^Tu_1)$ 。

公式两边同时左乘以$u_{1}$,可以容易看出，$\lambda_1 = u_{1}^TSu_1$ 。

所以当选择一个最大的特征值对应的是其最大的方差，此时对应的特征向量就被成为主成分。每个特征特征向量为D × 1的列向量。选定K（K<=D）个较大特征值对应的特征向量U（D × K），作为投影向量。那么原数据经过投影后的数据便为 $X' = X × U$。

总结一下，PCA的实施步骤为：

1.数据集减去平均值
2.计算协方差矩阵
3.求得协方差矩阵的特征值与特征向量
4.对特征值从大到小排序，选定要使用的特征值与特征向量
5.生成最终（降维后）数据

2.高维情况

就这样了么？理论上是可行的。可是对协方差矩阵求特征解的时候，会有难度。因为大多数情况下，数据的维度远远比数据的数量大，即 N << D。特别对于图像处理而言，一个像素对应着一个维度，因此维度会特别大，协方差矩阵也会随之膨大(D×D)，导致计算量激增(协方差矩阵的计算复杂度为$O(D^{3})$。这里有个trick,将原数据转置，这样将数据的列转换数据的数目N，对其进行特征值求解，然后将特征向量转化为原矩阵的特征向量。Bishop 的《Pattern Recognition and Machine Learning》给出了证明。

给出一数据集X（已经减除平均值），其大小为（N × D，N << D）。协方差矩阵即为 $S = N^{-1}X^{T}X$,根据上面求PCA的步骤，计算协方差矩阵的特征值，便有：

$N^{-1}X^{T}Xu_{i} = {\lambda}_{i}u_i $

稍微作下变形。两边同时左乘$X$,则有 $$N^{-1}XX^T(Xu{i}) = \lambda{i}(Xu_{i})$$ 注意到，$XX^T$是矩阵$X^T$协方差的表达。这是原数据的转置的协方差矩，大小N × N。对其分解，得到特征向量$v_i = Xu_i$ 同时，对上式两边再次左乘$X^T$,有

$$(N^{-1}X^TX)(X^Tv_i) = \lambda_{i}(X^Tv_i)$$

这不正是原始数据的分解矩阵么？！，可以看出 $X^Tv_i$ 正是其特征向量，它由原数据的转置$X^T$线性变换而来！

$$u_i = \frac{1}{(N\lambda_{i})^{½}}X^Tv_i$$

即利用转置后的特征向量$v_i$,进行某种线性变换，获得的结果与本身的特征向量相同。可是，却在特征分解的时候减少了计算量。

3.人脸识别

2中的知识其实已经说的很明白了，它解决了高维情况下矩阵分解问题，处理图像起来也就得心应手，一个简单的人脸鉴别便可做了。 步骤大致如下：

1.准备一个人脸不同照片，图片的大小务必一致。可以从网上的人脸库中提取一些;

2.加载训练图片，获得原始数据X(N × D)。根据2中步骤，获得K个投影向量$u_i$;

3.加载新图片，计算投影后向量X'(1 × K);

4.计算与训练图片的投影距离，平均距离在阈值内则认为是该类。