nips nips2004 nips2004-150 nips2004-150-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Richard S. Zemel, Miguel Á. Carreira-Perpiñán
Abstract: Many machine learning algorithms for clustering or dimensionality reduction take as input a cloud of points in Euclidean space, and construct a graph with the input data points as vertices. This graph is then partitioned (clustering) or used to redefine metric information (dimensionality reduction). There has been much recent work on new methods for graph-based clustering and dimensionality reduction, but not much on constructing the graph itself. Graphs typically used include the fullyconnected graph, a local fixed-grid graph (for image segmentation) or a nearest-neighbor graph. We suggest that the graph should adapt locally to the structure of the data. This can be achieved by a graph ensemble that combines multiple minimum spanning trees, each fit to a perturbed version of the data set. We show that such a graph ensemble usually produces a better representation of the data manifold than standard methods; and that it provides robustness to a subsequent clustering or dimensionality reduction algorithm based on the graph. 1
[1] Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Trans. on Pattern Anal. and Machine Intel., 15(11):1101–1113, November 1993.
[2] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Anal. and Machine Intel., 22(8):888–905, August 2000.
[3] Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Efficient graph-based image segmentation. Int. J. Computer Vision, 59(2):167–181, September 2004.
[4] Romer Rosales, Kannan Achan, and Brendan Frey. Learning to cluster using local neighborhood structure. In ICML, 2004.
[5] Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, December 22 2000.
[6] Sam T. Roweis and Lawrence K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, December 22 2000.
[7] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, June 2003.
[8] Kilian Q. Weinberger and Lawrence K. Saul. Unsupervised learning of image manifolds by semidefinite programming. In CVPR, 2004.
[9] Marcelo Blatt, Shai Wiseman, and Eytan Domany. Data clustering using a model granular magnet. Neural Computation, 9(8):1805–1842, November 1997.
[10] C. T. Zahn. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Trans. Computers, C–20(1):68–86, April 1971.
[11] Chakra Chennubhotla and Allan Jepson. EigenCuts: Half-lives of EigenFlows for spectral clustering. In NIPS, 2003.
[12] Christopher M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, New York, Oxford, 1995.
[13] Yoram Gdalyahu, Daphna Weinshall, and Michael Werman. Self organization in vision: Stochastic clustering for image segmentation, perceptual grouping, and image database organization. IEEE Trans. on Pattern Anal. and Machine Intel., 23(10):1053–1074, October 2001.