光阴冢

We make choices and life has a way of making us pay for them.

PCA 算法

Nov 7, 2017   # Machine Learning  # Algorithm 

今天刚刚接触到 PCA(Principal Components Analysis,主成分分析),感觉又是学起来很舒服的一个概念,原理很简单,然后结果也很优美。

主成分分析,顾名思义的话,就是想要把数据集中的主要的特征部分尽可能提取出来。它的输入是一个总量为 $P$ ,维度为 $N$ 的数据集 $\vec{X}$,然后输出一个总量为 $P$,维度为 $M(M<N)$ 的降维后的集合 $\vec{Y}$。

基本想法

PCA 最主要的想法就是想将高维向量投影到低维,同时尽可能使得不丢失重要的特征。可以比较好想的是最大化投影结果的方差。由于 $\vec{Y}$ 中的每一个元素又都有 $M$ 个分量,因此可以对这 $M$ 个分量分别进行考虑。

设投影矩阵为

$$ \begin{matrix} -- & a_1 & -- \\ -- & a_2 & -- \\ -- & \cdots & -- \\ -- & a_M & -- \\ \end{matrix} $$

对输出 $\vec{Y}$ 有 $Y_i = A \times {(X_i - \bar{X})}$。

推导

对于 $a_1$ 来说,它的规划可以写成

$$ \begin{aligned} \max && E{(a_1)} &= \frac{1}{P}{\sum_P}{|a_1X_i-a_1\bar{X}|^2} \\ s.t. && ||a_1|| &= 1 \end{aligned} $$

\[ \begin{aligned} E{(a_1)} &= \frac{1}{P}{\sum_P}{|a_1X_i-a_1\bar{X}|^2} \\ &=\frac{1}{P}{\sum_P}{[a_1(X_i-\bar{X})\times [a_1(X_i-\bar{X})]^\mathrm{T}]} \\ &=\frac{1}{P}{\sum_P}{[a_1(X_i-\bar{X})(X_i-\bar{X})^\mathrm{T}a_1^\mathrm{T}]} \\ &=a_1\Sigma{a_1^\mathrm{T}} \end{aligned} \]

其中 $\Sigma$ 为协方差矩阵:

$$ \Sigma = \frac{1}{P}{\sum_P[(X_i-\bar{X})(X_i-\bar{X})^\mathrm{T}]} $$

之后使用拉格朗日乘子法解规划:

$$ M(a_1) = E(a_1) - \lambda(a_1a_1^\mathrm{T}) \\ \frac{\partial{M}}{\partial{a_1}} = 2\Sigma{a_1^\mathrm{T}} - 2\lambda{a_1^\mathrm{T}} $$

$$ \begin{aligned} a&=b+c \\ d+e&=f \end{aligned} $$

偏导为零,即可知 $\lambda$ 是协方差矩阵 $\Sigma$ 的特征值,而又要使 $E(a_1)$ 最大化,$\lambda$ 为协方差矩阵的最大特征值,$a_1$ 为该特征根对应的特征向量。

由于 $A$ 中的每一个行向量 $a_i$ 相互正交,可以类似推导出其他的特征向量。

算法步骤

  1. 求协方差矩阵 $\Sigma$。

  2. 求该矩阵的更大的 $M$ 个特征值所对应的特征向量。

  3. 归一化特征向量,即可得到降维矩阵 $A$。