A quasi-Bayesian perspective to online clustering (Q1786586)

The subject of the paper is an analysis of clustering algorithms for a high frequency stream of data. A new adaptive online clustering algorithm relying on a quasi-Bayesian approach, with a dynamic estimation of the (unknown and changing) number of clusters is proposed. The resulting clusters are time-dependent. It is proved that the proposed approach is supported by minimax regret bounds. Based on reasoning similar to the one that led to the creation of a reversible-jump MCMC algorithm (cf. \textit{P. J. Green} [Biometrika 82, No. 4, 711--732 (1995; Zbl 0861.62023)], \textit{Q. F. Gronau}, \textit{H. Singmann} and \textit{E. Wagenmakers} [``bridgesampling: an R package for estimating normalizing constants'', \url{https://doi.org/10.31222/osf.io/v94h6} (2017)] and see the RJMCMC software \url{https://swmath.org/software/21805}) an implementation (called PACBO -- Probability Approximately Correct Bayesian On-line Clustering, cf. [\textit{D. McAllester} and \textit{T. Akinbiyi}, in: Empirical inference. Festschrift in honor of Vladimir N. Vapnik. Berlin: Springer. 95--103 (2013; Zbl 1325.62100)]) is proposed for which a convergence is a guarantee. Numerical experiments illustrate the potential of the procedure. Software: PACBO (see \url{https://cran.r-project.org/web/packages/PACBO/index.html}; \url{https://swmath.org/software/15756}), RJMCMC (see \url{https://swmath.org/software/21805}).