理解PCA

点击量:565

引言
之前写过一篇关于PCA的文章,写完之后就以为自己已经完全理解这个东西了。直到最近data mining课上又讲到这个内容,和同学交流时才发现有些细节根本没有理解到位。上一篇文章主要介绍如何一步一步计算出一个PCA算法,而今天则侧重于从数学的角度讲讲为什么。

基本概念
再深入介绍之前,先理解几个基本的数学概念:
方差(Variance):
一个变量的方差可以看做是每个元素与变量均值的差的平方和的均值,即:$${\displaystyle \Sigma =\mathrm {cov} (X_{i},X_{i}) = \mathrm {E} {\begin{bmatrix}(X_{i}-\mu _{i})^{2}\end{bmatrix}} = \mathrm {E} {\begin{bmatrix}(X_{i}-\mu _{i})(X_{i}-\mu _{i})\end{bmatrix}}}
$$
其中,\(E\)表示的是均值函数,\(\mu_{j}\)表示的是样本的均值。方差用来度量单个变量样本数据的离散(偏离均值)的程度。

协方差(Covariance):
变量\(X_{i}\)和\(X_{j}\)之间的协方差被定义为如下形式:
$$
{\displaystyle \Sigma _{ij}=\mathrm {cov} (X_{i},X_{j})=\mathrm {E} {\begin{bmatrix}(X_{i}-\mu _{i})(X_{j}-\mu _{j})\end{bmatrix}}}
$$
简单理解为:要计算两个变量(向量)\(X_{i}\)和\(X_{j}\)之间的协方差,分别计算变量(向量)\(X_{i}\)和它的平均值\(\mu_{i}\)之间的差值\(D_i\),变量(向量)\(X_{j}\)和它的平均值\(\mu_{j}\)之间的差值\(D_j\),两者相乘之后再求平均值,即是这两个变量的协方差。

协方差矩阵(Covariance Matrix):
协方差矩阵的定义如下:
$$
\Sigma=\mathrm{E}
\left[
\left(
\textbf{X} – \mathrm{E}[\textbf{X}]
\right)
\left(
\textbf{X} – \mathrm{E}[\textbf{X}]
\right)^\top
\right]
$$

$$
{\displaystyle ={\begin{bmatrix}\mathrm {E} [(X_{1}-\mu _{1})(X_{1}-\mu _{1})]&\mathrm {E} [(X_{1}-\mu _{1})(X_{2}-\mu _{2})]&\cdots &\mathrm {E} [(X_{1}-\mu _{1})(X_{n}-\mu _{n})]\\\\\mathrm {E} [(X_{2}-\mu _{2})(X_{1}-\mu _{1})]&\mathrm {E} [(X_{2}-\mu _{2})(X_{2}-\mu _{2})]&\cdots &\mathrm {E} [(X_{2}-\mu _{2})(X_{n}-\mu _{n})]\\\\\vdots &\vdots &\ddots &\vdots \\\\\mathrm {E} [(X_{n}-\mu _{n})(X_{1}-\mu _{1})]&\mathrm {E} [(X_{n}-\mu _{n})(X_{2}-\mu _{2})]&\cdots &\mathrm {E} [(X_{n}-\mu _{n})(X_{n}-\mu _{n})]\end{bmatrix}}}
$$
观察以上公式可以发现协方差矩阵有如下特点:

  • 沿着对角线对称
  • 对角线上的元素是单个变量m个样本的方差
  • 非对角线上的元素为各个变量之间的协方差

协方差的作用
协方差主要是用来度量两个变量之间的变化关系,是同向变化还是反向变化?同向或者反向的变化程度如何?对照上面的公式就很好理解了:如果\(X_{i}\)和\(X_{j}\)都为正或者负,那么他们的乘积就是正数,也就是同向变化;如果\(X_{i}\)和\(X_{j}\)一个为正另一个为负,那么就说明反向变化。从数值来看,协方差的数值越大,两个变量同向程度也就越大,反之亦然。

理解降维
PCA的主要目标是降维,比如把N维数据降低到K维,那这一过程遵循了哪些原则?具体又是如何操作的呢?我们先举两个简单的例子:

  • 二维降到一维
    假设有如下二维的样本数据:
    1_dimension
    现在我们要把它降低到一维,也就是说要找到一条直线把这些样本点投射上去。那么该如何选取这条直线呢?我们自然希望尽可能地保留更多的信息,也就是说信息丢失率要最小。怎么理解?假设这条直线是X轴,你会发现5个点被降低到了只有3个点,因为最左边两列的样本点在X轴上重叠了!这么一想你就知道,我们希望各个样本点在投射之后尽可能地分散(尽可能地不重叠),也就是说在投射之后这个维度上的样本点的方差尽可能的大!(可以证明的是:最大方差解释和样本点到直线的垂直距离之和最小的解释是等价的)
  • 三维降到二维
    那么再看三维降低到二维的情况:
    1_dimension
    三维样本数据被降低到了二维数据,与降低到一维唯一的不同是:降维后有两个方向的向量(因为降低到了二维嘛)。我们希望不同向量(维度)之间尽可能地偏离。为什么?因为如果两个向量很接近,极限思考下如果他们近到几乎重叠的地步,那么自然很多信息就丢失了。而且从设计原理上讲,这如果两个向量近到几乎重叠的地步,那么他们就应该被整合成一个,而不是两个。不同变量越接近,则信息丢失率越高,所以他们应该互相远离。

将上述例子推广到更高维度,我们就可以得出降维的优化目标:在降维之后要尽可能保证各个变量(维度)相互独立,最理想的情况是他们是两两正交(向量垂直)的,也就是说他们的product是0;同时要保证各个变量(维度)内部的样本方差尽可能地大。

降维优化目标的数学表达
接下来,我们要把上述优化目标用数学公式表达出来。首先,我们定义\(X\)为大小为\(n \times m\)的样本数据矩阵(\(n\)为特征数量,\(m\)为样本数量),\(C_{x}\)为它的协方差矩阵。根据协方差公式:
$$
\Sigma=\mathrm{E}
\left[
\left(
\textbf{X} – \mathrm{E}[\textbf{X}]
\right)
\left(
\textbf{X} – \mathrm{E}[\textbf{X}]
\right)^\top
\right]
$$
同时,我们知道在计算PCA时会先对\(X\)进行均值化处理(详情可以参考上一篇关于PCA的文章),所以\(E(X) = 0\),于是我们有:
$$
C_{x} = \frac{1}{m} XX^{T}
$$
我们假设矩阵\(Y\)为原始样本数据矩阵\(X\)经过矩阵\(P\)变换之后得到矩阵,那么我们有:
$$Y = PX$$
其中,\(Y\subseteq \mathbb{R}^{k*m}\)即为降维后的矩阵,而\(P\subseteq \mathbb{R}^{k*n}\)即为我们要求的目标矩阵,\(X\subseteq \mathbb{R}^{n*m}\)是原始样本数据矩阵。接下来,我们把目标优化的描述转化成数学表达:我们希望降维后的矩阵\(Y\)的协方差矩阵\(C_{y}\)应该满足如下两个条件:

  • \(C_{y}\)对角线上的元素要尽可能的大(保证各个变量(维度)内部的样本方差尽可能地大)
  • \(C_{y}\)非对角线元素应该为0(保证各个变量(维度)相互独立,两个向量正交,product为0

通过如下的数学推导:
$$
\begin{align*}
& C_{y} = \frac{1}{m}YY^{T} \\
& = \frac{1}{m}(PX)(PX)^{T} \\
& = \frac{1}{m}PXX^{T}P^{T} \\
& = P\frac{1}{m}XX^{T}P^{T} \\
& =PC_{x}P^{T}
\end{align*}
$$
我们可以得出\(C_{x}\)、\(C_{y}\)、\(P\)的关系:
$$ C_{y} = PC_{x}P^{T} $$
于是优化目标可以进一步表达成:寻找这样的一个矩阵\(P\),使得\(PC_{x}P^{T}\)是一个对角矩阵(主对角线之外的元素皆为0的矩阵)。那到这一步,这就是一个纯粹的数学问题了,求解PCA问题主要有两种方法:

  • 基于特征值分解的PCA
  • 基于奇异值分解(SVD)的PCA

这两个方法的推导本文不打算介绍了,具体可以参考线性代数之主成分分析(PCA)算法,推导过程很完整。总之,两种数学方法推导后得到的最终结论是:\(C_{y}\)即为协方差矩阵\(C_{x}\)的特征值矩阵,而主成分矩阵\(P\)是协方差矩阵\(C_{x}\)的特征向量矩阵。因此,我们只需要对协方差矩阵\(C_{x}\)进行特征值分解,得到的前\(k\)大特征值对应的特征向量就是最佳的\(k\)维新特征。在Matlab/Octave中使用svd函数算出来特征值是排好序的,直接取前\(k\)列即可。

本文主要参考两位大神的文章:
PCA的数学原理
线性代数之主成分分析(PCA)算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注