PCA原理详解

1 简介2 详细原理2.1 特征值和特征向量2.2 奇异值分解(SVD)2.2.1 SVD定义2.2.2 SVD举例2.2.3 SVD性质 2.3 PCA实现方法2.3.1 基于特征值分解协方差矩阵实现PCA算法2.3.2 基于SVD分解协方差矩阵实现PCA算法 3 总结

1 简介

  在机器学习中我们都知道，有时候训练样本的特征太多也并非是好事，由于各特征之间存在一定的相关关系，从而增加了问题分析的复杂性。因此可以考虑将关系紧密的变量变成尽可能少的新变量，使这些新变量是两两不相关的，那么就可以用较少的综合指标分别代表存在于各个变量中的各类信息。将n维的特征映射到k维，再用k维特征进行模型的预测。 降维具有如下一些优点： （1）使得数据集更易使用。 （2）降低算法的计算开销。 （3）去除噪声。 （4）使得结果容易理解。   降维的算法有很多，比如奇异值分解(SVD)、主成分分析(PCA)、因子分析(FA)、独立成分分析(ICA)。PCA（Principal Components Analysis），就是其中的最常用的降维方法之一。

2 详细原理

  为了实现将n维的特征映射到k维，这全新的k维正交的特征就被称为主成分。PCA就是从原始n维空间中顺序地找出一组k维正交的坐标轴，原始空间总的所有点可以在新的空间中表示出来，其实就相当于空间向量的坐标变换。   具体步骤是：第1个新坐标轴选择原始数据中方差最大的方向，第2个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的方向，第3个轴是与第1,2个轴正交的平面中方差最大的方向。依次类推，通过这种方式可以得到n个坐标轴，但其中大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为0。于是，我们可以忽略余下的坐标轴，只保留前面k个含有绝大部分方差的坐标轴。事实上，这相当于只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为0的特征维度，实现对数据特征的降维处理。   因此，如何得到这些包含最大差异性的主成分方向呢？   答案是这样的，首先计算数据矩阵的协方差矩阵，然后得到协方差矩阵的特征值特征向量，选择特征值最大(即方差最大)的k个特征所对应的特征向量组成的矩阵。这样就可以将数据矩阵转换到新的空间当中，实现数据特征的降维。 在详细讲述之前，先要讲一些基本的数学知识。

2.1 特征值和特征向量

  如果一个向量$v$是矩阵$A$的特征向量，则满足： $$Av=\lambda v$$   其中，$\lambda$是特征值，向量$v$是$\lambda$对应的特征向量。不同特征值之间的特征向量是两两正交。两个矩阵相乘$A\times B$的意义是对矩阵$A$进行了拉升或旋转的操作，而这里表示$A$在$v$的方向上进行了拉升或压缩操作，$\lambda$反应了拉升或压缩的程度，特征值的方向是变化程度最大的方向。   对于矩阵$A$，有一组特征向量$v$，将这组向量进行正交化单位化，就能得到一组正交单位向量。特征值分解，就是将矩阵A分解为如下式： $$A=Q\Sigma Q^{-1}$$   其中，$Q$是矩阵$A$的特征向量组成的矩阵，是$A$的一个极大线性无关组，$\Sigma$则是一个对角阵，对角线上的元素就是特征值。   一般我们会把$Q$的这n个特征向量标准化，即满足$||v_i|{|}^2=1$, 或者说$v_i^T{v}_i=1$，此时$Q$的n个特征向量为标准正交基，满足$Q^{T}Q=I$，即$Q^T=Q^{-1}$, 也就是说$Q$为酉矩阵。这样特征分解的表达式可以写成： $$A=Q\Sigma Q^T$$   注意到要进行特征分解，矩阵$A$必须为方阵。那么如果$A$不是方阵，即行和列不相同时，那还可以对矩阵进行分解吗？答案是可以，此时SVD登场了。

2.2 奇异值分解(SVD)

2.2.1 SVD定义

  奇异值分解（Singular Value Decomposition，SVD）是能对任意矩阵进行分解。对于任意矩阵A总是存在一个奇异值分解： $$A=U\Sigma V^T$$   其中$U$是一个$m\times m$的矩阵，$\Sigma$是一个$m\times n$的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，$V$是一个$n\times n$的矩阵。$U$和$V$都是酉矩阵，即满足$U^{T}U=I,V^{T}V=I$。下图可以很形象的看出上面SVD的定义：   那么我们如何求出SVD分解后的$U,\Sigma ,V$这三个矩阵呢？   如果我们将$A$的转置和$A$做矩阵乘法，那么会得到$n\times n$的一个方阵$A^{T}A$。既然$A^{T}A$是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式： $$(A^{T}A)v_i={\lambda }_i{v}_i$$   这样我们就可以得到矩阵$A^{T}A$的n个特征值和对应的n个特征向量$v$了。将$A^{T}A$的所有特征向量张成一个$n\times n$的矩阵$V$，$V{V}^T=V^{T}V=I$，就是我们SVD公式里面的$V$矩阵了。一般我们将$V$中的每个特征向量叫做$A$的右奇异向量。   如果我们将$A$和$A$的转置做矩阵乘法，那么会得到$m\times m$的一个方阵$A{A}^T$。既然$A{A}^T$是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式： $$(A{A}^T)u_i={\lambda }_i{u}_i$$   这样我们就可以得到矩阵$A{A}^T$的m个特征值和对应的m个特征向量$u$了。将$A{A}^T$的所有特征向量张成一个$m\times m$的矩阵$U$，$U{U}^T=U^{T}U=I$，就是我们SVD公式里面的$U$矩阵了。一般我们将$U$中的每个特征向量叫做A的左奇异向量。   $U$和$V$我们都求出来了，现在就剩下奇异值矩阵$\Sigma$没有求出了。由于$\Sigma$除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值${\sigma }_i$就可以了。 $$A=U\Sigma V^T\Rightarrow AV=U\Sigma V^{T}V\Rightarrow AV=U\Sigma$$$$\Rightarrow A(v_1,v_2,...,v_i)=(u_1,u_2,...,u_i)\left(\begin{array}{cccc}{\sigma }_1& 0& \cdots & 0\\ 0& {\sigma }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\sigma }_i\end{array}\right)$$$$\Rightarrow (A{v}_1,A{v}_2,...,A{v}_i)=({\sigma }_1{u}_1,{\sigma }_2{u}_2,...,{\sigma }_i{u}_i)\Rightarrow A{v}_i={\sigma }_i{u}_i\Rightarrow {\sigma }_i=A{v}_i/u_i$$   样我们可以求出我们的每个奇异值，进而求出奇异值矩阵$\Sigma$。   上面还有一个问题，为什么$A^{T}A$的特征向量组成的就是我们SVD中的$V$矩阵，而$A{A}^T$的特征向量组成的就是我们SVD中的$U$矩阵？我们可以证明，以$V$矩阵的证明为例： $$A=U\Sigma V^T\Rightarrow A^T=V{\Sigma }^T{U}^T\Rightarrow A^{T}A=V{\Sigma }^T{U}^{T}U\Sigma V^T=V{\Sigma }^2{V}^T$$   上式证明使用了:$U^{T}U=I,{\Sigma }^T\Sigma ={\Sigma }^2$。可以看出$A^{T}A$的特征向量组成的的确就是我们SVD中的$V$矩阵。类似的方法可以得到$A{A}^T$的特征向量组成的就是我们SVD中的$U$矩阵。 进一步还推导出： $$A^{T}A=V{\Sigma }^T{U}^{T}U\Sigma V^T=V{\Sigma }^2{V}^T$$$$A{A}^T=U\Sigma V^{T}V{\Sigma }^T{U}^T=U{\Sigma }^2{U}^T$$   由此可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系： $${\sigma }_i=\sqrt{{\lambda }_i}$$   这样也就是说，我们可以不用${\sigma }_i=A{v}_i/u_i$来计算奇异值，也可以通过求出$A^{T}A$和$A{A}^T$的特征值取平方根来求奇异值。

2.2.2 SVD举例

$$A=\left(\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right)$$   首先求出$A^{T}A$和$A{A}^T$ $$A^{T}A=\left(\begin{array}{ccc}0& 1& 1\\ 1& 1& 0\end{array}\right)\left(\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$$$$A{A}^T=\left(\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{ccc}0& 1& 1\\ 1& 1& 0\end{array}\right)=\left(\begin{array}{ccc}1& 1& 0\\ 1& 2& 1\\ 0& 1& 1\end{array}\right)$$   进而求出$A^{T}A$的特征值和特征向量： $${\lambda }_1=3;v_1=\left(\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right);{\lambda }_2=1;v_2=\left(\begin{array}{c}-1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right);$$   $A{A}^T$的特征值和特征向量： $${\lambda }_1=3;u_1=\left(\begin{array}{c}1/\sqrt{6}\\ 2/\sqrt{6}\\ 1/\sqrt{6}\end{array}\right);{\lambda }_2=1;u_2=\left(\begin{array}{c}1/\sqrt{2}\\ 0\\ -1/\sqrt{2}\end{array}\right);{\lambda }_3=0;u_3=\left(\begin{array}{c}1/\sqrt{3}\\ -1/\sqrt{3}\\ 1/\sqrt{3}\end{array}\right);$$   根据$A{v}_i={\sigma }_i{u}_i,i=1,2$求奇异值 $$\left(\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right)={\sigma }_1\left(\begin{array}{c}1/\sqrt{6}\\ 2/\sqrt{6}\\ 1/\sqrt{6}\end{array}\right)\Rightarrow {\sigma }_1=3$$$$\left(\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}-1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right)={\sigma }_2\left(\begin{array}{c}1/\sqrt{2}\\ 0\\ -1/\sqrt{2}\end{array}\right)\Rightarrow {\sigma }_2=1$$   当然，我们也可以用${\sigma }_i={\sqrt{\lambda }}_i$直接求出奇异值为$\sqrt{3}$和$1.最终得到$A$的奇异值分解为: $$A=U\Sigma V^T=\left(\begin{array}{ccc}1/\sqrt{6}& 1/\sqrt{2}& 1/\sqrt{3}\\ 2/\sqrt{6}& 0& -1/\sqrt{3}\\ 1/\sqrt{6}& -1/\sqrt{2}& 1/\sqrt{3}\end{array}\right)\left(\begin{array}{cc}\sqrt{3}& 0\\ 0& 1\\ 0& 0\end{array}\right)\left(\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ -1/\sqrt{2}& 1/\sqrt{2}\end{array}\right)$$

2.2.3 SVD性质

  对于奇异值，它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的$k$个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说： $$A_{m\times n}=U_{m\times m}{\Sigma }_{m\times n}{V}_{n\times n}^T\approx U_{m\times k}{\Sigma }_{k\times k}{V}_{k\times n}^T$$   其中$k$要比$n$小很多，也就是一个大的矩阵$A$可以用三个小的矩阵$U_{m\times k},{\Sigma }_{k\times k},V_{k\times n}^T$来表示。如下图所示，现在我们的矩阵$A$只需要灰色的部分的三个小矩阵就可以近似描述了。   SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。

2.3 PCA实现方法

2.3.1 基于特征值分解协方差矩阵实现PCA算法

  为什么我们还要用协方差呢？我们应该注意到，标准差和方差一般是用来描述一维数据的，但现实生活我们常常遇到含有多维数据的数据集，面对这样的数据集，我们当然可以按照每一维独立的计算其方差，但是通常我们还想了解这些维度之间的关系，这时，我们就要用协方差，协方差就是一种用来度量两个随机变量关系的统计量，其定义为： $$cov(X,Y)=\frac{{\Sigma }_{i=1}^n(X_i-X^{\prime })(Y-Y^{\prime })}{n}$$   协方差性质：$cov(X,X)=var(X),cov(X,Y)=cov(Y,X)$   需要注意的是，协方差也只能处理二维问题，那维数多了自然就需要计算多个协方差，比如n维的数据集就需要计算$\frac{n!}{(n-2)!\times 2}$个协方差，那自然而然的我们会想到使用矩阵来组织这些数据。给出协方差矩阵的定义： $$C_{n\times n}=(C_{i,j},C_{i,j}=cov(Di{m}_i,Di{m}_j))$$   假设数据集有$x,y,z$三个维度，则协方差矩阵为 $$C=\left(\begin{array}{ccc}cov(x,x)& cov(x,y)& cov(x,z)\\ cov(y,x)& cov(y,y)& cov(y,z)\\ cov(z,x)& cov(z,y)& cov(z,z)\end{array}\right)$$   可见协方差矩阵是一个对称的矩阵，而且对角线是各个维度上的方差。 假设原有的数据$X=(x_1,x_2,...,x_n)$，需要降到$k$维。

去平均值(即去中心化)，即每一位特征减去各自的平均值。计算协方差矩阵$A=\frac{1}{n}X{X}^T$求$A$的特征值和特征向量对特征值从大到小排序，选择其中最大的$k$个。然后将其对应的k个特征向量分别作为行向量组成特征向量矩阵$Q$。将数据转换到$k$个特征向量构建的新空间中，即$Y=QX$。

2.3.2 基于SVD分解协方差矩阵实现PCA算法

  假设原有的数据$X=(x_1,x_2,...,x_n)$，需要降到$k$维。

去平均值，即每一位特征减去各自的平均值。计算协方差矩阵。通过SVD计算协方差矩阵的特征值与特征向量。对特征值从大到小排序，选择其中最大的k个。然后将其对应的k个特征向量分别作为列向量组成特征向量矩阵。将数据转换到k个特征向量构建的新空间中。 在PCA降维中，我们需要找到样本协方差矩阵的最大$k$个特征向量，然后用这最大的$k$个特征向量组成的矩阵来做低维投影降维。可以看出，在这个过程中需要先求出协方差矩阵,当样本数多、样本特征数也多的时候，这个计算量还是很大的。

  当我们用到SVD分解协方差矩阵的时候，SVD有两个好处： 第一， 有一些SVD的实现算法可以先不求出协方差矩阵也能求出我们的右奇异矩阵$V$，这个方法在样本量很大的时候很有效。实际上，scikit-learn的PCA算法的背后真正的实现就是用的SVD，而不是特征值分解。 第二，注意到PCA仅仅使用了SVD的左奇异矩阵，没有使用到右奇异值矩阵，那么右奇异值矩阵有什么用呢？   假设我们的样本是$m\times n$的矩阵$X$，如果我们通过SVD找到了矩阵最大的$k$个特征向量组成的$k\times n$的矩阵 ,则我们可以做如下处理：   可以得到一个$m\times k$的矩阵$X^{\prime }$,这个矩阵和我们原来$m\times n$的矩阵$X$相比，列数从$n$减到了$k$，可见对列数进行了压缩。也就是说，左奇异矩阵可以用于对行数的压缩；右奇异矩阵可以用于对列(即特征维度)的压缩。这就是我们用SVD分解协方差矩阵实现PCA可以得到两个方向的PCA降维(即行和列两个方向)。

##Python实现PCA import numpy as np def pca(X, k): # k is the components you want # mean of each feature n_samples, n_features = X.shape mean = np.array([np.mean(X[:, i]) for i in range(n_features)]) # normalization norm_X = X - mean # scatter matrix scatter_matrix = np.dot(np.transpose(norm_X), norm_X) # Calculate the eigenvectors and eigenvalues eig_val, eig_vec = np.linalg.eig(scatter_matrix) eig_pairs = [(np.abs(eig_val[i]), eig_vec[:, i]) for i in range(n_features)] # sort eig_vec based on eig_val from highest to lowest eig_pairs.sort(reverse=True) # select the top k eig_vec feature = np.array([ele[1] for ele in eig_pairs[:k]]) # get new data data = np.dot(norm_X, np.transpose(feature)) return data X = np.array([[-1, 1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]]) print(pca(X, 1))

3 总结

  降维的目的是将高维度的数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度。本章主要介绍可了PCA两种方法的基本原理： 1 基于特征值分解协方差矩阵 2 基于SVD分解协方差矩阵

参考内容：https://blog.csdn.net/program_developer/article/details/80632779