主成分分析(Principal Component Analysis)

机器学习需要处理各种各样的数据,通常这些数据可以以向量的形式进行表示,现在现实环境中遇到的一大难题是数据的维数过高,导致后续处理起来时间开销消耗太大,在前面的文章中提到了一类典型的机器学习方法,也就是基于投影变换的方法。这篇文章介绍一种灰常重要的投影方法,也就是主成分分析(Principal Component Analysis, PCA)。在这一篇文章里主要弄清两个问题:一、投影的意义是什么?二、主成分分析的思想是什么?

一、投影的意义

     前面我们提到,对于一个样本可以表示成高维特征的形式,如x=(x_{1},x_{2},...x_{n})\,其本质上是高维坐标系中的一个点,其中x_{k}\是样本点在不同维度或者特征上的取值,习惯性地我们称之为“坐标”;另外,单个的样本点还可以看成是从原点出发的一个向量,而如果我们以向量为边以样本点做各个坐标轴作垂线,也就可以得到了x_{k}\。现在我们有这样一个策略,我们原有的坐标系已经不满足需求,然后需要一组新的坐标系来替代原始的坐标系,而且新坐标体系下样本点的位置或者坐标轴的个数都有可能发生变化。直观地,以二维坐标系为例,可以看到下图中原始样本点x\,而向量w\表示为一个新的坐标系下的坐标轴,显然它只有一维,这个时候只要将x\往向量w\的方向上作垂线也就得到了在新的坐标系下的值,假设为x^{'}\,那么对于这样的操作,把原始样本x\从二维坐标系变换到新的一维坐标系的过程就是通过投影变换完成的,在这个过程中我们完成了维数约减。不过这里举的例子非常特殊,原始样本只有二维,投影(降维)之后只有一维了,而实际的投影过程可以用x^{'}=w^{^{T}}x\进行表示,其中x\in \mathbb{R}^{n\times 1}\表示原始样本,x^{'}\in \mathbb{R}^{d\times 1}\表示投影后的样本,w\in \mathbb{R}^{n\times d}\表示投影变换矩阵,这里d\也就是降维后样本的维数,其几何意义表示新的坐标系中坐标的个数,也就是用d\个坐标轴来重构原始坐标系。

图1

       从线性代数的角度来看,一组坐标系可以用一组基进行表示,使用这一组基表示某个样本,即获得了样本的坐标值。而投影方法正是通过寻求矩阵变换使得基或者基的数目发生变化来达到坐标变换和降维的目的。如果基向量之间满足正交的话也就是我们通常所说的正交基,而如果基的模为1的话也就是标准正交基。单个基向量可以看成单个的向量,比如上图中的w\向量,x^{'}=w^{^{T}}x\本质上表示的是原始样本在这个基下的坐标值,在高维的情况下,显然对原始数据降至1维是不合理的,这个时候需要用d\个基来代替原始的n\个基,即通过变换矩阵W=(w_{1},w_{2},...w_{d})\得到新的样本x'=W^{T}x\,这正是降维的本质。

二、主成分分析的思想

       在第一部分中提到通过寻找矩阵变换来达到投影和降维的目的,一旦获得了这种矩阵变换也就能得到样本基于新的基的坐标值,然后就可以做后续的一些分类或者回归的工作。现在有个问题,就是我们如何寻找这样的投影变换W=(w_{1},w_{2},...w_{d})\呢?假设我们现在考虑的是分类问题,一个比较直观的想法是使得变换之后样本的离散信息较大,这样不同的样本便能够较好地进行区分,而样本的方差能够度量样本离散程度的方差。如图2所示,白色点表示原始样本,w_{1}\w_{2}\表示两个投影方向,从可分性的角度来看显然投影方向w_{1}\远好于w_{2}\,这种情况投影之后样本直接方差打,离散程度高。

图2

为了便于表示,假设新的样本集合为\left \{ y_{i} \right \}\i=1,2...m\m\为样本的个数,新的样本通过

y_{i}=w^{T}x_{i}\                                                                                   (1)

投影获得,那么投影之后样本集方差为

\sum_{i=1}^{m}\left ( y_{i} -\overline{y}\right )^{2}\                                                                          (2)

\overline{y}\为样本均值,定义\widetilde{y}=y-\overline{y}\为样本偏差那么方差可以进一步写成

\sum_{i=1}^{m}\widetilde{y_{i}}^{2}\                                                                                  (3)

对于这种多个向量平方和的形式可以利用小技巧写成矩阵迹的形式。为了简单表示,令样本集Y=\left (y_{1},y_{1}...,y_{m}\right )\表示偏差向量的集合(这里省略了偏差的上标波浪号),此时可以用矩阵YY^{T}\的迹tr(YY^{T})\来表示多个偏差向量的平方和。仔细观察矩阵YY^{T}\相乘可以发现,其对角的第一个元素是所有样本偏差第一个维度的平方和,类似地第k\个元素是所有样本偏差第k\个维度的平方和,我们知道偏差向量平方其实对应的是每个维度的平方和,那么矩阵YY^{T}\对角元素之和恰巧就是样本的总体方差。PCA的目的正是最大化方差也就是

\max tr(YY^{T})\                                                                             (4)

Y\通过Y=W^{T}X\获得,其中X\是原始样本经归一化之后的集合,这个时候优化模型可以归为

 \max tr(W^{T}XX^{T}W)\                                                                   (5)

s.t. W^{T}W=I\                                                                             

上式中给出了W^{T}W=I\ 这样的约束,其最主要的是考虑到我们所求解的基向量的长度约束为1,因此根据矩阵乘法可以恰巧得到W^{T}W=I\这样的约束条件,这种约束还有一个好处就是,如果不固定W\的话,那么优化目标可以无限拉伸投影向量的模,这个时候是无法给出最优解的。对于式(5)这种形式的优化模型可以直接用拉个人朗日乘子法获得解析解,令L(W)=tr(W^{T}XX^{T}W)+\lambda (W^{T}W-I)\,对W\进行求导并令其为0可以得到

XX^{T}W=\lambda W\                                                                     (6)

式(6)是一个标准的特征方程问题,只需要求解矩阵XX^{T}\d\个特征值对应的特征向量也就构成了投影矩阵,那么怎样选取这些特征值呢?事实上式(6)有很强的几何意义,如果仅考虑单一的投影方向w\,通过稍微变形可以得到tr(w^{T}XX^{T}w)=\lambda\,恰巧对应了原始样本集在这个方向上的方差;因此我们需要选取前d\大个特征值对应的特征向量也就获得了投影矩阵的解~形如XX^{T}\这种形式的矩阵通常我们称作协方差矩阵,它包含有很好的物理意义,能够刻画样本的离散信息,结合式(6)可以看成把协方差矩阵往对应的特征向量方向进行拉伸,因此\lambda\越大对应的往这个方向拉伸程度越高。

       这样一来,我们可以总结一下PCA降维的主要步骤:

       (1)对原始样本集合做归一化,也就是对于每个样本计算减去均值后的样本偏差;

       (2)使用归一化之后的样本集合计算协方差矩阵;

       (3)计算协方差矩阵对应的前d\个特征向量,构成投影变换矩阵;

       (4)利用投影变换矩阵对原始样本作投影,便得到新的经过降维后的样本,然后进行下一步的分类工作。

发表评论

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