线性降维

作者:管理员 发布时间:2021-01-28 10:25

主成分分析算法(PCA)

Principal Component Analysis(PCA)是最常用的线性降维方法,它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性。

通俗的理解,如果把所有的点都映射到一起,那么几乎所有的信息(如点和点之间的距离关系)都丢失了,而如果映射后方差尽可能的大,那么数据点则会 分散开来,以此来保留更多的信息。可以证明,PCA是丢失原始数据信息最少的一种线性降维方式。(实际上就是最接近原始数据,但是PCA并不试图去探索数 据内在结构)

设 n 维向量w为目标子空间的一个坐标轴方向(称为映射向量),最大化数据映射后的方差,有:


其中 m 是数据实例的个数, xi是数据实例 i 的向量表达, x拔是所有数据实例的平均向量。定义W为包含所有映射向量为列向量的矩阵,经过线性代数变换,可以得到如下优化目标函数:


其中tr表示矩阵的迹,A是数据协方差矩阵。

容易得到最优的W是由数据协方差矩阵前 k 个最大的特征值对应的特征向量作为列向量构成的。这些特征向量形成一组正交基并且最好地保留了数据中的信息。

PCA的输出就是Y = W‘X,由X的原始维度降低到了k维。

PCA追求的是在降维之后能够最大化保持数据的内在信息,并通过衡量在投影方向上的数据方差的大小来衡量该方向的重要性。但是这样投影以后对数据 的区分作用并不大,反而可能使得数据点揉杂在一起无法区分。这也是PCA存在的最大一个问题,这导致使用PCA在很多情况下的分类效果并不好。具体可以看 下图所示,若使用PCA将数据点投影至一维空间上时,PCA会选择2轴,这使得原本很容易区分的两簇点被揉杂在一起变得无法区分;而这时若选择1轴将会得 到很好的区分结果。

Discriminant Analysis所追求的目标与PCA不同,不是希望保持数据最多的信息,而是希望数据在降维后能够很容易地被区分开来。后面会介绍LDA的方法,是另一 种常见的线性降维方法。另外一些非线性的降维方法利用数据点的局部性质,也可以做到比较好地区分结果,例如LLE,Laplacian Eigenmap等。以后会介绍。 

 

LDA

Linear Discriminant Analysis(也有叫做Fisher Linear Discriminant)是一种有监督的(supervised)线性降维算法。与PCA保持数据信息不同,LDA是为了使得降维后的数据点尽可能地容易被区分!

假设原始数据表示为X,(m*n矩阵,m是维度,n是sample的数量)

既然是线性的,那么就是希望找到映射向量a, 使得 a‘X后的数据点能够保持以下两种性质:

1、同类的数据点尽可能的接近(within class)

2、不同类的数据点尽可能的分开(between class)

所以呢还是上次PCA用的这张图,如果图中两堆点是两类的话,那么我们就希望他们能够投影到轴1去(PCA结果为轴2),这样在一维空间中也是很容易区分的。


接下来是推导,因为这里写公式很不方便,我就引用Deng Cai老师的一个ppt中的一小段图片了: 

思路还是非常清楚的,目标函数就是最后一行J(a),μ(一飘)就是映射后的中心用来评估类间距,s(一瓢)就是映射后的点与中心的距离之和用来评估类内距。J(a)正好就是从上述两个性质演化出来的。

因此两类情况下:

加上a’a=1的条件(类似于PCA)

可以拓展成多类:

以上公式推导可以具体参考pattern classification书中的相应章节,讲fisher discirminant的

OK,计算映射向量a就是求最大特征向量,也可以是前几个最大特征向量组成矩阵A=[a1,a2,….ak]之后,就可以对新来的点进行降维了: y = A’X (线性的一个好处就是计算方便!)

可以发现,LDA最后也是转化成为一个求矩阵特征向量的问题,和PCA很像,事实上很多其他的算法也是归结于这一类,一般称之为谱(spectral)方法。

线性降维算法我想最重要的就是PCA和LDA了,后面还会介绍一些非线性的方法。

 

标签:
Copyright © 2020 万物律动 旗下 AI算法狮 京ICP备20010037号-1
本站内容来源于网络开放内容的收集整理,并且仅供学习交流使用;
如有侵权,请联系删除相关内容;