# Worst-case and smoothed analysis of $k$-means clustering with Bregman divergences

Bodo Manthey, Heiko Röglin

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

## Abstract

The $k$-means algorithm is the method of choice for clustering large-scale data sets and it performs exceedingly well in practice. Most of the theoretical work is restricted to the case that squared Euclidean distances are used as similarity measure. In many applications, however, data is to be clustered with respect to other measures like, e.g., relative entropy, which is commonly used to cluster web pages. In this paper, we analyze the running-time of the $k$-means method for Bregman divergences, a very general class of similarity measures including squared Euclidean distances and relative entropy. We show that the exponential lower bound known for the Euclidean case carries over to almost every Bregman divergence. To narrow the gap between theory and practice, we also study $k$-means in the semi-random input model of smoothed analysis. For the case that $n$ data points in $\mathbb{R}^d$ are perturbed by noise with standard deviation $\sigma,$ we show that for almost arbitrary Bregman divergences the expected running-time is bounded by poly($n^{\sqrt k}, 1/\sigma$) and $k^{kd}$ poly($n, 1/\sigma$).
Original language Undefined Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009 Yingfei Dong, Dingzhu Du, Oscar Ibarra Berlin Springer 1024-1033 10 978-3-642-10630-9 https://doi.org/10.1007/978-3-642-10631-6_103 Published - 2009 20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, Hawaii, USADuration: 16 Dec 2009 → 18 Dec 2009

### Publication series

Name Lecture Notes in Computer Science Springer 5878

### Conference

Conference 20th International Symposium on Algorithms and Computation, ISAAC 2009 16/12/09 → 18/12/09 16-18 Dec 2009

## Keywords

• $k$-Means
• Bregman divergence
• IR-68761
• METIS-264223
• Relative entropy
• Kullback-Leibler divergence
• Itakura-Saito Divergence
• Generalized I-Divergence
• Clustering
• Mahalanobis Distance
• Machine Learning
• EWI-16970
• Smoothed Analysis