论文研究-保持局部邻域关系的增量Hessian LLE算法 .pdf

所需积分/C币:9 2019-08-17 05:21:47 651KB .PDF
64
收藏 收藏
举报

保持局部邻域关系的增量Hessian LLE算法,高翠珍,胡建龙,Hessian LLE算法是一种经典的流形学习算法,但该方法是以批处理的方式进行的,当新的数据点加入时,必须重新运行整个算法计算所有数�
山国科技论文在线 http:/www.paper.edu.cn 了LLE的局部带权线性表示;2)每个点的切空间要求其邻域是线性的.即选择合适的邻域, 80保证邻域的局部线性特性,这是HLLE需要克服的一个问题;3)HLLE需要对每个数据点计 算dxd次偏导数,当观察数据的维数非常髙时,计算量较大,这是HLLE需要克服的另一个问 题ε因此,针对增量的IILE算法,本文着重考虑这两个问题,保证随着数据点的增多,邻 域的大小也自适应地发生变化,同时尽可能降低算法的复杂度 2增量 Hessian llE算法( LIHLLE) 85 在假设原样本点计算结果准确的基础上,本文提岀的保持局部邻域关系的增量HLLE 算法,分三步来计算新样本的低维嵌入:①根据流形结构的局部线性特性,从而自适应的确 定新增点的邻域,邻域的线性程度用PCA米度量;②通过使得新增点在原空间中的邻域线 性表示和其本身的误差最小,计算新增点在原空间中的邻域权值:③利用原样本的嵌入结果, 保持原空间和嵌入空间邻域权值不变,计算新増点的投景值 902.1自适应的邻域选择 设原样本集为X={x1…,xn},用经典的HLLE算法得到的ⅹ的嵌入结果为 Y-{F12,y,},新增样本点记为x。用KNN(xn+)表示x1的K最近邻,用RN(xn+)表示 x,的合理邻域集,初始值为空。新增样本x加入后,其合理邻域的计算过程如下 (1)计算距离其最近的K(K>d)个点,按边长度递增的顺序排列,记为 5NN(xn1)={xn+1,xn1x},同时令RN(xn1)={xn12…,xnb}; (2)用PCA方法度量其局部线忙特性,满足邻域线性条件的点为合理邻域点,即依次计 算 xn1∪RN(xn1)(=d+1:K)样本集的协方差矩阵的特征值λ≥λ≥…≥λ2,如果特征值满 足∑,∑>n(n为经验值),x就记为x1的合理邻域, 100 RN(X,D=X,M URN(x,)u 22计算邻域权值 通过RNxm)米计算新增样本点xn1的重构权值wn+,代价函数为 e(W)=xm+-∑Wm1xm1,其中xm,∈RN(xm 权值W,满足条件∑n=1 (2) 105 这样,求最优权值就是对于公式(1)在约束条件(2)下求解最小二乘问题。 23计算低维嵌入 邻域权值wn确定后,新样本点xn的低维表示可以通过以下公式得到: xn+1->Jn+1= n+1,1n+1 其中rn1∈ (3) 3 山国科技论文在线 http:/www.paper.edu.cn 以上算法可以计算出单个新增点的低维嵌入,当有多个样本同吋加入吋,循坏计算每个 110数据点,将每次计算出的结果加入已有的嵌入结果中作为原始点,依次计算出所有新增点的 低维嵌入。(本实验中K取30,n取093) 3实验结果及分析 3.1实验 实验选取 Swiss roll with hole和 frey rawface两个数据集,分别用批处理HLLE和增量 115HLLE两种方法计算样本点的投影值,通过比较两种方法的实验结果验证本算法的有效性。 Swiss roll with hole数据集为3维空间的面包圈,将其嵌入到2维空间; frey rawface数据集 由1965幅,像素为20*28,不同姿态和衣情的人脸图像组成,即原始空间为20*28-=560维, 嵌入到2维空间分别表示人险姿态和情。图1是 frey rawface数据集的些样本。为了比 较批处理HLLE算法和增量HLLE两种算法嵌入值的差别,定乂误差米度量。误差的表示 120形式为: F;-y;| errot (4) LF: II 其中y和;分别表示第r个点用HLLE和LHLE计算的低维嵌入值,误差越小, LIHLLE的嵌入结果越接近于HLE的嵌入结果。同时通过比较两种方法所耗的时间来度量 算法的效率。 125 adaseslasaslesla 品二 图1 frey rawface数据库中的10个样本 Fig. I ten samples in the databasc fry rawfacc /:)时 叶, : ∵…, ,, (a)N=1000 (b)HLLE (C) LLIhLLE ∵∷慧 :, (d)N=1500 (D LIlLe (e) hll e 4 山国删技论文在线 http:/www.paper.edu.cn ∷∴,; D 0t 135 随然状 (g)N=2000 (h) HLle G) LIHLLE 图2原始图,HLLE嵌入图, LIHLLE嵌入图(样本点分别为1000、1500、2000) Fig 2 raw figure, HLLE embedding figure and Lille embedding figure sample points, respectively 1000 140 1500.2000 x10 样本敞 样本数 (a) Swiss roll with hole b) frey rawface 冬3 LIHLLE算法的误差曲线图 145 Fig. 3 error curve of lIllE algorithm 先在每个数据集上各随机抽取500个点作为原始样本点,用HLE计算它们的低维嵌入, 然后再将新样本点一个接一个地加入,用 LIHLLE算法计算它们的投影值,直到2000个数 据点 150 图2显示了在 Swiss roll with hole数据集上的效果图,(a.b.c),(d,ef,、gh三组图分别表 小样本点数N从500增加到1000、1500、200时对应的原始数据图、HLLE算法的低维嵌 入图及 LIHLLE算法的低维嵌入图。图3用误差曲线图定量的表小」两种方法的低维嵌入结 果,图3(a)为 Swiss roll with hole数据集上, LIHLLE算法对应的误差曲线图,图3(b)为 frey rawfac数据集上, LIHLLE算法对应的误差曲线图,其中椟轴均表示样本数,纵轴均表 155示用两种方法映射产生的误差。同时表1记录了原始样本点数N从500依次增加为1000、 1500、2000个数据点时,用两种方法映射到低维空间时所消耗的时间 表1HLLE和 LIHLLE的运行时间(单位:s) Tab 1 running time of hlle and lihlle (unit : s) Swiss roll with hole frey rawface HLLE LIHLLE HLLE LIHLLE 500 51 5.96 1000 0.14 4013 0.46 l500 4951.1 12573.7 200013530.2 0.65 NA 1603.2结果分析 通过图2可以直观地发现本文提出的增量HLLE算法也可以很好地将 Swiss roll with 山国科技论文在线 http:/www.paper.edu.cn hole数据集展川,和原始HLLE算法的展川结果几乎样。图3(a)和3(b)进步用误差定量 的证明了本文中算法的有效性,该方法在 Swiss roll with hole数据集上的平均误差为 9.7153e-005,在 frey rawface数据集上的平均误差为1.8955-004,这个误差均很小,可见该 165方法的处理精度完全满足要求。 表1的数据表示了本文的增量HLE算法和原始的HLLE算法在两种数据集上的运行 时间,由此可知本文中算法的速度明显快于批处理的HLE算法。此外,文献中提出的增 量HLLE学习方法虽然比原始的HLLE算法效率高,但仍需要对每个点计算 Hession矩阵, 计算过程仍然是复杂的,而夲文提出的算法巧妙地避免了这些复杂的计算,大大减少了算法 170运行的时间。凼此,本文在保证嵌入结果准确的前挠下,大大提高了算法的效率 4结束语 本文基于流形的局部线性特性,在假设原来的映射结果准确的基础上提出了增量的 HLLE算法。该算法避免了重复计算所有样本点的嵌入,利用原有的嵌入结果简单高效的计 算出了新増样本点的嵌入结果,实现了HLLE的增量学习。在 Swiss roll with hole和 175 frey rawface数据集上的实验证明,该算法得到的结果与批处理方法得到的结果相近,然而 算法的效率得到了很大的提高 参考文献( References) 180 [1] TENENBAUM J B. DE SILVA V, LANGFORD J C. Aglobal geometric framework for nonlinear [2 ROWEIS S T, SAUL L K. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000.290:2323-2326 [3 BELKINM, NIYOGI P Laplacian eigenmaps for dimensionality reduction and data rep resentation[]. Neural Computing,2003,15(6:1373-1396 185 [4] DONOHO D L, GRIMES C. Hessian Eigenmaps: Locally Linear Embedding Techniques for High Dimensional Data]. Proceedings of the National Academy of Sciences of the United States of America,2003,100(10):5591-5596. 5 MARTN HCL, ANIL K J Incremental Nonlinear Dimensionality Reduction by Manifold Learning[J. IEEE Trans. Pattern Analysis and Machine Intelligence, 2006, 28(3): 377-391 190 16]P. JIA et al. Incremental Laplacian eigenmaps by preserving adjacent information between data points[-] Pattern Recognition, 2009, 30: 1457-1463 [7 OLGA KOUROPTEVA, OLEG OKUN et al. Incremental locally linear embedding algorithm[]. Pattern Recognition,2005,38(10):1764-1767 [8]李厚森,成礼智.增量 Hessian lle算法研究[门.计算机工程,2010,37(6):159-161 195

...展开详情
试读 6P 论文研究-保持局部邻域关系的增量Hessian LLE算法 .pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-保持局部邻域关系的增量Hessian LLE算法 .pdf 9积分/C币 立即下载
1/6
论文研究-保持局部邻域关系的增量Hessian LLE算法 .pdf第1页
论文研究-保持局部邻域关系的增量Hessian LLE算法 .pdf第2页

试读结束, 可继续阅读

9积分/C币 立即下载