Automatically finding clusters in normalized cuts

Mariano Tepper (1) , Pablo Musé (2) , A. Almansa (3) , Marta Mejail (1)

1 Department of Computer Science [Buenos Aires]
2 UDELAR - Universidad de la República [Montevideo]
3 LTCI - Laboratoire Traitement et Communication de l'Information

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.

Keywords: Clustering; A contrario; Normalized cuts

Domains: Computer Science [cs]; Image Processing [eess.IV]

Mariano Tepper, Pablo Musé, A. Almansa, Marta Mejail. Automatically finding clusters in normalized cuts. Pattern Recognition, 2011, 44 (7), pp.1372-1386. ⟨10.1016/j.patcog.2011.01.003⟩. ⟨hal-00631620⟩