Nonlinear Dimension Reduction by Local Multidimensional Scaling

详细信息    查看全文

• 关键词：Dimension reduction ; Nonlinear manifold ; Neighbourhood ; preserving ; Local multidimensional scaling
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9711
• 期：1
• 页码：158-171
• 全文大小：2,918 KB
• 参考文献：1.Sorzano, C.O.S., Vargas, J., Montano, A.P.: A survey of dimensionality reduction techniques (2014). arXiv preprint arXiv:​ 1403.​2877
  2.Sarveniazi, A.: An actual survey of dimensionality reduction. Am. J. Comput. Math. 4(5), 55–72 (2014)CrossRef
  3.van der Maaten, L.J., Postma, E.O., van den Herik, H.J.: Dimensionality reduction: a comparative review. J. Mach. Learn. Res. 10(1–41), 66–71 (2009)
  4.Jiang, X., Gao, J., Hong, X., Cai, Z.: Gaussian processes autoencoder for dimensionality reduction. In: Tseng, V.S., Ho, T.B., Zhou, Z.-H., Chen, A.L.P., Kao, H.-Y. (eds.) PAKDD 2014, Part II. LNCS, vol. 8444, pp. 62–73. Springer, Heidelberg (2014)CrossRef
  5.Roweis, S.T., Saul, L.K.: Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500), 2323–2326 (2000)CrossRef
  6.Tenenbaum, J.B., De Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290(5500), 2319–2323 (2000)CrossRef
  7.Abdi, H., Williams, L.J.: Principal component analysis. Wiley Interdisc. Rev. Comput. Stat. 2(4), 433–459 (2010)CrossRef
  8.Borg, I., Groenen, P.J.: Modern Multidimensional Scaling: Theory and Applications. Springer Science & Business Media, New York (2005)MATH
  9.Brown, T.A.: Confirmatory Factor Analysis for Applied Research. Guilford Publications, New York (2015)
  10.Li, M., Yuan, B.: 2d-lda: a statistical linear discriminant analysis for image matrix. Pattern Recogn. Lett. 26(5), 527–532 (2005)CrossRef
  11.Hardoon, D.R., Shawe-Taylor, J.: Convergence analysis of kernel canonical correlation analysis: theory and practice. Mach. Learn. 74(1), 23–38 (2009)MathSciNet CrossRef
  12.Hyvärinen, A., Oja, E.: Independent component analysis: algorithms and applications. Neural Netw. 13(4), 411–430 (2000)CrossRef
  13.Schölkopf, B., Smola, A., Müller, K.-R.: Kernel principal component analysis. In: Gerstner, W., Hasler, M., Germond, A., Nicoud, J.-D. (eds.) ICANN 1997. LNCS, vol. 1327. Springer, Heidelberg (1997)
  14.Bernstein, M., De Silva, V., Langford, J.C., Tenenbaum, J.B.: Graph approximations to geodesics on embedded manifolds, Technical report, Department of Psychology, Stanford University (2000)
  15.Saul, L., Roweis, S.: “Think globally, fit locally: unsupervised learning of nonlinear manifolds,” Technical report MS CIS-02-18 (2002)
  16.Donoho, D.L., Grimes, C.: Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. Proc. Natl. Acad. Sci. 100(10), 5591–5596 (2003)MathSciNet CrossRef MATH
  17.Zhang, Z., Zha, H.: Nonlinear dimension reduction via local tangent space alignment. In: Liu, J., Cheung, Y., Yin, H. (eds.) IDEAL 2003. LNCS, vol. 2690. Springer, Heidelberg (2003)
  18.Hastie, T.: Principal curves and surfaces, Technical report, DTIC Document (1984)
  19.Horn, B.K., Hilden, H.M., Negahdaripour, S.: Closed-form solution of absolute orientation using orthonormal matrices. JOSAA 5(7), 1127–1135 (1988)MathSciNet CrossRef
  20.Lee, J.A., Verleysen, M. et al.: Quality assessment of nonlinear dimensionality reduction based on k-ary neighborhoods. In: FSDM, pp. 21–35 (2008)
  
• 作者单位：Yuzhe Ma (15)
  Kun He (15)
  John Hopcroft (16)
  Pan Shi (15)
  
  15. Huazhong University of Science and Technology, Wuhan, China
  16. Cornell University, New York, USA
  
• 丛书名：Frontiers in Algorithmics
• ISBN：978-3-319-39817-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9711

文摘

We propose a neighbourhood-preserving method called LMB for generating a low-dimensional representation of the data points scattered on a nonlinear manifold embedded in high-dimensional Euclidean space. Starting from an exemplary data point, LMB locally applies the classical Multidimensional Scaling (MDS) algorithm on small patches of the manifold and iteratively spreads the dimension reduction process. Differs to most dimension reduction methods, LMB does not require an input for the reduced dimension, as LMB could determine a well-fit dimension for reduction in terms of the pairwise distances of the data points. We thoroughly compare the performance of LMB with state-of-the-art linear and nonlinear dimension reduction algorithms on both synthetic data and real-world data. Numerical experiments show that LMB efficiently and effectively preserves the neighbourhood and uncovers the latent embedded structure of the manifold. LMB also has a low complexity of \(O(n^2)\) for n data points.