Le clustering consiste à répartir des observations dans des groupes, généralement non observés, en fonction de caractéristiques observables. Il s’agit d’une application classique, en machine learning de méthodes non supervisées puisqu’on ne dispose généralement pas de l’information sur le groupe auquel appartient réellement une observation. Les applications au monde réel sont nombreuses, notamment dans le domaine de la segmentation tarifaire.

Author

Lino Galiana

Published

July 20, 2023

Download nbviewer Onyxia Onyxia
Binder Open In Colab githubdev

Nous allons continuer avec le même jeu de données que précédemment, c’est-à-dire les résultats des élections US 2020 présentés dans l’introduction de cette partie : les données de vote aux élections présidentielles américaines croisées à des variables sociodémographiques. Le code est disponible sur Github.

import requests

url = 'https://raw.githubusercontent.com/linogaliana/python-datascientist/master/content/modelisation/get_data.py'
r = requests.get(url, allow_redirects=True)
open('getdata.py', 'wb').write(r.content)

import getdata
votes = getdata.create_votes_dataframes()

Introduction sur le clustering

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 en regroupant des observations qui se ressemblent à partir de leurs caractéristiques (features) communes.

Rappel: l’arbre de décision des méthodes Scikit

L’objectif est de créer des groupes d’observations (clusters) 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. 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.

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

Les k-means

Principe

L’objectif des k-means est de partitionner 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 :

Dans ce chapitre nous allons principalement utiliser Scikit. Voici néanmoins une proposition d’imports de packages, pour gagner du temps.

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import geopandas as gpd
from sklearn.cluster import KMeans #pour kmeans
import seaborn as sns #pour scatterplots

La carte obtenue à la question 4, qui permet de représenter spatialement nos groupes, est la suivante :

Le nuage de point de la question 5, permettant de représenter la relation entre Median_Household_Income_2019 et Unemployment_rate_2019, aura l’aspect suivant :

Enfin, l’histogramme des votes pour chaque cluster est :

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.

from sklearn.cluster import KMeans
from yellowbrick.cluster import KElbowVisualizer

visualizer = KElbowVisualizer(model, k=(2,12))
visualizer.fit(df2[xvars])        # Fit the data to the visualizer
<Axes: title={'center': 'Distortion Score Elbow for KMeans Clustering'}, xlabel='k', ylabel='distortion score'>
<Figure size 768x528 with 0 Axes>

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é :

from yellowbrick.cluster import SilhouetteVisualizer

fig, ax = plt.subplots(2, 2, figsize=(15,8))
j=0
for i in [3, 4, 6, 10]:
    j += 1
    '''
    Create KMeans instance for different number of clusters
    '''
    km = KMeans(n_clusters=i, init='k-means++', n_init=10, max_iter=100, random_state=42)
    q, mod = divmod(j, 2)
    '''
    Create SilhouetteVisualizer instance with KMeans instance
    Fit the visualizer
    '''
    visualizer = SilhouetteVisualizer(km, colors='yellowbrick', ax=ax[q-1][mod])
    ax[q-1][mod].set_title("k = " + str(i))
    visualizer.fit(df2[xvars])

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 trois exemples en particulier :

  • Le clustering ascendant hiérarchique
  • DBSCAN
  • les mélanges de Gaussiennes

Clustering Ascendant Hiérarchique (CAH)

Quel est le principe ?

  • On commence par calculer la dissimilarité entre nos N individus, i.e. leur distance deux à deux dans l’espace de nos variables
  • Puis on regroupe les deux individus dont le regroupement minimise un critère d’agrégation donné, créant ainsi une classe comprenant ces deux individus.
  • On calcule ensuite la dissimilarité entre cette classe et les N-2 autres individus en utilisant le critère d’agrégation.
  • Puis on regroupe les deux individus ou classes d’individus dont le regroupement minimise le critère d’agrégation.
  • On continue ainsi jusqu’à ce que tous les individus soient regroupés.

Ces regroupements successifs produisent un arbre binaire de classification (dendrogramme), dont la racine correspond à la classe regroupant l’ensemble des individus. Ce dendrogramme représente une hiérarchie de partitions. On peut alors choisir une partition en tronquant l’arbre à un niveau donné, le niveau dépendant soit des contraintes de l’utilisateur, soit de critères plus objectifs.

Plus d’informations ici.

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.

L’Analyse en Composantes Principales

Pour la visualisation de clusters

La méthode la plus simple pour visualiser les clusters, peu importe la méthode avec laquelles ils ont été obtenus, serait de représenter chaque individu dans l’espace à N dimensions des variables de la table, et colorier chaque individu en fonction de son cluster. On pourrait alors bien différencier les variables les plus discrimantes et les différents groupes. Un seul problème ici : dès que N > 3, nous avons du mal à représenter le résultat de façon intelligible…

C’est là qu’intervient l’Analyse en Composantes Principales (ACP), qui permet de projeter notre espace à haute dimension dans un espace de dimension plus petite. La contrainte majeure de la projection est de pouvoir conserver le maximum d’information (mesurée par la variance totale de l’ensemble de données) dans notre nombre réduit de dimensions, appelées composantes principales. En se limitant à 2 ou 3 dimensions, on peut ainsi se représenter visuellement les relations entre les observations avec une perte de fiabilité minimale.

On peut généralement espérer que les clusters déterminés dans notre espace à N dimensions se différencient bien sur notre projection par ACP, et que la composition des composantes principales en fonction des variables initiales permette d’interpréter les clusters obtenus. En effet, la combinaison linéaire des colonnes donnant naissance à nos nouveaux axes a souvent un “sens” dans le monde réel :

  • Soit parce qu’une petite poignée de variables représente la majorité de la composante
  • Soit parce que la plupart des colonnes intervenant dans la composante sommée se combinent bien pour former une interprétation naturelle.

Pour mettre en pratique les méthodes de création de clusters, de la base brute jusqu’à la visualisation par ACP, vous pouvez consulter la partie 2 du sujet 3 du funathon 2023, Explorer les habitudes alimentaires de nos compatriotes, sur le SSP Cloud ou sur Github.

Pour la réduction de dimension

L’ACP est également très utile dans le champ de la réduction du nombre de variables pour de nombreux types de modélisations, comme par exemple les régressions linéaires. Il est ainsi possible de projeter l’espace des variables explicatives dans un espace de dimension donnée plus faible, pour notamment limiter les risques d’overfitting.

Back to top

References

Géron, Aurélien. 2022. Hands-on Machine Learning with Scikit-Learn, Keras, and TensorFlow. " O’Reilly Media, Inc.".

Citation

BibTeX citation:
@book{galiana2023,
  author = {Galiana, Lino},
  title = {Python Pour La Data Science},
  date = {2023},
  url = {https://pythonds.linogaliana.fr/},
  doi = {10.5281/zenodo.8229676},
  langid = {en}
}
For attribution, please cite this work as:
Galiana, Lino. 2023. Python Pour La Data Science. https://doi.org/10.5281/zenodo.8229676.