论文研究-流形学习算法及泛化研究 .pdf

所需积分/C币:10 2019-08-19 16:43:58 260KB .PDF

流形学习算法及泛化研究,王欣,张闯,本文介绍了流形学习以及目前流形学习研究中的几种常见的算法:等度归映射算法(Isomap,Isometric Mapping),拉普拉斯特征映射算法(LE��
山国科技记文在线 http://www.paper.edu.cn 1选择邻域 ○ 重构,计算 重构重系数 W X Ik XK 3低维状入 图1LLE保持高维空间中邻域内的线性关系 3.2对每个点ⅹ及其构成的邻域,计算重构权重系数M 对每个数据点X,找到其K最近邻以后,为每个相邻的点赋一个重构系数。而表 征了数据点与数据点X;的接近程度,即数据点X;对重构数据点X所做的页献。数据 点的重构误差用下面函数来衡量 j=X a W X, 其中,aW=1,使得j最小,从而计算最优的重构权重系数W。 33计算m维嵌入Y 为了能够尽量正确地在低维(n维)空间中体现维(M维)空间的局部线性结构, 需要使得代价函数f最小,代价函数的定义如下: 邋}H1)Q(y(m) 山国科技记文在线 http://www.paper.edu.cn 这一优化问题可以通过对S=(-W)(1-W)进行特征值分解得到。假设S的最小m+1 个特征值及分别对应的特征向量为<l,:>,i1,2-…m,除去特征值为O的特征向量,第 i个样本嵌入的第j个分量为√l;ln,其屮la为u,的第i个分量。 4.LLE的泛化 在实际的应用中,需要对新的数据进行泛化,如何提高算法的泛化能力显得十分重要。 对于传统的LLE算法,当有新的数据出现时,需要将之前所有的向量和新的向量集中起来, 并对所有的数据重新进行LLE操作。这样操作虽然性能较好,但效率地下,无法对新数据 进行泛化,灵活性较低,不适合动态的场景 参考文献6中介绍了种LLE算法泛化的方法:LLE的输入为N个M维向量X,i=1, N,构成的集合A,对于一个新的输入向量Xx+1,在集合A中所有的元素中,挑选与XM+1 欧式距离最近的向量Xk,XIA,假设K为在低维嵌入空间的投影,所以X与有 如下关系 YK=UXK 其中,U是个mM的线性转换矩阵,衣达式为:U=YX1 当流形被很好的采样时,集合A能够很充分地代表潜在的流形。假设Y+1为XM+1在低 维嵌入空间的投影,此时由于X1与距离较近,二者可以采用相同的转换知阵。所以 下式可以近似成立 N+1 UX 本方法对噪声非常敏感,冋时在当流形没有被很好的采样时性能较差。 针对这一不足,参考文献[提出了一种新的针对LLE算法的泛化方法 首先在集合A中选取XN1的K最近邻;然后计算线性重构系数W,使得X,能够从其 邻域最优重构,并满足aW=1,最后输出为Xx+=aWY 这种方法虽然不需要重新计算特征向量,但需要对每个新薮据选择K最近邻,并据 此计算重构系数矩阵,计算量较大,并且在出现流形没有被很好的采样,集合A无法充分 地代表潜在的流形时性能较差。 针对上述两种方法的不足,本文提出了一种新的泛化方法: LLE的输入为N个M维向量X,i1,,N,这些向量构成的集合A。对」一个新的 输入向量XN1,,计算集合A中任意元素X与XN1的欧式距离d;: dFX XMl ,X A 在集合A中挑选与XM+欧式距离最近的向量Xk,并计算最短的欧式距离d: minl LY - XN+FX -XN+, X i A 此时有如下几种情况: 41当dd时 在集合A中挑选与ⅪM+1欧式距离最近的向量Xk,并计算最短的欧式距离d: 假设Ⅴ为Xk在低维嵌入空间的投影,所以Xk与Yk有如下关系 4 山国科技记文在线 http://www.paper.edu.cn YK=UX 其屮,U是一个mM的线性转换矩阵,表达式如下: U=YkK 此吋由于ⅩM1与Xk距离较近,二者可以采用相同的转换矩阵。所以有 42当d<d时 (1)首先在集合A中选取x+1的K最近邻,构成邻域{Xn,X12”…Xk}; (2)计算线性重构系数W; +x-ax,使得/最小,并满是aF=1,这样能够使X从其邻域 最优重构。 (3)输出F=aWy。 巧是XN-1邻域中的向量x在低维嵌入空间的投影。 43当4d时 此时需要将X1与集合A合并,组成集合B,对集合B进行LLE (1)选取邻域,对数据集合B屮的每一个数据点选取X2的K最近邻; (2)对个点X及其构成的邻域,计算重构系数形,使得XaWX最小,并 且使得aW=1; (3)计算低维入、使得代价函数/邋H-ae)()) 最小,满足约束条件: A+a YY=I N+1 a-0 5.结论 本文中提出的LLE泛化方法的门限值d和d可以根据实际的应用场景进行灵活调整, 以适应不同的需求。例如,当d和dl较大时,计算速度较快;而当d和d较小时,精确 读较高。本方法在流形没有被很好的采样,集合A尢法充分地代表潜在的流形时也能够有 效工作 尽管基于沇行学习的降维方法及其应用在最近几年中已经取得了较大的进展,但由于高 维数据的复杂性,以及流形学习应用的多学科性,使得流形学习仍然有很多值得进一步探讨 的问题。 山国科技记文在线 http://www.paper.edu.cn 参考文献 1 SRoweis, L.Saul. Nonlinear dimensionality reduction by locally linear embedding j. Science, 290(5500) 2323-2326,Dec.2000. [2]M. Balasubramanian, E L Schwarts and J B. Tenenbaum. The Isomap algorithm and topological stability[J] Science,295(5552):7,Jan.2002. 3 M. Belkin, P Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation J]. Neural Comoutations, 15(6): 1373-1396, 2003 4 ZHANG Z, ZHA H Principal manifolds and nonlinear dimension reduction via local tangent space alignment SIAM Journal of Scicntific Computing, 26(1): 313-338, 2004 [5]黄启宏.流形学习方法理论研究及图像屮应用[D].成都:电子科技大学,2007 [6B. Laura. Addressing fault and calibration in wireless sensor networks[D]. Los Angeles: University of California. 2007 」何秀玪,杨扬,陈增照等.基于流形学习的单字符字体辨别山计算机程与应用,208,446):206-209 Rearch on Mainfold Learning Algorithms and Generalizing Method Wang Xin, Zhang Chuang, Xiao Bo, Lin Zhiqing School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing(100876) Abstract Manifold learning and several common algorithms of manifold learning are introduced in this papet Isomap(Isometric Mapping), LE (Laplacian Eigenmaps), LLE Locally lincar 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 method and introduces some 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 6

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源