• 15 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 01/02/2019

Définissez les critères que doit satisfaire votre clustering

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

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 les unes des autres ; à quel point une observation est proche d'un cluster ; et à quel point deux clusters sont proches les uns des autres.

Une distance est formellement définie comme une fonction $\(d: \mathbb{R}^p \rightarrow \mathbb{R}_+\)$, 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 : $\(d(u,v)=||u−v||_2=\sqrt{\sum^p_{j=1}(u_j−v_j)^2}\)$  

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

Une particularité de la corrélation de Pearson est de prendre 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 : $\({\mu}_k = \frac{1}{|\mathcal{C}_k|} \sum_{{x} \in \mathcal{C}_k} x\)$.

Le centroide (en orange) du cluster $C_k$
Le centroïde (en orange) du cluster $C_k$

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

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 :

 $\(T = \frac{1}{K} \sum_{k=1}^K T_k\)$ .

Nous avions dit plus haut aussi vouloir 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 : $\(S_{k,l} = d(\mu_k, \mu_l)\)$. Encore une fois, on peut calculer la moyenne de ces quantités sur l'ensemble des paires de cluster $\((k, l)\)$ obtenues :

$\(S = \frac{2}{K(K-1)} \sum_{k=1}^K \sum_{l=k+1}^K S_{k,l}\)$ 

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 cette indice est de comparer les distannce intra-cluster (c'est l'homogénéité), que l'on veut faibles, aux distances inter-cluster (la séparation), que l'on veut grandes. Pour un cluster k, cet indice est donné par  $\(D_k = \max_{l \neq k} \frac{T_l + T_k}{S_{k, l}}\)$ 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 :

 $\(D = \frac{1}{K} \sum_{k=1}^K D_k\)$

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 : $\(a(x) = \frac{1}{|C_k|-1} \sum_{u \in C_k, u \neq x} d(u, x)\)$ . Pour répondre à la deuxième, on calcule la plus petite valeur que pourrait prendre a(x), si x était assigné à un autre cluster : $\(b(x) = \min_{l \neq k} \frac{1}{|C_l|} \sum_{u \in C_l} d(u, x)\)$ . Si x a été correctement assigné, alors a(x) < b(x). Le coefficient de silhouette est donné par $\(s(x) = \frac{b(x) - a(x)}{\max(a(x), b(x))}\)$ . 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.

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

Stabilité des clusters

Un autre critère important est 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.

Combien de clusters ?
Combien de clusters ?

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 1000 images étiquetées par l'objet qu'elles représentent : chien, chat, ou panda.

Chien, chat, ou panda ?
Chien, chat, ou panda ?

Il s'agit maintenant d'évaluer si les groupes formés par l'algorithme de clustering correspondent à ceux définis a priori. Facile ! C'est comme d'évaluer un algorithme de classification multi-classes. 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.

Un exemple de ces mesures est 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 point é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) :

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

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. Dansscikit-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.

Exemple de certificat de réussite
Exemple de certificat de réussite