Clustering spectral : marcher sur les observations pour les regrouper (travail conjoint avec Bruno Pelletier)

Le but de cet exposé est de présenter un résultat de consistance d'un algorithme permettant de regrouper des observations vectorielles en fonction de leur similarité.

Comme Hartigan, nous proposons de regrouper les observations suivant les l composantes connexes d'un ensemble de niveau t de la densité. Nous adaptons l'algorithme de clustering spectral de Ng, Jordan et Weiss de la façon suivante. Nous commençons par extraire de l'échantillon les observations de l'ensemble de niveau t d'une estimation de la densité. Puis, nous définissons une marche au hasard symétrique sur ces observations. La probabilité de transition d'une observation extraite à une autre est proportionnelle à une fonction (à support compact) de la distance entre ces deux observations. On injecte alors les observations dans le sous-espace des l premiers vecteurs propres de la matrice de transition. Et on applique un algorithme de clustering simple, par exemple, un k-means, pour séparer les observations extraites.

En particulier, nous montrons le résultat de consistance suivant. Lorsque le nombre d'observations tend vers l'infini, la marche au hasard définie ci-dessus, converge en un certain sens vers une chaîne de Markov sur l'ensemble de niveau t de la densité des observations. Les fonctions harmoniques de cette chaîne sont les fonctions constantes sur les composantes connexes de l'ensemble de niveau. Un argument de continuité (en fonction de l'opérateur) d'un système isolé de valeurs propres d'un opérateur borné permet de conclure que l'algorithme est consistant.

J.A. Hartigan, Clustering Algorithms. Wiley, 1975

A. Ng, M. Jordan and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processins Systems. MIT Press 2002.