The X-Alter algorithm : a parameter-free method to perform clustering

Thomas Laloë (1) , Rémi Servien (2)

1 JAD - Laboratoire Jean Alexandre Dieudonné
2 MISTEA - Mathématiques, Informatique et STatistique pour l'Environnement et l'Agronomie

Using quantization techniques, Laloë (2009) defined a new algorithm called Alter. This $L^1$-based algorithm is proved to be convergent, but suffers two shortcomings. Firstly the number of clusters $K$ has to be supplied by the user. Secondly it has an high complexity. In this article, we adapt the idea of $X$-means algorithm (Pelleg and Moore; 2000) to offer solutions for these problems. This fast algorithm is used as a building-block which quickly estimates $K$ by optimizing locally the Bayesian Information Criterion (BIC). Our algorithm combines advantages of $X$-means (calculation of $K$ and speed) and Alter (convergence and parameter-free). Finally, an aggregative step is performed to adjust the relevance of the final clustering according to BIC criterion. We confront here our algorithm to different simulated data sets, which show its relevance.

Mots clés: Free-parameter algorithm; Clustering; Quantization; K-means; Free-parameter algorithm .

Domaines: Statistiques [math.ST]; Théorie [stat.TH]

Thomas Laloë, Rémi Servien. The X-Alter algorithm : a parameter-free method to perform clustering. 2011. ⟨hal-00674407v2⟩