PCA

主成分分析（PCA，Principle Component Analysis）就是在寻找使方差最大的方向，并在该方向上投影。(通常方差越大被视为越重要，方差也常常被称为能量)

$Y=A\left( X-\overline{X} \right)$

$Y$是PCA的输出，$a$是投影的方向矩阵，$X$是PCA的输入，$\overline{X}$是$X$的期望(通常也可以用均值代替$\overline{X}=\frac{1}{P}\sum_{i=1}^P{X_i}$）。

其中：$Y$是$M\times1$矩阵，$a$是$M\times N$矩阵，$X$和$\overline{X}$是$N \times1$矩阵。可以看出，PCA把$N$维的数据$X$投影到了以$a_i$为基向量的空间中得到$M$维的$Y$，完成降维。（$M<N$）

$A=\left[ \begin{array}{c} a_1\\ a_2\\ \vdots\\ a_M\\ \end{array} \right]$

PCA的推导

假设训练样本有$\left\{ X_i \right\} _{i=1\sim P}$，则$Y_i$可以写成：

$\begin{aligned} Y_i=\left[ \begin{array}{c} y_{i1}\\ y_{i2}\\ \vdots\\ y_{iM}\\ \end{array} \right] =\left[ \begin{array}{c} a_1\left( X_i-\overline{X} \right)\\ a_2\left( X_i-\overline{X} \right)\\ \vdots\\ a_M\left( X_i-\overline{X} \right)\\ \end{array} \right] \,\, \quad\quad \left( i=1\sim P \right) \end{aligned}$

由主成分的含义，$y_{i1}$有最大的方差，因此我们需要最大化 $var(y_{1})=\sum_{i=1}^P{\left( y_{i1}-\overline{y_{i1}} \right)^2}$。

又因为：

$\overline{y_{i1}}=\frac{1}{P}\sum_{i=1}^P{y_{i1}}=\frac{1}{P}\sum_{i=1}^P{a_i\left( X_i-\overline{X} \right)}=\frac{a_i}{P}\left( \sum_{i=1}^P{X_i}-P\overline{X} \right) =0$

所以有：

$\begin{aligned} var(y_{1})&=\sum_{i=1}^P{\left( y_{i1}-\overline{y_{i1}} \right) ^2}=\sum_{i=1}^P{y_{i1}^2}=\sum_{i=1}^P{\left[ a_1\left( X_i-\overline{X} \right) \right] ^2} \\ &=\sum_{i=1}^P{\left[ a_1\left( X_i-\overline{X} \right) \right] \left[ a_1\left( X_i-\overline{X} \right) \right] ^T} \\ &=a_1\sum_{i=1}^P{\left[ \left( X_i-\overline{X} \right) \left( X_i-\overline{X} \right) ^T \right]}a_1^T \\ &=a_1\varSigma a_1^T \end{aligned}$

其中$\varSigma =\sum_{i=1}^P{ \left( X_i-\overline{X} \right) \left( X_i-\overline{X} \right) ^T }$称为$X$的协方差矩阵。在上式中，我们不希望$y_{1}$的大小和$a_1$有关，因为$a_1$只是一个基向量，控制投影的方向，我们希望$a_1$是一个单位向量。因此，上述求最大值变成以下优化问题：

$\begin{aligned} &\max:\quad a_1\varSigma a_1^T \\ &s.t. \quad a_1a_1^T=\lVert a_1 \rVert ^2 =1 \end{aligned}$

解上面优化问题可以使用拉格朗日乘数法：

$\begin{aligned} &E\left( a_1 \right) =a_1\varSigma a_1^T-\lambda_1 \left( a_1a_1^T-1 \right) \\ &\frac{\partial E\left( a_1 \right)}{\partial a_1}=2\left( \varSigma a_1^T-\lambda_1 a_1^T \right) ^T=0 \end{aligned}$

得到：$\varSigma a_1^T=\lambda_1 a_1^T$（即$a_1^T$是$\Sigma$的特征向量，$\lambda_1$是对应的特征值）

目标函数变为：

$var(y_1)=a_1\varSigma a_1^T=\lambda_1 a_1a_1^T=\lambda_1$

则当$a_1$是$\Sigma$最大的特征值$\lambda_{1}$对应的特征向量时，$a_1$是此优化问题的解。

我们称$y_1=a_1\left( X-\overline{X} \right)$为$X$的第一主成分，$a_1$是$\Sigma$最大的特征值$\lambda_{1}$对应的特征向量。

我们接着求$a_2$，我们希望求出的主成分之间是不相关的，即：

$\begin{aligned} cov\left( y_1,y_2 \right) &=\sum_i^P{\left( y_{i1}-\overline{y_{i1}} \right) \left( y_{i2}-\overline{y_{i2}} \right)}=\sum_i^P{y_{i1}y_{i2}} \\ &=\sum_i^P{\left[ a_1\left( X_i-\bar{X} \right) \right] \left[ a_2\left( X_i-\bar{X} \right) \right] ^T} \\ &=a_1\varSigma a_2^T=0 \end{aligned}$

同理，由$cov\left( y_2,y_1 \right)=0$推出$a_2\varSigma a_1^T=0$，且由上面的推导可知，$a_2\varSigma a_1^T=\lambda _1a_2a_1^T=0$推出$a_2a_1^T=0$，即$a_1$与$a_2$正交。

求解$a_2$变成了下列优化问题：

$\begin{aligned} &\max :\quad a_2\varSigma a_{2}^{T} \\ &s.t.\quad a_2a_{2}^{T}=\lVert a_2 \rVert ^2=1,a_1a_{2}^{T}=a_2a_{1}^{T}=0 \end{aligned}$

解上面优化问题可以使用拉格朗日乘数法：

$\begin{aligned} &E\left( a_2 \right) =a_2\varSigma a_{2}^{T}-\lambda _2\left( a_2a_{2}^{T}-1 \right) -\beta a_1a_{2}^{T} \\ &\frac{\partial E\left( a_2 \right)}{\partial a_2}=\left( 2\varSigma a_{2}^{T}-2\lambda_2 a_{2}^{T}-\beta a_{1}^{T} \right) ^T=0 \end{aligned}$

得到：

$\begin{aligned} \left( 2\varSigma a_{2}^{T}-2\lambda _2a_{2}^{T}-\beta a_{1}^{T} \right) ^T&=2a_2\varSigma ^T-2\lambda _2a_2-\beta a_1=2a_2\varSigma -2\lambda _2a_2-\beta a_1=0 \\ \left(2 a_2\varSigma -2\lambda _2a_2-\beta a_1 \right) a_{1}^{T}&=2a_2\varSigma a_{1}^{T}-2\lambda _2a_2a_{1}^{T}-\beta a_1a_{1}^{T}=-\beta =0 \end{aligned}$

将$\beta=0$带入$\frac{\partial E\left( a_2 \right)}{\partial a_2}$得到：

$\varSigma a_{2}^{T}-\lambda _2a_{2}^{T}=0$

即$a_2^T$是$\Sigma$的特征向量，$\lambda_2$是对应的特征值

目标函数变为：

$var(y_2)=a_2\varSigma a_2^T=\lambda_2 a_2a_2^T=\lambda_2$

则当$a_2$是$\Sigma$第二大的特征值$\lambda_2$对应的特征向量时，$a_2$是此优化问题的解。

$\Sigma$最大的特征值$\lambda_1$已经分配给$var(y_1)$了

我们称$y_2=a_2\left( X-\overline{X} \right)$为$X$的第二主成分，$a_2$是$\Sigma$最大的特征值$\lambda_{2}$对应的特征向量。

按照上述方法可以求得第一、第二、直到第$M$主成分$y_i$，其系数向量$a_1^T,a_2^T,\cdots ,a_M^T$分别是$\Sigma$的第一个、第二个、直到第$M$个单位特征向量，$\lambda_1,\lambda_2,\cdots,\lambda_M$分别是对应的特征值，其值依次递减。并且，第$k$主成分的方差等于$\Sigma$的第$k$个特征值。

PCA算法总结

PCA算法：

1. 求$\varSigma =\sum_{i=1}^P{ \left( X_i-\overline{X} \right) \left( X_i-\overline{X} \right) ^T }$

2. 求$\varSigma$的特征值并按从大到小排序$\left[ \lambda _1,\lambda _2,\cdots ,\lambda _M \right]$，对应特征值$\left[ a_1^T,a_2^T,\cdots ,a_M^T \right]$

3. 归一化所有$a_i^T$,使$\lVert a_{i}^{T} \rVert =1$

4. $A=\left[ \begin{array}{c} a_1\\ a_2\\ \vdots\\ a_M\\ \end{array} \right]$

5. $Y=A\left( X-\overline{X} \right)$

SVD（Singular Value Decomposition）算法可以快速求得特征值