流形学习算法及泛化研究.doc

《流形学习算法及泛化研究.doc》由会员分享，可在线阅读，更多相关《流形学习算法及泛化研究.doc（6页珍藏版）》请在三一办公上搜索。

1、精品论文流形学习算法及泛化研究王欣，张闯，肖波，蔺志青北京邮电大学信息与通信工程学院，北京 (100876)E-mail: wang.x.919摘要：本文介绍了流形学习以及目前流形学习研究中的几种常见的算法：等度归映射算法（Isomap，Isometric Mapping），拉普拉斯特征映射算法（LE，Laplacian Eigenmaps），局 部线性嵌套算法（LLE，Locally linear Embedding），局部切空间排列算法（LTSA，Local tangent space alignment）等。分析了这几种算法的特点和复杂度，并重点研究了其中的 LLE 算法， 介绍了 LL

2、E 算法的主要步骤以及几种已有的针对 LLE 算法的泛化方法。根据 LLE 算法的特 点和目前 LLE 算法泛化中存在的问题，本文提出了一种新的针对 LLE 算法的泛化方案，本 方案能够显著提高 LLE 的泛化性能，在流形没有被很好的采样，无法充分地代表潜在的流 形时也能够有效工作，同时具有较小的运算复杂度，能够快速精确实现 LLE 的泛化。 关键词：流形；降维；LLE；泛化中图分类号：TP391.41.引言随着信息时代的到来，目前出现了大量的高维数据，尤其是高维图像数据，使得传统的 线性降维方法遇到了前所未有的挑战。虽然统的线性降维方法具有简单性、易解释性和可延 展性等优点，但膨胀的维数导致

3、计算量迅速上升，而高维的数据又导致样本点数相对较少， 使得某些统计上不再满足渐近性质，而线性方法在处理高维数据时无法满足稳健性要求。为 了对大量新出现的高维数据进行降维处理，近年来出现了多种非线性降维方法。其中，基于 流形学习的降维方法就是其中一种。流形学习的算法目前已经发展出了有很多种，参考文献 1234 分别介绍了几种常见的流形学习的算法： 1 介绍了 LLE （Locally linear Embedding）算法， 2介绍了 Isomap （Isometric Mapping）算法，3介绍了 LE（Laplacian Eigenmaps）算法，4介绍了 LTSA (Local tang

4、ent space alignment)算法。本文将主要对其中的 LLE 算法进行研究，并提出了一种针对 LLE 算法泛化的方法，能 够较好地解决 LLE 泛化中出现的一些问题，同时拥有较小的运算复杂度。本文的结构如下：第 1 节简单介绍了流形学习的数学定义以及几种常见算法的特点和复 杂度；第 2 节介绍 LLE 算法的特征；第 3 节研究了 LLE 泛化中出现的一些问题，并提出了 一种 LLE 泛化方法；第 4 节为研究结论。2.流形学习 流形（Manifold）一般可以认为是局部具有欧氏空间性质的空间，其数学定义如下： 定义：假设 M 是一个 Hausdorff 拓扑空间，若对任意点 p

5、M ，都有 p 的一个开邻域U和 Rm 中的一个开子集同胚，则称 M 是 m 维拓扑流形，简称为 m 维流形。 当数据是采样于一个高维欧式空间中的低维流形时，流形学习的目的就是根据这一组在高维空间的数据内在规律，将其在低维空间中重新表示，恢复出其低维流形，并发现对应的 嵌入映射，从而实现数据的降维和化简。目前，流形学习的算法有很多，其中主要有以下几种： Isomap，LE，LLE， LTSA 等。 这些流形学习方法具有一些共同的特征：首先构造流形上样本点的局部邻域结构，然后用这 些局部邻域结构来将样本点全局的映射到一个低维空间。它们之间的不同之处主要是在于构 造的局部邻域结构不同以及利用这些局

6、部邻域结构来构造全局的低维嵌入方法的不同。正是- 1 -由于这些算法具有各自的特点和优势，造成了它们在性能和使用范围上存在一定的差异性。Isomap 是一种全局优化方法，它的嵌入结果能够反映出高维样本点之间的流形距离。 因此，如果高维数据所在的低维流形与欧氏空间的一个子集是全局等距的，则可以得到很理 想的嵌入结果。但当所对应的低维空间的子集是非凸时，计算流形上样本点间的最短路径时 会产生较大的偏差，从而导致嵌入结果产生较为明显的形变。同时，Isomap 所需的计算时 间较多，该算法算法选取邻域的计算复杂度为 O(mN 2 ) ，其中， m 为高维样本点的维数；计算最短路径的计算复杂度为 O(

7、N 3 ) ；此外，由于距离矩阵的稠密性，计算嵌入结果的计 算复杂度为 O( N 3 ) 。而 LE 是一种局部算法，其基本思想是用一个无向有权图来描述一个流形，然后通过用图的嵌入（graph embedding）来寻找低维表示。LE 适用的范围较广，速度也很快：其选取 邻域的计算复杂度为 O(mN 2 ) ，计算重构权重系数的计算复杂度为 O(kmN ) ，其中， k 为 邻域个数；计算 d 维嵌入的计算复杂度为 O(dN 2 ) 。但 LE 算法中流形上较远的点之间的关 系不明确，性能相对来说较差，并不能够很好的对抗噪声和错位点。LTSA 算法所反映的局部结构是它的局部低维坐标系统，其复杂

8、度较低，计算速度较快：选取邻域的计算复杂度为 O(mN 2 ) ，计算局部坐标系统的计算复杂度为 O(k 2 mN ) ；计算 d 维嵌入的计算复杂度为 O(dN 2 ) 。但 LTSA 算法对样本点密度和曲率变化较大的流形较为敏 感，可能会出现扭曲的现象。LLE 算法不需要考虑远距离点之间的关系，不需迭代，同时，LLE 低维嵌入的计算可归结为稀疏矩阵特征值的求解，计算复杂度相对较小, 易于执行。LLE 选取邻域的计算复杂度为 O(mN 2 ) ，计算重构权的计算复杂度为 O(m+ k )k 2 N ) ，计算 d 维嵌入的计算复杂度- 6 -为 O(dN 2 )5。此外，由于 LLE 算法只

9、需要考虑流形邻近点之间的关系，因此，并不需要流形所对应的低维空间的子集是凸的，所以有着广泛的适用场景。3.LLE 算法LLE 算法是一种非线性降维方法，它存在这样一个假设：一个流形可能不是全局线性 的流形, 但在很小的局部领域下是线性的, 或者说局部意义下的点在一个超平面上, 这是因 为当局部分析时, 流形的曲率不大, 此时流形可以考虑为局部平坦的。这样每个数据点都被 其一个其邻域构成的加权线性组合表示，即可以用这个点周围的点在最下二乘意义下的最优 线性表示。而这种在高维空间中的局部线性关系在低维嵌入表示应仍然保持，这样就能够把 高维的数据映射到一个低维空间中，并仍保持了其邻接关系。即高维空间

10、中某个邻域组成的 “片”(patch),在变换到低维嵌入空间后仍应该保持相对关系不变。LLE 算法学习的主要思想如 图 1 所示。LLE 算法的主要步骤如下：假设输入为一个由 N 个 M 维向量构成的集合，组成一个 MN 大小的矩阵 X , 输出是 由 N 个 m 维向量( mM) 组成的大小为 mN 大小的矩阵 Y3.1 选取邻域对样本点 X i ，i=1, , N, 计算另外 N- 1 个点与 X i 的欧式距离，根据欧式距离进行排， 并选取 X i 的 K 最近邻。图 1 LLE 保持高维空间中邻域内的线性关系3.2 对每个点 X i 及其构成的邻域，计算重构权重系数Wij对每个数据点

11、X i ，找到其 K 最近邻以后，为每个相邻的点赋一个重构系数Wij 。Wij 表 征了数据点 X i 与数据点 X j 的接近程度，即数据点 X j 对重构数据点 X i 所做的贡献。数据点的重构误差用下面函数来衡量：X i 2j ijjj =-W X其中， Wij = 1，使得j 最小，从而计算最优的重构权重系数Wij 。j3.3 计算 m 维嵌入Yi为了能够尽量正确地在低维（ m 维）空间中体现高维（ M 维）空间的局部线性结构， 需要使得代价函数f 最小，代价函数的定义如下：f = 邋Yi -WijYj2= trace(Y T (I- W )T (I- W )Y)ij这一优化问题可以通

12、过对 S= (I- W )T (I- W ) 进行特征值分解得到。假设 S 的最小 m+ 1个特征值及分别对应的特征向量为 ，i= 1,2,.,m ，除去特征值为 0 的特征向量，第i 个样本嵌入的第 j 个分量为4.LLE 的泛化l j u ji ，其中 u ji 为 u j 的第 i 个分量。在实际的应用中，需要对新的数据进行泛化，如何提高算法的泛化能力显得十分重要。 对于传统的 LLE 算法，当有新的数据出现时，需要将之前所有的向量和新的向量集中起来， 并对所有的数据重新进行 LLE 操作。这样操作虽然性能较好，但效率地下，无法对新数据 进行泛化，灵活性较低，不适合动态的场景。参考文献6

13、中介绍了一种 LLE 算法泛化的方法：LLE 的输入为 N 个 M 维向量 X i ，i=1, , N，构成的集合 A ，对于一个新的输入向量 X N + 1 ，在集合 A 中所有的元素中，挑选与 X N + 1欧式距离最近的向量 X k ， X k A ，假设Yk 为 X k 在低维嵌入空间的投影，所以 X k 与Yk 有 如下关系：Yk = UX k其中，U 是一个 m M 的线性转换矩阵，表达式为：U= Yk X k - 1当流形被很好的采样时，集合 A 能够很充分地代表潜在的流形。假设YN + 1 为 X N + 1 在低 维嵌入空间的投影，此时由于 X N + 1 与 X k 距离较

14、近，二者可以采用相同的转换矩阵。所以，下式可以近似成立：YN + 1= UX N + 1 本方法对噪声非常敏感，同时在当流形没有被很好的采样时性能较差。 针对这一不足，参考文献7提出了一种新的针对 LLE 算法的泛化方法：首先在集合 A 中选取 X N + 1 的 K 最近邻；然后计算线性重构系数W j ，使得 X j 能够从其邻域最优重构，并满足 W j =1 ，最后输出为YN + 1=jW jYj 。j这种方法虽然不需要重新计算特征向量，但需要对每一个新数据选择 K 最近邻，并据 此计算重构系数矩阵，计算量较大，并且在出现流形没有被很好的采样，集合 A 无法充分 地代表潜在的流形时性能较差

15、。针对上述两种方法的不足，本文提出了一种新的泛化方法：LLE 的输入为 N 个 M 维向量 X i ，i=1, , N，这些向量构成的集合 A 。对于一个新的 输入向量 X N + 1 ，计算集合 A 中任意元素 X i 与 X N + 1 的欧式距离 di ：di =X i -X N + 1 ，X i A在集合 A 中挑选与 X N + 1 欧式距离最近的向量 X k ，并计算最短的欧式距离 d ：d= min X i -X i AX N + 1 =X k -X N + 1 ，X k A此时有如下几种情况：4.1 当 d dl 时在集合 A 中挑选与 X N + 1 欧式距离最近的向量 X

16、k ，并计算最短的欧式距离 d ： 假设Yk 为 X k 在低维嵌入空间的投影，所以 X k 与Yk 有如下关系：Yk = UX k其中，U 是一个 m M 的线性转换矩阵，表达式如下：- 1U= Yk X k此时由于 X N + 1 与 X k 距离较近，二者可以采用相同的转换矩阵。所以有：YN + 1= UX N + 14.2 当 dl du 时此时需要将 X N + 1 与集合 A 合并，组成集合 B ，对集合 B 进行 LLE。（1）选取邻域，对数据集合 B 中的每一个数据点选取 X i 的 K 最近邻；（2）对每个点 X i 及其构成的邻域，计算重构系数Wij ，使得X i- Wij

17、 X j j最小，并且使得 Wij = 1；j（3）计算低维嵌入。使得代价函数f = 邋Yi -WijYj2= trace(Y T (I- W )T (I- W )Y)最小，满足约束条件：ij1 N + 1 YiYiT = I N+1 i= 1N + 15.结论i= 1Yi = 0本文中提出的 LLE 泛化方法的门限值 dl 和 du 可以根据实际的应用场景进行灵活调整， 以适应不同的需求。例如，当 dl 和 du 较大时，计算速度较快；而当 dl 和 du 较小时，精确 读较高。本方法在流形没有被很好的采样，集合 A 无法充分地代表潜在的流形时也能够有 效工作。尽管基于流行学习的降维方法及其

18、应用在最近几年中已经取得了较大的进展，但由于高 维数据的复杂性，以及流形学习应用的多学科性，使得流形学习仍然有很多值得进一步探讨 的问题。参考文献1 S.Roweis, L.Saul. Nonlinear dimensionality reduction by locally linear embeddingJ. Science, 290 (5500):2323-2326, Dec. 2000.2 M. Balasubramanian, E L. Schwarts and J B. Tenenbaum. The Isomap algorithm and topological stabilit

19、yJ. Science, 295(5552): 7, Jan. 2002.3 M.Belkin, P.NiyogiLaplacian eigenmaps for dimensionality reduction and data representationJ. NeuralComoutations, 15 (6):1373-1396, 2003.4 ZHANG Z, ZHA H. Principal manifolds and nonlinear dimension reduction via local tangent space alignmentJ. SIAM Journal of S

20、cientific Computing, 26(1): 313-338, 2004.5 黄启宏. 流形学习方法理论研究及图像中应用D. 成都: 电子科技大学, 20076 B. Laura. Addressing fault and calibration in wireless sensor networksD. Los Angeles: University ofCalifornia, 2007.7 何秀玲，杨扬，陈增照等基于流形学习的单字符字体辨别J. 计算机工程与应用, 2008, 44(6):206-209.Rearch on Mainfold Learning Algorithms

21、 andGeneralizing MethodWang Xin, Zhang Chuang, Xiao Bo, Lin ZhiqingSchool of Information and Communication Engineering, Beijing University of Posts andTelecommunications, Beijing (100876)AbstractManifold learning and several common algorithms of manifold learning are introduced in this paper: Isomap

22、 (Isometric Mapping), LE (Laplacian Eigenmaps), LLE (Locally linear Embedding), LTSA(Local tangent space alignment). The characteristics and complexities of these algorithms are analyzed. This paper focuses on the LLE （Locally linear Embedding） algorithm and the generalizing methodand introduces som

23、e generalizing methods for LLE. According to the characteristics of LLE algorithms and the disadvantages of existing generalizing methods, a new generalizing method for LLE algorithms is proposed. It can improve the performance of generalizing method, resolve some problems faced in the exciting methods, have lower complexity and achieve the LLE generalizing accurately.Keywords: Manifold-learing; Dimension-reducing; LLE; Generalizing