基于LLE的数据降维方法研究.docx

杨志伟黄秀云 （安徽大学）摘 要 ：随着当今社会科学技术的飞速发展，数据信息日益向高维最早开始研究并得到应用的是线性降维方法，其中以化过渡，所以，想要从它们之间提取出我们所需要的信息越来越难， 二十世纪早期提出的主成分分析法(pca)应用最广，至今也给我们带来了前所未有的挑战。因此，对把高维数据通过降维的方法投影到一个相对低维的空间，进而找到隐藏在其间对我们有用的 低维结构的研究就成为当前工作中的重中之重。鉴于此，本文主要进 行了以下的工作：简述了当前国内外关于降维方法的研究情况以及当前一些比 较流行的降维方法。重点分析了非线性降维方法局部线性嵌入，局部线性嵌 入算法(locally linear embedding,lle)是解决降维的方法，并通过实 验结果对比 pca 与 lle 算法。结合已有的一些结论对该算法中参数的选择方法做了改进。仍然在各个领域的降维问题中占有很大的比重甚至是主要地位。它是可以在方差最大化的映射方向上，以丢失很少的数据的代价把许多冗杂的指标转化成数量不多的几个综合指标的方法。之后又提出了线性判别法(lda)，这种方法先找出原始样本观测数据的特征向量，并将数据映射到一个合适的低维方向上，映射成功后能做到不同集合的数据尽量分开，而同一集合内的样本数据就相对靠拢，最后在低维空间中再一次对映射过后的样本数据进行更加详细的分类。21.3 降维问题的分类根据降维结果的要求和降维目的不同，把降维要处理的问题大致归为三类:1.3.1 硬降维问题这是最基本的一种降维问题，目的就是前文所叙述的，把高维原始样本观测数据映射到低维空间上以便寻找数据结构上的基本特征。它的处理对象维数高达几十万，所以必须对数据集进行非常彻底的降维，以使数据能够进行处理。1.3.2 软降维问题本质上是维数不高的低维数据，但在形式上表现为高维空间的流形，我们的目的就是将其进行变换，使其可以用低维的方式进行表示。1.3.3 可视化问题这种待处理数据一般本身维数并不高，但是为了提高数据的视觉效果，必须继续对其进行降维，一般取 2 或 3。21.4 降维方法概述1.4.1 线性降维方法线性降维方法本质是建立最佳线性模型，只不过不同的方法对降维结果的要求不同，所以建立的线性模型也都不相同，都有自己的侧重点。它因为直接，所以具有一些很关 键 词 ：局部线性嵌入 lle1 绪论1.1 目的和意义数据降维主成分分析 pca1.1.1 图像处理及其目的和意义所谓图像处理（image processing），又叫数字图像处理，就是用计算机对已有的图形信息进行分析、修改、加工或其他方式的处理，以达到应用者或观赏者在视觉或心理上所需要的要求。其本质是一段能被计算机还原显示、并修改和导出一幅图形的数字码。很多情况下，外界的图形信息对于人的肉眼来说是无法准确捕捉甚至是不可见的，通过数字图像处理中的模式识别技术，可以把人类肉眼无法识别的图形进行分类处理，快速、准确的查找、匹配和识别出需要的信息。1.1.2 降维的目的及意义随着科技的飞速发展，人们在行为过程中所接触和处理的数据已经不再是局限的小数据，而是蕴含信息量很多的超大型数据，也就是本文的处理对象高维数据。这些数据晦涩难懂，难以发掘，却蕴含着各个方面我们需要获取和应用的信息，利用这些信息可以大大提高我们的科技水平和生活水平。要从这些超大型数据中搜寻出我们所需要了解的信息，总结出隐藏在数据中的本质特征并加以运用，是一个很有难度的工程。也就是所谓的“维数灾难”。 好的性质，如:计算量小、可解释性较强等。为了克服“维数灾难”这个难题，人们总结和研究出一些降维方法，即通过线性或非线性方法使高维空间输入进来的数据样本在保存其高维空间中的本质结构特征的情况下被映射到一个满足要求的低维空间，这就是降维的基本思想。其目的是提取和显示出隐藏在高维样本观测数据中无法直接获取但却具有研究价值的信息并在低维空间显示，使其能够得以应用。1.2 国内外研究概况解决降维问题的方法主要可以分为两大类：线性降维方法与非线性降维方法。国外较早的意识到了研究降维方法的重要性，目前已逐渐建立形成较为系统的理论方法体 系并在各个领域中得到了较为广泛的运用；而在国内的发展则相对缓慢，但近年来也在降维方法的研究上取得了很大的进步。197线性方法主要有：主成分分析 (pca)、线性判别法(lda)、投影寻踪(pp)。1.4.2 非线性降维方法在现实生活中我们所需要研究的数据集合绝大多数时候表现为非线性的结构，这时线性方法就不能达到很好的处理效果，非线性降维方法成为了研究的重点。非线性降维方法建立的模型可以处理非常复杂的非线性结构的数据，但作为代价的是计算相对复杂，计算量大，并且可解释性较差。非线性方法主要有:局部线性嵌入法(lle)、多维尺度法(mds)、等距映射法(isomap)、拉普拉斯特征映射(le)、核 - 主成分分析(k-pca)、局部切空间法(ltsa)。2局部线性嵌入降维法局部线性嵌入算法(locally linear embedding，lle)是(a)(b) (c)x軑ix軑j軑wijxjjx軑jsw)= x ?w x一种应用很广，并且是针对非线性数据降维的方法，它的特点是可以使处理后的低维数据保持和高维原始观测样本数据相同的拓扑关系。2.1 lle- 局部线性嵌入算法lle 算法可以由图 1 所示的一个例子来形象地描述。在图 1 所示中，lle 能很好地将三维非线性数据映射到二维空间中。如果把图 1（b）中的数据分别看成是分布在三 维空间中的两类数据，通过 lle 算法降维后，则数据在二 维空间中仍能保持相对独立的两类。在图 1（b）中的黑色小圈中可以看出，如果将黑色小圈中的数据映射到二维空间中，如图 1（c）中的黑色小圈所示，映射后的数据仍能保持原有的数据流形，这说明 lle 算法确实能保持流形的领 域不变性。数据项，要求使原嵌套空间与内在低维空间局部邻域关系相同，即在原嵌套空间中每个样本点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权重值不变，重 构原数据点，使重构误差最小。lle 算法大致可以归纳为三个步骤：寻找每个样本点的 k 个近邻点。由每个样本点的近邻点计算出该样本点的局部重 建权值矩阵。由该样本点的局部重建权值矩阵和其近邻点计算出该样本点在低维空间上投影的输出值。具体的算法流程如图 2 所示。图 2 lle 算法的三个步骤 2.2.2 局部线性嵌入法（lle）的原理分析局部线性嵌入算法的第一个步骤是计算出高维空间中每个样本点 x（i i=1，2，n）的 k 个近邻点，把距离所求样本点最近的 k 个其他样本点定义为所求样本点的 k 个近邻点。k 是一个根据计算要求预先的给定值。局部线性嵌入算法的第二个步骤是计算出样本点的 局部重建权值矩阵。这里需要定义一个成本函数(costfunction)，如式(1)所示，用来测量重建误差：图 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 算法简介局部线性嵌入的核心思想是对一组在高维空间上的（1）即所有样本点与它们的重建之间的距离的平方和。令(i)w 是第 j 个近邻点到第 i 个样本点之间的权重。为了计算j(i)权重 wj ，我们提出两个限制条件来作为成本函数取最小值的标准：首先，每个样本点 xi 仅从它的近邻点那里被重(i)建，如果 xj 不属于 xi 的近邻点的集合，则令 wj =0；其次，n(i)矩阵中每行的权重总和为 1，即：wj =1。j = 1(i)为了让重建的误差最小，权重 wj 必须服从一种重要的对称性，即对所有特定样本点来说，它们与自己的近邻 点之间经过旋转、重新排列、转换等各种变换后，彼此之间 的拓扑结构必须保持不变，以达到让重建权重准确描述每198信息技术成本函数：nk 2y)= y ?w (i)yri j ji=1 j=1n? yi = 0(i = 1, 2,n)i=1n1 y y t = 1(i = 1, 2,n)i in i=1select neighbors adaptivelycluster using apc rcconstruct with linear weightsmap to cmbedded coordinatesd = ? b个近邻的基本几何特性的要求。所以可以认为高维原始空间内的数据局部几何特征和在映射过后的低维流形上的局部拓扑结构是完全等效的。局部线性嵌入算法的最后一个步骤是把所有高维原始空间上的观测样本点集 xi 映射到内部全局坐标的低维(i)向量 yi 上并输出。wj 代表着高维空间上 xi 周围的局部信息，又由于映射结果需要在低维空间中最大化地保持原始 空间中的局部线性结构，映射条件必须满足式（2）所示的(affinity propagation clustering)，仿射传播聚类，有效率高、不依靠起始点选取等多种优秀性质，它将全体样本点都作为候选的类代表点），将聚类以后的高维数据结果作 为 lle 算法的输入。alle 的第一个步骤就是计算样本点所在区域内的 n个点之间的相似度，并得出相似度矩阵 s，矩阵的元素为1s =ij（5）ij（2）其中，为成本函数值，yi 是 xi 在低维空间上的输出向量，yj 是 xi 的第 j 个近邻点在低维空间上的输出向量，并且要满足以下两个条件：（3）（4）式（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 对高维的数据进行聚 类（apc199图 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 的目的。最 后，计算局部重建矩阵，最小化重构误差（注：此时高维的 误差函数和低维的重构误差函数都需要重新定义），计算低维空间的投影。73.2 加权局部线性嵌入算法（wlle 算法）基本 lle 对噪声的干扰十分敏感，为了改进 lle 的 性能，提出了加权局部线性嵌入算法（wlle）。wlle 算法相对于基本 lle 算法的主要区别在构建局部重构权值矩阵 w，满足重构误差函数之后，这时需要计算每个样本点 xi 对自身所处的样本集的重要性 dii，公式（6）：（6）其中x x信息技术 ? ?exp ? x x?, x kx b = ? ? ? ? ?0,% nn? y = 0 , ? y y t = nli i ii=1 i=1n2tsi w ?= dii yi ? wijyj= ? mij yi yji=1 ij达到最小。最后，对稀疏对称矩阵m = d i w ?t ?i w ?(a)夹竹桃 (b)其他21.510.50-0.5-1-1.5-2-2.5-3-1.5-1-0.500.511.522.533000200010000-1000-2000-3000-12000 -11000 -10000 -9000 -8000 -7000 -6000 -5000 -4000（7）然后计算高维空间 x 在低维空间的映射 y，满足（8）约束条件：（8）使加权误差函数（9）图 5 lle 算 法（10）进行非稀疏对角化，得到其最小的（d+1）个特征值对 应的特征向量。由于第一个特征值接近于零，故舍去，则高 维空间的样本集在 x 的低维空间上的映射 y 通常取第 2 到第（d+1）个非零特征值对应的特征向量，d 表示嵌入的 维数。6，74 局部线性嵌入算法的相关实验及其结果4.1 lle 叶片数据集实验及其结果为了验证局部线性嵌入算法在图像处理降维方面的高效性和优越性，需要利用植物叶片数据库进行分类实 验。该数据库包括 220 种植物的 16846 幅叶片图像。本次 试验从 68 幅夹竹桃叶片图像中随机选取 30 幅作为正类样本，再从其他 219 种植物叶片中随机选取 30 幅作为负类样本。部分图像叶片如图 4 所示。图 6 pca 算 法优值。显然自适应性有所欠缺；同时对于测试样本低维映 射关系的确立也采用的是通用的近似的方法。5 结束语本文主要完成了以下的各项研究工作：简述了数据降维的目的和意义。简述了当前国内外关于降维方法的研究情况。重点分析了非线性降维方法局部线性嵌入，局 部线性嵌入算法(locally linear embedding，lle) 是解决 降维的方法。通过实验验证了 lle 算法的效果和优越性。简述了目前几种基于 lle 算法的改进算法的原理及其针对问题的处理结果的优越性。参 考