机器学习基础算法 -- 主成分分析（Principal Component Analysis）

本文主要记录 PCA 相关算法核心公式推导。

基本思想

PCA 降维就是将 维空间的数据 经过线性变换 映射到 维空间中，其一般表达式为

其中，

更进一步，如果在原 维空间按照各轴投影方式重新表达数据 ，则有

上述 为 维空间单位基，降维就是仅取其中的 个基（公式前一项）。

PCA 降维的基本思想就是最大可分性或最近重构性提前下，去掉上述公式的第二项。

前者的思路是让保留的数据投影尽量分散，后者的思路则是让丢失的数据变化尽量小。

最大可分性

投影后的数据尽量分散，实际上就是希望方差尽量的大，其数学表达形式如下

对于数据集来说，我们首先将其中心化然后再去上面的式子的第一项，并使用其系数的平方平均作为损失函数并最大化：

由于协方差矩阵中心化形式可表示为

所以，损失函数可以进一步化简为

上式为带约束条件的优化问题，引入 Lagrange 函数：

最终有

从上式可以看出，协方差矩阵的特征根即为 维空间坐标基，损失函数最大对应取前 个最大特征值。

这样只要对协方差矩阵做特征值分解，就可以实现到 维空间的降维。

最近重构性

最大可分性考虑的为前 项，如果考虑后面 项，即对应最近重构性。参照上述损失函数

前下面看其损失的信息最少这个条件，同样适用系数的平方平均作为损失函数，并最小化：

引入 Lagrange 函数，同样可以得出与最大可分性相同的结果。

SVD 求解

直接对中心矩阵 做特征分解，有

因为

记

对 做奇异值分解，有

考虑如下变换

由上式可以看出，直接对 做奇异值分解，就可以直接得出 的特征分解结果，而 SVD 的计算效率通常要比特征分解要快得多。

Reference

机器学习 (nju.edu.cn)

统计学习方法 (豆瓣) (douban.com)

Eigendecomposition of a matrix - Wikipedia

Singular value decomposition - Wikipedia