Contributions à l’étude de la classification spectrale et applications

Classification spectrale : algorithme et étude du paramètre

Ce chapitre s’intéresse à la méthode de classification spectrale (ou clustering spectral) et à sa mise en oeuvre. Comme cette méthode repose sur la seule mesure d’affinité entre tous les couples de points, sans a priori sur les formes des classes (ou clusters), nous étudierons plus particulièrement, après une présentation de l’algorithme, le paramètre de l’affinité gaussienne. En effet, son rôle est crucial dans le partitionnement des données et il n’existe pas a priori de moyen pour définir un paramètre optimal, mais un ordre de grandeur peut être accessible. On propose donc deux heuristiques qui seront confrontées aux résultats théoriques dans le chapitre suivant. Dans un premier temps, les diverses définitions, globales et locales, basées sur des interprétations physiques seront présentées. Ensuite nous proposerons une heuristique basée sur un point de vue géométrique et nous introduirons une mesure de qualité pour étudier l’influence de ce paramètre sur les résultats de classification (ou clustering). 

Présentation de la classification spectrale 

Dans la suite, nous présentons un algorithme de spectral clustering et le choix du paramètre de l’affinité gaussienne sera étudié. 

Algorithme de classification spectrale 

La méthode de clustering spectral consiste à extraire les vecteurs propres associés aux plus grandes valeurs propres d’une matrice affinité normalisée, issue d’un noyau de Mercer. Ces vecteurs propres constituent un espace de dimension réduite dans lequel les données transformées seront linéairement séparables. Deux principales classes d’algorithmes de clustering spectral ont été développées à partir de partitionnement de graphes . La première est fondée sur un partitionnement bipartite récursif à partir du vecteur propre associé à la seconde plus grande valeur propre du graphe du Laplacien normalisé, ou vecteur de Fiedler dans le cas non-normalisé. La deuxième classe d’algorithmes n’utilise pas de manière récursive un seul vecteur propre mais propose de projeter les données originales dans un espace défini par les k plus grands vecteurs propres d’une matrice d’adjacence normalisée (ou matrice similaire à celle-ci), et d’appliquer un algorithme standard comme k-means sur ces nouvelles coordonnées [84, 79]. Nous porterons l’étude principalement sur cette dernière classe dans un souci de coût numérique et de simplicité algorithmique. Y.Weiss et al (NJW) présentent cette dernière classe d’algorithmes (c.f. Algorithme 1) pour partitionner un ensemble de points S = {x1, …, xN } ⊂ R p en k clusters où k est fixé. NJW justifient 9 10 Classification spectrale : algorithme et étude du paramètre cet algorithme en considérant un cas idéal avec 3 clusters bien séparés. En partant de l’hypothèse que les points sont déjà ordonnés consécutivement par classe, la matrice affinité bien que dense, a alors une structure numérique proche de celle d’une matrice bloc-diagonale. Ainsi, la plus grande valeur propre de la matrice affinité normalisée est 1 avec un ordre de multiplicité égal à 3. Les lignes normalisées de la matrice constituée des vecteurs propres associés aux plus grandes valeurs propres sont constantes par morceaux. Dans l’espace défini par les k = 3 plus grands vecteurs propres de L, il est facile d’identifier 3 points bien séparés qui correspondent aux 3 constantes par morceaux des vecteurs propres, ce qui définit les clusters. Un exemple de cas idéal est illustré sur la figure 1.1, où les différentes étapes de l’algorithme de clustering spectral sont représentées.

 Problème du choix du paramètre 

Dans l’algorithme 1, la matrice d’affinité A ∈ MN,N (R), Aij désignant l’affinité entre les objets xi et xj , possède les propriétés suivantes : ( ∀ (i, j), Aij = Aji, ∀ (i, j), 0 ≤ Aij ≤ 1. Parmi les noyaux de Mercer [7, 58], le noyau Gaussien est le plus communément choisi. L’affinité entre deux points distincts xi et xj de R p est alors définie par : Aij = ( exp(− kxi − xjk 2 2 /2σ 2 ) si i 6= j, 0 sinon, (1.1) où σ est un paramètre et k.k2 est la norme euclidienne usuelle. L’expression de l’affinité gaussienne dépend donc d’un paramètre σ. Or, le principe du clustering spectral reposant sur la mesure d’affinité, ce paramètre influe directement sur la méthode. En effet, σ influe sur la séparabilité des données dans l’espace de projection spectrale (spectral embedding) comme indiqué dans l’exemple géométrique des figures 1.2 (a) et (b). L’espace de projection spectrale est tracé pour deux valeurs différentes de σ. Pour la première valeur σ = 0.09, les points projetés dans l’espace spectral forment deux paquets compacts où les points projetés associés au même cluster sont concentrés autour d’un seul et même point alors que, pour σ = 0.8, les points projetés dans cet espace décrivent un arc de cercle et aucune séparation ou agglomération de points ne sont distinguées. Dans ce cas, la méthode de k-means classique échoue et les clusters sont difficiles à déterminer. Il s’en suit les clusterings respectifs des figures 1.2 (c) et (d). Donc un mauvais choix de σ a des répercutions sur la séparabilité des clusters dans l’espace propre. En segmentation d’images , ce paramètre est souvent laissé libre et doit être fixé par les utilisateurs. Cependant, plusieurs interprétations sur le rôle de ce paramètre ont été développées afin de guider le choix de manière automatique ou semi-automatique. Les principales méthodes sont les suivantes. Seuillage Une première approche repose sur l’idée de seuillage via une analyse descriptive des données ou bien via la théorie des graphes . En effet, Perona et Freeman définissent σ comme une distance seuil en dessous de laquelle deux points sont considérés comme similaires et au-dessus de laquelle ils sont dissemblables. Von luxburg interprète σ comme le rayon du voisinage. Il joue donc un rôle équivalent à celui du ǫ, distance de voisinage pour la méthode graphe à ǫ-voisinage. Ces interprétations donnent des informations sur le rôle que joue le paramètre σ. Cependant, le choix du seuil reste ouvert et non automatisable. Approche globale Une seconde approche repose sur des définitions globales de ce paramètre, principalement basées sur l’analyse descriptive des données et des interprétations physiques. D’après Ng, Jordan, 

Problème du choix du paramètre 

Weiss [84], σ contrôle la similarité entre les données et conditionne la qualité des résultats. Ainsi, parmi les différentes valeurs de σ, on sélectionne celle qui minimise la dispersion des points d’un même cluster dans l’espace propre réduit. Cette sélection peut être implémentée automatiquement de manière non supervisée en considérant la dispersion des projections dans l’espace propre comme indicateur. Ce choix peut être défini à l’aide d’un histogramme sur les normes kxi − xjk2 entre tous les points xi , xj , pour tout i, j ∈ {1, .., N}. En supposant l’existence de clusters, l’histogramme deviendra multi-modal : le premier mode correspondra à la moyenne intra-cluster et les suivants représenteront les distances entre les clusters. Sélectionner un σ de l’ordre du premier mode de l’histogramme revient donc à privilégier les affinités au sein des clusters et donc la structure blocdiagonale de la matrice affinité. Brand et Huang [20] définissent un paramètre scalaire global semblable à l’heuristique sur les histogrammes. En effet, σ doit être égal à la moyenne de la distance entre chaque point de l’ensemble S et son plus proche voisin. Cette heuristique est testée sur divers exemples géométriques 2D aux densités variées et les résultats du clustering sont représentés sur la figure 1.3. Sur certains exemples, cette estimation peut s’avérer insuffisante notamment lorsque les densités au sein même d’un cluster varient comme pour les exemples (b) et (e) de la figure 1.3. De plus, cette définition requiert de faire une boucle sur tous les points xi ∈ S pour résoudre min j kxi − xjk2, pour tout i ∈ {1, .., N}, ce qui peut être coûteux numériquement dans le cas d’un nombre important de données xj en particulier.