Data embedding techniques and applications

ABSTRACT

As an effective way for dimensionality reduction, data embedding has direct applications in data mining, data indexing and searching, information retrieval, and multimedia data processing. As two representative techniques for data embedding, both Isomap and LLE require the construction of neighborhood graphs on which every point is connected to its neighbors. This paper reviews several techniques that have been developed to construct connected neighborhood graphs. These methods have made Isomap and LLE applicable to a wide range of data including under-sampled data and non-uniformly distributed data. Application-related issues of data embedding techniques are also discussed.

REFERENCES

• 1: M. Balasubramanian, E. L. Schwartz, J. B. Tenenbaum, V. de Silva, and J. C. Langford. The Isomap algorithm and topological stability. Science, 295:7a, Jan. 2002.
• 2: T. F. Cox and M. A. A. Cox. Multidimensional Scaling, 2nd Edition. Chapman & Hall, 2001.
• 3: P. Demartines and J. Herault. Curvilinear component analysis: A self-organizing neural network for nonlinear mapping of data sets. IEEE Trans. Neural Networks, 8(1):148--154, Jan. 1997.
• 4: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 5: S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM J. Computing, 4(4):507--518, Dec. 1975.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: J. J. W. Sammon. A nonlinear mapping for data structure analysis. IEEE Trans. Computers, C-18(5):401--409, May 1969.
• 8: J. Kruskal. Multidimensional scaling by optimizing goodness-of-fit to a nonmetric hypothesis. Psychometrika, 29:1--27, 1964.
• 9: J. A. Lee, A. Lendasse, N. Donckers, and M. Verleysen. A robust nonlinear projection method. In Proc. 8th European Symp. Artificial Neural Networks (ESANN2000), Bruges, Belgium, Apr. 2000.
• 10: K. Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:95--115, 1927.
• 11: S. T. Roweis and L. K. Saul. Nonlineaar dimensionality reduction by locally linear embedding. Science, 290:2323--2326, Dec. 2000.
• 12: Lawrence K. Saul , Sam T. Roweis, Think globally, fit locally: unsupervised learning of low dimensional manifolds, The Journal of Machine Learning Research, 4, p.119-155, 12/1/2003
• 13: H. S. Seung and D. Lee. The manifold ways of perception. Science, 290:2268--2269, Dec. 2000.
• 14: J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319--2323, Dec. 2000.
• 15: Li Yang, Distance-Preserving Projection of High-Dimensional Data for Nonlinear Dimensionality Reduction, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1243-1246, September 2004 [doi>10.1109/TPAMI.2004.66]
• 16: Li Yang, k-Edge Connected Neighborhood Graph for Geodesic Distance Estimation and Nonlinear Data Projection, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 1, p.196-199, August 23-26, 2004 [doi>10.1109/ICPR.2004.517]
• 17: Li Yang, Sammon's Nonlinear Mapping Using Geodesic Distances, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 2, p.303-306, August 23-26, 2004 [doi>10.1109/ICPR.2004.801]
• 18: Li Yang, Building k-edge-connected neighborhood graph for distance-based data projection, Pattern Recognition Letters, v.26 n.13, p.2015-2021, 1 October 2005 [doi>10.1016/j.patrec.2005.03.021]
• 19: Li Yang, Building k Edge-Disjoint Spanning Trees of Minimum Total Length for Isometric Data Embedding, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.10, p.1680-1683, October 2005 [doi>10.1109/TPAMI.2005.192]
• 20: H. Zha and Z. Zhang. Isometric embedding and continuum ISOMAP. In Proc. 20th Inter. Conf. Machine Learning (ICML'03), pages 864--871, Washington, DC, Aug. 2003.
• 21: C. Zhang, J. Wang, N. Zhao, and D. Zhang. Reconstruction and analysis of multi-pose face images based on nonlinear dimensionality reduction. Pattern Recognition, 37(2):325--336, Feb. 2004.

INDEX TERMS

Keywords:
data embedding, dimensionlaity reduction, manifold learning, neighborhood graph