浅谈流形学习中的LLE算法

王 雄

（1.成都大学,四川 成都 610106 2.四川大学锦江学院，四川 眉山 620860）

一、引言

机器学习是一门综合性学科，其涵盖了大量的数据与计算科学。为了构建“智慧”的机器，近似实现人类智慧，我们对机器“智慧”算法的探索一直在不断研究和进步。随着科学技术的创新和硬件设备的发展进步，人们对“智慧”机器的需求越来越高，对智慧的依赖程度和判断精度也越来越强，为了适应新时代的发展要求，研究和发展机器学习智能算法成为当今各科研机构和AI企业发展的重中之重。

我们面临着信息爆炸的时代，同时也面临着垃圾数据包围的困境。由于信息数据变得越来越多，变得越来越复杂，关系也越来越错综，信息的维度变得越来越高，如何能有效的处理这些庞杂的数据，如何快速的分拣和清洗这些数据，如何将错综复杂的高维信息数据转变为低维直观有效的信息成为了目前机器学习领域中至关重要的研究课题，要解决这些问题，好的算法就是利器。在流形学习中，如何处理高维数据转换为低维数据，这种方法如何保留或保持其数据本质结构特征，LLE就是其中的一种重要算法。

二、关于流形学习

所谓的流形就是几何对象的一种总称，它包括各种维度的曲线与曲面等，它是把一组在高维空间中的数据在低维空间中进行重新表示。

一个流形好比是一个M维的空间，在一个N维的空间中（N>M）被扭曲之后的结果。但是，流形具有在局部与欧式空间同胚的空间，也就是说它在局部具有欧式空间的性质，能用欧式距离来进行距离计算，即高维空间通过连续的变换映射到低维空间后，最后都能保持一致或相似的相关特性和数据结构。

所以，流形学习假设所处理的数据点分布在嵌入于外维欧式空间的一个潜在的流形体上，或者说这些数据点可以构成这样一个潜在的流形体。在保持流形上点的某些几何性质特征的情况下，找出一组对应的内蕴坐标，将流形尽量展开在低维平面上，这种低维表示也叫内蕴特征，外围空间的维数叫观察维数，其表示叫自然坐标。流形学习就是建立内蕴坐标到自然坐标的构建，使得高维数据处理变得方便。典型的转换就是地球仪与世界地图的一种转换，如图1所示。

图1 立体地球仪转换为平面地图

流形学习中比较经典的数据降维方法可以分为两种，一种是线性降维方法，一种是非线性降维方法。线性降维方法相对于非线性降维方法而言，计算相对简单，但对于那些非线性结构的数据就无法得到有效的解决。非线性流形方法则可以对非线性结构进行分析计算，产生较为可靠的结果。流形学习作为非线性降维的主要方法其研究和发展的空间很大，表1列举了当前几种典型的流形处理方法[1]。

表1 几种典型的流形数据处理算法

三、LLE（局部线性嵌入）

局部线性嵌入（LLE）是一种非线性降维算法，我们重点强调它是一种局部算法，即假设采样数据所在的低维流形在局部上是线性的，并假设每个采样点均可以利用其近邻样本进行线性重构表示。

LLE算法的基本思想就是流形在局部可以近似等价于欧氏空间，这样使得低维空间中保持每个邻域中的重构权值不变，在嵌入映射为局部线性的条件下，最小化重构误差，最终形式化为特征值分解问题，它能够使降维后的数据较好地保持原有流形结构。

一个流形在很小的局部邻域上可以近似看成是欧氏的，即局部线性的。那么，在小的局部邻域中，一个点就可以用它周围的点在最小二乘意义下的最优线性来表示。LLE方法即是把这种线性拟合的系数当成这个流形的局部几何性质的描述，如图2所示。

图2 三维空间映射到二维空间

LLE算法希望上式的关系在二维空间中得以继续保持，也就是说高维空间映射到低维空间时，上述式子依然能够成立。如果设法将局部映射关系推广到全局，对高维空间中的所有有效数据都进行类似的处理，那么高维空间中的数据就可以实现降维，达到相应的目的。

如图3 所示，使用LLE 将三维数据映射到二维之后，映射后的数据仍能保持原有的数据流形（关系），这就说明LLE有效地保持了数据原有的流行结构[3]。

图3 使用LLE进行降维

基于上述思想，使用LLE算法降维基本可以概括为以下几步：

（1）确定邻域。即我们需要多少个邻域样本来线性表示某个样本，对于给定的数据集，为其每个样本点，通过欧几里德进行距离计算，即假设这个值为K，我们可以通过和KNN一样的思想通过距离度量比，来选择某样本的K个最近邻。

LLE 可以说是流形学习方法比较经典的算法之一，很多后续的流形学习、降维方法都与LLE有密切联系，它可以学习任意维的局部线性的低维流形，并能够归结为稀疏矩阵特征值计算，计算复杂度相对较小，但是当数据分布在整个封闭的球面上时，LLE 则不能将它很好的映射到低维空间，且不能保持原有的数据流形，所以，在此基础上，很多研究就集中在了如何去改进LLE算法的研究上。

四、基于LLE的改进系列算法

GRDLLE算法，基于Geodesic Rank-order 距离的局部线性嵌入，算法首先应用最短路径算法找到最短路径长度来近似计算任意两个样本间的测地线距离，然后计算Rank-order 距离用于LLE算法的相似性度量[5]。

MM-LLE学习算法作为一种考虑多流形情况的改进算法，通过任意两类间的局部低维流形组合构建分类器来提高分类精度，利用任意两流形间的低维嵌入以及未标记样本点在高维空间中的近邻类别构造DAG分类器来提高高维数据降维后的分类性能，同时改进了MM-LLE 算法的最佳维度选取方案，从训练集中提取验证集用于验证所降维度的好坏，并结合最大化目标函数来获取最佳维度[6]。

基于模糊聚类的改进LLE算法，算法根据聚类中心含有大量信息这一特点，基于模糊聚类原理，采用改进的样本点距离计算方法，定义了近似重构系数，提高了LLE计算速度,改进了模糊近邻点个数的选取[7]。

基于改进距离的并根据剩余方差来智能选取参数值的LLE算法，该算法通过引入新的距离度量公式来替代原有算法中的欧氏距离，并根据K，D值引入剩余方差来评估高维数据结构嵌入到低维空间的效果好坏，用来解决针对局部线性嵌入算法在流形呈卷曲状，两个曲面间距离比较小时，可能造成流形结构在重构过程的扭曲，以及近邻个数K，降维维数D值选择过程中没有一致的标准导致的降维效果下降等问题[8]。