Title :
Building k-connected neighborhood graphs for isometric data embedding
Author_Institution :
Dept. of Comput. Sci., Western Michigan Univ., Kalamazoo, MI, USA
fDate :
5/1/2006 12:00:00 AM
Abstract :
Isometric data embedding using geodesic distance requires the construction of a connected neighborhood graph so that the geodesic distance between every pair of data points can be estimated. This paper proposes an approach for constructing k-connected neighborhood graphs. The approach works by applying a greedy algorithm to add each edge, in a nondecreasing order of edge length, to a neighborhood graph if end vertices of the edge are not yet k-connected on the graph. The k-connectedness between vertices is tested using a network flow technique by assigning every vertex a unit flow capacity. This approach is applicable to a wide range of data. Experiments show that it gives better estimation of geodesic distances than other approaches, especially when the data are undersampled or nonuniformly distributed.
Keywords :
data handling; graph theory; greedy algorithms; pattern recognition; geodesic distance; greedy algorithm; isometric data embedding; k-connected neighborhood graphs; network flow technique; unit flow capacity; Buildings; Data mining; Greedy algorithms; Indexing; Information processing; Level measurement; Multidimensional systems; Nearest neighbor searches; Pattern analysis; Testing; Data embedding; graph connectivity; manifold learning; network flow.; Algorithms; Artificial Intelligence; Databases, Factual; Information Storage and Retrieval;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
DOI :
10.1109/TPAMI.2006.89