  Using a trimming approach, we investigate a k-means type method based on
Bregman divergences for clustering data possibly corrupted with clutter noise.
The main interest of Bregman divergences is that the standard Lloyd algorithm
adapts to these distortion measures, and they are well-suited for clustering
data sampled according to mixture models from exponential families. We prove
that there exists an optimal codebook, and that an empirically optimal codebook
converges a.s. to an optimal codebook in the distortion sense. Moreover, we
obtain the sub-Gaussian rate of convergence for k-means 1 $\sqrt$ n under mild
tail assumptions. Also, we derive a Lloyd-type algorithm with a trimming
parameter that can be selected from data according to some heuristic, and
present some experimental results.
