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