彻底学会PCA2-最大可分性的推导


【系列文章】:
彻底学会PCA1-理解PCA原理
彻底学会PCA2-最大可分性的推导
彻底学会PCA3-最近重构性的推导

前言

上一篇文章《彻底学会PCA1-理解PCA原理》中,我为大家讲解了一下PCA是什么,这一篇文章我打算从数学的角度推导一下PCA。PCA一共有2种证明方式,一种是最大可分性,一种是最近重构性。这一篇文章从最大可分性的角度进行介绍,另一种解释会在下一篇文章中介绍。希望可以帮助到大家,欢迎随时通过邮箱与我交流。

阅读本篇文章,您需要掌握基本的向量、基、方差、协方差矩阵等相关基础知识。

优化目标

推导的大体思路就是明确优化目标,然后求出最优解。我们在这里通过一个例子来引出优化目标。假设我们有一组数据(2个特征,5组数据): \[ \begin{pmatrix} 1&1&2&4&2\\1&3&3&4&4 \end{pmatrix} \] 我们分别将第一个和第二个字段减去各自的平均值,可以得到: \[ \begin{pmatrix} -1&-1&0&2&0\\-2&0&0&1&1 \end{pmatrix} \] 将上述数据映射到坐标系中可以得到:
现在问题来了:如果我们必须使用一维来表示这些数据,又希望尽量保留原始的信息,你要如何选择?

通过上一节对基变换的讨论我们知道,这个问题实际上是要在二维平面中选择一个方向,将所有数据都投影到这个方向所在直线上,用投影值表示原始记录。这是一个实际的二维降到一维的问题。

那么如何选择这个方向(或者说基)才能尽量保留最多的原始信息呢?一种直观的看法是:希望投影后的投影值尽可能分散。

以上图为例,可以看出如果向x轴投影,那么最左边的两个点会重叠在一起,中间的两个点也会重叠在一起,于是本身四个各不相同的二维点投影后只剩下两个不同的值了,这是一种严重的信息丢失,同理,如果向y轴投影最上面的两个点和分布在x轴上的两个点也会重叠。所以看来x和y轴都不是最好的投影选择。我们直观目测,如果向通过第一象限和第三象限的斜线投影,则五个点在投影后还是可以区分的。

方差

在数学中,表示分散程度使用一种度量就是方差。方差是每一个样本与平均值的差的平方和的均值: \[Var(a) = \frac{1}{m}\sum_{i=1}^m (a _i-\mu)^2\] 注意我们一开始对所有的数据都减去了均值,即现在的均值为0.所以\(\mu=0\),那么上式等于: \[Var(a) = \frac{1}{m} \sum _{i=1}^m a _i^2\] 那么对于我们刚刚提到的例子,我们只需要找到一个一维的基,使得所有数据变换到这个基上后,方差值最大即可。

协方差

对于上面二维降成一维的问题来说,找到那个使得方差最大的方向就可以了。不过对于更高维,还有一个问题需要解决。考虑三维降到二维问题。与之前相同,首先我们希望找到一个方向使得投影后方差最大,这样就完成了第一个方向的选择,继而我们选择第二个投影方向。

如果我们还是单纯只选择方差最大的方向,很明显,这个方向与第一个方向应该是“几乎重合在一起”,显然这样的维度是没有用的,因此,应该有其他约束条件。从直观上说,让两个字段尽可能表示更多的原始信息,我们是不希望它们之间存在(线性)相关性的,因为相关性意味着两个字段不是完全独立,必然存在重复表示的信息。

数学上可以用两个字段的协方差表示其相关性,由于已经让每个字段均值为0,则: \[Cov(a,b) = \frac{1}{m} \sum _{i=1}^m a _i b _i\] 当协方差为0时,表示两个字段完全独立。为了让协方差为0,我们选择第二个基时只能在与第一个基正交的方向上选择。因此最终选择的两个方向一定是正交的。

至此,我们得到了降维问题的优化目标:将一组N维向量降为K维(K大于0,小于N),其目标是选择K个单位(模为1)正交基,使得原始数据变换到这组基上后,各字段两两间协方差为0,而字段的方差则尽可能大(在正交的约束下,取最大的K个方差)。

协方差矩阵

上面我们导出了优化目标,但是这个目标似乎不能直接作为操作指南(或者说算法),因为它只说要什么,但根本没有说怎么做。所以我们要继续在数学上研究计算方案。

我们看到,最终要达到的目的与字段内方差及字段间协方差有密切关系。因此我们希望能将两者统一表示,仔细观察发现,两者均可以表示为内积的形式,而内积又与矩阵相乘密切相关。于是我们来了灵感:

假设我们只有a和b两个字段,那么我们将它们按行组成矩阵X: \[ X=\begin{pmatrix} a _1&a _2&...&a _m\\b _1&b _2&...&b _m \end{pmatrix} \] 然后我们用X乘以X的转置,并乘上系数1/m: \[ \frac{1}{m}XX^T =\begin{pmatrix} \frac{1}{m}\sum _{i=1}^m a _i^2&\frac{1}{m}\sum _{i=1}^m a _i b _i\\ \frac{1}{m}\sum _{i=1}^m a _i b _i&\frac{1}{m}\sum _{i=1}^m b _i^2 \end{pmatrix} \] 我们惊奇的发现这个矩阵对角线的两个元素分别是两个字段的方差,剩下的元素是a和b的方差。方差和协方差就这么被统一到了一个矩阵中。根据矩阵的运算法则,这个结论是可以被推广到一般情况的。

协方差矩阵对角化

那么如何找到一组基,并将它们合理的排序,使得前K个能最小损失的表示我们的数据呢?我们只需要将协方差矩阵对角化即可。那么为什么要对角化呢?我们来举个例子。设原始矩阵X对应的协方差矩阵C,而P是一组基按照行组成的矩阵,设Y = PX,则Y为X对P做基变换后的数据。设Y的协方差矩阵为D,那么D与C的关系可以这么推导出来: \[\begin{aligned} D {}&= \frac{1}{m}YY^T{} \\
&=\frac{1}{m}(PX)(PX)^T \\ &=\frac{1}{m}PXX^TP^T \\ &=P(\frac{1}{m}XX^T)P^T \\ &=PCP^T \end{aligned}\] 这不就是矩阵对角化的关系式嘛!我们要找的P就是能让原始协方差矩阵对角化的P,即寻找一个矩阵P,使得\(PCP^T\)是一个对角矩阵,并且对角元素从大到小排列,那么P的前K行就是要寻找的基。

剩下的知识就是单纯的对C进行对角化处理。

对角化处理

这里给大家举个例子,方便大家了解相关的对角化处理知识。假设我们要对矩阵A进行对角化处理:
下面我们一步一步来进行对角化处理:

参考文献

PCA的数学原理


分享博文


评论博文


Last one :   彻底学会PCA3-最近重构性的推导

Next article :   彻底学会PCA1-理解PCA原理