K-edge connected neighborhood graph for geodesic distance estimation and nonlinear data projection
Author:
- 1 January 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10514651) , 196-199 Vol.1
Abstract
Nonlinear data projection based on geodesic distances requires the construction of a neighborhood graph that spans all data points so that the geodesic distance between any pair of data points could be estimated by the graph distance between the pair. This paper proposes an approach for constructing a k-edge connected neighborhood graph. The approach works by repeatedly extracting minimum spanning trees from the complete Euclidean graph of all data points. The constructed neighborhood graph has the following properties: (1) it is k-connected; (2) each point connects to its k-nearest neighbors; (3) if the graph is cut into two partitions, the cut edges contain k-shortest edges between the two partitions. Experiments show that the presented approach works well for clustered data and outperforms the nearest neighbor approaches used in Isomap for evenly distributed data.Keywords
This publication has 8 references indexed in Scilit:
- The Isomap Algorithm and Topological StabilityScience, 2002
- The Manifold Ways of PerceptionScience, 2000
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- Curvilinear component analysis: a self-organizing neural network for nonlinear mapping of data setsIEEE Transactions on Neural Networks, 1997
- A Nonlinear Mapping for Data Structure AnalysisIEEE Transactions on Computers, 1969
- Minimum Spanning Trees and Single Linkage Cluster AnalysisJournal of the Royal Statistical Society Series C: Applied Statistics, 1969
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman ProblemProceedings of the American Mathematical Society, 1956