PCA - webdancer's Blog

PCA

webdancer posted @ 2012年11月11日 04:04 in machine learning with tags Machine learning , 2446 阅读

PCA是一种降低数据特征维度的技术。它通过将高维空间数据正交投影到低维子空间,使投影空间中数据的方差最大来实现。另外的一种理解是它通过将高维空间数据正交投影到低维子空间,最小化从投影数据恢复到原数据的误差。PCA带来的好处是数据压缩后,能有更小的存储要求,有更快的分类速度;但是带来的坏处就是,在数据压缩的过程中,可能会丢失一些特征。

1.投影

在PCA形式化表示的时候需要用到向量投影的知识,这里我们简单看一下。两个向量:$\vec{a},\vec{b}$,我们将$\vec{b}$正交投影到$\vec{a}$上,如下图所示:

我们将投影向量表示为:$\vec{p}={\vec{a}x}$,将垂直于向量$\vec{a}$的向量$\vec{e}=\vec{b}-\vec{p}=\vec{b}-\vec{a}x$。

根据两个向量:$\vec{p},\vec{e}$的垂直关系,则可以得出:

\[
\vec{p}^{T}\vec{e}=0\\
\Rightarrow (\vec{a}x)^{T}(\vec{b}-\vec{a}x)=0\\
\Rightarrow (\vec{a}x)^{T}\vec{b} = (\vec{a}x)^{T}\vec{a}x\\
\Rightarrow \vec{a}^{T}x\vec{b} = \vec{a}^{T}x\vec{a}x\\
\Rightarrow x=\frac{\vec{a}^{T}\vec{b}}{\vec{a}^{T}\vec{a}}
\]

通过上面的推导得出x的值,即投影向量的长度。那么投影向量:

\[
\vec{p}=\vec{a}x=\frac{\vec{a}\vec{a}^{T}\vec{b}}{\vec{a}^{T}\vec{a}}=\frac{\vec{a}\vec{a}^{T}}{\vec{a}^{T}\vec{a}}\vec{b}
\]

则如果我们右侧的矩阵定义为投影矩阵$P=\frac{\vec{a}\vec{a}^{T}}{\vec{a}^{T}\vec{a}}$。另外:投影矩阵有两个性质:$P=P^{T};P=P^{2}$。这三个公式是下面我们进行向量运算的一个基础。注意:在高维情况下,推导过程基本类似,可以得出基本类似的过程,不过投影矩阵的表达形式不同,可以参考线性代数的教科书,形式为:$P=A(A^TA)^{-1}A^T$,其中,$A=(a_1,a_2,..a_n)$.

2.最大化投影数据的方差


如上图所示,我们选择不同的投影子空间,就会有不同的投影点。根据PCA的概念,我们选择一个投影子空间使得投影数据的方差最大。那么下面我们就来形式化这个过程。

我们的数据集为:N个D维的数据点,表示为:${x_1,x_2,...,x_N}$。

i.投影到1维空间的情况。

我们先来看一下最简单的情况,把D维数据投影到一维的情况,设投影的方向向量为:$u$(不失一般性,我们假设$u$为单位向量,即$u^Tu=1$),根据上面我们的投影推导可以得出投影矩阵为:$P=uu^{T}$,投影点表示为:$Px=uu^{T}x$。那么可以得出投影点向量的长度为:$u^{T}x$。那么,投影点的期望表示为:

\[
\mathbb E(\hat x)=\frac{1}{N}\sum_{n=1}^{N}u^{T}x=u^{T}\frac{1}{N}\sum_{n=1}^{N}x=u^{T}\bar{x}
\]

其中,$\bar{x}=\frac{1}{N}\sum_{n=1}^{N}x$

投影空间中数据点的方差表示为:

\[
\frac{1}{N}\sum_{n=1}^{N}\{u^{T}x-u^{T}\bar{x}\}^{2}=u^{T}Su
\]

其中:$S=\frac{1}{N}\sum_{n=1}^{N}\{x-\bar{x}\}^{2}$(上面式子再推导的过程中用到了$\|a\|^2=a^Ta$)。

这样我们就得到了目标函数:

\[
J(u)=argmax_{u}u^{T}Su \\
s.t.u^{T}u=1
\]

这样我们就得到了一个有约束的优化问题,使用Lagrange Multipler 方法,可以得到:

\[
J(u)=argmax_{u}\{u^{T}Su+\lambda_1(1-u^{T}u)\}
\]

求导,然后得到式子:$Su-\lambda_1u=0 \Rightarrow Su=\lambda_1u$,将这个式子再代入目标函数$J(u)$,得到:

\[
J(u)=argmax_{u}u^{T}Su \Rightarrow J=argmax\lambda_1 \\
s.t.u^{T}u=1
\]

这样我们就可以看到,我们目标函数的最大值就是最大的特征值,这样我们的向量$u$就是最大特征值对应的特征向量,这样就找到了我们的投影子空间。

ii.投影到M(M<D)维空间的情况。

把D维数据投影到M维的情况与投影到一维的情况大体相差不多。我在推导的过程中存在的一个主要的盲点就是:在高维的情况下,投影点的方差如何表示的问题,以及里面的矩阵变化。

设投影的方向向量为:$U=(u_1,u_2,...,u_M)$(不失一般性,我们假设$u_i$为单位向量,即$u^Tu=1$),根据上面我们的投影推导可以得出投影矩阵为:$P=UU^{T}$(我们选择的$u_i$都是单位向量,导致(U^{T}U)^{-1}是单位矩阵),投影点表示为:$Px=UU^{T}x$。过程与上面的差不多,投影空间中数据点的方差表示为:

\[
\frac{1}{N}\sum_{n=1}^{N}\{U^{T}x-U^{T}\bar x \}^{T}\{U^{T}x-U^{T}\bar x\}\\
\Rightarrow  trace(\frac{1}{N}\sum_{n=1}^{N}\{U^{T}x-U^{T}\bar x\}\{U^{T}x-U^{T}\bar x^{T}\}^{T})\\
\Rightarrow  trace(U^{T}\frac{1}{N}\sum_{n=1}^{N}\{x-\bar x\}\{x-\bar x\}^{T}U)\\
\Rightarrow  trace(U^{T}SU)
\]

其中:$S=\frac{1}{N}\sum_{n=1}^{N}\{x-\bar x\}\{x-\bar x\}^{T}; \bar{x}=\frac{1}{N}\sum_{n=1}^{N}x$

这样我们就得到了目标函数:

\[
J(U)=argmax_{U}trace(U^{T}SU)=argmax_{U}\sum_{m=1}^{M}u_m^{T}\\
s.t.  U^{T}U=I
\]

这样我们就得到了一个有约束的优化问题,使用Lagrange Multipler 方法,可以得到:

\[
J(U)=argmax_{U}argmax_{U}\sum_{m=1}^{M}u_m^{T}Su_m+\sum_{m=1}^{M}\lambda_m(1-u_m^Tu_m)
\]

对$u_m$求偏导,然后得到式子:$Su_m-\lambda_mu_m=0 \Rightarrow Su_m=\lambda_mu_m$,将这个式子再代入目标函数$J(u)$,得到:

\[
J(U)=argmax_{U}trace(U^{T}SU)=argmax_{U}\sum_{m=1}^{M}u_m^{T}Su_m\\
\Rightarrow J=argmax\sum_{m=1}^M\lambda_m\\
s.t.  U^{T}U=I
\]

这样我们就可以看到,我们目标函数的最大值就是求前M个最大的特征值,这样我们的向量$u_m$就是特征值对应的特征向量,这样就找到了我们的投影子空间。

3.最小化投影误差函数

将投影点从投影空间恢复到原空间的式子为:$\hat x_i=\sum_{i=1}z_{ni}u_i+b$,则我们很容易写出误差函数(欧式距离):

\[
J(z,u,b)=argmin_(z,u,b)\frac{1}{N}\sum_{n=1}^{N}\|x_n-\hat x_i\|^2 \\
s.t. U^{T}U=I
\]

对上面的式子分别对$z,b$求偏导数,可以得出:

$z_{ni}^*=x_n^Tu_i,b^*=\bar x$(这里用到的一个小trick还是$\|a\|^2=a^Ta$,展开后求解偏导数会容易很多)

然后将上面求出来的代入目标函数,可以得到关于u的函数,

\[
J(z*,u,b*)=argmin_u\frac{1}{N}\sum_{n=1}{N}\|x_n-\hat x_i\|^2 代入即可)\\
\Rightarrow J(U)=argmax_{U}trace(U^{T}SU)=argmax_{U}\sum_{m=1}^{M}u_m^{T}Su_m\\
s.t. U^{T}U=I
\]

这样我们就得到了与(2)最大化投影方差相同的目标函数。下面的过程就与上面相同了,也转到了求前M个最大特征向量。

4.方差的理解[2]

对于我们用于机器学习的数据(主要是训练数据),方差大才有意义,不然输入的数据都是同一个点,那方差就为0了,这样输入的多个数据就等同于一个数据了。以下面这张图为例子:
image
 
     这个假设是一个摄像机采集一个物体运动得到的图片,上面的点表示物体运动的位置,假如我们想要用一条直线去拟合这些点,那我们会选择什么方向的线呢?当然是图上标有signal的那条线。如果我们把这些点单纯的投影到x轴或者y轴上,最后在x轴与y轴上得到的方差是相似的(因为这些点的趋势是在45度左右的方向,所以投影到x轴或者y轴上都是类似的),如果我们使用原来的xy坐标系去看这些点,容易看不出来这些点真正的方向是什么。但是如果我们进行坐标系的变化,横轴变成了signal的方向,纵轴变成了noise的方向,则就很容易发现什么方向的方差大,什么方向的方差小了。

5.特征值,特征向量求解

在matlab中,可以使用eig或是svd来求解特征值。具体的求解算法这里不详细讨论了。关于SVD这里有一篇文章,记录的很详细。

6.PCA的应用

PCA的一个应用就是进行维度下降,比如在人脸识别应用中,使用PCA可以生成eighface。

如下图的10幅人脸:

经过PCA降维,得到的特征向量为(展示成图象):

pca的另一个应用就是数据可视化。

7.总结

PCA是一种传统的统计分析方法,将高维空间数据投影到低维子空间,在这个过程中尽量保持原有数据的主要信息。但是,PCA由于没有考虑类别信息,可能会丢失类别信息。PCA算法总结如下:

1.对数据进行归一化(data normalization)

2.计算数据集合的协方差矩阵(covariance matrix computing)

3.计算(2)中求得的协方差矩阵的特征值,特征向量

4.根据投影空间维数选择投影空间基向量,计算投影点

 

【引用】:

1.prml

2.http://www.cnblogs.com/LeftNotEasy/


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee