Robust Bregman clustering

DOI10.1214/20-AOS2018MaRDI QIDQ820825zbMATH OpenFDO

Authors Claire Brécheteau, Aurélie Fischer, Clément Levrard

Publication date 28 September 2021

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.04356

zbMATH Keywords

Bregman divergenceclusteringrobustness

Mathematics Subject Classification ID

Nonparametric robustness (62G35) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: 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.

Recommendations

• Clustering with Bregman divergences.
• A general trimming approach to robust cluster analysis
• Trimming algorithms for clustering contaminated grouped data and their robustness
• Bregman bubble clustering: a robust framework for mining dense clusters
• Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences

Cites work

• 10.1162/153244303321897735
• A general trimming approach to robust cluster analysis
• A note on the breakdown point of the least median of squares and least trimmed squares estimators
• Best approximations to random variables based on trimming procedures
• Clustering with Bregman divergences.
• Convex Analysis
• Distortion measures for speech processing
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm
• Empirical risk minimization for heavy-tailed losses
• Geometric inference for probability measures
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 3829050 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• Least squares quantization in PCM
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• On Bregman Voronoi diagrams
• On the Optimality of Conditional Expectation as a Bregman Predictor
• On the Performance of Clustering in Hilbert Spaces
• Pattern classification.
• Persistence-based clustering in Riemannian manifolds
• Prediction, Learning, and Games
• Quantization and clustering with Bregman divergences
• Quantization/clustering: when and why does k-means work?
• Robust machine learning by median-of-means: theory and practice
• Robust Statistics
• Trimmed \(k\)-means: An attempt to robustify quantizers

Cited in

(6)

• Robust \(k\)-means clustering for distributions with two moments
• Bregman bubble clustering: a robust framework for mining dense clusters
• Clustering with Bregman divergences.
• ROBP a robust border-peeling clustering using Cauchy kernel
• Topics in robust statistical learning
• Consistency and inconsistency in k-means clustering

Describes a project that uses

Uses Software

• dbscan
• k-means++
• robustbase
• TCLUST

This page was built for publication: Robust Bregman clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820825)