基于局部线性嵌入法的流形学习.pdfVIP

数学理论与应用 V01．29No．4 第29卷第4期 2OO9年 l2月 ^tA1HEMA1fICAI．1HE()RY DAPPLICAT／ONS Dec，2009 基于局部线性嵌入法的流形学习 黄移军 (中南大学数学科学与计算技术学院，长沙，410075) 摘 要 本文介绍了一种非线性降维方法一局部线性嵌入法，并通过实例与PCA对 比，论证了LLE在处理非 线性高维数据中的优越性。 关键词 降维 局部线性嵌入法 主成分法 可视化 StudyBasedonLocallyLinearEmbedding HuangYijun (SchoolofMathematicalScienceandComputingTechnology，CSU，ChaI】ha，410075) Abstract Inthispaper，anonlineardimensionalityreductionmethods—LocallyLinearEmbeddingisintroduced．Comm ing withP0 ．LLEperformsbetterforllonlillearhighdimensional data． Keywords Dimensionalityreduction Locallylinearembedding Principalcomponentanalysis Visualization 随着科学技术的高速发展，人们所接触到的海量数据随处可见，这些高维数据已超过了我 们想象的空问，也难于处理。然而这些数据其本征维数 ¨是比较低的。 因此，降维技术一直受到关注，如早期发展起来的PCAJ，以及后来的PPL3(ProjectPur- suit)等，这些方法很好的解决了高维空间中具有线性关系的数据，但事实上，很多高维数据都 呈现非线性性，而前面的方法在这些数据面前基本失效，因此，急迫需要非线性的降维技术。 Tenenbaum等在Science杂志提出了全局几何方法，其它的一些方法，如等距映射4【J，拉普拉斯 特征映射[5】等，这些降维方法为高维数据的可视化提供了可能。 UE方法是由Roweis和Saul提出的一种非线性降维方法，它主要是从局部人手，通过欧氏 距离以局部线形来保持整体拓扑结构。I』 对非线性数据降维的效果很好且效率很高，本文 介绍u正，并通过实例与PCA对比，论证 l『l肛 在处理非线性高维数据中的优越性。 李俊平 教授推荐 收稿 日期：2OO9年 5月 19日 基于局部线性嵌入法的流形学习 39 1 方法简述 1．1 局部线性嵌入法(LLE) 设在高维欧氏空间R。中有数据集X={ ，：，…， }。数据集位于本征维数为 d(d ， 典型的情况是dD)的非线性流形上或其附近。l皿 的目的就是希望找到 的一个低 维嵌入映射到一个相对低维的嵌入空间 上，同时尽可能的保持原数据所携带的信息，即保 持数据集的拓扑结构，我们假设 Y={Y，Y，…，Y }就是嵌入空间 R 上的一个低维嵌入。算 法 如下 ： Stepl 设 瓢∈X (a)找到每一点 在集合 附近的k个近邻； (b)计算邻域的重构权重，该权重使得 的重构误差最小化。 Step2 计算最合适的低嵌入 ，，，这个Y是基于权矩阵 上获得的。 第一步中的(a)主要是由欧氏距离来定义邻域的，基于 一近邻的定义，第一步中的(b)主 要是寻找最好的重构权值。最优的方法是通过最小化 的局部重构误差的平方和最小得到 的 Ei= 一 wox；cI (1) 其中 ∑Wgi：1，巧 N 时 ：0。在重复第一步中的X中所有N个点后，我们可以得到重构 EN 权值的一个矩阵 W：[W] ；第二步