大机器学习降维算法：PCA、LDA、LLE、Laplacian

《大机器学习降维算法：PCA、LDA、LLE、Laplacian》由会员分享，可在线阅读，更多相关《大机器学习降维算法：PCA、LDA、LLE、Laplacian（12页珍藏版）》请在装配图网上搜索。

1、机器学习领域中所谓的降维就是指采用某种映射方法，将原高维空间中的数据点 映射到低维度的空间中。降维的本质是学习一个映射函数f : X-，其中x是原 始数据点的表达，目前最多使用向量表达形式。y是数据点映射后的低维向量 表达，通常y的维度小于x的维度（当然提高维度也是可以的）。f可能是显式 的或隐式的、线性的或非线性的。目前大部分降维算法处理向量表达的数据，也有一些降维算法处理高阶张量表达 的数据。之所以使用降维后的数据表示是因为在原始的高维空间中，包含有冗余 信息以及噪音信息，在实际应用例如图像识别中造成了误差，降低了准确率；而 通过降维，我们希望减少冗余信息所造成的误差，提高识别（或其他应用

2、）的精度。 又或者希望通过降维算法来寻找数据内部的本质结构特征。在很多算法中，降维算法成为了数据预处理的一部分，如PCA。事实上，有一 些算法如果没有降维预处理，其实是很难得到很好的效果的。主成分分析算法（PCA）Principal Componen t Analysis（PCA是最常用的线性降维方法，它的目标是通过 某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度 上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特 性。通俗的理解，如果把所有的点都映射到一起，那么几乎所有的信息（如点和点之 间的距离关系）都丢失了，而如果映射后方差尽可能的大，那么数据

3、点则会分散 开来，以此来保留更多的信息。可以证明，PCA是丢失原始数据信息最少的一 种线性降维方式。（实际上就是最接近原始数据，但是PCA并不试图去探索数 据内在结构）设n维向量w为目标子空间的一个坐标轴方向（称为映射向量），最大化数据映射后的方差，有：其中m是数据实例的个数，xi是数据实例i的向量表达，x拔是所有数据实例的平均向量。定义W为包含所有映射向量为列向量的矩阵,经过线性代数变换,minfr(W7AW)? s t WrW=I可以得到如下优化目标函数:鱼二丄y 復厂野企匚 其中tr表示矩阵的迹，： JA是数据协方差矩阵。容易得到最优的W是由数据协方差矩阵前k个最大的特征值对应的特征向量

4、作 为列向量构成的。这些特征向量形成一组正交基并且最好地保留了数据中的信息。PCA的输出就是Y = WX由X的原始维度降低到了 k维。PCA追求的是在降维之后能够最大化保持数据的内在信息，并通过衡量在投影 方向上的数据方差的大小来衡量该方向的重要性。但是这样投影以后对数据的区 分作用并不大，反而可能使得数据点揉杂在一起无法区分。这也是PCA存在的 最大一个问题，这导致使用PCA在很多情况下的分类效果并不好。具体可以看 下图所示，若使用PCA将数据点投影至一维空间上时，PCA会选择2轴，这使 得原本很容易区分的两簇点被揉杂在一起变得无法区分;而这时若选择1轴将会 得到很好的区分结果。Discri

5、minant Analysis追求的目标与PCA不同，不是希望保持数据最多的信 息，而是希望数据在降维后能够很容易地被区分开来。后面会介绍LDA的方法， 是另一种常见的线性降维方法。另外一些非线性的降维方法利用数据点的局部性 质，也可以做到比较好地区分结果，例如LLE， Laplacian Eigenmap等。以后 会介绍。LDALinear Discriminant Analys也有叫做 Fisher Linear Discrimina是一种有监 督的(supervised)线性降维算法。与PCA保持数据信息不同，LDA是为了使 得降维后的数据点尽可能地容易被区分！ 假设原始数据表示为X，

6、(m*n矩阵，m是维度，n是sample的数量) 既然是线性的，那么就是希望找到映射向量a，使得a 后的数据点能够保持 以下两种性质： 1、同类的数据点尽可能的接近 (wit hin class) 2、不同类的数据点尽可能的分开 (between class ) 所以呢还是上次PCA用的这张图，如果图中两堆点是两类的话，那么我们就希 望他们能够投影到轴1去(PCA结果为轴2)，这样在一维空间中也是很容易区分的。接下来是推导，因为这里写公式很不方便，我就引用Deng Cai老师的一个ppt中的一小段图片了： Two Classes coj2Tz a1 x1 v = ntLZ闵=士Z = a% 1

7、Ml - “2 丨二 I（M1 -具2）l 殳=（Zigi）2 ZE6l）i 扣g、（禺-直2尸思路还是非常清楚的，目标函数就是最后一行J （a）,（飘）就是映射后的 中心用来评估类间距，s （一瓢）就是映射后的点与中心的距离之和用来评估类 内距。J（a）正好就是从上述两个性质演化出来的。因此两类情况下：加上aa=1的条件（类似于PCA ）Two Classes 畑二爲囂Sg d = ASn可以拓展成多类:x xaTSRaMulti-classes 丿（a）=aTSwacc=Si二仪一险）（工一 i）T i=li=l x6oic =（=1Sscl ASTa以上公式推导可以具体参考pattern

8、 classification的相应章节，讲fisher discirminan的OK，计算映射向量a就是求最大特征向量，也可以是前几个最大特征向量组成 矩阵A=a1,a2,.ak之后，就可以对新来的点进行降维了： y = AX （线性的一 个好处就是计算方便！）可以发现，LDA最后也是转化成为一个求矩阵特征向量的问题，和PCA很像, 事实上很多其他的算法也是归结于这一类，一般称之为谱（spectral方法。线性降维算法我想最重要的就是PCA和LDA 了，后面还会介绍一些非线性的方 法。局部线性嵌入（LLE ）Locally linear embeddingLLE ）是一种非线性降维算法，它能

9、够使降维后的数 据较好地保持原有流形结构。LLE可以说是流形学习方法最经典的工作之一。很 多后续的流形学习、降维方法都与LLE有密切联系。见图1，使用LLE将三维数据（b）映射到二维（c）之后，映射后的数据仍能 保持原有的数据流形（红色的点互相接近，蓝色的也互相接近），说明LLE有 效地保持了数据原有的流行结构。但是LLE在有些情况下也并不适用，如果数据分布在整个封闭的球面上，LLE 则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据 中，首先假设数据不是分布在闭合的球面或者椭球面上。图1 LLE降维算法使用实例LLE算法认为每一个数据点都可以由其近邻点的线性加权组合构造得

10、到。算法的 主要步骤分为三步：（1）寻找每个样本点的k个近邻点；（2）由每个样本点的近 邻点计算出该样本点的局部重建权值矩阵；（3）由该样本点的局部重建权值矩LLE AL/flUT朝江 D*亠口亠-亠.Select neighbors.阵和其近邻点计算出该样本点的输出值。具体的算法流程如图2所示:L impute the lieigliboi -s of fficli darn pohitf Af,2. Compute the lveilits 唏 rhnt best recon struct etich data point 国 from its neigh- bofs? tninitniz

11、iLLg rhe ecsr in E(itnfio (I) by constrntiied linT hr仁3Compute the iertor5 Yi bfst reconitiucri by tilt Heights %、minimi zingThu qnadi fltit fbim in Equation (2) by its bonom iioEizio eiginvctQi 5图2 LLE算法步骤券骤L竄法的第一步是计離出每个样本点的k个近鄂虽例如采用KNN的藤略，护相对于所 求样本点距离（常用欧氐距离）最诉的上个样本点战定为所求样本点的个蚯邻点.箕是一 个预先给定值.歩骤2;讣母

12、出禅本点的局部锻建权龄陈昭 首先能义瑜构逞総咖卜习用-乙眄可以及喝部协方差矩阵爲c厂G-巧）仁瓦）其中丈表示一个特定的凤 它的的 S近邻战用77表示.于是，冃标函数&诫小化,奶卜习忆-乙地西1核花 这里可叹雄if煉捋對W.然后砂醍1中皆设用数据重构閘的*淒.和聲维空耐中的就构馭彊显共享船cJta同的人将所有的样本点映射到託维空柯札映射条件満足如下所亦:呻（y卜工卜鶴上式可以转优为;（亠 1X（XT）其肛 M =(l-W(I-W)WJJP上限制条fh（中心化）,=（单检曲方差）可以得到锻塑解的歷这样一个问渥 wy=ay标准的特征分解问題 即取为W!附就小协个非寒特征值厮时应的特征向猛在处理 过程

13、中，将慟的特征值从峦到大并列，第一桶征值几乎接近于虧那么舍古笫一牛特征 値。通常取弟土到耐工间的转fiHi凋对应的特征向量组成列向童，作为输出结果，即rEm的数括表达矩阵鸣 假设冇M个数据点*Laplacian Eigenmaps 拉普拉斯特征映射继续写一点经典的降维算法，前面介绍了 PCA,LDA , LLE ,这里讲一讲Laplacian Eigenmaps。其实不是说每一个算法都比前面的好，而是每一个算法都是从不同 角度去看问题，因此解决问题的思路是不一样的。这些降维算法的思想都很简单， 却在有些方面很有效。这些方法事实上是后面一些新的算法的思路来源。Laplacian Eigenmap

14、s1看问题的角度和LLE有些相似，也是用局部的角度去 构建数据之间的关系。它的直观思想是希望相互间有关系的点（在图中相连的点）在降维后的空间中尽 可能的靠近。Laplacian Eigenmaps可以反映出数据内在的流形结构。使用时算法具体步骤为:步骤1:构建图使用某一种方法来将所有的点构建成一个图，例如使用KNN算法，将每个点最近的K个点连上边。K步骤2 :确定权重个预先设定的值。确定点与点之间的权重大小，例如选用热核函数来确定，如果点i和点j相连, 那么它们关系的权重设定为：ir = *使用最小的m个非零特征值对应的特征向量作为降维后的结果输出。前面提到过，Laplacian Eigenm

15、ap具有区分数据点的特性，可以从下面的例子PT1Q10看出: 见图1所示，左边的图表示有两类数据点（数据是图片），中间图表示采用 Laplacian Eigenmap降维后每个数据点在二维空间中的位置，右边的图表示采 用PCA并取前两个主要方向投影后的结果，可以清楚地看到，在此分类问题上，Laplacian Eigenmap的结果明显优于PCA。图2 rol数据的降维图2说明的是，高维数据（图中3D）也有可能是具有低维的内在属性的（图中 rol实际上是2D的），但是这个低维不是原来坐标表示，例如如果要保持局部 关系，蓝色和下面黄色是完全不相关的，但是如果只用任何2D或者3D的距离 来描述都是不准确的。下面三个图是Laplacian Eigenmap在不同参数下的展开结果（降维到2D），可 以看到，似乎是要把整个带子拉平了。于是蓝色和黄色差的比较远。