基于LLE的数据降维方法研究
摘要：随着当今社会科学技术的飞速发展，数据信息日益向高维化过渡，所以，想要从它们之间提取出我们所需要的信息越来越难，也给我们带来了前所未有的挑战。因此，对把高维数据通过降维的方法投影到一个相对低维的空间，进而找到隐藏在其间对我们有用的低维结构的研究就成为当前工作中的重中之重。鉴于此，本文主要进行了以下的工作：
①简述了当前国内外关于降维方法的研究情况以及当前一些比较流行的降维方法。
②重点分析了非线性降维方法――局部线性嵌入，局部线性嵌入算法（locally linear embedding，LLE）是解决降维的方法，并通过实验结果对比PCA与LLE算法。
③结合已有的一些结论对该算法中参数的选择方法做了改进。
关键词：局部线性嵌入LLE 数据降维 主成分分析PCA
1 绪论
1.1 目的和意义
1.1.1 图像处理及其目的和意义
所谓图像处理（image processing），又叫数字图像处理，就是用计算机对已有的图形信息进行分析、修改、加工或其他方式的处理，以达到应用者或观赏者在视觉或心理上所需要的要求。其本质是一段能被计算机还原显示、并修改和导出一幅图形的数字码。很多情况下，外界的图形信息对于人的肉眼来说是无法准确捕捉甚至是不可见的，通过数字图像处理中的模式识别技术，可以把人类肉眼无法识别的图形进行分类处理，快速、准确的查找、匹配和识别出需要的信息。
随着科技的飞速发展，人们在行为过程中所接触和处理的数据已经不再是局限的小数据，而是蕴含信息量很多的超大型数据，也就是本文的处理对象――高维数据。这些数据晦涩难懂，难以发掘，却蕴含着各个方面我们需要获取和应用的信息，利用这些信息可以大大提高我们的科技水平和生活水平。要从这些超大型数据中搜寻出我们所需要了解的信息，总结出隐藏在数据中的本质特征并加以运用，是一个很有难度的工程。也就是所谓的“维数灾难”。
为了克服“维数灾难”这个难题，人们总结和研究出一些降维方法，即通过线性或非线性方法使高维空间输入进来的数据样本在保存其高维空间中的本质结构特征的情况下被映射到一个满足要求的低维空间，这就是降维的基本思想。其目的是提取和显示出隐藏在高维样本观测数据中无法直接获取但却具有研究价值的信息并在低维空间显示，使其能够得以应用。
解决降维问题的方法主要可以分为两大类：线性降维方法与非线性降维方法。国外较早的意识到了研究降维方法的重要性，目前已逐渐建立形成较为系统的理论方法体系并在各个领域中得到了较为广泛的运用；而在国内的发展则相对缓慢，但近年来也在降维方法的研究上取得了很大的进步。
最早开始研究并得到应用的是线性降维方法，其中以二十世纪早期提出的主成分分析法（PCA）应用最广，至今仍然在各个领域的降维问题中占有很大的比重甚至是主要地位。它是可以在方差最大化的映射方向上，以丢失很少的数据的代价把许多冗杂的指标转化成数量不多的几个综合指标的方法。之后又提出了线性判别法（LDA），这种方法先找出原始样本观测数据的特征向量，并将数据映射到一个合适的低维方向上，映射成功后能做到不同集合的数据尽量分开，而同一集合内的样本数据就相对靠拢，最后在低维空间中再一次对映射过后的样本数据进行更加详细的分类。[2]
1.3 降维问题的分类
根据降维结果的要求和降维目的不同，把降维要处理的问题大致归为三类：
1.3.1 硬降维问题
这是最基本的一种降维问题，目的就是前文所叙述的，把高维原始样本观测数据映射到低维空间上以便寻找数据结构上的基本特征。它的处理对象维数高达几十万，所以必须对数据集进行非常彻底的降维，以使数据能够进行处理。
本质上是维数不高的低维数据，但在形式上表现为高维空间的流形，我们的目的就是将其进行变换，使其可以用低维的方式进行表示。
1.3.3 可视化问题
这种待处理数据一般本身维数并不高，但是为了提高数据的视觉效果，必须继续对其进行降维，一般取2或3。[2]
1.4 降维方法概述
1.4.1 线性降维方法
线性降维方法本质是建立最佳线性模型，只不过不同的方法对降维结果的要求不同，所以建立的线性模型也都不相同，都有自己的侧重点。它因为直接，所以具有一些很好的性质，如：计算量小、可解释性较强等。
线性方法主要有：主成分分析（PCA）、线性判别法（LDA）、投影寻踪（PP）。
在现实生活中我们所需要研究的数据集合绝大多数时候表现为非线性的结构，这时线性方法就不能达到很好的处理效果，非线性降维方法成为了研究的重点。
非线性降维方法建立的模型可以处理非常复杂的非线性结构的数据，但作为代价的是计算相对复杂，计算量大，并且可解释性较差。
非线性方法主要有：局部线性嵌入法（LLE）、多维尺度法（MDS）、等距映射法（ISOMAP）、拉普拉斯特征映射（LE）、核-主成分分析（K-PCA）、局部切空间法（LTSA）。
2 局部线性嵌入降维法
局部线性嵌入算法（locally linear embedding，LLE）是一种应用很广，并且是针对非线性数据降维的方法，它的特点是可以使处理后的低维数据保持和高维原始观测样本数据相同的拓扑关系。
2.1 LLE-局部线性嵌入算法
LLE算法可以由图1所示的一个例子来形象地描述。在图1所示中，LLE能很好地将三维非线性数据映射到二维空间中。如果把图1（B）中的数据分别看成是分布在三维空间中的两类数据，通过LLE算法降维后，则数据在二维空间中仍能保持相对独立的两类。在图1（B）中的黑色小圈中可以看出，如果将黑色小圈中的数据映射到二维空间中，如图1（C）中的黑色小圈所示，映射后的数据仍能保持原有的数据流形，这说明LLE算法确实能保持流形的领域不变性。 ■
图1 LLE降维示例
由此可以看出LLE算法可以应用于样本的聚类。而线性方法，如PCA，是无法与它比拟的。LLE算法不仅操作简单，而且算法的优化不涉及到局部最小化。不过虽然该算法能解决非线性映射，但当处理数据的维数过大或数量过多，涉及到的稀疏矩阵过于庞大，就不易于处理了。在图1所示的球形面中，当缺少北极面时，LLE算法能很好的将其映射到二维空间中，如图1中的（C）所示。但倘若数据分布在整个封闭的球面上，LLE就不能很好的将它映射到二维空间了，并且无法保持原有的数据流形。所以在处理数据中，为了便于处理，我们首先假设数据不是分布在闭合的球面或者椭球面上的。
图1为非线性降维的一个实例：（B）是从A中提取的样本点（位于三维空间），通过非线性降维算法（LLE），将数据映射到二维空间中如（C）。从（C）图中的颜色可以看出通过LLE算法处理后的数据，能很好的保持原有数据的邻域特性。
2.2 LLE-LLE及其参数的确定
2.2.1 LLE-LLE算法简介
局部线性嵌入的核心思想是对一组在高维空间上的数据项，要求使原嵌套空间与内在低维空间局部邻域关系相同，即在原嵌套空间中每个样本点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权重值不变，重构原数据点，使重构误差最小。
LLE算法大致可以归纳为三个步骤：
①寻找每个样本点的k个近邻点。
②由每个样本点的近邻点计算出该样本点的局部重建权值矩阵。
③由该样本点的局部重建权值矩阵和其近邻点计算出该样本点在低维空间上投影的输出值。
具体的算法流程如图2所示。
■
图2 LLE算法的三个步骤
2.2.2 局部线性嵌入法（LLE）的原理分析
局部线性嵌入算法的第二个步骤是计算出样本点的局部重建权值矩阵。这里需要定义一个成本函数（cost function），如式
（1）所示，用来测量重建误差：
即所有样本点与它们的重建之间的距离的平方和。令w■■是第j个近邻点到第i个样本点之间的权重。为了计算权重w■■，我们提出两个限制条件来作为成本函数取最小值的标准：首先，每个样本点xi仅从它的近邻点那里被重建，如果xj不属于xi的近邻点的集合，则令w■■=0；其次，矩阵中每行的权重总和为1，即：■w■■=1。
为了让重建的误差最小，权重w■■必须服从一种重要的对称性，即对所有特定样本点来说，它们与自己的近邻点之间经过旋转、重新排列、转换等各种变换后，彼此之间的拓扑结构必须保持不变，以达到让重建权重准确描述每个近邻的基本几何特性的要求。所以可以认为高维原始空间内的数据局部几何特征和在映射过后的低维流形上的局部拓扑结构是完全等效的。
局部线性嵌入算法的最后一个步骤是把所有高维原始空间上的观测样本点集xi映射到内部全局坐标的低维向量yi上并输出。w■■代表着高维空间上xi周围的局部信息，又由于映射结果需要在低维空间中最大化地保持原始空间中的局部线性结构，映射条件必须满足式
（2）所示的成本函数：
其中， 为成本函数值，yi是xi在低维空间上的输出向量，yj是xi的第j个近邻点在低维空间上的输出向量，并且要满足以下两个条件：
式
（4）中的1指的是m*m单位矩阵。
为了使成本函数值取到最小值，取yj为M的最小m个非零特征值所对应的单位坐标特征向量。我们需要将M的特征值按照递增的顺序进行排列，通常第一个特征值很小，所以舍去。一般取第2到第m+1之间的特征值所对应的单位坐标特征向量作为输出结果。
3 LLE的一些改进算法的简述
3.1 自适应LLE算法（ALLE算法）
所谓自适应，即算法程序自行根据将要处理的对象的样本点分布状况，自动选择近邻点个数k。
前面已经提到过，LLE算法的第一步中选取k值在大部分情况下是根据经验选择的一个活动性很大的值，需要尝试且不方便控制：
①k取的过大就可能会影响整个流形的平滑性，甚至丢失流形的一些小规模的结构，而k取的过小则又可能会把连续的流形误划分成脱节的子流形。
②且如果对所有样本集区域内的样本点选取相同的近邻点个数，对于所含结构信息很重要的样本集区域，也许就会丢失许多我们所需要和寻找的内容，相反，对于所含结构信息不重要的样本集区域，就会额外加大许多不必要的计算量，浪费了计算机的效率和时间，甚至可能会因为多选取了一些错误的近邻点，破坏了其真实的局部结构特征，使最后的低维流形与实际不符，从而误导我们的分析，也就是所谓的噪声干扰和冗余数据的影响。
③对于弯曲弧度非常大的不光滑流形，基本LLE算法所采用的一致的值也会使高维数据流形在低维空间映射的结果与数据集本身的实际不符。
综上所述，k值的自适应选取是改进LLE算法性能的关键。
ALLE算法采用APC对高维的数据进行聚类（APC（affinity propagation clustering），仿射传播聚类，有效率高、不依靠起始点选取等多种优秀性质，它将全体样本点都作为候选的类代表点），将聚类以后的高维数据结果作为LLE算法的输入。
ALLE的第一个步骤就是计算样本点所在区域内的N个点之间的相似度，并得出相似度矩阵S，矩阵的元素为
（5）
■
图3 ALLE算法流程 这里的距离采用欧氏距离，选取矩阵的对角线元素p=s（j，j）为xi与其他样本点的平均相似度。令r（i，j）和a（i，j）为零，其中r（i，j）是xj对xi的吸引度，表示xj相对于xi的类代表程度，a（i，j）是xi对xj的归属度，表示xi选择xj作为自己的类代表点的合适程度。通过对这两个量的迭代并求和，进行数据的收集和传递，调整p=s（j，j）使目标函数达到最优，满足一定的条件后停止，找到每个点各自的类代表点，每个点只在它们各自的类代表点集区域内建立最合适的局部重建矩阵，以达到所有样本点能够应根据自身所处的局部结构特征自适应地选择近邻点个数k的目的。最后，计算局部重建矩阵，最小化重构误差（注：此时高维的误差函数和低维的重构误差函数都需要重新定义），计算低维空间的投影。[7]
3.2 加权局部线性嵌入算法（WLLE算法）
基本LLE对噪声的干扰十分敏感，为了改进LLE的性能，提出了加权局部线性嵌入算法（WLLE）。
WLLE算法相对于基本LLE算法的主要区别在构建局部重构权值矩阵W，满足重构误差函数之后，这时需要计算每个样本点xi对自身所处的样本集的重要性Dii，公式
（6）：
其中
然后计算高维空间X在低维空间的映射Y，满足
（8）约束条件：
（8）
使加权误差函数
（9）
达到最小。
最后，对稀疏对称矩阵
（10）
4 局部线性嵌入算法的相关实验及其结果
4.1 LLE叶片数据集实验及其结果
■
（a）夹竹桃 （b）其他
图4 正负类叶片图像
因为源数据库中图片大小不一，为方便起见对所有图像进行预处理：将其低采样成64×64像素、256灰度级、白色背景的灰度图像。每幅图像构成1个矩阵。然后将每个矩阵以行为单位依次连接成1个一维向量（详见附录程序）。得到二维可视化结果如图7所示。
在样本集的量较大的时候，LLE算法相对于其他降维方式的优越性会更大。
4.2 结论
实验结果表明PCA方法对于样本类别信息挖掘不够，所以数据的聚类效果很差，而该算法因为更有效地利用了样本的类别信息，样本的聚类性能较好，因此利用最简单的分类器也可以得到较优的分类效果。
但是对于k值的选择仍然是通过反复实验确定的最优值。显然自适应性有所欠缺；同时对于测试样本低维映射关系的确立也采用的是通用的近似的方法。
5 结束语
本文主要完成了以下的各项研究工作：
①简述了数据降维的目的和意义。
②简述了当前国内外关于降维方法的研究情况。
③重点分析了非线性降维方法――局部线性嵌入，局部线性嵌入算法（locally linear embedding，LLE） 是解决降维的方法。
④通过实验验证了LLE算法的效果和优越性。
⑤简述了目前几种基于LLE算法的改进算法的原理及其针对问题的处理结果的优越性。