Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Le Li 1, * Benjamin Guedj 2 Sébastien Loustau 1
* Corresponding author
2 MODAL - MOdel for Data Analysis and Learning
Inria Lille - Nord Europe, LPP - Laboratoire Paul Painlevé - UMR 8524, METRICS - Evaluation des technologies de santé et des pratiques médicales - ULR 2694, Polytech Lille - École polytechnique universitaire de Lille, Université de Lille, Sciences et Technologies
Résumé : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-01264934
Contributor : Le Li <>
Submitted on : Friday, January 29, 2016 - 8:07:48 PM
Last modification on : Friday, November 27, 2020 - 2:18:02 PM
Long-term archiving on: : Friday, November 11, 2016 - 9:40:04 PM

File

Online_Clustering___JdS_2016 (...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01264934, version 1

Collections

Citation

Le Li, Benjamin Guedj, Sébastien Loustau. Clustering en ligne : le point de vue PAC-bayésien. 2016. ⟨hal-01264934⟩

Share

Metrics

Record views

323

Files downloads

766