### G-96-02

# Minimum Sum of Squares Clustering in a Low Dimensional Space

## Pierre Hansen, Brigitte Jaumard, and Nenad Mladenović

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* (*N*^{p+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.

Published **January 1996**
,
24 pages

This cahier was revised in **December 1996**