PCA原理


一篇PCA学习笔记


1. 简介

PCA是无监督学习算法中的一种,与回归分析中希望根据输入,预测输出的方法不同,无监督学习希望探索输入和输出之间的相关性

对于数据降维问题来说,Principal Component Analysis (PCA) 是目前最流行、最常用的算法。还有一些其他的降维方法,比如因子分析 (Factor Analysis, FA)、独立成分分析 (Independent Component Analysis, ICA).

降维是一种数据化简的手段,对数据化简的好处有:

  • 使数据集更易使用
  • 降低计算成本
  • 去除噪声
  • 使结果更方便展示(绘图),便于理解

在PCA中,数据从原来的坐标系转换到新的坐标系, 新坐标系的选择是由数据本身决定的。第一个新坐标轴选择的是原始数据中方差最大的方向(第一个主成分),第二个新坐标轴的选择和第一个坐标轴正交且具有最大方差的方向(第二个主成分,就是数据差异性第二大的方向)。该过程一直重复, 重复次数为原始数据中特征的数目。

用PCA降维意味着去除一个或多个最小主成分,从而得到一个更低维度且保留最大数据方差的数据投影。

2. 低维度例子

  1. 在普通的二维坐标轴下选择主轴:

    变换后的第一条坐标轴(第一条主轴)为覆盖数据的最大方差位置,即上图中的直线B。数据的最大方差给出了数据最重要的信息。

    第一条主轴确定了之后,选择第二条主轴,选择与第一条主轴垂直的直线(超过二维称为正交(orthogonal)),这也就是覆盖数据差异性次大的坐标轴。

    利用PCA,就可以将数据坐标轴旋转至数据角度上的那些最重要的方向。

  2. 利用PCA把二维数据将为一维,如下图所示:

    浅色的点是原始数据,深色的点是投影的版本。我们可以很请楚地看到PCA降维的含义: 沿着最不重要的主轴的信息都被去除了,仅留下了含有最高方差值的数据成分。被去除的那一小部分方差值(与主轴上分布的点成比例,如图所示)基本可以看成是数据在降维后损失的“信息”量。这种降维后的数据集在某种程度上足以体现数据中最主要的关系:虽然有50%的数据维度被削减,但数据的总体关系仍然被大致保留了下来。

  3. 二维数据分类:

    只用一维信息便可对数据进行分类,另一维度可以理解为噪声。

3. 算法

通过数据集的而协方差矩阵及其特征值分析,我们就可以求得这些主成分的值。一旦得到了协方差矩阵的特征向量,就可以保留最大的N个值。这些特征向量也给出了N个最重特征的真实结构。我们可以通过将数据乘上这N个特征向量而将它转换到新的空间。

对于降维之后的新空间(对降维之前的空间来说是一个超平面),应该具有如下两条性质:

  • 最近重构性:样本点到这个超平面的距离足够近
  • 最大可分性:样本点在这个超平面上的投影尽可能分开

这两条性质在上面的3个小例子中能够体现出来。

3.1 从最近重构性角度推导

首先对数据进行中心化,即令样本的均值为0。样本的协方差矩阵就是$\frac {1}{m-1} \sum_{i=1}^m\vec{\boldsymbol{x_i}}·\vec{\boldsymbol{x_i}}^T$. 前面的系数并不产生影响,所以下面的推导过程将其忽略。

设新空间的坐标系为$\{\vec{\boldsymbol{w_1}},\vec{\boldsymbol{w_2}},···,\vec{\boldsymbol{w_d}}\}$,其中$\vec{\boldsymbol{w_i}}$是标准正交基向量,$\Vert \vec{\boldsymbol{w_i}}\Vert_2=1,\vec{\boldsymbol{w_i}}^T·\vec{\boldsymbol{w_j}}=0(i≠j)$.若丢弃新坐标系中的部分坐标,即将维度降低到$d’<d$,则样本点$\vec{\boldsymbol{x_i}}$在低维坐标系中的投影是$\vec{\boldsymbol{z_i}}=(z_{i1};z_{i2};···;z_{id’})$,其中$z_{ij}=\vec{\boldsymbol{w_j}}^T·\vec{\boldsymbol{x_i}}$是$\vec{\boldsymbol{x_i}}$在低维坐标系下第$j$维的坐标。若基于$\vec{\boldsymbol{z_i}}$来重构$\vec{\boldsymbol{x_i}}$,则会得到$\vec{\boldsymbol{\hat{x_i}}}=\sum\limits_{j=1}^{d’}z_{ij}\vec{\boldsymbol{w_j}}$.

考虑整个训练集,原样本点$\vec{\boldsymbol{x_i}}$与基于投影重构的样本点$\vec{\boldsymbol{\hat{x_i}}}$之间的距离为:
$$
\begin{array}{ll}
\sum\limits_{i=1}^m\Bigg\Vert\sum\limits_{j=1}^{d’}z_{ij}\vec{\boldsymbol{w_j}}-\vec{\boldsymbol{x_i}}\Bigg\Vert_2^2&=\sum\limits_{i=1}^m\vec{\boldsymbol{z_i}}^T\vec{\boldsymbol{z_i}}-2\sum\limits_{i=1}^m\vec{\boldsymbol{z_i}}^T\boldsymbol{W^T}\vec{\boldsymbol{x_i}}+const \\
&\propto -tr(\boldsymbol{W^T}(\sum\limits_{i=1}^m\vec{\boldsymbol{x_i}}·\vec{\boldsymbol{x_i}}^T)\boldsymbol{W})
\end{array}
\tag{3.1}
$$
其中const表示一个常数,$\boldsymbol{W}=(\vec{\boldsymbol{w_1}},\vec{\boldsymbol{w_2}},···,\vec{\boldsymbol{w_d}})$.根据最近重构性,需要最小化目标$(3.1)$的正比例项,考虑到$\vec{\boldsymbol{w_j}}$是标准正交基,$\sum\limits_{i=1}^m\vec{\boldsymbol{x_i}}·\vec{\boldsymbol{x_i}}^T$是协方差矩阵,即主成分分析的优化目标是:
$$
\begin{array}{ll}
\min\limits_{\boldsymbol{W}} & -tr(\boldsymbol{W^T}\boldsymbol{X}\boldsymbol{X^T}\boldsymbol{W}) \\
\text{s.t.} & \boldsymbol{W^T}\boldsymbol{W}=\boldsymbol{I}
\end{array}
\tag{3.2}
$$

3.2 从最大可分性角度推导

样本点$\vec{\boldsymbol{x_i}}$在新空间(超平面)中的投影是$\boldsymbol{W^T}·\vec{\boldsymbol{x_i}}$.如果想使所有样本点的投影尽可能分开,应该令投影后的样本点的方差最大化。

投影后样本点的方差是$\sum_{i} \boldsymbol{W^T}\vec{\boldsymbol{x_i}}·\vec{\boldsymbol{x_i}}^T\boldsymbol{W}$,优化目标可以写为:
$$
\begin{array}{ll}
\max\limits_{\boldsymbol{W}} & tr(\boldsymbol{W^T}\boldsymbol{X}\boldsymbol{X^T}\boldsymbol{W}) \\
\text{s.t.} & \boldsymbol{W^T}\boldsymbol{W}=\boldsymbol{I}
\end{array}
\tag{3.3}
$$
式$(3.2)$与式$(3.3)$等价。

3.3 求解

对$(3.2)$或$(3.3)$使用拉格朗日乘子法可得:
$$
\boldsymbol{X}\boldsymbol{X^T}\vec{\boldsymbol{w_i}}=\lambda_i\vec{\boldsymbol{w_i}} \tag{3.4}
$$
于是,只需对协方差矩阵$\boldsymbol{X}\boldsymbol{X^T}$进行特征值分解,实践中通常对$\boldsymbol{X}$进行奇异值分解svd来代替协方差矩阵的特征值分解eig,对于这里的协方差矩阵,用这两种方法会得到同样的答案,因为协方差均值总满足一个数学性质——对称正定 (symmetric positive definite) 。将求得的特征值排序:​$\lambda_1\geq \lambda_2\geq ···\geq \lambda_d$,再取前​$d’$个(通常人为选取新空间维度)特征值对应的特征向量构成​$\boldsymbol{W^*}=(\vec{\boldsymbol{w_1}},\vec{\boldsymbol{w_2}},···,\vec{\boldsymbol{w_{d’}}})$. 这就是主成分分析的解。整体算法流程如下:

简介中介绍的”逐一选取方差最大方向”方法和直接选取最大$d’$个特征值方法等价。

ToDo

参考:协方差和协方差矩阵复习相关知识


----------over----------


文章标题:PCA原理

文章作者:Ge垚

发布时间:2018年06月03日 - 13:06

最后更新:2018年06月03日 - 20:06

原始链接:http://geyao1995.com/PCA原理/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。