PCA (principal component analysis)算法-526互联

一、 PCA算法

PCA(principal component analysis)是一种应用广泛的降维算法，其基本思想是想通过找到一个低维的“最具有代表性”的方向，并将原数据映射到这个低维空间中去，从而实现数据的降维。

1. 算法原理

我们先从二维数据简单说明，假设我们有n个二维数据组成的数据集\(D_{n\times 2}\)(如图)，现在我们想要将其映射到一维空间，并且我们的目的是尽可能保留信息。那问题是如何寻找这个主方向？假设我们的原数据集为\(X_{n\times m}\)(n为数据维度，m为数据个数)，那么上述问题就等价表述为：找到一个变换矩阵，将X从高维空间映射到低维空间中去，即：

\[Y_{k\times m} =A_{k\times n} X_{n\times m} \qquad \qquad (1) \]


图1. 二维PCA降维示意图（由于技术限制，本图映射并没有遵循投影规则）

我们首先先确定我们的优化目标，即什么情况下的映射能尽可能保留我们数据的信息，又或者说映射成的数据\(Y\)要满足什么条件？

1. redundancy (冗余)

假设在一个二维数据中，是否所有维度都应该保留？在图2中，我们对于几组不同的数据，很明显能看出，左侧图中\(r_{1},r_{2}\)两个维度相关性较弱，我们无法通过一个数据预测另一个数据值，所以这组数据具有低冗余性。对于右侧一组数据，很明显，\(r_{1},r_{2}\)具有十分强的相关关系，因此我们完全可以通过回归方程由一个数据值来预测另一个数据值，即该数据是只需要一个维度即可表示，故该数据是高度冗余的。

为此PCA的思想就是去除那些冗余的维度，让映射到的低维空间中，每个方向都具有低的相关性，从而使映射后的数据\(Y\)冗余程度大大减小，从而实现降维的目的。


图2. 来自两个单独的测量，\(r_{1}\)，\(r_{2}\) 的数据中可能存在冗余的情况。左图中的两个测量是不相关的，因为你不能从一个预测另一个。相反，右图中的两个测量高度相关，这意味着数据高度冗余。

2. 协方差矩阵

由概率论的知识我们知道，协方差可以用来描述两个变量之间的相关性。
协方差的定义为：

\[Cov(x,y) = \frac{\sum\limits_{i=1}^{n}(x_{i}-\bar{x})(y_{i}-\bar{y})}{n-1} \]

协方差越大，两个变量的相关性越强；协方差等于0，两个变量没有相关性。

对于一个零均值化后数据矩阵\(X_{n\times m}\)(m为数据个数，n为数据维度)，其协方差矩阵的定义为：

\[Cov(X) = \frac{1}{n-1}XX^{T} = \frac{1}{n-1} \left( \begin{matrix} Cov(x_{1},x_{1})\quad Cov(x_{1},x_{2}) \quad \cdots \\ Cov(x_{2},x_{1}) \quad Cov(x_{2},x_{2}) \quad \cdots \\ \cdots \\ Cov(x_{n},x_{1})\quad Cov(x_{n},x_{2}) \quad \cdots \end{matrix} \right) \]

其中协方差矩阵对角线上的元素是每个变量自身的方差，其他元素是两个变量之间的协方差。协方差矩阵反应了数据的噪声与信号，其中对角代表着信号值，其余代表着噪声。我们不仅希望噪声越小，还希望信号越大，即我们希望保留数据方差最大所代表的方向。
对于式（1），我们可以求得：\(Cov(X) = \frac{1}{m-1} XX^{T}\)，我们希望新数据集\(Y\)的数据维度之间没有冗余，即我们希望他们之间的协方差为0，因此\(Y\)的协方差矩阵是一个对角矩阵。

3. 算法推导

由上述已知Y的协方差矩阵为一个对角矩阵，即为\(\Lambda\)，由（1）及题意有：

\[Cov(Y) = \frac{1}{n-1 }AX(AX)^{T} = \frac{1}{n-1}AXX^{T}A = \Lambda \]

即:

\[ACov(X)A = \Lambda \]

由线性代数的知识我们知道，上式是一个对称矩阵的合同变换，其中对角阵\(\Lambda\)是其特征值组成的矩阵，\(A\)是其特征值对应特征向量所组成的矩阵。

综上我们得知，如果要将X映射到Y中，只需要选取最大特征值所对应的特征向量构成变换矩阵A，则可获得映射后的数据集Y。

4. 算法步骤

将数据集X零均值化
计算X的协方差矩阵，并进行特征值分解
选取k个最大的特征值所对应的特征向量，组成变换矩阵A
得到降维后的新数据Y=AX

2. 代码补充

补充的代码如下：

######### 需要你完成: #########  
# 1. 计算数据的均值向量mu  
mu = np.mean(X,axis=0)  
X = X - mu  
  
# 2. 计算数据的协方差矩阵S  
S = np.cov(X.T)  
  
# 3. 对S进行特征值分解，求得其特征值L以及对应的特征向量U  
L,U = np.linalg.eig(S)  
L = np.real(L)  
  
# 4. 选取L中前k个最大的特征值所对应的特征向量构成降维矩阵W  
idx = np.argsort(L)[::-1]  
W = U[:, idx[:k]]  
###############################