Clustering with Entropy-like k-means Algorithms

M. Teboulle, P. Berkhin, Inderjit Dhillon, Yuqiang Guan, J. Kogan

Abstract:   The aim of this chapter is to demonstrate that many results attributed to the classical k-means clustering algorithm with the squared Euclidean distance can be extended to many other distance-like functions. We focus on entropy-like distances based on Bregman [88] and Csiszar [119] divergences, which have previously been shown to be useful in various optimization and clustering contexts. Further, the chapter reviews various versions of the classical k-means and BIRCH clustering algorithms with squared Euclidean distance and considers modifications of these algorithms with the proposed families of distance-like functions. Numerical experiments with some of these modifications are reported.

Download: pdf


  • Clustering with Entropy-like k-means Algorithms (pdf, software)
    M. Teboulle, P. Berkhin, I. Dhillon, Y. Guan, J. Kogan.
    Grouping Multidimensional Data – Recent Advances in Clustering, pp. 127-160, January 2005.