作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (5): 53-56,60. doi: 10.3969/j.issn.1000-3428.2013.05.010

• 先进计算与数据处理 • 上一篇    下一篇

基于稀疏约束的LLE改进算法

孙 洋,叶庆卫,王晓东,周 宇   

  1. (宁波大学信息科学与工程学院,浙江 宁波 315211)
  • 收稿日期:2012-05-22 出版日期:2013-05-15 发布日期:2013-05-14
  • 作者简介:孙 洋(1987-),男,硕士研究生,主研方向:信号处理;叶庆卫、王晓东、周 宇,副教授
  • 基金资助:
    国家自然科学基金资助项目(61141015);浙江省自然科学基金资助项目(Y1110161);宁波市自然科学基金资助项目(2011A610181)

Improved LLE Algorithm Based on Sparse Constraint

SUN Yang, YE Qing-wei, WANG Xiao-dong, ZHOU Yu   

  1. (College of Information Science and Engineering, Ningbo University, Ningbo 315211, China)
  • Received:2012-05-22 Online:2013-05-15 Published:2013-05-14

摘要: 局部线性嵌入(LLE)算法可以发现隐藏在高维空间中的局部线性低维流形,实现数据降维,而LLE算法对数据噪声比较敏感,在较强噪声下算法稳定性很差。为此,提出一种基于稀疏约束的改进算法,在计算重构误差的表达式后添加L1范数的惩罚性约束,促使最优重构权值矩阵更具有稀疏性。通过正则化处理,把添加稀疏约束的重构误差最优化目标函数变换成一般二次规划问题,引入内点迭代法快速搜索最优解。仿真实验结果表明,在不同噪声影响下,稀疏约束的改进LLE算法的降维效果明显好于经典LLE算法,具有更强的噪声抵抗能力。

关键词: 稀疏约束, 局部线性嵌入, 流形学习, 鲁棒性, L1范数, 内点迭代法

Abstract: Locally Linear Embedding(LLE) algorithm can achieve data dimensionality reduction by finding the local linear low-dimensional manifold hidden in the high-dimensional space. The LLE algorithm is sensitive to noise, moreover, the stability of the algorithm is very poor when exposed to strong noise. This paper proposes a sparse constraint improvement method, by adding L1 norm punitive constraint to the reconstruction error function, the optimal reconstruction weight matrix is sparser. Transform the reconstruction error function which adds the sparse constraint into a general quadratic programming problem by regularization, and uses interior-point iteration method to search the optimal solution quickly. Simulation experimental results of the typical high-dimensional data set dimensionality reduction show that the dimensionality reduction results of the LLE algorithm in sparse constraint is significantly better than the classic LLE algorithm under the influence of different noise, and has a stronger ability in resisting noise.

Key words: sparse constraint, Locally Linear Embedding(LLE), manifold learning, robustness, L1-norm, interior-point iteration method

中图分类号: