Explorez vos données avec des algorithmes non supervisés

Dans le cas d'algorithmes non supervisés, le but de l'algorithme est moins évident à définir que dans le cas d'algorithmes supervisés, où il y a une tâche claire à accomplir. Le succès du modèle est donc plus subjectif. Le fait que la tâche soit plus difficile à définir n'empêche pas qu'il existe un large éventail de mesures de la performance d'un algorithme supervisé !

Distances et similarités

Faire un clustering, c'est regrouper ensemble les points les plus proches ou les plus semblables. Le concept de clustering repose fortement sur ceux de distance et de similarité.

Ces concepts vont nous être très utiles pour formaliser à quel point deux observations sont proches l'une de l'autre, à quel point une observation est proche d'un cluster, et à quel point deux clusters sont proches l'un de l'autre.

Une distance est formellement définie comme une fonction $\$\backslash (d:\; \backslash mathbb\{R\}^p\; \backslash rightarrow\; \backslash mathbb\{R\}\_+\backslash )\$$  , qui vérifie trois propriétés :

•  d(x,x)=0 (auto-similarité) ;

• d(u,v)=d(v,u) (symétrie) ;

• d(u,v) ≤ d(u,x)+d(x,v) (inégalité triangulaire).

Les exemples les plus utilisés de distances sont :

• la distance euclidienne :   $\$\backslash (d(u,v)=||u-v||\_2=\backslash sqrt\{\backslash sum^p\_\{j=1\}(u\_j-v\_j)^2\}\backslash )\$$   ;

• la distance de Manhattan :   $\$\backslash (d(u,v)=||u-v||\_1=\backslash sum^p\_\{j=1\}|u\_j-v\_j|\backslash )\$$   , ainsi appelée parce qu'elle correspond en deux dimensions à la distance parcourue par un taxi dans les rues de Manhattan, qui sont toutes soit parallèles soit perpendiculaires les unes aux autres.

Une des particularités de la corrélation de Pearson est qu'elle prend en compte la forme des signaux plutôt que leur amplitude. À l'inverse, la distance euclidienne prend surtout l'amplitude en considération. On fera donc attention au choix de la distance !

La courbe bleue et la courbe orange représentent chacune une variable mesurée sur 25 observations. À gauche, les profils de ces deux variables sont similaires, mais pas leurs amplitudes : l'inverse de la corrélation de Pearson est faible, la distance euclidienne grande. À l'inverse, à droite, les variables ont des formes et amplitudes similaires, mais sont décalées l'une par rapport à l'autre. L'inverse de la corrélation de Pearson est grand, la distance euclidienne faible.

Forme des clusters

Nous voulons de nos clusters qu'ils soient :

• resserrés sur eux-mêmes : deux points qui sont proches doivent appartenir au même cluster ;

• loin les uns des autres : deux points qui sont éloignés doivent appartenir à des clusters différents.

Notons d la distance que nous allons utiliser, par exemple la distance euclidienne.

On appelle centroïde d'un cluster le barycentre des points de ce cluster : $\$\backslash (\{\backslash mu\}\_k\; =\; \backslash frac\{1\}\{|\backslash mathcal\{C\}\_k|\}\; \backslash sum\_\{\{x\}\; \backslash in\; \backslash mathcal\{C\}\_k\}\; x\backslash )\$$.

On définit ainsi l'homogénéité (notée $\$\backslash (T\_k\backslash )\$$ , pour tightness, en anglais) d'un cluster comme la moyenne des distances de chacun des points contenus dans ce cluster au centroïde   $\$\backslash (\backslash mu\_k\; :\; T\_k\; =\; \backslash frac\{1\}\{|\backslash mathcal\{C\}\_k|\}\; \backslash sum\_\{\{x\}\; \backslash in\; \backslash mathcal\{C\}\_k\}\; d(x,\; \backslash mu\_k)\backslash )\$$  .

Un cluster resserré aura une hétérogénéité plus faible qu'un cluster de points épars.

Pour caractériser non pas un cluster, mais l'ensemble des clusters, on peut calculer la moyenne des homogénéités de chaque cluster :

 $\$\backslash (T\; =\; \backslash frac\{1\}\{K\}\; \backslash sum\_\{k=1\}^K\; T\_k\backslash )\$$ 

Nous avons dit plus haut vouloir aussi que les clusters soient loin les uns des autres. Pour quantifier cela, on définit la séparation de deux clusters comme la distance entre leurs centroïdes :   $\$\backslash (S\_\{k,l\}\; =\; d(\backslash mu\_k,\; \backslash mu\_l)\backslash )\$$   . Encore une fois, on peut calculer la moyenne de ces quantités sur l'ensemble des paires de clusters $\$\backslash ((k,\; l)\backslash )\$$ obtenues :

$\$\backslash (S\; =\; \backslash frac\{2\}\{K(K-1)\}\; \backslash sum\_\{k=1\}^K\; \backslash sum\_\{l=k+1\}^K\; S\_\{k,l\}\backslash )\$$ 

Nous avons maintenant deux critères à optimiser. Pour nous faciliter la tâche, nous pouvons les regrouper en un seul critère, l'indice de Davies-Bouldin. L'idée de cet indice est de comparer les distances intraclusters (c'est l'homogénéité), que l'on veut faibles, aux distances interclusters (la séparation), que l'on veut grandes. Pour un cluster k, cet indice est donné par    $\$\backslash (D\_k\; =\; \backslash max\_\{l\; \backslash neq\; k\}\; \backslash frac\{T\_l\; +\; T\_k\}\{S\_\{k,\; l\}\}\backslash )\$$   , et est d'autant plus faible que tous les clusters sont homogènes (le numérateur de cette fraction est petit) et que tous sont bien séparés (le dénominateur est grand). Encore une fois, on peut calculer un indice de Davies-Bouldin global en moyennant les indices de Davies-Bouldin de tous les clusters :

 $\$\backslash (D\; =\; \backslash frac\{1\}\{K\}\; \backslash sum\_\{k=1\}^K\; D\_k\backslash )\$$

Une autre façon de quantifier à quel point un clustering répond à ces deux exigences (homogénéité et séparation) est de mesurer ce que l'on appelle le coefficient de silhouette. Pour un point x donné, le coefficient de silhouette s(x) permet d'évaluer si ce point appartient au "bon" cluster : est-il proche des points du cluster auquel il appartient ? Est-il loin des autres points ? Pour répondre à la première question, on calcule la distance moyenne de x à tous les autres points du cluster C_k auquel il appartient :   $\$\backslash (a(x)\; =\; \backslash frac\{1\}\{|C\_k|-1\}\; \backslash sum\_\{u\; \backslash in\; C\_k,\; u\; \backslash neq\; x\}\; d(u,\; x)\backslash )\$$  . Pour répondre à la deuxième, on calcule la plus petite valeur que pourrait prendre a(x), si x était assigné à un autre cluster :   $\$\backslash (b(x)\; =\; \backslash min\_\{l\; \backslash neq\; k\}\; \backslash frac\{1\}\{|C\_l|\}\; \backslash sum\_\{u\; \backslash in\; C\_l\}\; d(u,\; x)\backslash )\$$  . Si x a été correctement assigné, alors a(x) < b(x). Le coefficient de silhouette est donné par $\$\backslash (s(x)\; =\; \backslash frac\{b(x)\; -\; a(x)\}\{\backslash max(a(x),\; b(x))\}\backslash )\$$  . Il est donc compris entre -1 et 1, et d'autant plus proche de 1 que l'assignation de x à son cluster est satisfaisante. Pour évaluer un clustering, on peut calculer son coefficient de silhouette moyen.

Dans scikit-learn  , le coefficient de silhouette se calcule avec sklearn.metrics.silhouette_score.

Stabilité des clusters

Autre critère important, la stabilité du clustering : si je lance l'algorithme plusieurs fois sur les mêmes données avec une initialisation différente, ou sur des sous-ensembles différents des données, ou encore sur les mêmes données légèrement bruitées, est-ce que j'obtiens les mêmes résultats ?

Ce critère est particulièrement pertinent pour choisir le nombre de clusters : si le nombre de clusters choisi correspond à la structure naturelle des données, le clustering sera plus stable que si ce n'est pas le cas. Sur l'image ci-dessous, un algorithme qui cherche à déterminer 3 clusters va raisonnablement retrouver les trois groupes que l'on voit. Mais si on lui demande de déterminer 4 clusters, la répartition dans ces 4 clusters sera plus aléatoire, et ne sera pas nécessairement deux fois la même. C'est une façon de déterminer que 3 est un meilleur nombre de clusters que 4.

Compatibilité avec des connaissances spécifiques au domaine

Très souvent, on va aussi évaluer un algorithme de clustering « à l'œil », et regarder si les clusters proposés ont du sens. Les textes regroupés dans ce cluster parlent-ils tous du même sujet ? Les images dans ces deux clusters représentent-elles des sujets différents ?

Pour faire ça plus proprement, on peut travailler sur un jeu de données (par exemple, un sous-ensemble des données qui nous intéressent) sur lequel on connaît une partition raisonnable des données. On va ensuite comparer cette partition avec celle retournée par notre algorithme de clustering.

Par exemple, on peut travailler avec 1 000 images étiquetées par l'objet qu'elles représentent : chien, chat ou panda.

Il s'agit maintenant d'évaluer si les groupes formés par l'algorithme de clustering correspondent à ceux définis à priori. Facile ! C'est comme évaluer un algorithme de classification multiclasse. Mais pas si vite : si on s'intéresse à ce que les mêmes objets appartiennent au même cluster, que ce cluster soit le premier, le deuxième ou le k-ième importe peu.

Il faut donc utiliser des mesures de performance spécifiques, qui permettent d'évaluer la concordance de deux partitions du jeu de données. Vous en trouverez une liste dans scikit-learn.metrics.

Exemple de ces mesures, l'indice de Rand. L'indice de Rand est la proportion de paires de points  \((x_1, x_2)\) qui sont groupées de la même façon dans les deux partitions : soit parce que, dans les deux cas, x_1 et x_2 appartiennent au même cluster, soit parce que, dans les deux cas,  x_1 et x_2 appartiennent à des clusters différents.

L'indice de Rand peut être gonflé artificiellement en prédisant beaucoup de clusters : les paires de points appartenant à des clusters différents seront nombreuses, et il y aura de grandes chances que deux points étiquetés différemment soient dans deux clusters différents. L'indice de Rand ajusté (ARI, pour Adjusted Rand Index) corrige cet effet en normalisant l'indice de Rand (RI) :

 $\$\backslash (ARI\; =\; \backslash frac\{RI\; -\; E(RI)\}\{\backslash max(RI)\; -\; E(RI)\}\backslash )\$$

où E(RI) est l'espérance de la valeur de l'indice de Rand, autrement dit l'indice obtenu en partitionnant les données au hasard. Cet index ajusté est proche de 0 pour un clustering aléatoire, et égal à 1 uniquement quand le clustering correspond exactement à la partition initiale. Dans scikit-learn  , on peut le calculer grâce àsklearn.metrics.adjusted_rand_score  .

Résumé

Pour évaluer un algorithme de clustering, on peut s'intéresser à :

• la forme des clusters qu'il produit (sont-ils denses, bien séparés ?). On utilise ici souvent le coefficient de silhouette ;

• la stabilité de l'algorithme ;

• la compatibilité des résultats avec des connaissances spécifiques au domaine, que l'on peut évaluer à l'aide de mesures d'enrichissement.