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

Nous nous interessons dans ce travail a la construction et a la mise en oeuvre d'une methode de clustering en ligne. Face a des flux de donnees massives, le clustering est une gageure tant d'un point de vue theorique qu'algorithmique. Nous proposons un nouvel algorithme de clustering en ligne, reposant sur l'approche PAC-bayesienne. En particulier, le nombre de clusters est estime dynamiquement (c'est-a-dire qu'il peut changer au cours du temps), et nous demontrons des bornes de regret parcimonieuses. De plus, un algorithme via RJMCMC, appele Paco est presente, et ses performances sur donnees simulees seront commentees. Mots-cles. Bornes de regret parcimonieuses, Clustering en ligne, Reversible Jump MCMC, Theorie PAC-bayesienne. 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.