Clustering

Download nbviewer Onyxia
Binder Open In Colab githubdev

</p>

Nous allons continuer avec le jeu de données de résultat des élections US 2020 au niveau des comtés

Jusqu’à présent, nous avons fait de l’apprentissage supervisé puisque nous connaissions la vraie valeur de la variable à expliquer/prédire (y). Ce n’est plus le cas avec l’apprentissage non supervisé.

Le clustering est un champ d’application de l’apprentissage non-supervisé. Il s’agit d’exploiter l’information disponible pour regrouper des observations qui se ressemblent.

L’objectif est de créer des clusters d’observations pour lesquels :

  • au sein de chaque cluster, les observations sont homogènes (variance intra-cluster minimale)
  • les clusters ont des profils hétérogènes, c’est-à-dire qu’ils se distinguent les uns des autres (variance inter-cluster maximale)

En Machine Learning, les méthodes de clustering sont très utilisées pour faire de la recommandation. En faisant, par exemple, des classes homogènes de consommateurs, il est plus facile d’identifier et cibler des comportements propres à chaque classe de consommateurs.

Ces méthodes ont également un intérêt en économie et sciences sociales parce qu’elles permettent de regrouper des observations sans a priori et ainsi interpréter une variable d’intérêt à l’aune de ces résultats. Cette publication sur la ségrégation spatiale utilisant des données de téléphonie mobile utilise par exemple cette approche.

Les méthodes de clustering peuvent aussi intervenir en amont d’un problème de classification (dans des problèmes d’apprentissage semi-supervisé). Le manuel Hands-on machine learning with scikit-learn, Keras et TensorFlow présente dans le chapitre dédié à l’apprentissage non supervisé quelques exemples.

Dans certaines bases de données, on peut se retrouver avec quelques exemples labellisés mais la plupart sont non labellisés. Les labels ont par exemple été faits manuellement par des experts.

Par exemple, supposons que dans la base MNIST des chiffres manuscrits, les chiffres ne soient pas labellisés et que l’on se demande quelle est la meilleure stratégie pour labelliser cette base. On pourrait regarder des images de chiffres manuscrits au hasard de la base et les labelliser. Les auteurs du livre montrent qu’il existe toutefois une meilleure stratégie. Il vaut mieux appliquer un algorithme de clustering en amont pour regrouper les images ensemble et avoir une image représentative par groupe, et labelliser ces images représentatives au lieu de labelliser au hasard.

Les méthodes de clustering sont nombreuses. Nous allons nous pencher sur la plus intuitive : les k-means.

Données

Comme précédemment, le code de chargement des données est disponible sur Github.

Principe

L’objectif des k-means est de partitioner l’espace des observations en trouvant des points (centroids) jouant le rôle de centres de gravité pour lesquels les observations proches peuvent être regroupées dans une classe homogène. L’algorithme k-means fonctionne par itération, en initialisant les centroïdes puis en les mettant à jour à chaque itération, jusqu’à ce que les centroïdes se stabilisent. Quelques exemples de clusters issus de la méthode k-means :

In [3]:
import matplotlib.pyplot as plt

Choisir le nombre de clusters

Le nombre de clusters est fixé par le modélisateur. Il existe plusieurs façons de fixer ce nombre :

  • connaissance a priori du problème ;
  • analyse d’une métrique spécifique pour définir le nombre de clusters à choisir ;
  • etc.

Il y a un arbitrage à faire entre biais et variance : un trop grand nombre de clusters implique une variance intra-cluster très faible (sur-apprentissage, même s’il n’est jamais possible de déterminer le vrai type d’une observation puisqu’on est en apprentissage non supervisé).

Sans connaissance a priori du nombre de clusters, on peut recourir à deux familles de méthodes :

  • La méthode du coude (elbow method): On prend le point d’inflexion de la courbe de performance du modèle. Cela représente le moment où ajouter un cluster (complexité croissante du modèle) n’apporte que des gains modérés dans la modélisation des données.

  • Le score de silhouette : On mesure la similarité entre un point et les autres points du cluster par rapport aux autres clusters. Plus spécifiquement :

Silhouette value is a measure of how similar an object is to its own cluster (cohesion) compared to other clusters (separation). The silhouette ranges from −1 to +1, where a high value indicates that the object is well matched to its own cluster and poorly matched to neighboring clusters. If most objects have a high value, then the clustering configuration is appropriate. If many points have a low or negative value, then the clustering configuration may have too many or too few clusters

Source: Wikipedia)

Le score de silhouette d’une observation est donc égal à (m_nearest_cluster - m_intra_cluster)/max( m_nearest_cluster,m_intra_cluster)m_intra_cluster est la moyenne des distances de l’observation aux observations du même cluster et m_nearest_cluster est la moyenne des distances de l’observation aux observations du cluster le plus proche.

Le package yellowbrick fournit une extension utile à scikit pour représenter facilement la performance en clustering.

Pour la méthode du coude, la courbe de performance du modèle marque un coude léger à $k=4$. Le modèle initial semblait donc approprié.

yellowbrick permet également de représenter des silhouettes mais l’interprétation est moins aisée et le coût computationnel plus élevé :

Le score de silhouette offre une représentation plus riche que la courbe coudée.

Sur ce graphique, les barres verticales en rouge et en pointillé représentent le score de silhouette global pour chaque k choisi. On voit par exemple que pour tous les k représentés ici, le score de silhouette se situe entre 0.5 et 0.6 et varie peu. Ensuite, pour un k donné, on va avoir la représentation des scores de silhouette de chaque observation, regroupées par cluster. Par exemple, pour k = 4, ici, on voit bien quatre couleurs différentes qui sont les 4 clusters modélisés. Les ordonnées sont toutes les observations clusterisées et en abscisses on a le score de silhouette de chaque observation. Si au sein d’un cluster, les observations ont un score de silhouette plus faible que le score de silhouette global (ligne verticale en rouge), cela signifie que les observations du clusters sont trop proches des autres clusters.

Grâce à cette représentation, on peut aussi se rendre compte de la taille relative des clusters. Par exemple, avec k = 3, on voit qu’on a deux clusters conséquents et un plus “petit” cluster relativement aux deux autres. Cela peut nous permettre de choisir des clusters de tailles homogènes ou non.

Enfin, quand le score de silhouette est négatif, cela signifie que la moyenne des distances de l’observation aux observations du cluster le plus proche est inférieure à la moyenne des distances de l’observation aux observations de son cluster. Cela signifie que l’observation est mal classée.

Autres méthodes de clustering

Il existe de nombreuses autres méthodes de clustering. Parmi les plus connues, on peut citer deux exemples en particulier :

  • DBSCAN
  • les mélanges de Gaussiennes

DBSCAN

L’algorithme DBSCAN est implémenté dans sklearn.cluster. Il peut être utilisé pour faire de la détection d’anomalies notamment. En effet, cette méthode repose sur le clustering en régions où la densité des observations est continue, grâce à la notion de voisinage selon une certaine distance epsilon. Pour chaque observation, on va regarder si dans son voisinage selon une distance epsilon, il y a des voisins. S’il y a au moins min_samples voisins, alors l’observation sera une core instance.

Les observations qui ne sont pas des core instances et qui n’en ont pas dans leur voisinage selon une distance espilon vont être détectées comme des anomalies.

Les mélanges de gaussiennes

En ce qui concerne la théorie, voir le cours Probabilités numériques et statistiques computationnelles, M1 Jussieu, V.Lemaire et T.Rebafka Se référer notamment aux notebooks pour l’algorithme EM pour mélange gaussien.

Dans sklearn, les mélanges gaussiens sont implémentés dans sklearn.mixture comme GaussianMixture. Les paramètres importants sont alors le nombre de gaussiennes n_components et le nombre d’initiatisations n_init. Il est possible de faire de la détection d’anomalie savec les mélanges de gaussiennes.