Email this article Extension of ISOMAP for Imperfect Manifolds
Abstract
As one of the most promising nonlinear dimensionality reduction techniques, Isometric Mapping (ISOMAP) performs well only when the data belong to a single well-sampled manifold, where geodesic distances can be well approximated by the corresponding shortest path distances in a suitable neighborhood graph. Unfortunately, the approximation gets less and less precise generally as the number of edges of the corresponding shortest path increases, which makes ISOMAP tend to overlap or overcluster the data, especially for disjoint or imperfect manifolds. To alleviate this problem, this paper presented a variant of ISOMAP, i.e. Edge Number-based ISOMAP (ENISOMAP), which uses a new variant of Multidimensional Scaling (MDS), i.e. Edge Number-based Multidimensional Scaling (EN-MDS), instead of the classical Multidimensional Scaling (CMDS) to map the data into the low-dimensional embedding space. As a nonlinear variant of MDS, ENMDS gives larger weight to the distances with fewer edges, which are generally better approximated and then more trustworthy than those with more edges, and thus can preserve the more trustworthy distances more precisely. Finally, experimental results verify that not only imperfect manifolds but also intrinsically curved manifold can be visualized by EN-ISOMAP well.
Keywords
References
[1] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, Second Edition. New York, NY, USA: John Wiley & Sons, Inc., 2000.
[2] D. A. Keim, “Designing pixel-oriented visualization techniques: Theory and applications,” IEEE Transactions on Visualization and Computer Graphics, vol. 6, no. 1, pp. 59–78, 2000.
http://dx.doi.org/10.1109/2945.841121
[3] A. Inselberg and B. Dimsdale, “Parallel coordinates: A tool for visualizing multi-dimensional geometry,” in Proceedings of the 1st IEEE Conference on Visualization, San Francisco, CA, USA, 1990, pp. 361–378.
http://dx.doi.org/10.1109/VISUAL.1990.146402
[4] E. Kandogan, “Visualizing multi-dimensional clusters, trends, and outliers using star coordinates,” in Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2001, pp. 107–116.
http://dx.doi.org/10.1145/502512.502530
[5] J. LeBlanc, M. O. Ward, and N. Wittels, “Exploring n-dimensional databases,” in Proceedings of the 1st IEEE Conference on Visualization, San Francisco, CA, USA, 1990, pp. 230–237.
http://dx.doi.org/10.1109/VISUAL.1990.146386
[6] B. Shneiderman, “Tree visualization with treemaps: A 2d space-filling approach,” ACM Transactions on Graphics, vol. 11, no. 1, pp. 92–99, 1992.
http://dx.doi.org/10.1145/102377.115768
[7] R. M. Pickett and G. G. Grinstein, “Iconographic displays for visualizing multidimensional data,” in Proceedings of the 1988 IEEE Conference on Systems, Man and Cybernetics, Beijing and Shenyang, China, 1998, pp. 514–519.
[8] M. O. Ward, “Xmdvtool: Integrating multiple methods for visualizing multivariate data,” in Proceedings of the 5th IEEE Conference on Visualization, Washington, DC, USA, 1994, pp. 326–336.
[9] A. Naud and W. Duch, “Interactive data exploration using mds mapping,” in Proceedings of the 5th Conference on Neural Networks and Soft Computing, Zakopane, Poland, Jun. 2000, pp. 255–260.
[10] M. Quist and G. Yona, “Distributional scaling: An algorithm for structure-preserving embedding of metric and nonmetric spaces,” Journal of Machine Learning Research, vol. 5, pp. 399–420, 2004.
[11] H. Yin, “Nonlinear multidimensional data projection and visualisation,” in Proceedings of the 4th International Conference on Intelligent Data Engineering and Automated Learning, Hong Kong, China, Mar. 2003, pp. 377–388.
http://dx.doi.org/10.1007/978-3-540-45080-1_49
[12] C. Shao, X. Zhang, C. Wan, and W. Shang, “A som-based method for manifold learning and visualization,” in Proceedings of the 2nd International Joint Conference on Computational Sciences and Optimization, Sanya, Hainan, China, 2009, pp. 312–316.
http://dx.doi.org/10.1109/CSO.2009.49
[13] J. B. Tenenbaum, V. de Silva, and J. C. Langford, “A global geometric framework for nonlinear dimensionality reduction,” Science, vol. 290, no. 5500, pp. 2319–2323, 2000.
http://dx.doi.org/10.1126/science.290.5500.2319
PMid:11125149
[14] M. Vlachos, C. Domeniconi, D. Gunopulos, G. Kollios, and N. Koudas, “Non-linear dimensionality reduction techniques for classification and visualization,” in Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, Jul. 2002, pp. 645–651.
http://dx.doi.org/10.1145/775047.775143
[15] C. Shao, H. Huang, and L. Zhao, “A more topologically stable isomap algorithm,” Journal of Software (in Chinese), vol. 18, no. 4, pp. 869–877, 2007.
http://dx.doi.org/10.1360/jos180869
[16] S. T. Roweis and L. K. Saul, “Nonlinear dimensionality reduction by locally linear embedding,” Science, vol. 290, no. 5500, pp. 2323–2326, 2000.
http://dx.doi.org/10.1126/science.290.5500.2323
PMid:11125150
[17] A. Hadid and M. Pietik¨ainen, “Efficient locally linear embeddings of imperfect manifolds,” in Proceedings of the 3rd International Conference on Machine Learning and Data Mining, Leipzig, Germany, Jul. 2003, pp. 188–201.
[18] M. Belkin and P. Niyogi, “Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Computation, vol. 15, no. 6, pp. 1373–1396, 2003.
http://dx.doi.org/10.1162/089976603321780317
[19] D. L. Donoho and C. Grimes, “Hessian eigenmaps: Locally linear embedding techniques for high dimensional data,” Proceedings of the National Academy of Sciences, vol. 100, no. 10, pp. 5591–5596, 2003.
http://dx.doi.org/10.1073/pnas.1031596100
PMCid:156245
[20] Y. Li, “Distance-preserving projection of high-dimensional data for nonlinear dimensionality reduction,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1243–1246, 2004.
http://dx.doi.org/10.1109/TPAMI.2004.66
PMid:15742900
[21] M. Bernstein, V. de Silva, J. C. Langford, and J. B. Tenenbaum, “Graph approximations to geodesics on embedded manifolds,” Department of Psychology, Stanford University, Tech. Rep., 2000.
[22] J. Lee, A. Lendasse, and M. Verleysen, “Nonlinear projection with curvilinear distances: Isomap versus curvilinear distance analysis,” Neurocomputing, vol. 57, no. 1, pp. 49–76, 2004.
http://dx.doi.org/10.1016/j.neucom.2004.01.007
[23] O. Kouropteva, O. Okun, A. Hadid, M. Soriano, S. Marcos, and M. Pietik¨ainen, “Beyond locally linear embedding algorithm,” Machine Vision Group, University of Oulu, Tech. Rep. MVG-01-2002, 2002.
[24] V. de Silva and J. B. Tenenbaum, “Unsupervised learning of curved manifolds,” in Proceedings of the MSRI workshop on nonlinear estimation and classification, Berkeley, CA, USA, 2002, pp. 453–466.
[25] M. W. Trosset, “Extensions of classical multidimensional scaling: Computational theory,” Computational Statistics, vol. 17, pp. 147–162, 2002.
http://dx.doi.org/10.1007/s001800200099
[26] M. Balasubramanian, E. Shwartz, J. Tenenbaum, V. de Silva, and J. Langford, “The isomap algorithm and topological stability,” Science, vol. 295, no. 5552, pp. 7a–7, 2002.
http://dx.doi.org/10.1126/science.295.5552.7a
PMid:11778013
Full Text: PDF