nips nips2003 nips2003-46 nips2003-46-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Bernd Fischer, Volker Roth, Joachim M. Buhmann
Abstract: Clustering aims at extracting hidden structure in dataset. While the problem of finding compact clusters has been widely studied in the literature, extracting arbitrarily formed elongated structures is considered a much harder problem. In this paper we present a novel clustering algorithm which tackles the problem by a two step procedure: first the data are transformed in such a way that elongated structures become compact ones. In a second step, these new objects are clustered by optimizing a compactness-based criterion. The advantages of the method over related approaches are threefold: (i) robustness properties of compactness-based criteria naturally transfer to the problem of extracting elongated structures, leading to a model which is highly robust against outlier objects; (ii) the transformed distances induce a Mercer kernel which allows us to formulate a polynomial approximation scheme to the generally N Phard clustering problem; (iii) the new method does not contain free kernel parameters in contrast to methods like spectral clustering or mean-shift clustering. 1
[1] P. Brucker. On the complexity of clustering problems. Optimization and Operations Research, pages 45–54, 1977.
[2] D. Comaniciu. An algorithm for data-driven bandwidth selection. IEEE T-PAMI, 25(2):281– 288, 2003.
[3] D. Comaniciu and P. Meer. Mean shift: A robust approach toward feature space analysis. IEEE T-PAMI, 24(5):603–619, 2002.
[4] M. Deza and M. Laurent. Applications of cut polyhedra. J. Comp. Appl. Math., 55:191–247, 1994.
[5] P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay. Clustering on large graphs and matrices. In Proc. of the ACM-SIAM Symp. on Discrete Algorithm., pages 291–299, 1999.
[6] R. Duda, P. Hart, and D. Stork. Pattern Classification. Wiley & Sons, 2001.
[7] B. Fischer and J.M. Buhmann. Path-based clustering for grouping of smooth curves and texture segmentation. IEEE T-PAMI, 25(4):513–518, 2003.
[8] M. Inaba, N. Katoh, and H. Imai. Applications of weighted voronoi diagrams and randomization to variance-based k-clustering. In 10th ACM Sympos. Computat. Geom., pages 332–339, 1994.
[9] A. Jain and R. Dubes. Algorithms for Clustering Data. Prentice Hall, 1988.
[10] A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, volume 14, pages 849–856, 2002.
[11] R. Ostrovsky and Y. Rabani. Polynomial time approximation schemes for geometric min-sum median clustering. Journal of the ACM, 49(2):139–156, 2002.
[12] J. Puzicha, T. Hofmann, and J.M. Buhmann. A theory of proximity based clustering: Structure detection by optimization. Pattern Recognition, 2000. ¨
[13] V. Roth, J. Laub, J.M. Buhmann, and K.-R. Muller. Going metric: Denoising pairwise data. In NIPS, volume 15, 2003. to appear.
[14] B. Sch¨ lkopf, A. Smola, and K.-R. M¨ ller. Nonlinear component analysis as a kernel eigenvalue o u problem. Neural Computation, 10:1299–1319, 1998.
[15] G. Young and A. S. Householder. Discussion of a set of points in terms of their mutual distances. Psychometrica, 3:19–22, 1938.