主成分分析(PCA)

1. 坐标投影

主成分分析(PCA, Principal Component Analysis)是最常用的一种线性降维方法。

假设原来的样本是 d 维空间，样本矩阵 $X=\begin{bmatrix}x_1 & x_2 & \cdots & x_m \end{bmatrix} \in \mathbb{R^{d\times m}}$ ， $x_i \in \mathbb{R^d}$ 表示第 i 个样本。为了方便起见，假设样本进行了中心化，即 $\sum_{i=1}^m x_i=0$ 。现在要将样本投影到一个 k 维的超平面，其中 $k < d$ 。选取此超平面中的一组标准正交基作为坐标轴，记为 $W=\begin{bmatrix}w_1 & w_2 & \cdots & w_k \end{bmatrix}$ ，其中 $w_i$ 是标准正交向量，即 $\left \| w_i\right \|_2=1$ ， $w_i^Tw_j=0\ (i \neq j)$ 。则每个样本 $x_i$ 在这个低维坐标系中的投影为 $z_i=\begin{bmatrix}z_{i1} & z_{i2} & \cdots & z_{ik} \end{bmatrix}^T$ , 其中 $z_{ij}=w_j^T x_i$ 是 $x_i$ 投影到第 j 个坐标轴 $w_j$ 得到的坐标，证明如下。

证明方法一： $x_i$ 到第 j 个坐标轴 $w_j$ 的投影长度为 $\frac{w_j^Tx_i}{\left \| w_i\right \|_2}=w_j^Tx_i$ ，因为 $\left \| w_i\right \|_2=1$ ，所以投影的长度即为坐标。
证明方法二：假设 $x_i$ 投影在 $w_j$ 的坐标为 c，则 $x_i$ 可分解为两个分量，一个分量是 $c\cdot w_j$ ，另一个是垂直 $w_j$ 的分量，为 $x_i-c\cdot w_j$ ，可得 $w_j^T(x_i-c\cdot w_j)=0$ ，即 $w_j^Tx_i=c \left \| w_i\right \|_2^2$ ，因为 $\left \| w_i\right \|_2=1$ ，所以 $c=w_j^Tx_i$

所以，样本 $x_i$ 在这个低维坐标系中的投影坐标为 $z_i=W^Tx_i$ ，所有样本投影之后的结果是 $Z=W^TX$ ， $Z$ 的每一列是一个新的样本坐标。下面使用两种优化目标来推导 PCA 的求解公式。

2. 最近重构性

投影之后，利用投影得到的坐标 $z_i$ 来重构 $x_i$ ，得到 $\hat{x}_i=\sum_{j=1}^kz_{ij}w_j=Wz_i$ 。由于 k 比 d 小，因此投影之后一般会有信息损失（除非所有 $x_i$ 都在 k 维超平面上，即 $W$ 的列空间里）。信息损失为 $\left \| x_i-\hat{x}_i\right \|_2^2$ ，即 $x_i$ 到上述 k 维超平面的距离。要想使信息损失最小，则需要让所有样本到超平面的距离最小化，如下：
$\sum_{i=1}^m\left \| x_i-\hat{x}_i\right \|_2^2=\sum_{i=1}^m\left \| x_i-Wz_i\right \|_2^2=\left \|X-WZ\right \|_2^2$ 把 $Z=W^TX$ 代入，根据 $\left \| A\right \|_2^2=tr(A^TA)=tr(AA^T)$ 得
$\begin{aligned} \left \|X-WW^TX\right \|_2^2 & =tr((X-WW^TX)^T(X-WW^TX)) \\ & = tr((X^T-X^TWW^T)(X-WW^TX)) \\ & = tr(X^TX-2\cdot X^TWW^TX+X^TWW^TWW^TX) \\ & = tr(X^TX-2\cdot X^TWW^TX+X^TWW^TX)\\ & = tr(X^TX-X^TWW^TX) \\ & = tr(X^TX)-tr(X^TWW^TX) \end{aligned}$ 上面的变换主要利用了 $W^TW=I$ ，注意 $W$ 不是方阵，因此 $WW^T \neq I$ ，不能消去。由于 $tr(X^TX)$ 是常数，可以从优化目标里去掉，并且：
$tr(X^TWW^TX)=tr((W^TX)^T(W^TX))=tr((W^TX)(W^TX)^T)=tr(W^TXX^TW)$ 因此最后的优化目标如下：
$\max_W tr(W^TXX^TW) \\ s.t. \quad W^TW=I$ 由于样本做了中心化，因此 $XX^T$ 是协方差矩阵。

3. 最大可分性

除了要求信息损失最小之外，也可以从另一个角度去优化，我们希望投影之后的点在超平面上尽可能地分散开，不要都挤到一起，即使投影后的样本点方差最大化。由于 $\sum_{i=1}^mz_i=\sum_{i=1}^mW^Tx_i=W^T\sum_{i=1}^mx_i=0$ （因为 $x_i$ 做了中心化），可以得出 $z_i$ 的均值也为 $0$ 。所以投影后方差可以表示为
$\sum_{i=1}^m\left \|z_i\right \|_2^2=\left \|Z\right \|_2^2=\left \| W^TX \right \|_2^2$ 根据 $\left \| A\right \|_2^2=tr(A^TA)=tr(AA^T)$ ，有：
$\left \| W^TX \right \|_2^2=tr((W^TX)(W^TX)^T)=tr(W^TXX^TW)$ 因此优化目标为：
$\max_W tr(W^TXX^TW) \\ s.t. \quad W^TW=I$

4. 求解

使用拉格朗日乘子法，令导数为0，可得
$XX^TW=\lambda W$ 对 $XX^T$ 进行特征值分解，将得到的特征值从大到小排列，前 k 个特征值对应的特征向量即为 $W$ 的各个列向量。然后用 $W^TX$ 就可求得降维后的样本矩阵 $Z$ 。

原文链接：https://blog.csdn.net/caitzh/article/details/88753028

机器学习笔记之——降维（二）主成分分析(PCA)

目录

主成分分析(PCA)

1. 坐标投影

2. 最近重构性

3. 最大可分性

4. 求解