主成分分析 PCA

主成分分析用于在多维数据中，寻找对于数据方差贡献最大的方向，也即寻找对于划分数据最有益的方向。主成分分析主要适用于同量纲多维数据的分析。

如图所示，$(x+y)$ 显然是个更能区分数据的方向，PCA 的功能就是找出找个方向。

算法

主成分分析的算法非常简单。首先计算样本的协方差矩阵 $C$.

\[\begin{align} X_i &= [x_i^{(1)}, x_i^{(2)} \cdots x_i^{(N)}] \\ C &= \left[ \begin{matrix} \operatorname{cov}\left(x^{(1)},x^{(1)}\right) & \operatorname{cov}\left(x^{(1)}, x^{(2)}\right) &\cdots &\operatorname{cov}\left(x^{(1)},x^{(N)}\right) \\ \operatorname{cov}\left(x^{(2)},x^{(1)}\right) & \operatorname{cov}\left(x^{(2)}, x^{(2)}\right) &\cdots &\operatorname{cov}\left(x^{(2)},x^{(N)}\right) \\ \cdots &\cdots &\cdots &\cdots \\ \operatorname{cov}\left(x^{(N)},x^{(1)}\right) & \operatorname{cov}\left(x^{(N)}, x^{(2)}\right) &\cdots &\operatorname{cov}\left(x^{(N)},x^{(N)}\right) \end{matrix} \right] \end{align}\]

$C$ 为 $N \times N$ 矩阵，$N$ 为特征个数（数据维度）。$\operatorname{cov}$ 代表对两个随机变量求协方差，所有的样本的某一个维度的数据点 $x^{(j)}$ 构成了一个随机变量的采样。

然后，对 $C$ 进行特征值分解，并将特征值按照大小排序：

\[\begin{align} C \cdot V = V \cdot W \end{align}\]

则 $V$ 的第一个分量即为要求的主成分方向向量。之后，如果需要求解第二主成分，第三主成分等，可以将数据中第一主成分方向的分量减去之后再运行主成分分析算法。

下面的演示计算中直接绘制了两个特征向量方向。

理论：方差最大化

主成分分析的一个理论解释是，试图找到一个方向向量 $u$，使得样本在这个方向向量上的投影的方差最大化。在样本零均值的情况下，也即最大化：

\[\begin{align} S &= \sum_i \left( x_i^T u \right) ^ 2 \\ &= \sum_i u^T x_i x_i^T u \\ &= u^T C u \end{align}\]

上式中 $C = \sum x_i x_i^T$ 即为协方差矩阵。注意下标 $i$ 是样本序号下标，每个 $x_i$ 是一个样本向量。注意，协方差与方差不同，协方差可以为负数。

当 $C \in R^{n \times n}$ 具有 $n$ 个不同特征值的情况下可以简单地证明 $u$ 为最大特征值对应的特征向量上式取到最大值（对于随机数据，$C$ 一般具有 $n$ 个线性无关特征向量）。由于协方差矩阵是实对称矩阵，其属于不同特征值的特征向量彼此正交。若有 $n$ 个不同特征值，则所有的特征向量彼此正交。

将 $u$ 写成特征向量的线性组合：

\[\begin{align} S &= \left(\sum_j a_j v_j \right)^T \cdot C \cdot \left(\sum_j a_j v_j \right) \\ &= \left(\sum_j a_j v_j \right)^T \cdot \left(\sum_j a_j \lambda_j v_j \right) \\ &= \sum_j a_j^2 v_j \lambda_j \end{align}\]

又有：

\[\begin{align} v_1^T C v_1 &= \left(\sum_j a_j v_j \right)^T \left(\sum_j a_j v_j \right) \lambda_1 \\ &= \sum a_j^2 \lambda_1 \end{align}\]

$\lambda_1 \geq \lambda_i$, 故 $v_1^T C v_i \geq u^T C u$.