PCA相关理解

转至http://blog.csdn.net/zhongkejingwang/article/details/42264479

 另一篇很好的文章 http://blog.codinglabs.org/articles/pca-tutorial.html

  在数据挖掘或者图像处理等领域经常会用到主成分分析&＃xff0c;这样做的好处是使要分析的数据的维度降低了&＃xff0c;但是数据的主要信息还能保留下来&＃xff0c;并且&＃xff0c;这些变换后的维两两不相关&＃xff01;至于为什么&＃xff1f;那就接着往下看。在本文中&＃xff0c;将会很详细的解答这些问题&＃xff1a;PCA、SVD、特征值、奇异值、特征向量这些关键词是怎么联系到一起的&＃xff1f;又是如何在一个矩阵上体现出来&＃xff1f;它们如何决定着一个矩阵的性质&＃xff1f;能不能用一种直观又容易理解的方式描述出来&＃xff1f;

数据降维

    为了说明什么是数据的主成分&＃xff0c;先从数据降维说起。数据降维是怎么回事儿&＃xff1f;假设三维空间中有一系列点&＃xff0c;这些点分布在一个过原点的斜面上&＃xff0c;如果你用自然坐标系x,y,z这三个轴来表示这组数据的话&＃xff0c;需要使用三个维度&＃xff0c;而事实上&＃xff0c;这些点的分布仅仅是在一个二维的平面上&＃xff0c;那么&＃xff0c;问题出在哪里&＃xff1f;如果你再仔细想想&＃xff0c;能不能把x,y,z坐标系旋转一下&＃xff0c;使数据所在平面与x,y平面重合&＃xff1f;这就对了&＃xff01;如果把旋转后的坐标系记为x&＃39;,y&＃39;,z&＃39;&＃xff0c;那么这组数据的表示只用x&＃39;和y&＃39;两个维度表示即可&＃xff01;当然了&＃xff0c;如果想恢复原来的表示方式&＃xff0c;那就得把这两个坐标之间的变换矩阵存下来。这样就能把数据维度降下来了&＃xff01;但是&＃xff0c;我们要看到这个过程的本质&＃xff0c;如果把这些数据按行或者按列排成一个矩阵&＃xff0c;那么这个矩阵的秩就是2&＃xff01;这些数据之间是有相关性的&＃xff0c;这些数据构成的过原点的向量的最大线性无关组包含2个向量&＃xff0c;这就是为什么一开始就假设平面过原点的原因&＃xff01;那么如果平面不过原点呢&＃xff1f;这就是数据中心化的缘故&＃xff01;将坐标原点平移到数据中心&＃xff0c;这样原本不相关的数据在这个新坐标系中就有相关性了&＃xff01;有趣的是&＃xff0c;三点一定共面&＃xff0c;也就是说三维空间中任意三点中心化后都是线性相关的&＃xff0c;一般来讲n维空间中的n个点一定能在一个n-1维子空间中分析&＃xff01;所以&＃xff0c;不要说数据不相关&＃xff0c;那是因为坐标没选对&＃xff01;

    上面这个例子里把数据降维后并没有丢弃任何东西&＃xff0c;因为这些数据在平面以外的第三个维度的分量都为0。现在&＃xff0c;我假设这些数据在z&＃39;轴有一个很小的抖动&＃xff0c;那么我们仍然用上述的二维表示这些数据&＃xff0c;理由是我认为这两个轴的信息是数据的主成分&＃xff0c;而这些信息对于我们的分析已经足够了&＃xff0c;z&＃39;轴上的抖动很有可能是噪声&＃xff0c;也就是说本来这组数据是有相关性的&＃xff0c;噪声的引入&＃xff0c;导致了数据不完全相关&＃xff0c;但是&＃xff0c;这些数据在z&＃39;轴上的分布与原点构成的夹角非常小&＃xff0c;也就是说在z&＃39;轴上有很大的相关性&＃xff0c;综合这些考虑&＃xff0c;就可以认为数据在x&＃39;,y&＃39;轴上的投影构成了数据的主成分&＃xff01;

    现在&＃xff0c;关于什么是数据的主成分已经很好的回答了。下面来看一个更具体的例子。

下面是一些学生的成绩&＃xff1a;

首先&＃xff0c;假设这些科目成绩不相关&＃xff0c;也就是说某一科考多少份与其他科没有关系。那么一眼就能看出来&＃xff0c;数学、物理、化学这三门成绩构成了这组数据的主成分&＃xff08;很显然&＃xff0c;数学作为第一主成分&＃xff0c;因为数学成绩拉的最开&＃xff09;。为什么一眼能看出来&＃xff1f;因为坐标轴选对了&＃xff01;下面再看一组数据&＃xff0c;还能不能一眼看出来&＃xff1a;

是不是有点凌乱了&＃xff1f;你还能看出来数据的主成分吗&＃xff1f;显然不能&＃xff0c;因为在这坐标系下数据分布很散乱。所以说&＃xff0c;看到事物的表象而看不到其本质&＃xff0c;是因为看的角度有问题&＃xff01;如果把这些数据在空间中画出来&＃xff0c;也许你一眼就能看出来。但是&＃xff0c;对于高维数据&＃xff0c;能想象其分布吗&＃xff1f;就算能描述分布&＃xff0c;如何精确地找到这些主成分的轴&＃xff1f;如何衡量你提取的主成分到底占了整个数据的多少信息&＃xff1f;要回答这些问题&＃xff0c;需要将上面的分析上升到理论层面。接下来就是PCA的理论分析。

    以下面这幅图开始我们的推导&＃xff1a;

上面是二维空间中的一组数据&＃xff0c;很明显&＃xff0c;数据的分布让我们很容易就能看出来主成分的轴&＃xff08;简称主轴&＃xff09;的大致方向。下面的问题就是如何通过数学计算找出主轴的方向。来看这张图&＃xff1a;

现在要做的事情就是寻找u1的方向&＃xff0c;对于这点&＃xff0c;我想好多人都有经验&＃xff0c;这不就是以前用最小二乘法拟合数据时做的事情吗&＃xff01;对&＃xff0c;最小二乘法求出来的直线&＃xff08;二维&＃xff09;的方向就是u1的方向&＃xff01;那u2的方向呢&＃xff1f;因为这里是二维情况&＃xff0c;所以u2方向就是跟u1垂直的方向&＃xff0c;对于高维数据&＃xff0c;怎么知道u2的方向&＃xff1f;经过下面的理论推导&＃xff0c;各个主轴都能确定下来。

    给定一组数据&＃xff1a;&＃xff08;如无说明&＃xff0c;以下推导中出现的向量都是默认是列向量&＃xff09;

将其中心化后表示为&＃xff1a;

中心化后的数据在第一主轴u1方向上分布散的最开&＃xff0c;也就是说在u1方向上的投影的绝对值之和最大&＃xff08;也可以说方差最大&＃xff09;&＃xff0c;计算投影的方法就是将x与u1做内积&＃xff0c;由于只需要求u1的方向&＃xff0c;所以设u1是单位向量。

也就是最大化下式&＃xff1a;

也即最大化&＃xff1a;

解释&＃xff1a;平方可以把绝对值符号拿掉&＃xff0c;光滑曲线处理起来方便。

两个向量做内积可以转化成矩阵乘法&＃xff1a;

所以目标函数可以表示为&＃xff1a;

括号里面就是矩阵乘法表示内积&＃xff0c;转置以后的行向量乘以列向量得到一个数。因为一个数的转置还是其本身&＃xff0c;所以又可以将目标函数化为&＃xff1a;

这样就可以把括号去掉&＃xff01;去掉以后变成&＃xff1a;

由于u1和i无关&＃xff0c;可以把它拿到求和符外面&＃xff1a;

注意&＃xff0c;其实括号里面是一个矩阵乘以自身的转置&＃xff0c;这个矩阵形式如下&＃xff1a;

X矩阵的第i列就是xi&＃xff0c;于是有&＃xff1a;

所以目标函数最后化为&＃xff1a;

上式到底有没有最大值呢&＃xff1f;如果没有前面的1/n&＃xff0c;那就是就是一个标准的二次型&＃xff01;并且XX&＃39;(为了方便&＃xff0c;用&＃39;表示转置)得到的矩阵是一个半正定的对称阵&＃xff01;为什么&＃xff1f;首先XX&＃39;是对称阵&＃xff0c;因为(XX&＃39;)&＃39;&＃61;XX&＃39;&＃xff0c;下面证明它是半正定&＃xff0c;什么是半正定&＃xff1f;就是所有特征值大于等于0。

假设XX&＃39;的某一个特征值为&＃xff0c;对应的特征向量为&＃xff0c;则有&＃xff1a;

证明完毕&＃xff01;对于半正定阵的二次型&＃xff0c;存在最大值&＃xff01;现在问题就是如何求目标函数的最大值&＃xff1f;以及取最大值时u1的方向&＃xff1f;下面介绍两种方法。

方法一  拉格朗日乘数法

目标函数和约束条件构成了一个最大化问题&＃xff1a;

构造拉格朗日函数&＃xff1a;

对u1求导

显然&＃xff0c;u1即为XX&＃39;特征值对应的特征向量&＃xff01;XX&＃39;的所有特征值和特征向量都满足上式&＃xff0c;那么将上式代入目标函数表达式即可得到

所以&＃xff0c;如果取最大的那个特征值&＃xff0c;那么得到的目标值就最大。有可能你会有疑问&＃xff0c;为什么一阶导数为0就是极大值呢&＃xff1f;那么再求二阶导数&＃xff1a;

二阶导数半负定&＃xff0c;所以&＃xff0c;目标函数在最大特征值所对应的特征向量上取得最大值&＃xff01;所以&＃xff0c;第一主轴方向即为第一大特征值对应的特征向量方向。第二主轴方向为第二大特征值对应的特征向量方向&＃xff0c;以此类推&＃xff0c;证明类似。

下面介绍第二种方法

方法二  奇异值法

这方法是从矩阵分析里面总结的&＃xff0c;随便取个名叫奇异值法。

首先&＃xff0c;对于向量x&＃xff0c;其二范数&＃xff08;也就是模长&＃xff09;的平方为&＃xff1a;

所以有&＃xff1a;

把二次型化成一个范数的形式&＃xff0c;最大化上式也即这个问题&＃xff1a;对于一个矩阵&＃xff0c;它对一个向量做变换&＃xff0c;变换前后的向量的模长伸缩尺度如何才能最大&＃xff1f;这个很有趣&＃xff0c;简直就是把矩阵的真面目给暴露出来了。为了给出解答&＃xff0c;下面引入矩阵分析中的一个定理&＃xff1a;

表示矩阵A的最大奇异值&＃xff01;一个矩阵A的奇异值为AA&＃39;(或A&＃39;A)的特征值开平方&＃xff0c;前面讲过AA&＃39;的特征值都大于等于0。当x为单位向量时&＃xff0c;上式就是我们的目标函数表达式。然而&＃xff0c;上式只是告诉我们能取到最大值是多少&＃xff0c;并没有说取到最大值时x的方向&＃xff0c;要想知道取到最大值时的方向&＃xff0c;那就来证明这个定理吧&＃xff01;

考察对称阵

设

为其n个特征值&＃xff0c;并令与之对应的单位特征向量为&＃xff1a;

对了&＃xff0c;忘了提醒&＃xff0c;对称阵不同特征值对应的特征向量两两正交&＃xff01;这组特征向量构成了空间中的一组单位正交基。

任意取一个向量x&＃xff0c;将其表示为

则

将代入上式可得

由于这些单位特征向量两两正交&＃xff0c;只有相同的做内积为1&＃xff0c;不同的做内积为0.所以上式做内积出来的结果为&＃xff1a;

根据特征值的大小关系有

所以

定理得证&＃xff01;

显然&＃xff0c;当时取得最大值

再回到我们的问题&＃xff0c;需要最大化&＃xff1a;

将X&＃39;代入上面证明过程中的矩阵A&＃xff0c;则u1的方向即为A&＃39;A&＃61;(X&＃39;)&＃39;X&＃39;&＃61;XX&＃39;对大特征值对应的特征向量的方向&＃xff01;

所以第一主轴已经找到&＃xff0c;第二主轴为次大特征值对应的特征向量的方向&＃xff0c;以此类推。

两种方法殊途同归&＃xff0c;现在来解答关于主成分保留占比的问题。上面我们知道第一主轴对应的最大值是最大奇异值&＃xff08;也就是AA&＃39;最大特征值开平方&＃xff09;&＃xff0c;第二主轴对应的最大值是次大奇异值&＃xff0c;以此类推。那么假设取前r大奇异值对应的主轴作为提取的主成分&＃xff0c;则提取后的数据信息占比为&＃xff1a;

分子是前r大奇异值的平方和&＃xff0c;分母是所有奇异值的平方和。

到此&＃xff0c;主成分分析PCA就讲完了&＃xff0c;文章最后提到了奇异值&＃xff0c;关于这个&＃xff0c;后面的奇异值分解&＃xff08;SVD&＃xff09;文章将会详细讲解并给出其具体应用&＃xff01;