深度学习知识点汇总-机器学习基础（11）

2.11 PCA的算法原理和流程

基于最小投影距离为评价指标推理：

假设数据集是 $m$ 个 $n$ 维数据， $(x^{(1)}, x^{(2)},...,x^{(m)})$ ，也就是默认为 $n$ 行 $m$ 列的矩阵。这个矩阵的数据已经进行了中心化。经过投影变换得到新坐标为 ${w_1,w_2,...,w_{n'}}$ ，其中 $w$ 是标准正交基，即 $| w |_2 = 1$ ， $w^T_iw_j = 0$ 。

降维
经过降维后，新坐标为 ${ w_1,w_2,...,w_{n'} }$ ，其中 $n'$ 是降维后的目标维数。样本点 $x^{(i)}$ 在新坐标系下的投影为 $z^{(i)} = \left(z^{(i)}_1, z^{(i)}_2, ..., z^{(i)}_{n'} \right)$ ，其中 $z^{(i)}_j = w^T_j x^{(i)}$ 是 $x^{(i)}$ 在低维坐标系里第 $j$ 维的坐标值。
升维
如果用 $z^{(i)}$ 去恢复 $x^{(i)}$ ，则得到的恢复数据为 $\widehat{x}^{(i)} = \sum^{n'}_{j=1} x^{(i)}_j w_j = Wz^{(i)}$ ，其中 $W$ 为标准正交基组成的矩阵。

考虑到整个样本集，样本点到这个超平面的距离足够近，目标变为最小化 $\sum^m_{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2$ 。对此式进行推理，可得：

$\begin{aligned} \sum^m_{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2 &= \sum^m_{i=1} | Wz^{(i)} - x^{(i)} |^2_2 \\ &= \sum^m_{i=1} \left( Wz^{(i)} \right)^T \left( Wz^{(i)} \right) - 2\sum^m_{i=1} \left( Wz^{(i)} \right)^T x^{(i)} + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= \sum^m_{i=1} \left( z^{(i)} \right)^T \left( z^{(i)} \right) - 2\sum^m_{i=1} \left( z^{(i)} \right)^T z^{(i)} + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= - \sum^m_{i=1} \left( z^{(i)} \right)^T z^{(i)} + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= -tr \left( W^T \left( \sum^m_{i=1} x^{(i)} \left( x^{(i)} \right)^T \right)W \right) + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \\ &= -tr \left( W^TXX^TW \right) + \sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)} \end{aligned}$

在推导过程中，用到了：

$\hat{x}^{(i)} = Wz^{(i)}$ ，
矩阵转置公式 $(AB)^T = B^TA^T$ ，
$W^TW = I$ ，
$z^{(i)} = W^Tx^{(i)}$ 以及矩阵的迹。

最后两步是将代数和转为矩阵形式。由于 $W$ 的每一列向量 $w_j$ 是标准正交基， $\sum^m_{i=1} x^{(i)} \left( x^{(i)} \right)^T$ 是数据集的协方差矩阵， $\sum^m_{i=1} \left( x^{(i)} \right)^T x^{(i)}$ 是一个常量（因为归一化了）。最小化 $\sum^m_{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2$ 的问题可以等价于
$\underbrace{\arg \min}_W - tr \left( W^TXX^TW \right) \\ s.t. \ W^TW = I$

利用拉格朗日函数可得到
$J(W) = -tr(W^TXX^TW) + \lambda(W^TW - I)$

对 $W$ 求导，可得 $-XX^TW + \lambda W = 0$ ，也即 $XX^TW = \lambda W$ 。 $W$ 是 $n'$ 个特征向量组成的矩阵， $\lambda$ 为 $XX^T$ 的特征值。 $W$ 即为我们想要的矩阵。对于原始数据，只需要 $z^{(i)} = W^TX^{(i)}$ ，就可把原始数据集降维到最小投影距离的 $n'$ 维数据集。

由上述分析，得到PCA的算法流程。

输入： $n$ 维样本集 $D = \left( x^{(1)},x^{(2)},...,x^{(m)} \right)$ ，目标降维的维数 $n'$ 。
输出：降维后的新样本集 $D' = \left( z^{(1)},z^{(2)},...,z^{(m)} \right)$ 。
主要步骤如下：

归一化。对所有的样本进行中心化， $x^{(i)} = x^{(i)} - \frac{1}{m} \sum^m_{j=1} x^{(j)}$ 。
计算样本的协方差矩阵 $XX^T$ 。
对协方差矩阵 $XX^T$ 进行特征值分解。
取出最大的 $n'$ 个特征值对应的特征向量 ${ w_1,w_2,...,w_{n'} }$ 。
标准化特征向量，得到特征向量矩阵 $W$ 。
转化样本集中的每个样本 $z^{(i)} = W^T x^{(i)}$ 。
得到输出矩阵 $D' = \left( z^{(1)},z^{(2)},...,z^{(n)} \right)$ 。
注：在降维时，有时不明确目标维数，而是指定降维到的主成分比重阈值 $k \ (k \in (0,1])$ 。假设 $n$ 个特征值为 $\lambda_1 \geqslant \lambda_2 \geqslant ... \geqslant \lambda_n$ ，则 $n'$ 可从 $\sum^{n'}_{i=1} \lambda_i \geqslant k \times \sum^n_{i=1} \lambda_i$ 得到。

PCA算法主要优缺点
优点:

仅仅需要以方差衡量信息量，不受数据集以外的因素影响。
各主成分之间正交，可消除原始数据成分间的相互影响的因素。
计算方法简单，主要运算是特征值分解，易于实现。

缺点:

主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强。
方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。