在我的第一篇机器学习笔记的文章中曾写到,机器学习所研究的主要内容是“关于在计算机上从数据中产生模型的算法”,因此在进行机器学习的研究与实践中必然要处理许多的数据。这些数据的维度从低维到高维不等,对于低维的数据计算机处理起来很快,但对于高维的数据计算机处理起来不仅费时费力,而且还往往由于高维中存在着大量噪声,使得最终训练出的模型正确率大大降低。因此如何对数据降维也是机器学习中一个十分重要的话题,本文主要讲述数据为什么能降维,以及最重要的降维方法之一主成分分析(Principal Component Analysis ,PCA)的推导过程。

目录

一、为什么数据能被降维?

二、主成分分析(Principal Component Analysis,PCA)的步骤

三、PCA的推导


一、为什么数据能被降维?

在回答这个问题之前,我们先来看一个例子。

在一个三维空间中有A、B、C三个点,如果我们用自然坐标系xyz来表示这组数据的话,它们的坐标分别为

A(1,0,0) B(0,1,0) C(0,0,1)

即我们表示每个点的坐标都需要三个数字,但有时我们觉得在三维的空间中对数据进行处理理解起来有些困难,比如求三维空间中两个向量的夹角,如果能把它们变成二维数据再进行处理我们人脑理解起来将会轻松很多,比如求平面上两个向量之间的夹角。那么我们能不能将它们用两个坐标进行表示呢?答案是肯定的!

仔细观察上图中的三个坐标,我们不难发现,ABC三点其实都分布在x+y+z=1的平面上

即xyz三变量间存在相关关系,知道了xy坐标,我们可以根据关系求出z,如果我们将XYZ坐标轴旋转平移一下,使平移后的x’与y’坐标轴与x+y+z=1平面重合,那么我们表示这组数据只需要x’和y’两个坐标就可以了。另外我们知道在三维空间中的3个点一定共面,也就是说用上面的这种方法,我们可以将三维空间中的任意3个点的组合用二维坐标表示出来,并使得他们之间蕴含的信息不受损失。上面例子可以降维的根本原因是不同的属性之间存在相关关系,一部分属性可以由另外一部分属性线性表出。同样地推广到n维的情况,我们也可以至少将它降维到n-1维空间中进行分析。

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

同样地,我们把以上三维空间中的情况扩展到n维,n维数据中也会存在一些抖动很小的属性,我们也可以把他们从数据中剔除,以达到降维的效果,最终保留下来的属性被称为数据的主成分。


二、主成分分析(Principal Component Analysis,PCA)的步骤

上一小节中我们已经知道了主成分的概念,主成分分析(Principal Component Analysis,简称PCA)正是这样一种从n维数据中选出k个主成分,然后将n维数据降维到k维空间的方法。需要注意的是这k维特征(这里的特征就是上节中的属性)是重新构造出来的k维特征(例如上面例子中的x’与y’),而不是简单地从n维特征中去除其余n-k维特征。

它的步骤如下:

输入:n维样本集D=(x(1),x(2),...,x(m)),要降维到的维数k。

输出:降维后的样本集D′

(1)对所有的样本进行中心化:

(2) 计算样本的矩阵

(3) 对矩阵

进行特征值分解

(4) 取出最大的k个特征值对应的特征向量(w1,w2,...,wk), 将所有的特征向量标准化后,组成特征向量矩阵W。

(5) 对样本集中的每一个样本x(i),转化为新的样本

(6) 得到输出样本集D′=(z(1),z(2),...,z(m))

三、PCA的推导

在信号处理中认为信号具有较大的方差,噪声有较小的方差,信噪比就是信号与噪声的方差比,越大越好。因此我们认为,最好的k(k<n)维特征是将n维样本点转换为k(k<n)维后,每一维上的样本方差都很大。所以我们的降维目标是:将一组N维向量降为k(k<n)维,其目标是选择k个单位正交基,使得原始数据变换到这组基上后,各特征的方差尽可能大。

假设我们现有n个n维的数据

我们先对这组数据进行一下预处理(为了使数据分布在原点附近,便于后续投影运算)

1、找出这组数据的数据中心的坐标

2、将这组数据中心化(将坐标原点移到样本点的中心点),中心化后的数据在每个特征上的均值都为0:

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

在这里,也就是最大化下式:

由矩阵代数相关知识可知,可以对绝对值符号项进行平方处理比较方便。所以进而就是最大化下式:

在这里,两个向量做内积,可以转化成矩阵乘法:

所以目标函数可以表示为:

又由于u1和i无关,可以拿到求和符外面,上式化简为:

学过矩阵代数的同学可能已经发现了,上式括号里面求和后的结果,就相当于一个大矩阵乘以自身的转置,其中,这个大矩阵的形式如下::

X矩阵的第i列就是xi

于是有:

所以目标函数最终化为:

其中的

就是一个二次型,

我们假设

的某一特征值为λ,对应的特征向量为ξ,有

所以

是半正定的对称矩阵,即

是半正定阵的二次型,由矩阵代数知识得出,目标函数存在最大值!

下面我们考虑求解最大值和取得最大值时u1的方向这两个问题。

1、求解最大值

先解决第一个问题,对于向量x的二范数平方为:

同样,目标函数也可以表示成映射后的向量的二范数平方:

把二次型化成一个范数的形式,由于在前面我们已设定u1为单位向量,所以此时最大化目标函数的基本问题也就转化为:对一个矩阵

,它对一个向量做变换,“变换后的向量的模长”比上“原向量的模长”如何才能最大?我们由矩阵代数中的定理知,向量经矩阵映射后与原来的向量长度之比的最大值就是这个矩阵的最大奇异值,即:

式中,

是矩阵A的最大奇异值(亦是矩阵A的二范数),它等于

(或

)的最大特征值开平方。

针对本问题来说,

是半正定对称阵,也就意味着它的特征值都大于等于0,且不同特征值对应的特征向量是正交的,构成所在空间的一组单位正交基。

2、取得最大值时u1的方向

再解决第二个问题,对一般情况,设对称阵

的n个特征值分别为:

相应的单位特征向量为:

任取一个向量x,用特征向量构成的空间中的这组基表示为:

则:

所以:

针对第二个问题,我们取上式中的

目标函数

取得的最大值就是

的最大特征值,对应的特征向量的方向,就是第一主成分u1的方向!(第二主成分的方向为

的第二大特征值对应的特征向量的方向,以此类推)。

3、总结

最后我们将整个过程进行一下梳理:

1)我们可以用数据中方差最大的若干个特征作为数据的主成分对数据进行降维

2)假设我们有n个n维数据组成的矩阵X,我们希望把它降维成由n个k维数据组成的矩阵Y,所以我们需要有一个k×n阶的矩阵 左乘矩阵X得到Y。即

3)矩阵W为n×k阶矩阵,它的每个列向量为K维空间中的一组基

4)在2中我们知道这k个基是 的最大的k个特征值对应的特征向量的标准化,因此我们需要求出的最大的k个特征值对应的单位特征向量。

5)进行运算得出降维后的数据集

参考文献

Ian Goodfellow等,《深度学习》

作者:桂。,PCA算法 - 桂。 - 博客园