本文略微有点长,请大家耐心观看,你一定会有收获fighting!!!
文章目录
- PCA数学原理
- 数据的向量表示及降维问题
- 向量的表示及基变换
- 内积与投影
- 基
- 基变换的矩阵表示
- 协方差矩阵及优化目标
- 方差
- 协方差
- 协方差矩阵
- 协方差矩阵对角化
- 算法
- 进一步讨论
- 主成分分析(李航)
- 16.1 总体主成分分析
- 16.1.1 基本想法
- 16.1.2 定义和导出
- 16.1.3 主要性质
- 16.1.4 主成分的个数
- 16.1 .5 规范化变量的总体主成分
- 16.2 样本主成分分析
- 16.2.1 样本主成分的定义与性质
- 16.2.2 相关矩阵的特征值分解算法
- 16.2.3 数据矩阵的奇异值分解算法
- PRML主成分分析
- 最⼤⽅差形式
- 最小误差形式(最小重构距离)
- PCA的应用
- 参考
PCA数学原理
首先,给出不太严谨的数学推导PCA
PCA(Principal Component Analysis)是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示,可用于提取数据的主要特征分量,常用于高维数据的降维。网上关于PCA的文章有很多,但是大多数只描述了PCA的分析过程,而没有讲述其中的原理。这篇文章的目的是介绍PCA的基本数学原理,帮助读者了解PCA的工作机制是什么。
当然我并不打算把文章写成纯数学文章,而是希望用直观和易懂的方式叙述PCA的数学原理,所以整个文章不会引入严格的数学推导。希望读者在看完这篇文章后能更好的明白PCA的工作原理。
数据的向量表示及降维问题
一般情况下,在数据挖掘和机器学习中,数据被表示为向量。例如某个淘宝店2012年全年的流量及交易情况可以看成一组记录的集合,其中每一天的数据是一条记录,格式如下:
(日期, 浏览量, 访客数, 下单数, 成交数, 成交金额)
其中“日期”是一个记录标志而非度量值,而数据挖掘关心的大多是度量值,因此如果我们忽略日期这个字段后,我们得到一组记录,每条记录可以被表示为一个五维向量,其中一条看起来大约是这个样子:
注意这里我用了转置,因为习惯上使用列向量表示一条记录(后面会看到原因),本文后面也会遵循这个准则。不过为了方便有时我会省略转置符号,但我们说到向量默认都是指列向量。
我们当然可以对这一组五维向量进行分析和挖掘,不过我们知道,很多机器学习算法的复杂度和数据的维数有着密切关系,甚至与维数呈指数级关联。当然,这里区区五维的数据,也许还无所谓,但是实际机器学习中处理成千上万甚至几十万维的情况也并不罕见,在这种情况下,机器学习的资源消耗是不可接受的,因此我们必须对数据进行降维。
降维当然意味着信息的丢失,不过鉴于实际数据本身常常存在的相关性,我们可以想办法在降维的同时将信息的损失尽量降低。
举个例子,假如某学籍数据有两列M和F,其中M列的取值是如何此学生为男性取值1,为女性取值0;而F列是学生为女性取值1,男性取值0。此时如果我们统计全部学籍数据,会发现对于任何一条记录来说,当M为1时F必定为0,反之当M为0时F必定为1。在这种情况下,我们将M或F去掉实际上没有任何信息的损失,因为只要保留一列就可以完全还原另一列。
当然上面是一个极端的情况,在现实中也许不会出现,不过类似的情况还是很常见的。例如上面淘宝店铺的数据,从经验我们可以知道,“浏览量”和“访客数”往往具有较强的相关关系,而“下单数”和“成交数”也具有较强的相关关系。这里我们非正式的使用“相关关系”这个词,可以直观理解为“当某一天这个店铺的浏览量较高(或较低)时,我们应该很大程度上认为这天的访客数也较高(或较低)”。后面的章节中我们会给出相关性的严格数学定义。
这种情况表明,如果我们删除浏览量或访客数其中一个指标,我们应该期待并不会丢失太多信息。因此我们可以删除一个,以降低机器学习算法的复杂度。
上面给出的是降维的朴素思想描述,可以有助于直观理解降维的动机和可行性,但并不具有操作指导意义。例如,我们到底删除哪一列损失的信息才最小?亦或根本不是单纯删除几列,而是通过某些变换将原始数据变为更少的列但又使得丢失的信息最小?到底如何度量丢失信息的多少?如何根据原始数据决定具体的降维操作步骤?
要回答上面的问题,就要对降维问题进行数学化和形式化的讨论。而PCA是一种具有严格数学基础并且已被广泛采用的降维方法。下面我不会直接描述PCA,而是通过逐步分析问题,让我们一起重新“发明”一遍PCA。
向量的表示及基变换
既然我们面对的数据被抽象为一组向量,那么下面有必要研究一些向量的数学性质。而这些数学性质将成为后续导出PCA的理论基础。
内积与投影
下面先来看一个高中就学过的向量运算:内积。两个维数相同的向量的内积被定义为:
内积运算将两个向量映射为一个实数。其计算方式非常容易理解,但是其意义并不明显。下面我们分析内积的几何意义。假设A和B是两个n维向量,我们知道n维向量可以等价表示为n维空间中的一条从原点发射的有向线段,为了简单起见我们假设A和B均为二维向量,则A=(x1,y1),B=(x2,y2)。则在二维平面上A和B可以用两条发自原点的有向线段表示,见下图:
好,现在我们从A点向B所在直线引一条垂线。我们知道垂线与B的交点叫做A在B上的投影,再设A与B的夹角是a,则投影的矢量长度为 ,其中
注意这里我们专门区分了矢量长度和标量长度,标量长度总是大于等于0,值就是线段的长度;而矢量长度可能为负,其绝对值是线段长度,而符号取决于其方向与标准方向相同或相反。
到这里还是看不出内积和这东西有什么关系,不过如果我们将内积表示为另一种我们熟悉的形式:
现在事情似乎是有点眉目了:A与B的内积等于A到B的投影长度乘以B的模。再进一步,如果我们假设B的模为1,即让|B|=1,那么就变成了:
也就是说, 设向量B的模为1,则A与B的内积值等于A向B所在直线投影的矢量长度 !这就是内积的一种几何解释,也是我们得到的第一个重要结论。在后面的推导中,将反复使用这个结论。
基
下面我们继续在二维空间内讨论向量。上文说过,一个二维向量可以对应二维笛卡尔直角坐标系中从原点出发的一个有向线段。例如下面这个向量:
在代数表示方面,我们经常用线段终点的点坐标表示向量,例如上面的向量可以表示为(3,2),这是我们再熟悉不过的向量表示。
不过我们常常忽略, 只有一个(3,2)本身是不能够精确表示一个向量的 。我们仔细看一下,这里的3实际表示的是向量在x轴上的投影值是3,在y轴上的投影值是2。也就是说我们其实隐式引入了一个定义:以x轴和y轴上正方向长度为1的向量为标准。那么一个向量(3,2)实际是说在x轴投影为3而y轴的投影为2。注意投影是一个矢量,所以可以为负。
更正式的说,向量(x,y)实际上表示线性组合:
不难证明所有二维向量都可以表示为这样的线性组合。此处(1,0)和(0,1)叫做二维空间中的一组基。
所以, 要准确描述向量,首先要确定一组基,然后给出在基所在的各个直线上的投影值,就可以了 。只不过我们经常省略第一步,而默认以(1,0)和(0,1)为基。
我们之所以默认选择(1,0)和(0,1)为基,当然是比较方便,因为它们分别是x和y轴正方向上的单位向量,因此就使得二维平面上点坐标和向量一一对应,非常方便。但实际上任何两个线性无关的二维向量都可以成为一组基,所谓线性无关在二维平面内可以直观认为是两个不在一条直线上的向量。
例如,(1,1)和(-1,1)也可以成为一组基。一般来说,我们希望基的模是1,因为从内积的意义可以看到,如果基的模是1,那么就可以方便的用向量点乘基而直接获得其在新基上的坐标了!实际上,对应任何一个向量我们总可以找到其同方向上模为1的向量,只要让两个分量分别除以模就好了。例如,上面的基可以变为 和
现在,我们想获得(3,2)在新基上的坐标,即在两个方向上的投影矢量值,那么根据内积的几何意义,我们只要分别计算(3,2)和两个基的内积,不难得到新的坐标为。下图给出了新的基以及(3,2)在新基上坐标值的示意图:
另外这里要注意的是,我们列举的例子中基是正交的(即内积为0,或直观说相互垂直),但可以成为一组基的唯一要求就是线性无关,非正交的基也是可以的。不过因为正交基有较好的性质,所以一般使用的基都是正交的。
基变换的矩阵表示
下面我们找一种简便的方式来表示基变换。还是拿上面的例子,想一下,将(3,2)变换为新基上的坐标,就是用(3,2)与第一个基做内积运算,作为第一个新的坐标分量,然后用(3,2)与第二个基做内积运算,作为第二个新坐标的分量。实际上,我们可以用矩阵相乘的形式简洁的表示这个变换:
太漂亮了!其中矩阵的两行分别为两个基,乘以原向量,其结果刚好为新基的坐标。可以稍微推广一下,如果我们有m个二维向量,只要将二维向量按列排成一个两行m列矩阵,然后用“基矩阵”乘以这个矩阵,就得到了所有这些向量在新基下的值。例如(1,1),(2,2),(3,3),想变换到刚才那组基上,则可以这样表示:
于是一组向量的基变换被干净的表示为矩阵的相乘。
一般的,如果我们有M个N维向量,想将其变换为由R个N维向量表示的新空间中,那么首先将R个基按行组成矩阵A,然后将向量按列组成矩阵B,那么两矩阵的乘积AB就是变换结果,其中AB的第m列为A中第m列变换后的结果 。
数学表示为:
其中是一个行向量,表示第i个基,是一个列向量,表示第j个原始数据记录。
特别要注意的是,这里R可以小于N,而R决定了变换后数据的维数。也就是说,我们可以将一N维数据变换到更低维度的空间中去,变换后的维度取决于基的数量。因此这种矩阵相乘的表示也可以表示降维变换。
最后,上述分析同时给矩阵相乘找到了一种物理解释: 两个矩阵相乘的意义是将右边矩阵中的每一列列向量变换到左边矩阵中每一行行向量为基所表示的空间中去 。更抽象的说,一个矩阵可以表示一种线性变换。很多同学在学线性代数时对矩阵相乘的方法感到奇怪,但是如果明白了矩阵相乘的物理意义,其合理性就一目了然了。
协方差矩阵及优化目标
上面我们讨论了选择不同的基可以对同样一组数据给出不同的表示,而且如果基的数量少于向量本身的维数,则可以达到降维的效果。但是我们还没有回答一个最最关键的问题:如何选择基才是最优的。或者说,如果我们有一组N维向量,现在要将其降到K维(K小于N),那么我们应该如何选择K个基才能最大程度保留原有的信息?
要完全数学化这个问题非常繁杂,这里我们用一种非形式化的直观方法来看这个问题。
为了避免过于抽象的讨论,我们仍以一个具体的例子展开。假设我们的数据由五条记录组成,将它们表示成矩阵形式:
其中每一列为一条数据记录,而一行为一个字段。为了后续处理方便,我们首先将每个字段内所有值都减去字段均值,其结果是将每个字段都变为均值为0(这样做的道理和好处后面会看到)。
我们看上面的数据,第一个字段均值为2,第二个字段均值为3,所以变换后:
我们可以看下五条数据在平面直角坐标系内的样子:
现在问题来了:如果我们必须使用一维来表示这些数据,又希望尽量保留原始的信息,你要如何选择?
通过上一节对基变换的讨论我们知道,这个问题实际上是要在二维平面中选择一个方向,将所有数据都投影到这个方向所在直线上,用投影值表示原始记录。这是一个实际的二维降到一维的问题。
那么如何选择这个方向(或者说基)才能尽量保留最多的原始信息呢?一种直观的看法是:希望投影后的投影值尽可能分散。
以上图为例,可以看出如果向x轴投影,那么最左边的两个点会重叠在一起,中间的两个点也会重叠在一起,于是本身四个各不相同的二维点投影后只剩下两个不同的值了,这是一种严重的信息丢失,同理,如果向y轴投影最上面的两个点和分布在x轴上的两个点也会重叠。所以看来x和y轴都不是最好的投影选择。我们直观目测,如果向通过第一象限和第三象限的斜线投影,则五个点在投影后还是可以区分的。
下面,我们用数学方法表述这个问题。
方差
上文说到,我们希望投影后投影值尽可能分散,而这种分散程度,可以用数学上的方差来表述。此处,一个字段的方差可以看做是每个元素与字段均值的差的平方和的均值,即:
由于上面我们已经将每个字段的均值都化为0了,因此方差可以直接用每个元素的平方和除以元素个数表示:
于是上面的问题被形式化表述为:寻找一个一维基,使得所有数据变换为这个基上的坐标表示后,方差值最大。
协方差
对于上面二维降成一维的问题来说,找到那个使得方差最大的方向就可以了。不过对于更高维,还有一个问题需要解决。考虑三维降到二维问题。与之前相同,首先我们希望找到一个方向使得投影后方差最大,这样就完成了第一个方向的选择,继而我们选择第二个投影方向。
如果我们还是单纯只选择方差最大的方向,很明显,这个方向与第一个方向应该是“几乎重合在一起”,显然这样的维度是没有用的,因此,应该有其他约束条件。从直观上说,让两个字段尽可能表示更多的原始信息,我们是不希望它们之间存在(线性)相关性的,因为相关性意味着两个字段不是完全独立,必然存在重复表示的信息。
数学上可以用两个字段的协方差表示其相关性,由于已经让每个字段均值为0,则:
可以看到,在字段均值为0的情况下,两个字段的协方差简洁的表示为其内积除以元素数m。
当协方差为0时,表示两个字段完全独立。为了让协方差为0,我们选择第二个基时只能在与第一个基正交的方向上选择。因此最终选择的两个方向一定是正交的。
至此,我们得到了降维问题的优化目标: 将一组N维向量降为K维(K大于0,小于N),其目标是选择K个单位(模为1)正交基,使得原始数据变换到这组基上后,各字段两两间协方差为0,而字段的方差则尽可能大(在正交的约束下,取最大的K个方差) 。
协方差矩阵
上面我们导出了优化目标,但是这个目标似乎不能直接作为操作指南(或者说算法),因为它只说要什么,但根本没有说怎么做。所以我们要继续在数学上研究计算方案。
我们看到,最终要达到的目的与字段内方差及字段间协方差有密切关系。因此我们希望能将两者统一表示,仔细观察发现,两者均可以表示为内积的形式,而内积又与矩阵相乘密切相关。于是我们来了灵感:
假设我们只有a和b两个字段,那么我们将它们按行组成矩阵X:
然后我们用X乘以X的转置,并乘上系数1/m:
奇迹出现了!这个矩阵对角线上的两个元素分别是两个字段的方差,而其它元素是a和b的协方差。两者被统一到了一个矩阵的。
根据矩阵相乘的运算法则,这个结论很容易被推广到一般情况:
设我们有m个n维数据记录,将其按列排成n乘m的矩阵X,设,则C是一个对称矩阵,其对角线分别个各个字段的方差,而第i行j列和j行i列元素相同,表示i和j两个字段的协方差 。
协方差矩阵对角化
根据上述推导,我们发现要达到优化目前,等价于将协方差矩阵对角化:即除对角线外的其它元素化为0,并且在对角线上将元素按大小从上到下排列,这样我们就达到了优化目的。这样说可能还不是很明晰,我们进一步看下原矩阵与基变换后矩阵协方差矩阵的关系:
设原始数据矩阵X对应的协方差矩阵为C,而P是一组基按行组成的矩阵,设Y=PX,则Y为X对P做基变换后的数据。设Y的协方差矩阵为D,我们推导一下D与C的关系:
现在事情很明白了!我们要找的P不是别的,而是能让原始协方差矩阵对角化的P。换句话说,优化目标变成了 寻找一个矩阵P,满足是一个对角矩阵,并且对角元素按从大到小依次排列,那么P的前K行就是要寻找的基,用P的前K行组成的矩阵乘以X就使得X从N维降到了K维并满足上述优化条件 。
至此,我们离“发明”PCA还有仅一步之遥!
现在所有焦点都聚焦在了协方差矩阵对角化问题上,有时,我们真应该感谢数学家的先行,因为矩阵对角化在线性代数领域已经属于被玩烂了的东西,所以这在数学上根本不是问题。
由上文知道,协方差矩阵C是一个是对称矩阵,在线性代数上,实对称矩阵有一系列非常好的性质:
1)实对称矩阵不同特征值对应的特征向量必然正交。
2)设特征向量λ重数为r,则必然存在r个线性无关的特征向量对应于λ,因此可以将这r个特征向量单位正交化。
由上面两条可知,一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量,设这n个特征向量为,我们将其按列组成矩阵:
则对协方差矩阵C有如下结论:
其中Λ为对角矩阵,其对角元素为各特征向量对应的特征值(可能有重复)。
以上结论不再给出严格的数学证明,对证明感兴趣的朋友可以参考线性代数书籍关于“实对称矩阵对角化”的内容。
到这里,我们发现我们已经找到了需要的矩阵P:
P是协方差矩阵的特征向量单位化后按行排列出的矩阵,其中每一行都是C的一个特征向量。如果设P按照Λ中特征值的从大到小,将特征向量从上到下排列,则用P的前K行组成的矩阵乘以原始数据矩阵X,就得到了我们需要的降维后的数据矩阵Y。
至此我们完成了整个PCA的数学原理讨论。在下面的一节,我们将给出PCA的一个实例。
算法
为了巩固上面的理论,我们在这一节给出一个具体的PCA实例。
总结一下PCA的算法步骤:
设有m条n维数据。
1)将原始数据按列组成n行m列矩阵X
2)将X的每一行(代表一个属性字段)进行零均值化,即减去这一行的均值
3)求出协方差矩阵
4)求出协方差矩阵的特征值及对应的特征向量
5)将特征向量按对应特征值大小从上到下按行排列成矩阵,取前k行组成矩阵P
6)Y=PX即为降维到k维后的数据
进一步讨论
根据上面对PCA的数学原理的解释,我们可以了解到一些PCA的能力和限制。PCA本质上是将方差最大的方向作为主要特征,并且在各个正交方向上将数据“离相关”,也就是让它们在不同正交方向上没有相关性。
因此,PCA也存在一些限制,例如它可以很好的解除线性相关,但是对于高阶相关性就没有办法了,对于存在高阶相关性的数据,可以考虑Kernel PCA,通过Kernel函数将非线性相关转为线性相关,关于这点就不展开讨论了。另外,PCA假设数据各主特征是分布在正交方向上,如果在非正交方向上存在几个方差较大的方向,PCA的效果就大打折扣了。
最后需要说明的是,PCA是一种无参数技术,也就是说面对同样的数据,如果不考虑清洗,谁来做结果都一样,没有主观参数的介入,所以PCA便于通用实现,但是本身无法个性化的优化。
希望这篇文章能帮助朋友们了解PCA的数学理论基础和实现原理,借此了解PCA的适用场景和限制,从而更好的使用这个算法。
有了上面的基础,那么再来看李航老师书上的推导(其中补充了推导不详细的部分),他这个新的部分在于SVD来求特征向量。
主成分分析(李航)
引出降维,二维三维上的结论在高维就不work了
- 主成分分析(principal component analysis, PCA)是一种常用的无监督学习方法,这一方法利用正交变换把由线性相关变量表示的观测数据转换为少数几个由线性无关变量表示的数据,线性无关的变量称为主成分。
- 主成分的个数通常小于原始变量的个数,所以主成分分析属于降维方法。
- 主成分分析主要用于发现数据中的基本结构,即数据中变量之间的关系
16.1 总体主成分分析
16.1.1 基本想法
主成分分析中,首先对给定数据进行规范化,使得数据每一变量的平均值为0,方差为1。之后对数据进行正交变换,原来由线性相关变量表示的数据,通过正交变换变成由若干个线性无关的新变量表示的数据。新变量是可能的正交变换中变量的方差的和(信息保存)最大的,方差表示在新变量上信息的大小。将新变量依次称为第一主成分、第二主成分等。这就是主成分分析的基本思想。
通过主成分分析,可以利用主成分近似地表示原始数据,这可理解为发现数据的“基本结构” ;也可以把数据由少数主成分表示,这可理解为对数据降维。
下面再看方差最大的解释。
假设有两个变量 和 , 三个样本点 , 样 本分布在由 和 轴组成的坐标系中, 如下图所示。对坐标系进行旋转变换, 得到新的坐标轴 , 表示新的变量 。样本点 在 轴上投影, 得到 轴的 坐标值 坐标值的平方和 表示样本在变量 上的方 差和。主成分分析旨在选取正交变换中方差最大的变量, 作为第一主成分, 也就是旋转变换中坐标值的平方和最大的轴。==注意到旋转变换中样本点到原点的距离的平方和 保持不变, 根据勾股定理, 坐标值的平方和 最大等价于样本点到 轴的距离的平方和
16.1.2 定义和导出
假设 是 维随机变量, 其均值向量是
协方差矩阵是
考虑由 维随机变量 到 维随机变量
其中 。
由随机变量的性质可知,
详细推导:
总体主成分
定义 (总体主成分) 给定一个如式 所示的线性变换, 如果它们满足下列条件:
(1) 系数向量 是单位向量, 即 ;
(2) 变量 与 互不相关, 即 ;
(3) 变量 是 的所有线性变换中方差最大的; 是与 不相关的 的所有 线性变换中方差最大的;一般地, 是与 都不相关 的 的所有线性变换中方差最大的; 这时分别称 为 的第一主成分、第二主成分、… 第 主成分。
定义中的条件 表明线性变换是正交变换,
条件 给出了一个求主成分的方法: 第一步, 在
中, 在 条件下, 求方差最大的, 得到 的第一主成分; 第二步, 在与 不相关的
中, 在 条件下, 求方差最大的, 得到 的第二主成分; 第 步, 在与 不相关的
中, 在 条件下, 求方差最大的, 得到 的第 主成分; 如此继续下去, 直到 得到 的第
16.1.3 主要性质
定理 设 是 维随机变量, 是 的协方差矩阵, 的特征值分别是 , 特征值对应的单位特征向量分别是 , 则 的 第
的第
即协方差矩阵 的第
证明 采用拉格朗日乘子法求出主成分。
首先求 的第一主成分 , 即求系数向量 。由定义 知, 第一主成 分的 是在 条件下,达到最大的。
求第一主成分就是求解约束最优化问题:定义拉格朗日函数
其中 是拉格朗日乘子。将拉格朗日函数L对
因此, 是 的特征值,
假设 是 的最大特征值 对应的单位特征向量, 显然 与 是最优化问题的解。所以, 构成第一主成分, 其方差等于协方差矩阵的最大特征值
接着求 的第二主成分 第二主成分的 是在 , 且 与 不相关的条件下,
达到最大的。
求第二主成分需要求解约束最优化问题注意到
以及
定义拉格朗日函数
其中 是拉格朗日乘子。对
将方程左乘以
正交=>
此式前两项为 0 , 且 , 导出 , 由此推出
由此, 是 的特征值,
假设 是 的第二大特征值 对应的单位特征向量, 显然 与 是以上 最优化问题的解 。于是 构成第二主成分, 其方差等于协方差矩阵的第二大特征值,
一般地, 的第 主成分是 , 并且 , 这里 是 的第 个 特征值并且 是对应的单位特征向量。可以从个第 主成分出发递推证明第 个主成分的情况。
按照上述方法求得第一、第二、直到第 主成分, 其系数向量 分别是 的第一个、第二个、直到第 个单位特征向量, 分别是对应 的特征值。并且, 第 主成分的方差等于 的第定理证毕。
推论 维随机变量 的分量依次是 的第一主成分 到第 主成分的充要条件是:
(1)
(1) 为了叙述方便,这里将变量和其最优值用同一符号表示。
(2)
其中 是 的第 个特征值, 是对应的单位特征向量, . 以上证明中, 是 的第 个特征值,
用矩阵表示即为
这里 是对角矩阵, 其第 个对角元素是 . 因为 是正交矩阵, 即 , 由式
和
总体主成分的性质:
(1)总体主成分
(2)总体主成分 的方差之和等于随机变量
其中 是随机变量 的方差, 即协方差矩阵 的对角元素。事实上, 利用式
为正交矩阵==>
(3) 第 个主成分 与变量 的相关系数 称为因子负荷量 (factor loading), 它表示第 个主成分 与变量
因为
其中 为基本单位向量, 其第
故得式
(4) 第 个主成分 与
由式
(5) 个主成分与第 个变量
由于
又因 可以表为 的线性组合, 所以 与
故得式
16.1.4 主成分的个数
定理 对任意正整数 , 考虑正交线性变换
其中 是 维向量, 是 矩阵, 令
则 的迹 在 时取得最大值, 其中矩阵 由正交矩阵 的前
证明 令 是 的第 列, 由于正交矩阵 的列构成 维空间的基, 所以 可以由
等价地
其中 是 矩阵, 其第 行第 列元素为 。
首先,其中 是 的第
其次, 由式 及
由于 是正交的,
即
这样, 矩阵 可以认为是某个 阶正交矩阵 的前 列。正交矩阵
其中 是 的第 行。由于矩阵 的行包括矩阵 的行的前
即
注意到在式 中 是 的系数, 由式 这些系数之和是 , 且 由式 知这些系数小于等于 1 。因为 , 显然, 当能找到
时, 最大。而当
满足式 。所以,当 时,
定理 表明, 当 的线性变换 在 时, 其协方差矩阵 的迹 取得最大值, 这就是说, 当取 的前 列取 的前
定理
这里 是 矩阵, 和 的定义与定理 相同, 则 在 时 取得最小值, 其中矩阵 由 的后 列组成。
定理 可以理解为, 当 舍弃 的后 列, 即舍弃变量 的后
以上两个定理作为选择 。
具体选择 的方法, 通常利用方差贡献率。
定义 第 主成分 的方差贡献率定义为 的方差与所有方差之和的比, 记作
个主成分 的累计方差贡献率定义为
通常取 使得累计方差贡献率达到规定的百分比以上, 例如 以上。累计方差贡献率反映了主成分保留信息的比例, 但它不能反映对某个原有变量 保留信息的比例, 这时通常利用 个主成分 对原有变量
定义 个主成分 对原有变量 的贡献率定义为 与 的相关系数的平方, 记作
计算公式如下:
16.1 .5 规范化变量的总体主成分
在实际问题中,直接求主成分有时会产生不合理的结果。为了消除这个影响, 常常对各个随机变量实施规范化, 使其均值为 0 , 方差为 1 。
设 为 维随机变量, 为第 个随机变量, , 令
其中 分别是随机变量 的均值和方差, 这时 就是 的规范化随机 变量。
显然, 规范化随机变量的协方差矩阵就是相关矩阵 主成分分析通常在规范化 随机变量的协方差矩阵即相关矩阵上进行。
对照总体主成分的性质可知, 规范化随机变量的总体主成分有以下性质:
(1)规范化变量主成分的协方差矩阵是
其中 为相关矩阵 的特征值。
(2)协方差矩阵的特征值之和为
(3)规范化随机变量 与主成分 的相关系数 因子负荷量
其中 为矩阵 对应于特征值 的单位特征向量。
(4)所有规范化随机变量 与主成分 的相关系数的平方和等于
(5)规范化随机变量 与所有主成分
16.2 样本主成分分析
预备知识
期望:
协方差:
中心矩阵
16.2.1 样本主成分的定义与性质
假设对 维随机变量 进行 次独立观测, 表示观测样本, 其中 表示第 个观测样本, 表示第 个 观测样本的第 个变量, 。 观测数据用样本矩阵
给定样本矩阵 , 可以估计样本均值, 以及样本协方差。样本均值向量
样本协方差矩阵
其中 为第 个变量的样本均值, 为第 个变量的样本 均值。
样本相关矩阵
定义 维向量 到 维向量
其中
考虑式
其中 是 维向量 的第 个变量, 相应于容量为 的样本 的 样本均值
其中 是随机向量
的样本方差
对任意两个线性变换 , 相应于容量为 的样本 ,
样本主成分的定义:
定义 (样本主成分) 给定样本矩阵 . 样本第一主成分 是在 条件下, 使得 的样本方差 最大的 的线性 变换; 样本第二主成分 是在 和 与 的样本协方差 条件下, 使得 的样本方差 最大的 的线性变换;一般地, 样本第 主成分 是在 和 与 的样本协方差 条件下, 使得 的样本方差 最大的 的线性变换。
样本主成分与总体主成分具有同样的性质。 这从样本主成分的定义容易看出。只 要以样本协方差矩阵 代替总体协方差矩阵 即可。总体主成分的定理 及定理 对样本主成分依然成立。
在使用样本主成分时, 一般假设样本数据是规范化的, 即对样本矩阵作如下变换:
其中
将规范化变量 仍记作 , 规范化的样本矩阵仍记作 。 这时, 样本协方差矩阵 就是样本相关矩阵
样本协方差矩阵 是总体协方差矩阵 的无偏估计, 样本相关矩阵 是总体相关矩阵的无偏估计, 的特征值和特征向量是
16.2.2 相关矩阵的特征值分解算法
数据的协方差矩阵或相关矩阵的特征值分解方法。
给定样本矩阵 , 利用数据的样本协方差矩阵或者样本相关矩阵的特征值分解进行主成分分析。具体步骤如下:
(1) 对观测数据按式 进行规范化处理, 得到规范化数据矩阵, 仍以 表示。
(2) 依据规范化数据矩阵, 计算样本相关矩阵
其中
(3) 求样本相关矩阵 的 个特征值和对应的 个单位特征向量。
求解
得 的
求方差贡献率 达到预定值的主成分个数
求前
(4) 求 个样本主成分
以 个单位特征向量为系数进行线性变换, 求出
(5) 计算 个主成分 与原变量 的相关系数 , 以及 个主成分对原 变量 的贡献率 。
(6) 计算 个样本的 个主成分值
将规范化样本数据代入 个主成分式 , 得到 个样本的主成分值。第 个 样本 的第
主成分分析得到的结果可以用于其他机器学习方法的输入。比如,将样本点投影到以主成分为坐标轴的空间中,然后应用聚类算法, 就可以对样本点进行聚类。
16.2.3 数据矩阵的奇异值分解算法
给定样本矩阵 , 利用数据矩阵奇异值分解进行主成分分析。具体过程如下。 这 里假设有 个主成分。
参照式 , 对于 实矩阵 , 假设其秩为 , 则可以将矩阵
式中 是 矩阵, 是 矩阵, 是 阶对角矩阵; 分别由取 的完全奇异值分解的矩阵 的前 列, 由取 的完全奇异值分解的矩阵 的 前 个对角线元素得到。
定义一个新的 矩阵
即 等于 的协方差矩阵
主成分分析归结于求协方差矩阵 的特征值和对应的单位特征向量, 所以问题转化 为求矩阵 的特征值和对应的单位特征向量。
假设 的截断奇异值分解为 , 那么 的列向量就是 。因此, 的列向量就是 的主成分。于是, 求 主成分可以通过 求
具体算法如下。
算法 (主成分分析算法)
输入: 样本矩阵 , 其每一行元素的均值为零;
输出: 样本主成分矩阵 。
参数: 主成分个数
(1) 构造新的
每一列的均值为零。
(2) 对矩阵
有 个奇异值、奇异向量。矩阵 的前 列构成 个样本主成分。
(3) 求
至此,PCA的讲解还不是太透彻,我们再来看PCA中从两个角度来推导的PCA
PRML主成分分析
有两种经常使用的PCA的定义, 它们会给出同样的算法。PCA可以被定义为数据在低维线性 空间上的正交投影, 这个线性空间被称为主子空间(principal subspace), 使得投影数据的方差 被最大化(Hotelling, 1933)。等价地, 它也可以被定义为使得平均投影代价最小的线性投影。 平均投影代价是指数据点和它们的投影之间的平均平方距离(Pearson, 1901)。正交投影的过 程如下图所示。我们依次讨论这些定义。
图1 : 主成分分析寻找⼀个低维空间,被称为主⼦平⾯,⽤紫⾊的线表⽰,使得数据点(红点)在⼦空
间上的正交投影能够最⼤化投影点(绿点)的⽅差。 PCA的另⼀个定义基于的是投影误差的平⽅和的最
⼩值,⽤蓝线表⽰。
最⼤⽅差形式
考虑一组观测数据集 , 其中 , 因此 是一个 维欧几里得空间中的变量。 我们的目标是将数据投影到维度 的空间中, 同时最大化投影数据的方差。现阶段, 我们 假设 的值是给定的。稍后在本章中, 我们会研究从数据中确定合适的 值的方法。
首先, 考虑在一维空间 上的投影。我们可以使用 维向量 定义这个空间的方 向。为了方便(并且不失一般性), 我们假定选择一个单位向量, 从而 (注意, 我们 只对 的方向感兴趣, 而对 本身的大小不感兴趣 。这样, 每个数据点 被投影到一个标量 值 上。投影数据的均值是 , 其中,
投影数据的方差为
其中
我们现在关于 最大化投影方差 。很明显, 最大化的过程必须满足一定的限制来防 止 。恰当的限制来自归一化条件 。为了强制满足这个限制, 我们引入拉格 朗日乘数, 记作 , 然后对下式进行一个无限制的最大化
通过令它关于
这表明 一定是 的一个特征向量。如果我们左乘 , 使用 , 我们看到方差为
因此当我们将 设置为与具有最大的特征值
我们可以用一种增量的方式定义额外的主成分, 方法为: 在所有与那些已经考虑过的方向正 交的所有可能的方向中, 将新的方向选择为最大化投影方差的方向。如果我们考虑 维投影 空间的一般情形, 那么最大化投影数据方差的最优线性投影由数据协方差矩阵 的 个特征 向量 定义, 对应于 个最大的特征值 。可以通过归纳法很容易地证明出 来。
总结一下, 主成分分析涉及到计算数据集的均值 和协方差矩阵 , 然后寻找 的对应 于 个最大特征值的 个特征向量。寻找特征值和特征向量的算法以及与特征向量分解相关的 定理, 可以参考Golub and Van Loan (1996)。注意, 计算一个 矩阵的完整的特征向量 分解的代价为 。如果我们计划将我们的数据投影到前 个主成分中, 那么我们只需寻 找前 个特征值和特征向量。这可以使用更高效的方法得到, 例如幂方法(power method) (Golub and Van Loan, 1996),它的时间复杂度为 , 或者我们也可以使用EM算法。
最小误差形式(最小重构距离)
我们现在讨论 的另一种形式, 基于误差最小化的投影。为了完成这一点, 我们引入 维 基向量的一个完整的单位正交集合 , 其中 , 且满足
由于基是完整的, 因此每个数据点可以精确地表示为基向量的一个线性组合, 即
其中, 系数 对于不同的数据点来说是不同的。这对应于将坐标系旋转到了一个由 定义的 新坐标系, 原始的 个分量 被替换为一个等价的集合 。与 做内 积, 然后使用单位正交性质, 我们有 , 因此不失一般性, 我们有
然而, 我们的目标是使用限定数量 个变量的一种表示方法来近似数据点, 这对应于 在低维子空间上的一个投影。不失一般性, 维线性子空间可以用前 个基向量表示, 因此我 们可以用下式来近似每个数据点
其中 依赖于特定的数据点, 而 是常数, 对于所有数据点都相同。我们可以任意选 择 和 , 从而最小化由维度降低所引入的失真。作为失真的度量, 我们使用原始数 据点与它的近似点
首先考虑关于 的最小化。消去 , 令它关于
其中 。类似地, 令 关于
其中 。如果我们消去 中的 和 , 使用一般的展开式 , 我们 有
从中我们看到, 从 到 的位移向量位于与主子空间垂直的空间中, 因为它是 的线性组 合, 其中 , 如图 1所示。这与预期相符, 因为投影点 一定位于主子空间 内, 但是我们可以在那个子空间内自由移动投影点, 因此最小的误差由正交投影给出。 于是, 我们得到了失真度量 的表达式, 它是一个纯粹的关于
剩下的任务是关于 对 进行最小化, 这必须是具有限制条件的最小化, 因为如果不这 样, 我们会得到 这一没有意义的结果。限制来自于单位正交条件, 并且正如我们将看到 的那样, 解可以表示为协方差矩阵的特征向量展开式。在考虑一个形式化的解之前, 让我们试 着直观地考察一下这个结果。考虑二维数据空间 以及一维主子空间 的情形。我们必 须选择一个方向 来最小化 , 同时满足限制条件 。使用拉格朗日乘数
令关于 的导数等于零, 我们有 , 从而 是 的一个特征向量, 且特征值为 。因 此任何特征向量都会定义失真度量的一个驻点。为了找到 在最小值点处的值, 我们将 的解 代回到失真度量中, 得到 。于是, 我们通过将 选择为对应于两个特征值中较小的那个 特征值的特征向量, 可以得到 的最小值。因此, 我们应该将主子空间与具有较大的特征值的 特征向量对齐。这个结果与我们的直觉相符, 即为了最小化平均平方投影距离, 我们应该将主 成分子空间选为穿过数据点的均值并且与最大方差的方向对齐。对于特征值相等的情形, 任何 主方向的选择都会得到同样的 值。
对于任意的 和任意的 , 最小化 的一般解都可以通过将
其中 , 并且与平常一样, 特征向量
这就是与主子空间正交的特征值的加和。于是, 我们可以通过将这些特征向量选择成 个 最小的特征值对应的特征向量, 来得到 的最小值, 因此定义了主子空间的特征向量是对应 于
虽然我们已经考虑了 的情形, 但是 对于 的情形仍然成立, 这种情况下没 有维度的降低, 仅仅是将坐标轴旋转, 与主成分对齐即可。
最后, 值得注意的时, 存在一个与此密切相关的线性维度降低的方法, 被称为典型相关分析 (canonical correlation analysis),或者CCA(Hotelling, 1936; Bach and Jordan, 2002)。PCA操 作的对象是一个随机变量, 而CCA考虑两个(或者更多)的变量, 并且试图找到具有较高的交 叉相关性的线性子空间对, 从而在一个子空间中的每个分量都与另一个子空间的一个分量具有 相关性。它的解可以表示为一般的特征向量问题。
PCA的应用
- 数据压缩
- 数据预处理
- 对数据的白化或者球形化
- 数据可视化
主成分分析的另一个常见应用是数据可视化。这里, 每个数据点被投影到二维 的 主子空间中, 从而数据点 被画在了一个笛卡尔坐标系中, 坐标系由 和 定义, 其 中 和 是特征向量, 对应于最大的和第二大的特征值。对于石油流数据集, 这种图的一个例子如下图所示。
参考
- 李航 统计学习方法
- Pattern Recognition and Machine Learning
- http://blog.codinglabs.org/articles/pca-tutorial.html