Total Jensen divergences: Definition, Properties and k-Means++ Clustering

Abstract

We present a novel class of divergences induced by a smooth convex function called total Jensen divergences. Those total Jensen divergences are invariant by construction to rotations, a feature yielding regularization of ordinary Jensen divergences by a conformal factor. We analyze the relationships between this novel class of total Jensen divergences and the recently introduced total Bregman divergences. We then proceed by defining the total Jensen centroids as average distortion minimizers, and study their robustness performance to outliers. Finally, we prove that the k-means++ initialization that bypasses explicit centroid computations is good enough in practice to guarantee probabilistically a constant approximation factor to the optimal k-means clustering.

27 pages

References in corpus (3)

• The Burbea-Rao and Bhattacharyya centroids
• Total Jensen divergences: Definition, Properties and k-Means++ Clustering
• On conformal divergences and their population minimizers

Cited by in corpus (11)

• On a generalization of the Jensen-Shannon divergence and the JS-symmetrization of distances relying on abstract means
• An elementary introduction to information geometry
• On a generalization of the Jensen-Shannon divergence
• Total Jensen divergences: Definition, Properties and k-Means++ Clustering
• On Hölder projective divergences
• Singapore Soundscape Site Selection Survey (S5): Identification of Characteristic Soundscapes of Singapore via Weighted k-means Clustering
• k-variates++: more pluses in the k-means++
• The α-divergences associated with a pair of strictly comparable quasi-arithmetic means
• A note on the quasiconvex Jensen divergences and the quasiconvex Bregman divergences derived thereof
• On Voronoi diagrams and dual Delaunay complexes on the information-geometric Cauchy manifolds
• Logarithmic divergences: geometry and interpretation of curvature