Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Normalized Cuts is a state-of-the-art spectral method for clustering. By applying spectral techniques, the data becomes easier to cluster and then k-means is classically used. Unfortunately the number of clusters must be manually set and it is very sensitive to initialization. Moreover, k-means tends to split large clusters, to merge small clusters, and to favor convex-shaped clusters. In this work we present a new clustering method which is parameterless, independent from the original data dimensionality and from the shape of the clusters. It only takes into account inter-point distances and it has no random steps. The combination of the proposed method with normalized cuts proved successful in our experiments. © 2011 Elsevier Ltd. All rights reserved.

Registro:

Documento: Artículo
Título:Automatically finding clusters in normalized cuts
Autor:Tepper, M.; Musé, P.; Almansa, A.; Mejail, M.
Filiación:Departmento de Computación, FCEN, Universidad de Buenos Aires, Argentina
Instituto de Ingeniera Elctrica, FI, Universidad de la Repblica, Uruguay
CNRS LTCI, Telecom ParisTech, France
Palabras clave:A contrario detection; Clustering; Normalized cuts; A contrario detection; Clustering; Clustering methods; Data dimensionality; K-means; Large clusters; Normalized cuts; Number of clusters; Small clusters; Spectral methods; Spectral techniques; Spectroscopy
Año:2011
Volumen:44
Número:7
Página de inicio:1372
Página de fin:1386
DOI: http://dx.doi.org/10.1016/j.patcog.2011.01.003
Título revista:Pattern Recognition
Título revista abreviado:Pattern Recogn.
ISSN:00313203
CODEN:PTNRA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00313203_v44_n7_p1372_Tepper

Referencias:

  • Ng, A., Jordan, M., Weiss, Y., On spectral clustering: Analysis and an algorithm (2001) Advances in Neural Information Processing Systems, pp. 849-856
  • Comaniciu, D., Meer, P., Mean shift: A robust approach toward feature space analysis (2002) IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (5), pp. 603-619. , DOI 10.1109/34.1000236
  • Felzenszwalb, P., Huttenlocher, D., Efficient graph-based image segmentation (2004) Int. J. Comput. Vision, 59, pp. 167-181
  • Leibe, B., Mikolajczyk, K., Schiele, B., Efficient clustering and matching for object class recognition (2006) Proceedings of the British Machine Vision Conference
  • Cao, F., Delon, J., Desolneux, A., Muse, P., Sur, F., A unified framework for detecting groups and application to shape recognition (2007) Journal of Mathematical Imaging and Vision, 27 (2), pp. 91-119. , DOI 10.1007/s10851-006-9176-0
  • Dhillon, I.S., Guan, Y., Kulis, B., Weighted graph cuts without eigenvectors a multilevel approach (2007) IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (11), pp. 1944-1957. , DOI 10.1109/TPAMI.2007.1115
  • Flake, G., Tarjan, R., Tsioutsiouliklis, K., Graph clustering and minimum cut trees (2004) Internet Math., 1, pp. 385-408
  • Kannan, R., Vempala, S., Vetta, A., On clusterings: Good, bad and spectral (2004) J. ACM, 51, pp. 497-515
  • Kleinberg, J., An impossibility theorem for clustering (2002) Advances in Neural Information Processing Systems, pp. 446-453
  • Jain, A.K., Data clustering: 50 years beyond k-means (2010) Pattern Recognition Lett., 31, pp. 651-666
  • Bandyopadhyay, S., An automatic shape independent clustering technique (2004) Pattern Recognition, 37 (1), pp. 33-45. , DOI 10.1016/S0031-3203(03)00235-8
  • Fowlkes, C., Belongie, S., Chung, F., Malik, J., Spectral grouping using the Nystrm method (2004) IEEE Trans. Pattern Anal. Mach. Intell., 26, pp. 214-225
  • Shi, J., Malik, J., Normalized cuts and image segmentation (2000) IEEE Trans. Pattern Anal. Mach. Intell., 22, pp. 888-905
  • Zahn, C.T., Graph-theoretical methods for detecting and describing gestalt clusters (1971) Trans. Comput., C-20, pp. 68-86
  • Wertheimer, M., Laws of Organization in Perceptual Forms, pp. 71-88. , Routledge and Kegan Paul
  • Desolneux, A., Moisan, L., Morel, J.-M., Edge detection by Helmholtz principle (2001) Journal of Mathematical Imaging and Vision, 14 (3), pp. 271-284. , DOI 10.1023/A:1011290230196
  • Chung, F., (1997) Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92), , American Mathematical Society
  • Von Luxburg, U., Belkin, M., Bousquet, O., Consistency of spectral clustering (2008) Ann. Statist., 36, pp. 555-586
  • Burnham, K., Anderson, D., (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, , second ed. Springer
  • Barron, A., Rissanen, J., Yu, B., The Minimum Description Length Principle in Coding and Modeling (1998) IEEE Transactions on Information Theory, 44 (6), pp. 2743-2760. , PII S0018944898052845
  • Nadler, B., Galun, M., Fundamental limitations of spectral clustering (2007) Advances in Neural Information Processing Systems, 19, pp. 1017-1024
  • Ozertem, U., Erdogmus, D., Jenssen, R., Mean shift spectral clustering (2008) Pattern Recognition, 41 (6), pp. 1924-1938. , DOI 10.1016/j.patcog.2007.09.009, PII S0031320307004153
  • Desolneux, A., Moisan, L., Morel, J.M., (2008) From Gestalt Theory to Image Analysis, 34. , Springer-Verlag
  • Fukunaga, K., (1999) Introduction to Statistical Pattern Recognition, , second ed. Academic Press
  • Hoffman, R., Jain, A.K., A test of randomness based on the minimal spanning tree (1983) Pattern Recognition Lett., 1, pp. 175-180
  • Jain, A.K., Xiaowei, X., Tin, K.H., Fan, X., Uniformity testing using minimal spanning tree (2002) Proceedings - International Conference on Pattern Recognition, 16 (4), pp. 281-284
  • Zelnik-Manor, L., Perona, P., Self-tuning spectral clustering (2004) Advances in Neural Information Processing Systems, 17, pp. 1601-1608. , MIT Press
  • Burrus, N., Bernard, T.M., Jolion, J.M., Image segmentation by a contrario simulation (2009) Pattern Recognition, 42, pp. 1520-1532
  • Fukunaga, K., Hostetler, L., The estimation of the gradient of a density function, with applications in pattern recognition (2003) IEEE Trans. Inf. Theory, 21, pp. 32-40
  • Martin, D., Fowlkes, C., Tal, D., Malik, J., A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics (2001) Proceedings of the IEEE International Conference on Computer Vision, 2, pp. 416-423
  • Cour, T., Benezit, F., Shi, J., Spectral segmentation with multiscale graph decomposition (2005) Proceedings of the IEEE International Conference on Comput Vision and Pattern Recognition, 2, pp. 1124-1131. , Washington, DC, USA
  • Yu, S., Shi, J., Multiclass spectral clustering (2003) Proceedings of the IEEE International Conference on Comput Vision, 1, pp. 313-319
  • Tarjan Robert, E., Van Leeuwen, J., Worst-case analysis of set union algorithms (1984) Journal of the ACM, 31 (2), pp. 245-281. , DOI 10.1145/62.2160
  • Press, W., Teukolsky, S., Vetterling, W., Flannery, B., (1992) Numerical Recipes in C, , second ed. Cambridge University Press Cambridge, UK

Citas:

---------- APA ----------
Tepper, M., Musé, P., Almansa, A. & Mejail, M. (2011) . Automatically finding clusters in normalized cuts. Pattern Recognition, 44(7), 1372-1386.
http://dx.doi.org/10.1016/j.patcog.2011.01.003
---------- CHICAGO ----------
Tepper, M., Musé, P., Almansa, A., Mejail, M. "Automatically finding clusters in normalized cuts" . Pattern Recognition 44, no. 7 (2011) : 1372-1386.
http://dx.doi.org/10.1016/j.patcog.2011.01.003
---------- MLA ----------
Tepper, M., Musé, P., Almansa, A., Mejail, M. "Automatically finding clusters in normalized cuts" . Pattern Recognition, vol. 44, no. 7, 2011, pp. 1372-1386.
http://dx.doi.org/10.1016/j.patcog.2011.01.003
---------- VANCOUVER ----------
Tepper, M., Musé, P., Almansa, A., Mejail, M. Automatically finding clusters in normalized cuts. Pattern Recogn. 2011;44(7):1372-1386.
http://dx.doi.org/10.1016/j.patcog.2011.01.003