Groupe d’études et de recherche en analyse des décisions

G-96-02

Minimum Sum of Squares Clustering in a Low Dimensional Space

, et

Clustering with a criterion which minimizes the sum of squared distances to cluster centroids is usually done in a heuristic way. An exact polynomial algorithm, with a complexity in O (Np+1 log N), is proposed for minimum sum of squares hierarchical divisive clustering of points in a p-dimensional space with small p. Empirical complexity is one order of magnitude lower. Data sets with N = 20000 for p = 2, N = 1000 for p = 3, and N = 200 for p = 4 are clustered in a reasonable computing time.

, 24 pages

Ce cahier a été révisé en décembre 1996