Paper abstract

Mixed Bregman Clustering with Approximation Guarantees

Richard Nock - CEREGMIA-Universite Antilles-Guyane, France
Panu Luosto - University of Helsinki, Finland
Jyrki Kivinen - University of Helsinki, Finland

Session: Clustering 2
Springer Link:

Two recent breakthroughs have dramatically improved the scope and performance of k-means clustering: squared Euclidean seeding for the initialization step, and Bregman clustering for the iterative step. In this paper, we first unite the two frameworks by generalizing the former improvement to Bregman seeding - a biased randomized seeding technique using Bregman divergences - while generalizing its important theoretical approximation guarantees as well. We end up with a complete Bregman hard clustering algorithm integrating the distortion at hand in both the initialization and iterative steps. Our second contribution is to further generalize this algorithm to handle mixed Bregman distortions, which smooth out the asymetricity of Bregman divergences. In contrast to some other symmetrization approaches, our approach keeps the algorithm simple and allows us to generalize theoretical guarantees from regular Bregman clustering.