Consistent Algorithms for Clustering Time Series

Abstract : The problem of clustering is considered for the case where every point is a time series. The time series are either given in one batch (offline setting), or they are allowed to grow with time and new time series can be added along the way (online setting). We propose a natural notion of consistency for this problem, and show that there are simple, com-putationally efficient algorithms that are asymptotically consistent under extremely weak assumptions on the distributions that generate the data. The notion of consistency is as follows. A clustering algorithm is called consistent if it places two time series into the same cluster if and only if the distribution that generates them is the same. In the considered framework the time series are allowed to be highly dependent, and the dependence can have arbitrary form. If the number of clusters is known, the only assumption we make is that the (marginal) distribution of each time series is stationary ergodic. No paramet-ric, memory or mixing assumptions are made. When the number of clusters is unknown, stronger assumptions are provably necessary, but it is still possible to devise nonparametric algorithms that are consistent under very general conditions. The theoretical findings of this work are illustrated with experiments on both synthetic and real data.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2016, 17 (3), pp.1 - 32
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01399613
Contributeur : Daniil Ryabko <>
Soumis le : samedi 19 novembre 2016 - 21:37:12
Dernière modification le : mercredi 25 avril 2018 - 15:42:32

Fichier

khaleghi16a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01399613, version 1

Collections

Citation

Azadeh Khaleghi, Daniil Ryabko, Jérémie Mary, Philippe Preux. Consistent Algorithms for Clustering Time Series. Journal of Machine Learning Research, Journal of Machine Learning Research, 2016, 17 (3), pp.1 - 32. 〈hal-01399613〉

Partager

Métriques

Consultations de la notice

307

Téléchargements de fichiers

95