一种基于线性插值的流形学习算法

第3 1卷第 1期2 0 1 3年 1月

佛山科学技术学院学报 (自然科学版 )J o u r n a l o f F o s h a n Un i v e r s i t y( Na t u r a l S c i e n c e Ed i t i o n )

Vo 1 . 3 1 No . 1

J a n .2 0 1 3

文章编号： 1 0 0 8— 0 1 7 1 ( 2 0 1 3 ) 0 1— 0 0 3 3— 0 6

一

种基于线性插值的流形学习算法顾艳春(佛山科学技术学院电子与信 g -工程学院，广东佛山 5 2 8 0 0 0 )

摘要：作为一种有效的非线性降维方法，流形学习在众多领域引起了广泛关注并取得了长足发展。但当样本点

较为稀疏时，样本点的局部邻域很难满足流形学习局部同胚的前提条件，此时流形学习算法往往效果变差甚至失效。一种有效的解决方法是增加一些新的插值点。为此，提出了一种基于三角形重心线性插值技术的流形学

习算法。实验结果表明，插值算法能改善样本点的局部结构。将插值算法应用到经典的流形学习算法如 L TS A 后，实验结果证实了算法的有效性和稳定性。关键词：流形学习；数据降维；重心；插值中图分类号： T P 3 0 1 . 6 文献标志码： A

流形学习是一种有效的非线性降维方法。近年来，流形学习方法在数据挖掘、机器学习、图像处理和计算机视觉等多个研究领域引起了广泛关注，众多流形学习方法涌现出来，包括 I s o me t r i c F e a t u r eMa p p i n g( I S OM a p)‘、 Lo c a l l y L i n e a r Em b e d d i n g( LLE)[州、 He s s i a n Ei g e n ma p s( HLLE)[引、 Lo c a l Ta n g e n t S p a c e Al i g n me n t( LTS A) 引、 La p l a c i a n Ei g e n ma p s( LE )[、 Ma n i f o l d Ch a r t i n g、 Di f f u s i o nm aps_ 9、

L o c a l l y L i n e a r I n l a y i n g( L L I )[ 1、Ma x i ma l L i n e a r Emb e d d i n g ( ML E) E 1 2 3

等。流形学习可以

分为两类：一类是全局方法 (如I s o ma p ),即从全局角度出发，在降维时流形上临近的点映射到低维空间时保持临近；另一类是局部方法 (如L L E、 L E、 HL L E、 L TS A等),这些降维方法只保证在一个局部范围内将临近点间的关系映射到低维空间。由于局部方法只需要考虑流形临近点之间的关系，无须要求流形所对应的低维空间为凸，且计算复杂度较低，因此局部方法有着更广泛的适用对象[ 1。

局部保持的流形学习方法通过保持邻域内的局部近邻结构来构造全局低维表示，所以，邻域结构的表示和保持程度将直接影响最终的嵌入效果。在刻画流形的局部几何特性时，需要尽量保证局部邻域能

够同胚于欧氏空间的一个连通开集。显然，邻域越小，近邻结构越容易忠实保持。另一方面，邻域之间需要有足够的交叠以保证全局排列时有足够的联系，这又使得邻域不能过小。这种矛盾一直伴随着流形学习算法，当样本点比较稀疏时，邻域内的局部同胚条件更加难以保持，这就造成了目前绝大多数流形学习算法在样本点较为稀疏时的失效。 ‘ 针对流形学习算法无法有效处理稀疏样本点集的问题，本文提出一种基于三角形重心的线性插值方法并应用于流形学习算法。在本文提到的算法中，首先在样本点的各邻域内选取与样本点距离最近的

3个点作为基本点；然后从这 3个点中任选 2个与原样本点本身组成一个三角形并求得其重心作为插

值点，利用这些插值点与原样本点一起组成新的样本点集，并求取其低维坐标；最后，将原样本点的坐标抽离和表示出来，最终得到原样本点集的低维坐标值。在将本文提到的插值算法应用到经典的流形学习算法如 L T S A后，实验结果证实了算法的有效性和稳定性。收稿日期： 2 0 1 2— 0 6一 i i

作者简介：顾艳春 ( 1 9 8 1一 ),男，河南信阳人，佛山科学技术学院讲师。

本文来源：https://www.bwwdw.com/article/ew91.html