计算机科学 ›› 2015, Vol. 42 ›› Issue (8): 244-248.

• 人工智能 • 上一篇    下一篇

一种新的基于MSC和ISOMAP的快速流形学习算法

雷迎科   

  1. 电子工程学院 合肥230037
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金(61272333,61273302,61171170,61473237),安徽省自然科学基金(1208085MF94,1308085QF99,1408085MF129)资助

New Fast Manifold Learning Algorithm Based on MSC and ISOMAP

LEI Ying-ke   

  • Online:2018-11-14 Published:2018-11-14

摘要: 针对等距特征映射(ISOMAP)算法计算复杂度高的问题,提出了一种新的基于最小子集覆盖(MSC)策略的快速等距特征映射算法(Fast-ISOMAP)。与原始的ISOMAP算法相比,Fast-ISOMAP算法在不显著改变原始ISOMAP算法嵌入性能的条件下,大大提高了算法的计算效率,也适用于大规模流形学习问题。在标准数据集上的实验结果验证了该算法的有效性。

关键词: 等距特征映射,最小子集覆盖,多维尺度分析,流形学习

Abstract: For the high complexity problem of the isometric feature mapping algorithm(ISOMAP),we designed a new fast isometric feature mapping(Fast-ISOMAP) method based on minimum set cover(MSC) strategy.It is found in experiments that Fast-ISOMAP can greatly improve the computational efficiency of the original ISOMAP and be used in large-scale manifold learning problems under the condition that it does not significantly change the performance of ISOMAP.Experimental results on many artificial benchmark datasets show the effectiveness of our proposed algorithm.

Key words: Isometric feature mapping,Minimum set cover,Multidimensional scaling,Manifold learning

[1] Tenenbaum J,de Silva V,Langford J.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323
[2] Roweis S,Saul L.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326
[3] Belkin M,Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation ,2003,15(6):1373-1396
[4] Donoho D,Grimes C.Hessian eigenmaps:new locally linear embedding techniques for high-dimensional data[J].Proceedings of the National Academy of Sciences,2003,100(10):5591-5596
[5] Weinberger K,Saul L.Unsupervised learning of image manifolds by semidefinite programming[C]∥Proceedings of CVPR2004.2004:988-995
[6] Zhang Z,Zha H.Principal manifolds and nonlinear dimension reduction via local tangent space alignment[J].SIAM Journal Scien-tific Computing,2005,26(1):313-338
[7] Lin T,Zha H B.Riemannian manifold learning[J].IEEE Trans-actions on Pattern Analysis and Machine Intelligence,2008,30(5):796-809
[8] Luo D J,Ding C,Nie F P,et al.Cauchy graph embedding[C]∥Proceedings of ICML2011.2011:553-560
[9] Zhang Z Y,Wang J,Zha H Y.Adaptive manifold learning[J].IEEE Trans.PAMI,2012,34(2):253-265
[10] Qiao H,Zhang P,Wang D,et al.An explicit nonlinear mapping for manifold learning[J].IEEE Trans.Cybernetics, 2013,43(1):51-63
[11] 刘辉,杨俊安,王一.基于流形学习的声目标特征提取方法研究[J].物理学报,2011,60(7):1-7 Liu H,Yang J A,Wang Y.A novel approach to research on feature extraction of acoustic targets based on manifold learning[J].Acta Phys.Sin.,2011,60(7):1-7
[12] He X,Yan S,Hu Y,et al.Face recognition using Laplacianfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340
[13] 刘利,韦佳,马千里.基于流形学习的图像检索研究进展[J].北京交通大学学报,2010,34(5):164-171 Liu L,Wei J,Ma Q L.State-of-the-art on image retrieval based on manifold learning[J].Journal of Beijing Jiaotong University,2010,34(5):164-171
[14] De Silva V,Tenenbaum J B.Global versus local methods in nonlinear dimensionality reduction[J].Advances in Neural Information Processing Systems,2003,15:721-728
[15] De Silva V,Tenenbaum J B.Sparse multidimensional scaling using landmark points[R].Stanford,CA:Dept.Math.,Stanford University,2004
[16] Garey M R,Johnson D S.Computers and intractability:a guide to the theory of NP-completeness[M].WH Freeman & Co.New York,NY,USA,1979
[17] Karp R.Reducibility among combinatorial problems[M]∥Complexity of Computer Computations.1972:85-103

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!