【CS231n】斯坦福大学李飞飞视觉识别课程笔记

数学原理推导和证明之类的大都一样，所以这里变身网络裁缝，借用网上的相应的博文等进行了总结，最后的最后只要知道是怎么回事就可以了。

一、引言

主成分分析（Principal Component Analysis，PCA）， 是一种统计方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。——百度百科

在许多领域的研究与应用中，通常需要对含有多个变量的数据进行观测，收集大量数据后进行分析和寻找规律。多变量、大数据集毫无疑问地会为研究和应用提供丰富的信息，但是也在一定程度上增加了数据采集的工作量。更重要的是在很多情形下，许多变量之间可能存在相关性，从而增加了问题分析的复杂性。如果分别对每个指标进行分析，分析往往是孤立的，不能完全利用数据中的信息，因此盲目减少指标会损失很多有用的信息，从而产生错误的结论。

因此需要找到一种合理的方法，在减少需要分析的指标同时，尽量减少原指标包含信息的损失，以达到对所收集数据进行全面分析的目的。由于各变量之间存在一定的相关关系，因此可以考虑将关系紧密的变量变成尽可能少的新变量，使这些新变量是两两不相关的，那么就可以用较少的综合指标分别代表存在于各个变量中的各类信息。主成分分析(PCA)与因子分析(FA)就属于这类降维算法。

说到降维，降维就是一种对高维度特征数据预处理方法。降维是将高维度的数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度的目的。在实际的生产和应用中，降维在一定的信息损失范围内，可以为我们节省大量的时间和成本。降维也成为应用非常广泛的数据预处理方法。

降维具有如下一些优点：

1. 使得数据集更易使用。
2. 降低算法的计算开销。
3. 去除噪声。
4. 使得结果容易理解。

降维的算法有很多，除了上面提到的主成分分析(PCA)与因子分析(FA)，还有像奇异值分解(SVD)、独立成分分析(ICA)等。

二、PCA原理详解

2.1、PCA的概念

PCA英文全称 Principal Component Analysis，即主成分分析，是一种使用最广泛的数据降维算法。PCA的主要思想是将n维特征映射到k维上，这k维是全新的正交特征也被称为主成分，是在原有n维特征的基础上重新构造出来的k维特征。

PCA的工作就是从原始的空间中按照一定的顺序地找一组相互正交的坐标轴，把数据从原来的坐标系转换到新的坐标系，新的坐标轴的选择与数据本身是密切相关的，也就是由数据本身决定的。转换坐标系时，以方差最大的方向作为坐标轴方向，因为数据的最大方差给出了数据的最重要的信息。

其中，第一个新坐标轴选择是原始数据中方差最大的方向；第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的；第三个轴是与第1，2个轴正交的平面中方差最大的；依次类推，可以得到若干个这样的坐标轴，重复次数为原始数据的特征维数。

通过这种方式获得的新的坐标轴，我们发现，大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为0。于是，我们可以忽略余下的坐标轴，只保留前面k个含有绝大部分方差的坐标轴。事实上，这相当于只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为0的特征维度，实现对数据特征的降维处理。

我们如何得到这些包含最大差异性的主成分方向呢？

事实上，通过计算数据矩阵的协方差矩阵，然后得到协方差矩阵的特征值及特征向量，选择特征值最大（也即包含方差最大）的N个特征所对应的特征向量组成的矩阵，我们就可以将数据矩阵转换到新的空间当中，实现数据特征的降维（N维）。

2.2、线性变换

一个矩阵与一个列向量A相乘，得到一个新的列向量B，则称该矩阵为列向量A到列向量B的线性变换。我们希望投影后投影值尽可能分散，而这种分散程度，可以用数学上的方差来表述：

$\operatorname{Var}(a)=\frac{1}{m} \sum_{i=1}^{m}\left(a_{i}-\mu\right)^{2}$Var(a)=m1​i=1∑m​(ai​−μ)2

即寻找一个一维基，使得所有数据变换为这个基上的坐标表示后，方差值最大。为什么要方差越大呢？因为方差越大，说明数据越分散。通常认为，数据的某个特征维度上数据越分散，该特征越重要。

对于更高维度，还有一个问题需要解决，考虑三维降到二维问题。与之前相同，首先我们希望找到一个方向使得投影后方差最大，这样就完成了第一个方向的选择，继而我们选择第二个投影方向。如果我们还是单纯只选择方差最大的方向，很明显，这个方向与第一个方向应该是“几乎重合在一起”，显然这样的维度是没有用的，因此，应该有其他约束条件——就是正交。为什么要正交呢？从直观上说，让两个降维后的样本的特征轴尽可能表示更多的原始信息，我们是不希望它们之间存在（线性）相关性的，因为相关性意味着两个降维后的样本的特征轴不是完全独立，必然存在重复表示的信息。

数学上可以用两个降维后的样本的特征轴的协方差表示其相关性：

$\operatorname{Cov}(a, b)=\frac{1}{m} \sum_{i=1}^{m}\left(a_{i}-\mu_{a}\right)\left(b_{i}-\mu_{b}\right)$Cov(a,b)=m1​i=1∑m​(ai​−μa​)(bi​−μb​)

当协方差为0时，表示两个降维后的样本的特征轴线性不相关。

2.3、协方差

在统计学上，协方差用来刻画两个随机变量之间的相关性，反映的是变量之间的二阶统计特性。考虑两个随机变量 $X_{i} 和X_{j}$Xi​和Xj​ ，它们的协方差定义为：

$\operatorname{cov}\left(X_{i}, X_{j}\right)=E\left[\left(X_{i}-E\left(X_{i}\right)\right)\left(X_{j}-E\left(X_{j}\right)\right)\right]$cov(Xi​,Xj​)=E[(Xi​−E(Xi​))(Xj​−E(Xj​))]

$\operatorname{cov}\left(X_{i}, X_{j}\right)=\frac{1}{n-1} \sum_{i=1}^{n}\left(x_{i}-\overline{x}\right)\left(y_{i}-\overline{y}\right)$cov(Xi​,Xj​)=n−11​i=1∑n​(xi​−x)(yi​−y​)

样本均值：

$\overline{x}=\frac{1}{n} \sum_{i=1}^{N} x_{i}$x=n1​i=1∑N​xi​

样本方差：

$S^{2}=\frac{1}{n-1} \sum_{i=1}^{n}\left(x_{i}-\overline{x}\right)^{2}$S2=n−11​i=1∑n​(xi​−x)2

我们只讨论离散型随机变量的情形下，独立、不相关与协方差为零三者的关系：

独立：随机变量 $\xi ,\eta$ξ,η 独立是指对于任意的常数a,b，都有$P(\xi=a, \eta=b)=P(\xi=a) \cdot P(\eta=b)$P(ξ=a,η=b)=P(ξ=a)⋅P(η=b)。

相关性：相关系数是$\rho_{\xi \eta}=\frac{\operatorname{cov}(\xi, \eta)}{\sqrt{\operatorname{var}(\xi)}\sqrt{\operatorname{var}(\eta)}}$ρξη​=var(ξ)​var(η)​cov(ξ,η)​，相关系数其实是“线性相关系数”。

相关系数和协方差在描述相关性方面是等价的，但独立与相关性的关系是：独立一定不相关，不相关不一定独立。

协方差矩阵：假设有m个变量，特征维度为2，$a_{1}$a1​表示变量1的a特征。那么构成的数据集矩阵为：
$X=\left( \begin{array}{llll}{a_{1}} & {a_{2}} & {\dots} & {a_{m}} \\ {b_{1}} & {b_{2}} & {\ldots} & {b_{m}}\end{array}\right)$X=(a1​b1​​a2​b2​​……​am​bm​​)

再假设它们的均值都是0，对于有两个均值为0的m维向量组成的向量组，

$\frac{1}{m} X X^{T}=\left( \begin{array}{ccc}{\frac{1}{m} \sum_{i=1}^{m} a_{i}^{2}} & {\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i}} \\ {\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i}} & {\frac{1}{m} \sum_{i=1}^{m} b_{i}^{2}}\end{array}\right)$m1​XXT=(m1​∑i=1m​ai2​m1​∑i=1m​ai​bi​​m1​∑i=1m​ai​bi​m1​∑i=1m​bi2​​)

可以发现对角线上的元素是两个降维后的样本的特征轴的方差，其他元素是两个降维后的样本的特征轴的协方差，两者都被统一到了一个矩阵——协方差矩阵中。

PCA算法的目标：方差max，协方差min。

要达到PCA降维目的，等价于将协方差矩阵对角化：即除对角线外的其他元素化为0，并且在对角线上将元素按大小从上到下排列，这样我们就达到了优化目的。

设原始数据矩阵X对应的协方差矩阵为C，而P是一组基按行组成的矩阵，设Y=PX，则Y为X对P做基变换后的数据。设Y的协方差矩阵为D，我们推导一下D与C的关系：

$D=\frac{1}{m} Y Y^{T}=\frac{1}{m}(P X)(P X)^{T}=\frac{1}{m} P X X^{T} P^{T}=P\left(\frac{1}{m} X X^{T}\right) P^{T}=P C P^{T}$D=m1​YYT=m1​(PX)(PX)T=m1​PXXTPT=P(m1​XXT)PT=PCPT

想让原始数据集X =>pca成数据集Y，使得Y的协方差矩阵是个对角矩阵。由上述推导可得，若有矩阵P能使X的协方差矩阵对角化，则P就是我们要找的PCA变换。

优化目标变成了寻找一个矩阵$P$P，满足$P C P^{T}$PCPT是一个对角矩阵，并且对角元素按从大到小依次排列，那么$P$P的前$K$K行就是要寻找的基，用$P$P的前前$K$K行组成的矩阵乘以$X$X就使得$X$X从$N$N维降到了$K$K维并满足上述优化条件。

2.4、矩阵对角化

首先，原始数据矩阵X的协方差矩阵C是一个实对称矩阵，它有特殊的数学性质：实对称矩阵不同特征值对应的特征向量必然正交；设特征值λ \lambdaλ重数为r，则必然存在r个线性无关的特征向量对应于λ \lambdaλ，因此可以将这r个特征向量单位正交化。

一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量，设这n个特征向量为 $e_{1}, e_{2}, \ldots, e_{n}$e1​,e2​,…,en​ ，我们将其按列组成矩阵：

$E=\left(e_{1} e_{2} \ldots e_{n}\right)$E=(e1​e2​…en​)

则对协方差矩阵C有如下结论：

$P=E^{T}$P=ET

P是协方差矩阵的特征向量单位化后按行排列出的矩阵，其中每一行都是C的一个特征向量。如果设P按照中特征值的从大到小，将特征向量从上到下排列，则用P的前K行组成的矩阵乘以原始数据矩阵X，就得到了我们需要的降维后的数据矩阵Y。

特征值λ \lambdaλ为什么要从大到小排列，为什么要选较大的 $\lambda$λ ？？？

因为我们协方差矩阵的对角线元素是方差，我们想要找方差交大的特征维度，所以要选择较大的对角线元素。而对角矩阵 $\Lambda$Λ 虽然是$C$C经过线性变化后的矩阵，但它在对角线上元素的大小关系没变，特征维度 $i$i 对应的特征值$\lambda_{i}$λi​越大，该维度上数据的方差越大。

2.5、特征值分解矩阵原理

(1) 特征值与特征向量

如果一个向量v是矩阵A的特征向量，将一定可以表示成下面的形式：
$A v=\lambda v$Av=λv
其中，λ是特征向量v对应的特征值，一个矩阵的一组特征向量是一组正交向量。

(2) 特征值分解矩阵

对于矩阵A，有一组特征向量v，将这组向量进行正交化单位化，就能得到一组正交单位向量。特征值分解，就是将矩阵A分解为如下式：
$A=Q \Sigma Q^{-1}$A=QΣQ−1
其中，Q是矩阵A的特征向量组成的矩阵，\Sigma则是一个对角阵，对角线上的元素就是特征值。

2.6、SVD分解矩阵原理

奇异值分解是一个能适用于任意矩阵的一种分解的方法，对于任意矩阵A总是存在一个奇异值分解：
$A=U \Sigma V^{T}$A=UΣVT
假设A是一个 $m*n$m∗n 的矩阵，那么得到的$U$U是一个 $m*m$m∗m 的方阵，$U$U里面的正交向量被称为左奇异向量。$Σ$Σ是一个$m*n$m∗n的矩阵，$Σ$Σ除了对角线其它元素都为0，对角线上的元素称为奇异值。$V^{T}$VT是$v$v的转置矩阵，是一个$n*n$n∗n的矩阵，它里面的正交向量被称为右奇异值向量。而且一般来讲，我们会将$Σ$Σ上的值按从大到小的顺序排列。

SVD分解矩阵A的步骤：

(1) 求$A A^{T}$AAT的特征值和特征向量，用单位化的特征向量构成 $U$U。

(2) 求$A^{T} A$ATA的特征值和特征向量，用单位化的特征向量构成 $V$V。

(3) 将$A A^{T}$AAT或者$A^{T} A$ATA的特征值求平方根，然后构成 $Σ$Σ。

2.6、另一种解释思路

该思路基于拉格朗日问题的求解方法。
回到一开始，$z=w^{T} x$z=wTx。其中，最主要的成分是这样的$w_{1}$w1​ ，样本投影到$w_{1}$w1​上之后最分散，使得样本点之间的差别变得最明显。为了得到唯一解且是该方向成为最重要的因素，我们要求$\left\|w_{1}\right\|=1$∥w1​∥=1。如果$z_{1}=w_{1}^{T} x$z1​=w1T​x且$\operatorname{Cov}(x)=\sum$Cov(x)=∑，则

$\operatorname{Var}\left(z_{1}\right)=E\left[\left(w^{T} x-w^{T} \mu\right)^{2}\right]=w_{1}^{t} \sum w_{1}$Var(z1​)=E[(wTx−wTμ)2]=w1t​∑w1​

寻找$w_{1}$w1​，使得$w_{1}$w1​在约束下最大化。将这写成拉格朗日问题，则有：

$\max _{w_{1}} w_{1}^{T} \sum w_{1}-\alpha\left(w_{1}^{T} w_{1}-1\right)$w1​max​w1T​∑w1​−α(w1T​w1​−1)

关于$w_{1}$w1​求导并让它等于0，有：

$2 \sum w_{1}-2 \alpha w_{1}=0$2∑w1​−2αw1​=0

因此，$\sum w_{1}=\alpha w_{1}$∑w1​=αw1​

如果$w_{1}$w1​ 是协方差矩阵$\sum$∑的特征向量，$a$a是对应的特征值，则上式成立。因为我们想最大化
$\operatorname{Var}\left(z_{1}\right)=w_{1}^{T} \sum w_{1}=\alpha w_{1}^{T} w_{1}=\alpha$Var(z1​)=w1T​∑w1​=αw1T​w1​=α
所以为了方差最大，我们选择具有最大特征值的特征向量。因此，主成分是输入样本的协方差矩阵的具有最大特征值$\lambda_{1}=\alpha$λ1​=α的特征向量。

第二个主成分$w_{2}$w2​也应该是最大化方差，具有单位长度，并且与$w_{1}$w1​正交。后一个要求是使得投影后$z_{2}=w_{2}^{T} x$z2​=w2T​x与$z_{1}$z1​不相关。对于第二个主成分，有
$\max _{u_{2}} w_{2}^{T} \sum w_{2}-\alpha\left(w_{2}^{T} w_{2}-1\right)-\beta\left(w_{2}^{T} w_{1}-0\right)$u2​max​w2T​∑w2​−α(w2T​w2​−1)−β(w2T​w1​−0)

最后，该式简化为$\sum w_{2}=\alpha w_{2}$∑w2​=αw2​，这表明$w_{2}$w2​应该是$\sum$∑的具有第二大特征值$\lambda_{2}=\alpha$λ2​=α特征向量。类次的，我们可以证明其他维被具有递减特征值的特征向量给出。

三、PCA算法实现

算法应用的实例在如下参考文章中：

机器学习实战之PCA
图文并茂的PCA教程
主成分分析（PCA）原理详解
【机器学习】主成分分析详解