Clustering processes

Daniil Ryabko 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : The problem of clustering is considered, for the case when each data point is a sample generated by a stationary ergodic process. We propose a very natural asymptotic notion of consistency, and show that simple consistent algorithms exist, under most general non-parametric assumptions. The notion of consistency is as follows: two samples should be put into the same cluster if and only if they were generated by the same distribution. With this notion of consistency, clustering generalizes such classical statistical problems as homogeneity testing and process classification. We show that, for the case of a known number of clusters, consistency can be achieved under the only assumption that the joint distribution of the data is stationary ergodic (no parametric or Markovian assumptions, no assumptions of independence, neither between nor within the samples). If the number of clusters is unknown, consistency can be achieved under appropriate assumptions on the mixing rates of the processes. (again, no parametric or independence assumptions). In both cases we give examples of simple (at most quadratic in each argument) algorithms which are consistent.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00477238
Contributeur : Daniil Ryabko <>
Soumis le : mardi 4 mai 2010 - 16:08:18
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 30 septembre 2010 - 16:21:21

Fichiers

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

Identifiants

  • HAL Id : inria-00477238, version 2
  • ARXIV : 1005.0826

Collections

Citation

Daniil Ryabko. Clustering processes. 27th International Conference on Machine Learning, Jun 2010, Haifa, Israel. pp.919-926, 2010. 〈inria-00477238v2〉

Partager

Métriques

Consultations de la notice

231

Téléchargements de fichiers

146