A quasi-Bayesian perspective to online clustering

DOI10.1214/18-EJS1479zbMATH Open1404.62068arXiv1602.00522OpenAlexW3098553720WikidataQ129210066 ScholiaQ129210066MaRDI QIDQ1786586FDOQ1786586

Authors: Le Li, Benjamin Guedj, Sébastien Loustau 

Publication date: 24 September 2018

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: When faced with high frequency streams of data, clustering raises theoretical and algorithmic pitfalls. We introduce a new and adaptive online clustering algorithm relying on a quasi-Bayesian approach, with a dynamic (i.e., time-dependent) estimation of the (unknown and changing) number of clusters. We prove that our approach is supported by minimax regret bounds. We also provide an RJMCMC-flavored implementation (called PACBO, see https://cran.r-project.org/web/packages/PACBO/index.html) for which we give a convergence guarantee. Finally, numerical experiments illustrate the potential of our procedure.

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

Recommendations

• Weak convergence and optimal tuning of the reversible jump algorithm
• A fast and recursive algorithm for clustering large datasets with \(k\)-medians
• Reversible jump MCMC
• R package rjmcmc: reversible jump MCMC using post‐processing
• Model-based clustering of high-dimensional data streams with online mixture of probabilistic PCA
• Efficient Construction of Reversible Jump Markov Chain Monte Carlo Proposal Distributions
• An adaptive sequential Monte Carlo sampler
• A data-driven selection of the number of clusters in the Dirichlet allocation model via Bayesian mixture modelling
• Bayesian inference for continuous-time hidden Markov models with an unknown number of states

zbMATH Keywords

reversible jump Markov chain Monte Carloonline clusteringRJMCMCBayesian on-line clusteringminimax regret boundsPACBOprobability approximately correctquasi-Bayesian learning

Mathematics Subject Classification ID

Bayesian inference (62F15) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Monte Carlo methods (65C05) Learning and adaptive systems in artificial intelligence (68T05) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Estimating the number of clusters in a data set via the gap statistic
• Slope heuristics: overview and implementation
• Finding Groups in Data
• Title not available (Why is that?)
• Reversible jump Markov chain Monte Carlo computation and Bayesian model determination
• Fast learning rates in statistical inference through aggregation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Prediction, Learning, and Games
• Learning Theory
• Optimal learning with Bernstein online aggregation
• Title not available (Why is that?)
• Multivariate T-Distributions and Their Applications
• Harris recurrence of Metropolis-within-Gibbs and trans-dimensional Markov chains
• On Bayesian model and variable selection using MCMC
• I-divergence geometry of probability distributions and minimization problems
• The weighted majority algorithm
• PAC-Bayesian bounds for sparse regression estimation with exponential weights
• A Criterion for Determining the Number of Groups in a Data Set Using Sum-of-Squares Clustering
• Title not available (Why is that?)
• Statistical learning theory and stochastic optimization. Ecole d'Eté de Probabilitiés de Saint-Flour XXXI -- 2001.
• How to use expert advice
• On the number of groups in clustering
• PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification
• The minimax distortion redundancy in empirical quantizer design
• Exponentiated gradient versus gradient descent for linear predictors
• Analysis of two gradient-based algorithms for on-line regression
• Competitive On-line Statistics
• Relative loss bounds for on-line density estimation with the exponential family of distributions
• An algorithm for online \(k\)-means clustering
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Sparse regression learning by aggregation and Langevin Monte-Carlo
• Mirror averaging with sparsity priors
• Aggregation by Exponential Weighting and Sharp Oracle Inequalities
• Some PAC-Bayesian theorems
• Sparse single-index model
• PAC-Bayesian high dimensional bipartite ranking
• PAC-Bayesian estimation and prediction in sparse additive models
• An oracle inequality for quasi-Bayesian nonnegative matrix factorization
• An MCMC model search algorithm for regression problems

Cited In (4)

• PACBO
• Strategies for online inference of model-based clustering in large and growing networks
• SAKM: self-adaptive kernel machine. A kernel-based algorithm for online clustering
• Online model-based clustering for crisis identification in distributed computing

Uses Software

• R
• CAPUSHE
• bridgesampling
• rjmcmc
• clusfind

This page was built for publication: A quasi-Bayesian perspective to online clustering

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