[toc]
理解主成分分析(PCA)
PCA的推导过程涉及较多的数学知识，主要有SVD、特征值分解、Lagrange乘子法求解带约束优化问题、矩阵求导、子空间的概念等，如果对这些数学知识没有兴趣的话，可以只看下面一句话概括PCA。
PCA是用来降维的（废话），我们知道在n维空间正交基有无数组，一般我们使用的都是标准正交基，有了标准正交基就可以得到任意一个向量的坐标表示，开始时我们拿到的样本都是标准正交基下的坐标，PCA本质上是在n维特征空间重新找一组正交基（可以理解为将坐标轴旋转了一下），然后计算出样本在这组新正交基下的坐标，这就是PCA所做的工作，如何找这样的一组正交基呢，就是下文中的推导过程了。
本文介绍PCA的两种推导方式，分别是基于最小重构残差和最大投影方差推导出PCA的最终形式,为了便于讨论，以下均假设样本是经过中心化的结果，也就是说样本的均值为0。
最小重构残差
假设我们有m个样本，每个样本具有n维特征，这m个样本所构成的样本矩阵为$X = [x_1, x_2, \cdots, x_m] \in R^{m\times n}.$ 现在我们知道每个样本都是在一个n维特征空间中，n可能是一个比较大的数字，由于某些原因我们需要对这些样本进行降维，不妨假设降维到$k$维，我们肯定不希望降维前后丢失太多的信息，也就是说对于所有的样本降维之后损失的信息应该极小化。那么，如何进行降维呢，正如我们假设的已经将每个样本降维至$k$维了，降维后每个样本落在一个k维子空间，所以我们需要找到这样一个k维子空间，并且保证原样本投影到这个k维子空间中，损失的信息最少。如何描述一个k维空间呢？答案就是只需找到一组k个互相正交的向量即可。具体来说，假设要找的k维子空间的k个正交向量为$\lbrace w_1,w_2,\cdots,w_k \rbrace$,他所构成的矩阵为$W = [w_1,w_2,\cdots,w_k],$那么对于每一个样本$x_i$，它在这个子空间下的投影坐标为$z_i = W^T x_i$ （注意：$z_i$ 是 $x_i$ 投影后的坐标！）,有了坐标，便很容易计算出$x_i$在$k$维子空间的投影向量为$y_i = z_{i1}w_1 + z_{i2}w_2 + \cdots + z_{ik} w_k = Wz_i$.
举一个具体的例子，如下图所示，在一个二维坐标系内，$w=(\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2})$是一个单位向量，$x_1 = (4,3)$是一个点，$y_1 = (\frac{7}{2}\sqrt{2},\frac{7}{2}\sqrt{2})$是$x_1$在方向向量$w$上的一个投影向量，若以$w$为坐标轴，那么$y_1$在$w$坐标轴上的坐标为7,所以7就是上面公式中的$z_i$，$\overrightarrow{y_1} = 7\overrightarrow{w}$就是$w$对于$x$的重构，那么我们可以计算出它对于$x_1$的重构残差为$| y_1 - x_1 |^2 .$project-emp.png)
回到n维m个样本的情况，我们希望这m个样本的投影后的重构残差$\sum_{i=1}^m \lVert y_i - x_i\rVert^2$最小，并且对于这个$k$维子空间的正交基我们只关心它们的方向，不关心它们的大小，于是约定$w_i^Tw_i= 1$,并且令$y_i = Wz_i$故得到如下优化目标：
\begin{equation}
\begin{array}{r,l}
\min & \sum_{i=1}^m \lVert y_i - x_i\rVert^2 \
\text{s.t.} & W^TW = I
\end{array}
\end{equation}
化简下目标函数,因为
\begin{equation}
\begin{array}{r,l}
& \lVert y_i - x_i\rVert^2 \
= & y_i^Ty_i - 2y_i^Tx_i + const \
= &-z_i^Tz_i + const \
= &- x_i^TWW^Tx_i + const \
\end{array}
\end{equation}
并且
\begin{equation}
\begin{array}{r,l}
& \sum_{i=1}^m-x_i^TWW^Tx_i \
= & \sum_{i=1}^mTr(-x_i^TWW^Tx_i) \
= & \sum_{i=1}^mTr(-W^Tx_ix_i^TW) \
= & Tr(\sum_{i=1}^m-W^Tx_ix_i^TW) \
= & -Tr(W^TXX^TW)
\end{array}
\end{equation}
最终的形式为
\begin{equation}
\begin{array}{r,l}
\max_W & Tr(W^TXX^TW) \
\text{s.t.} & W^TW = I
\end{array}
\end{equation}
对上面问题使用Lagrange乘子法得到：
$$
L(W,\Lambda) = Tr(W^TXX^TW) + Tr(\Lambda (W^TW - I))
$$
对Lagrange函数关于$W$求导并令其等0得到：
$$
XX^TW = \Lambda W
$$
显然是一个特征值分解问题。