Clustering en ligne : le point de vue PAC-bayésien

Abstract

Nous nous intéressons dans ce travail à la construction et à la mise en oeuvre d'une méthode de clustering en ligne. Face à des flux de données massives, le clustering est une gageure tant d'un point de vue théorique qu'algorithmique. Nous proposons un nouvel algorithme de clustering en ligne, reposant sur l'approche PAC-bayésienne. En particulier, le nombre de clusters est estimé dynamiquement (c'est-à-dire qu'il peut changer au cours du temps), et nous démontrons des bornes de regret parcimonieuses. De plus, un algorithme via RJMCMC, appelé Paco est présenté, et ses performances sur données simulées seront commentées. Mots-clés. Bornes de regret parcimonieuses, Clustering en ligne, Reversible Jump MCMC, Théorie PAC-bayésienne. Abstract. We address the online clustering problem. When faced with high frequency streams of data, clustering raises theoretical and algorithmic pitfalls. Working under a sparsity assumption, a new online clustering algorithm is introduced. Our procedure relies on the PAC-Bayesian approach, allowing for a dynamic (i.e., time-dependent) estimation of the number of clusters. Its theoretical merits are supported by sparsity regret bounds, and an RJMCMC-flavored implementation called Paco is proposed along with numerical experiments to assess its potential.