Affiliations: [a] Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza L. da Vinci, 32, 20133, Milan, Italy. Tel.: +39 02 2399 3545; Fax: +39 02 2399 3412; E-mail: savaresi@elet.polimi.it | [b] Department of Computer Science and Engineering, University of Minnesota, 4-192 EE/CSci, 200 Union St SE, Minneapolis, MN 55455, USA. E-mail: boley@cs.umn.edu
Abstract: This paper deals with the problem of clustering a data set. In particular, the bisecting divisive partitioning approach is here considered. We focus on two algorithms: the celebrated K-means algorithm, and the recently proposed Principal Direction Divisive Partitioning (PDDP) algorithm. A comparison of the two algorithms is given, under the assumption that the data set is uniformly distributed within an ellipsoid. In particular, the dynamic behavior of the K-means iterative procedure is studied and discussed; for the 2-dimensional case a closed-form model is given.
Keywords: unsupervised clustering, K-means, principal direction divisive partitioning
