A Dynamic Neighborhood Selection Approach for Locally Linear Embedding

Abstract:

Locally linear embedding is based on the assumption that the whole data manifolds are evenly distributed so that they determine the neighborhood for all points with the same neighborhood size. Accordingly, they fail to nicely deal with most real problems that are unevenly distributed. This paper presents a new approach that takes the general conceptual framework of Hessian locally linear embedding so as to guarantee its correctness in the setting of local isometry to an open connected subset but dynamically determines the local neighborhood size for each point. This approach estimates the approximate geodesic distance between any two points by the shortest path in the local neighborhood graph, and then determines the neighborhood size for each point by using the relationship between its local estimated geodesic distance matrix and local Euclidean distance matrix. This approach has clear geometry intuition as well as the better performance and stability to deal with the sparsely sampled or noise contaminated data sets that are often unevenly distributed. The conducted experiments on benchmark data sets validate the proposed approach.

• Periodical: Advanced Materials Research (Volumes 1033-1034)
• Pages: 1369-1372
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1033-1034.1369
• Online since: October 2014
• Authors: Gui Jun Shan*
• Keywords: Dimensionality Reduction, Hessian Locally Linear Embedding, Manifold Learning

References

[1] J. B. Tenenbaum, V. de Silva and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, no. 5500, pages 2319-2323, (2000).

DOI: 10.1126/science.290.5500.2319

[2] S. T. Roweis, L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, vol. 290, no. 5500, pages 2323-2326, (2000).

DOI: 10.1126/science.290.5500.2323

[3] X. Geng, D. C. Zhan and Z. H. Zhou. Supervised nonlinear dimensionality reduction for visualization and classification. IEEE Transactions on Systems, Man and Cybernetics, vol. 35, no. 6, pages 1098-1107, (2005).

DOI: 10.1109/tsmcb.2005.850151

[4] M. H. C. Law and A. K. Jain. Incremental nonlinear dimensionality reduction by manifold learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 3, pages 377-392, (2006).

DOI: 10.1109/tpami.2006.56

[5] D. L. Donoho and C. Grimes. Hessian eigenmaps: Locally linear embedding, techniques for high-dimensional data. PNAS, vol. 100, no. 10, pages 5591-5596, (2003).

DOI: 10.1073/pnas.1031596100

[6] O. Kouropteva, O. Okun and M. Pietikainen. Incremental locally linear embedding. Pattern Recognition, vol. 38, no. 10, pages 1764-1767, (2005).

DOI: 10.1016/j.patcog.2005.04.006

[7] D. de Ridder, M. Loog and M. J. T. Reinders. Local fisher embedding. In Proceedings of The 17th International Conference on Pattern Recognition, Vol. 2, pages 295-298, 2004. http: /ieeexplore. ieee. org/xpls/abs_all. jsp?arnumber=1334176.

DOI: 10.1109/icpr.2004.1334176