4.5 Clustering de données vectorielles
On dispose d’un tableau de données classique de taille \(n\times p\), i.e. \(n\) observations \(x_1,\dots,x_n\in \mathbb R^p\) de dimension \(p\). Le but est de faire de la classification non supervisée de cet ensemble de \(n\) points. Les techniques les plus classiquement utilisées sont le \(k\)-means ou la classification hiérarchique. Elles sont souvent fondées sur une notion de similarité \(s_{ij}\geq 0\) entre chaque paire d’observations \(x_i,x_j\), qui est inversement proportionnelle à la distance.
A partir d’une notion de similarité entre les vecteurs \(\{x_i\}_{i\le n}\), on peut définir un graphe \(G=(V,E)\) où
- l’ensemble des noeuds \(V=\{v_1,\dots,v_n\}\) représente les observations et
- \(e=\{v_i,v_j\}\) est une arête du graphe si p.ex. la similarité \(s_{ij}\) entre \(x_i,x_j\) dépasse un certain seuil. Le graphe \(G\) peut être binaire (\(s_{ij}\ge s \implies \{v_i,v_j\}\in E\) et \(s_{ij}<s \implies \{v_i,v_j\}\notin E\)) ou valué (\(s_{ij}\ge s \implies \{v_i,v_j\}\in E\) et l’arête porte la valeur \(s_{ij}\), sinon l’arête n’est pas présente).
Le problème de clustering des points \(x_1,\dots,x_n\) peut être reformulé comme un problème de partitionnement des noeuds du graphe de similarité où l’on cherche des groupes de noeuds tels que les connections intra-groupes sont importantes (les vecteurs qui correspondent aux noeuds du groupe sont très similaires entre eux) et tels que les connections inter-groupes sont faibles (peu de similarité entre les vecteurs qui correspondent à des noeuds de groupes différents).
On pourra alors utiliser le spectral clustering afin de calculer un clustering des noeuds du graphe de similarité, qui correspondra à un clustering des données vectorielles initiales.
4.5.1 Graphes de similarité
On considère un ensemble de \(n\) observations \(x_1,\dots,x_n\) avec \(x_i\in \mathbb R^p\). Pour quantifier la similarité entre deux observations, on utilise une mesure qui est inversement proportionnelle à la distance. La plus courante est la mesure de similarité gaussienne définit à travers les voisinages dans \(\mathbb R^p\) et donc la distance entre les points.
Nous définissons différents graphes de similarité \(G=(V,E)\) où l’ensemble de noeuds \(V=\{v_1,\dots, v_n\}\) représente les différentes observations \(x_1,\dots,x_n\).
Definition 4.8 (Graphe des \(k\) plus proches voisins) On commence par définir un graphe orienté \(\tilde G=(V,\tilde E)\) de manière suivante: Si \(x_j\) est l’un des \(k\) plus proches voisins de \(x_i\), i.e. \(s_{ij}\) est parmi les \(k\) plus grands éléments de \(\{s_{il} ; l \neq i\}\), alors on crée une arête orientée de \(v_i\) vers \(v_j\), i.e. \((v_i,v_j)\in \tilde E\). A partir de ce graphe orienté \(\tilde G\), on peut définir \(G=(V,E)\) non orienté de deux façons différentes:
- graphe des \(k\) plus proches voisins: Soit \(\{v_i,v_j\}\in E\) dès que \((v_i,v_j)\in \tilde E\) ou \((v_j,v_i)\in \tilde E\) ;
- graphe des \(k\) plus proches voisins mutuels: Soit \(\{v_i,v_j\}\in E\) dès que \((v_i,v_j)\in \tilde E\) et \((v_j,v_i)\in \tilde E\).
4.5.2 Commentaires pratiques
- Le choix de la fonction de similarité (quand on part de données non graphe) doit dépendre du type de données.
- Le choix du graphe de similarité entre les vecteurs \(x_i\) influe sur le résultat du clustering que l’on obtient sur les points. Mais on ne sait pas a priori quel choix est meilleur.
- Le graphe des \(k\) plus proches voisins est une sorte de compromis entre le graphe dense et le graphe de \(\varepsilon\)-voisinage: étape de seuillage qui réduit le bruit (comme pour le \(\varepsilon\)-voisinage) mais on garde les valeurs des arêtes \(s_{ij}\) les plus grandes (contrairement au \(\varepsilon\)-voisinage).
- Une différence importante entre le graphe d’\(\varepsilon\)-voisinage et les graphes des \(k\) plus proches voisins (simple ou mutuel) est l’adaptation locale du voisinage des seconds: les tailles de voisinage sont différentes en fonction des régions de l’espace (plus grandes dans les régions peu denses, plus petites dans les régions plus denses).
- Le graphe des \(k\) plus proches voisins mutuel tend à connecter entre eux des points dans des régions de densité constante (comme la version simple) mais ne connecte pas entre elles des régions proches mais de densité différente. En ce sens, c’est un compromis entre \(\varepsilon\)-voisinage et \(k\) plus proches voisins simple.
- Les graphes des \(k\) plus proches voisins sont plus faciles à manipuler que le graphe construit avec une similarité gaussienne (qui lui est dense). Il peuvent donc être préférables ; mais attention à la perte d’information: on peut par exemple avoir plus de composantes connexes dans ces graphes que de clusters désirés !
Recommandations empiriques pour le choix des paramètres
- prendre \(k\) de l’ordre de \(\log(n)\) pour le graphe des \(k\)-plus proches voisins simple et plus grand (sans règle explicite) pour le graphe des \(k\)-plus proches voisins mutuel. Il faut de toute façon regarder le nombre de composantes connexes obtenues, le comparer au nombre de clusters voulus et ajuster en conséquence.
- prendre \(\varepsilon\) tel que le graphe résultant soit connecté.
- pas de bonne règle pour le choix de \(\sigma\) dans la similarité gaussienne.