nips nips2011 nips2011-67 nips2011-67-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Xiaoyin Ge, Issam I. Safa, Mikhail Belkin, Yusu Wang
Abstract: Recovering hidden structure from complex and noisy non-linear data is one of the most fundamental problems in machine learning and statistical inference. While such data is often high-dimensional, it is of interest to approximate it with a lowdimensional or even one-dimensional space, since many important aspects of data are often intrinsically low-dimensional. Furthermore, there are many scenarios where the underlying structure is graph-like, e.g, river/road networks or various trajectories. In this paper, we develop a framework to extract, as well as to simplify, a one-dimensional ”skeleton” from unorganized data using the Reeb graph. Our algorithm is very simple, does not require complex optimizations and can be easily applied to unorganized high-dimensional data such as point clouds or proximity graphs. It can also represent arbitrary graph structures in the data. We also give theoretical results to justify our method. We provide a number of experiments to demonstrate the effectiveness and generality of our algorithm, including comparisons to existing methods, such as principal curves. We believe that the simplicity and practicality of our algorithm will help to promote skeleton graphs as a data analysis tool for a broad range of applications.
[1] Open street map. http://www.openstreetmap.org/.
[2] M. Aanjaneya, F. Chazal, D. Chen, M. Glisse, L. Guibas, and D. Morozov. Metric graph reconstruction from noisy data. In Proc. 27th Sympos. Comput. Geom., 2011.
[3] P. K. Agarwal, H. Edelsbrunner, J. Harer, and Y. Wang. Extreme elevation on a 2-manifold. Discrete and Computational Geometry (DCG), 36(4):553–572, 2006.
[4] M. Belkin and P. Niyogi. Laplacian Eigenmaps for dimensionality reduction and data representation. Neural Comp, 15(6):1373–1396, 2003.
[5] P. Bendich, B. Wang, and S. Mukherjee. Local homology transfer and stratification learning. In ACMSIAM Sympos. Discrete Alg., 2012. To appear.
[6] S. Biasotti, D. Giorgi, M. Spagnuolo, and B. Falcidieno. Reeb graphs for shape analysis and applications. Theor. Comput. Sci., 392:5–22, February 2008.
[7] K. Chang and J. Grosh. A unified model for probabilistic principal surfaces. IEEE Trans. Pattern Anal. Machine Intell., 24(1):59–64, 2002.
[8] F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in Euclidean space. Discrete Comput. Geom., 41(3):461–479, 2009.
[9] T. K. Dey and Y. Wang. Reeb graphs: Approximation and persistence. In Proc. 27th Sympos. Comput. Geom., pages 226–235, 2011.
[10] D Dong and T. J Mcavoy. Nonlinear principal component analysis based on principal curves and neural networks. Computers & Chemical Engineering, 20:65–78, 1996.
[11] T. Duchamp and W. Stuetzle. Extremal properties of principal curves in the plane. The Annals of Statistics, 24(4):1511–1520, 1996.
[12] H. Edelsbrunner and J. Harer. Computational Topology, An Introduction. Amer. Math. Society, 2010.
[13] X. Ge, I. Safa, M. Belkin, and Y. Wang. Data skeletonization via Reeb graphs, 2011. Full version at www.cse.ohio-state.edu/∼yusu.
[14] G. Haro, G. Randall, and G. Sapiro. Translated poisson mixture model for stratification learning. International Journal of Computer Vision, 80(3):358–374, 2008.
[15] W. Harvey, Y. Wang, and R. Wenger. A randomized O(mlogm) time algorithm for computing Reeb graphs of arbitrary simplicial complexes. In Proc. 26th Sympos. Comput. Geom., pages 267–276, 2010.
[16] T. J. Hastie. Principal curves and surfaces. PhD thesis, stanford university, 1984.
[17] T. J. Hastie and W. Stuetlze. Principal curves. Journal of the American Statistical Association, 84(406):502–516, 1989.
[18] B. K´ gl and A. Krzy˙ ak. Piecewise linear skeletonization using principal curves. IEEE Trans. Pattern e z Anal. Machine Intell., 24:59–74, January 2002.
[19] B. K´ gl, A. Krzyzak, T. Linder, and K. Zeger. Learning and design of principal curves. IEEE Trans. e Pattern Anal. Machine Intell., 22:281–297, 2000.
[20] M. Natali, S. Biasotti, G. Patan` , and B. Falcidieno. Graph-based representations of point clouds. Graphe ical Models, 73(5):151 – 164, 2011.
[21] P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39(1-3):419–441, 2008.
[22] U. Ozertem and D. Erdogmus. Locally defined principal curves and surfaces. Journal of Machine Learning Research, 12:1249–1286, 2011.
[23] I.-H. Park and C. Li. Dynamic ligand-induced-fit simulation via enhanced conformational samplings and ensemble dockings: A survivin example. J. Phys. Chem. B., 114:5144–5153, 2010.
[24] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000.
[25] B. Scholkopf, A. Smola, and K.R. Muller. Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation, 10:1299–1319, 2000.
[26] Derek Stanford and Adrian E. Raftery. Finding curvilinear features in spatial point patterns: Principal curve clustering with noise. IEEE Trans. Pattern Anal. Machine Intell., 22(6):601–609, 2000.
[27] J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.
[28] R. Tibshirani. Principal curves revisited. Statistics and Computing, 2:183–190, 1992.
[29] J. J. Verbeek, N. Vlassis, and B. Kr¨ se. A k-segments algorithm for finding principal curves. Pattern o Recognition Letters, 23(8):1009–1017, 2002. 9