机器学习降维算法

（我转正终面被问到的一个问题，估计也是我面试答得最烂的一个问题，在此查资料转载学习一下。）

引言：

机器学习领域中所谓的降维就是指采用某种映射方法，将原高维空间中的数据点映射到低维度的空间中。降维的本质是学习一个映射函数 f : x->y，其中x是原始数据点的表达，目前最多使用向量表达形式。 y是数据点映射后的低维向量表达，通常y的维度小于x的维度（当然提高维度也是可以的）。f可能是显式的或隐式的、线性的或非线性的。

当然还有一大类方法本质上也是做了降维，叫做feature selection，目的是从原始的数据feature集合中挑选一部分作为数据的表达。

目前大部分降维算法处理向量表达的数据，也有一些降维算法处理高阶张量表达的数据。

之所以使用降维后的数据表示是因为:

(1)在原始的高维空间中，包含有冗余信息以及噪音信息，在实际应用例如图像识别中造成了误差，降低了准确率；而通过降维,我们希望减少冗余信息所造成的误差,提高识别（或其他应用）的精度。

(2)或者希望通过降维算法来寻找数据内部的本质结构特征。

(3)通过降维来加速后续计算的速度

(4)还有其他很多目的，如解决数据的sparse问题

在很多算法中，降维算法成为了数据预处理的一部分，如PCA。事实上，有一些算法如果没有降维预处理，其实是很难得到很好的效果的。

如果你需要处理数据，但是数据原来的属性又不一定需要全部保留，那么PCA也许是一个选择。

 

主成分分析算法（PCA）

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

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

设n维向量w为目标子空间的一个坐标轴方向（称为映射向量），最大化数据映射后的方差，有：

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

   W'W=I是说希望结果的每一个feature都正交，这样每一维度之间不会有冗余信息。

 

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

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

PCA的输出就是Y = W'X，由X的原始维度降低到了k维。因此不知道推导也无所谓，只要会算就行，注意X需要均值化。

来看个例子：

 

当使用1个特征向量的时候，3的基本轮廓已经保留下来了，特征向量使用的越多就越与原始数据接近

   

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

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中的一小段图片了：

 a是投影向量，z是映射后的数据，x是原始数据，μ是一类点的质心（平均值）。

思路还是非常清楚的，目标函数就是最后一行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）方法。

LLE及其改进算法介绍

 

    Locally linear embedding (LLE) (Sam T.Roweis and Lawrence K.Saul, 2000)以及Supervised locally linear embedding (SLLE) (Dick and Robert, 2002) 是最近提出的非线性降维方法，它能够使降维后的数据保持原有拓扑结构。

    LLE算法可以有图1所示的一个例子来描述。在图1所示中，LLE能成功地将三维非线性数据映射到二维空间中。如果把图1（B）中红颜色和蓝颜色的数据分别看成是分布在三维空间中的两类数据，通过LLE算法降维后，则数据在二维空间中仍能保持相对独立的两类。在图1（B）中的黑色小圈中可以看出，如果将黑色小圈中的数据映射到二维空间中，如图1（C）中的黑色小圈所示，映射后的数据任能保持原有的数据流形，这说明LLE算法确实能保持流形的领域不变性。由此LLE算法可以应用于样本的聚类。而线性方法，如PCA和MDS，都不能与它比拟的。LLE算法操作简单，且算法中的优化不涉及到局部最小化。该算法能解决非线性映射，但是，当处理数据的维数过大，数量过多，涉及到的稀疏矩阵过大，不易于处理。在图1中的球形面中，当缺少北极面时，应用LLE算法则能很好的将其映射到二维空间中，如图1中的C所示。如果数据分布在整个封闭的球面上，LLE则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。

图1 非线性降维实例：B是从A中提取的样本点（三维），通过非线性降维
算法（LLE），将数据映射到二维空间中（C）。从C图中的颜色可以看出
通过LLE算法处理后的数据，能很好的保持原有数据的邻域特性

    LLE算法是最近提出的针对非线性数据的一种新的降维方法，处理后的低维数据均能够保持原有的拓扑关系。它已经广泛应用于图像数据的分类与聚类、文字识别、多维数据的可视化、以及生物信息学等领域中。

---

1 LLE算法

    LLE算法可以归结为三步: (1)寻找每个样本点的k个近邻点；（2）由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。具体的算法流程如图2所示。

图2 LLE算法流程

    算法的第一步是计算出每个样本点的k个近邻点。把相对于所求样本点距离最近的k个样本点规定为所求样本点的 个近邻点。k是一个预先给定值。Sam T.Roweis 和 Lawrence K.Saul算法采用的是欧氏距离，则减轻复杂的计算。然而本文是假定高维空间中的数据是非线性分布的，采用了diijstra距离。Dijkstra 距离是一种测地距离，它能够保持样本点之间的曲面特性，在ISOMAP算法中有广泛的应用。针对样本点多的情况，普通的dijkstra算法不能满足LLE算法的要求。

    LLE算法的第二步是计算出样本点的局部重建权值矩阵。这里定义一个误差函数，如下所示：

    

其中 为 的k个近邻点， 是 与 之间的权值，且要满足条件： 。这里求取W矩阵，需要构造一个局部协方差矩阵 。

    将上式与相结合，并采用拉格朗日乘子法，即可求出局部最优化重建权值矩阵：

    在实际运算中，可能是一个奇异矩阵，此时必须正则化，如下所示：

其中r是正则化参数，I是一个kxk的单位矩阵。

    LLE算法的最后一步是将所有的样本点映射到低维空间中。映射条件满足如下所示：

其中，为损失函数值，是的输出向量，是的k个近邻点，且要满足两个条件，即：

其中I是的单位矩阵。这里的可以存储在的稀疏矩阵W中，当是的近邻点时，，否则，。则损失函数可重写为：

其中M是一个的对称矩阵,其表达式为:

要使损失函数值达到最小, 则取Y为M的最小m个非零特征值所对应的特征向量。在处理过程中，将M的特征值从小到大排列，第一个特征值几乎接近于零，那么舍去第一个特征值。通常取第间的特征值所对应的特征向量作为输出结果。

2 SLLE算法

    Dick和Robert提出一种针对有监督的LLE算法，即SLLE。传统的LLE算法在第一步时是根据样本点间的欧氏距离来寻找 个近邻点。而SLLE在处理这一步时，增加了样本点的类别信息。SLLE的其余步骤同LLE算法是一致的。

    SLLE算法在计算点与点之间的距离时，采用如下公式：

其中是计算后的距离；在本文中是定义为dijkstra距离；是表示类与类之间的最大dijkstra距离；取0或者1，当两点属于同类时，取为0，否则取1；是控制点集之间的距离参数，是一个经验参数。当取为零时，此时的SLLE和LLE算法相同。

3 SLLE参数设置

    SLLE算法中有4个参数需要设置，即近邻点的个数k 、输出维数m 、正则化参数r和距离参数。k的选取在算法中起到关键因素，如果k取值太大，LLE不能体现局部特性，使得LLE算法趋向于PCA算法；反之取得太小，LLE便不能保持样本点在低维空间中的拓扑结构。本文中k没有作出进一步的改进，相当于一个经验参数，预先取值为12。

    本文的输出维数m，采用类似于PCA算法求取固有维数。SLLE算法在计算每个样本点的重建权值矩阵时，都要构造一个局部协方差矩阵，可以通过如下式子求出该样本点的输出维数。

其中为的特征值，且以从大到小排列。对于每个样本点，都需要计算一次样本点的输出维数。所有点输出维数的平均值规定为样本的输出维数。

    正则化参数r可以取一个特别小的值，或者采用自适应调整的方法得到。当采取自适应调整的办法来选定r的值。对于每个样本点，都要校正矩阵，此时正则化参数采取如下式子：

其中为的最小的个特征值。

    距离参数是一个经验参数。在求取点间的距离时，可以增加不同类点之间的距离，从而增加类类之间的距离。

4 SLLE的测数数据处理

    设训练样本为，训练样本的输出为，为训练样本的维数，m为训练样本的输出维数，N为训练样本的个数。设为测试样本的集合。主要算法分为三步：

（1）选取一个，将x加入X矩阵中，则X变为的矩阵。在训练样本中寻找的k个近邻点，此时还时采用dijkstra距离，但是不能像SLLE算法那样加上样本点的类别信息。

（2）求与其k个近邻点间的权值系数，且满足以下条件：

其中是的k个近邻点，是与其近邻点之间的权值。

（3）计算的输出向量：

其中为的输出向量。