Introduction au clustering hiérarchique en Python

Motivation

Imaginez que vous êtes Data Scientist dans une entreprise de retail. Votre manager vous demande de segmenter les clients en groupes  : faible, standard, premium ou platinum, selon leur comportement de dépense, afin d’alimenter des campagnes marketing ciblées et des recommandations de produits.

En l’absence de tout libellé historique associé à ces clients, comment les catégoriser ?

C’est là que le clustering entre en jeu. Il s’agit d’une technique d’apprentissage automatique non supervisé qui permet de regrouper des données non étiquetées en catégories similaires.

Ce tutoriel se concentre sur l’approche de clustering hiérarchique, l’une des nombreuses techniques en apprentissage non supervisé. Nous commencerons par définir ce qu’est le clustering hiérarchique, puis nous le comparerons à d’autres méthodes existantes.

Ensuite, nous vous guiderons pas à pas dans une implémentation en Python à l’aide de la bibliothèque populaire Scipy.

Définition du clustering hiérarchique

Le clustering hiérarchique consiste à construire des grappes successives à partir de clusters définis précédemment. Cette technique vise à organiser les données sous forme d’arbre de clusters, appelé dendrogramme, qui représente visuellement les relations hiérarchiques entre les groupes sous-jacents.

Comparer le clustering hiérarchique aux autres techniques

Le clustering hiérarchique est un algorithme puissant, mais ce n’est pas le seul. Chaque type de clustering a ses atouts et ses limites.

Voyons comment il se compare à d’autres approches comme K-means et le clustering basé sur des modèles. Il existe bien d’autres méthodes, mais ces deux-là, avec le clustering hiérarchique, sont largement utilisées et offrent un bon cadre pour comprendre les autres.

Pour en savoir plus sur le clustering en apprentissage automatique, consultez notre article dédié qui couvre cinq algorithmes essentiels.

Clustering hiérarchique vs clustering K-means

Contrairement au clustering hiérarchique, K-means partitionne les points de données en « K » groupes ou clusters, où l’utilisateur fixe « K » à l’avance.

L’idée générale est de chercher des clusters qui minimisent, sur l’ensemble des variables (ou caractéristiques), la somme des distances euclidiennes au carré entre tous les points et leurs centres, puis de regrouper les individus de manière itérative.

Notre tutoriel K-means clustering en Python avec Scikit-learn vous aidera à comprendre le fonctionnement interne de K-means à travers une étude de cas.

Avantages

• Plus efficace en calcul que le clustering hiérarchique et donc adapté aux grands jeux de données.
• K-means est plus simple à comprendre et à implémenter.

Inconvénients

• Moins flexible que le clustering hiérarchique, car il oblige à spécifier le nombre de clusters au préalable, ce qui n’est pas toujours évident.
• Le résultat peut varier d’une itération à l’autre sur un même jeu de données.
• Plus sensible aux valeurs aberrantes, car la moyenne du cluster est influencée par leur présence.
• K-means comme le clustering hiérarchique ne traitent pas directement les données catégorielles et peuvent mal fonctionner avec des données non continues ou de très grande variance.

Malgré ses limites, K-means reste une méthode populaire grâce à sa simplicité et son efficacité. Il sert souvent de référence pour comparer d’autres techniques de clustering.

Clustering basé sur un modèle

K-means et le clustering hiérarchique s’appuient sur une matrice de distances entre tous les points du jeu de données. Le clustering basé sur un modèle applique, lui, des techniques statistiques pour identifier les clusters. Le processus général est le suivant :

• Choisir le modèle statistique et le nombre de clusters.
• Ajuster le modèle sur les données.
• Identifier les clusters à partir des paramètres du modèle.

Avantages

• Plus flexible que le clustering hiérarchique, car il permet d’utiliser différents modèles pour détecter des types de clusters variés.
• Mieux adapté à des données aux formes ou structures complexes.

Inconvénients

• Plus coûteux en calcul que le clustering hiérarchique, surtout sur de grands volumes.
• Nécessite une bonne compréhension de la modélisation statistique, le choix du modèle influençant fortement le résultat.
• Comme K-means, il impose de fixer le nombre de clusters à l’avance.

Cas d’usage du clustering hiérarchique

Le clustering hiérarchique a de nombreuses applications au quotidien, notamment (sans s’y limiter) en biologie, traitement d’image, marketing, économie et analyse de réseaux sociaux.

Biologie

Le regroupement de séquences d’ADN est l’un des grands défis de la bio-informatique.

Les biologistes peuvent exploiter le clustering hiérarchique pour étudier les relations génétiques entre organismes et les classer en groupes taxonomiques. Cela facilite l’analyse rapide et la visualisation des relations sous-jacentes.

Traitement d’image

En traitement d’image, le clustering hiérarchique peut regrouper des régions ou des pixels similaires selon la couleur, l’intensité ou d’autres caractéristiques. C’est utile pour la segmentation d’image, la classification et la reconnaissance d’objets.

Marketing

Les spécialistes marketing peuvent utiliser le clustering hiérarchique pour hiérarchiser des profils de clients selon leurs habitudes d’achat, afin d’affiner les stratégies et les recommandations. Par exemple, des produits différents peuvent être proposés selon que les clients dépensent peu, moyennement ou beaucoup.

Analyse de réseaux sociaux

Les réseaux sociaux sont une source précieuse d’insights lorsqu’ils sont bien exploités. Le clustering hiérarchique permet d’identifier des groupes ou communautés, de comprendre leurs relations et la structure globale du réseau.

L’algorithme de clustering hiérarchique

Dans cette section, nous abordons trois notions clés : les étapes de l’algorithme hiérarchique, les deux variantes (agglomératif et divisif) et des techniques pour choisir la bonne mesure de distance.

Étapes de l’algorithme de clustering hiérarchique

L’algorithme s’appuie sur des mesures de distance pour former les clusters. Le processus se déroule comme suit :

Prétraitez les données en supprimant les valeurs manquantes et en appliquant les tâches nécessaires pour les rendre aussi propres que possible. Cette étape est générale à la plupart des projets de machine learning.

1. Calculez la matrice des distances entre chaque paire de points avec une métrique donnée, comme la distance euclidienne, la distance de Manhattan ou la similarité cosinus. Par défaut, on utilise la distance euclidienne.

2. Fusionnez les deux clusters les plus proches.

3. Mettez à jour la matrice des distances en tenant compte des nouveaux clusters.

4. Répétez les étapes 1, 2 et 3 jusqu’à fusionner tous les clusters en un seul.

Exemples de clustering hiérarchique

Le clustering agglomératif et le clustering divisif sont deux démarches opposées. Observons leur fonctionnement, avec un exemple et une visualisation.

Clustering hiérarchique agglomératif

Ce premier scénario correspond à l’approche décrite ci-dessus. On démarre en considérant chaque observation comme un cluster singleton (un seul point). Puis on fusionne itérativement les clusters jusqu’à n’en obtenir qu’un. On parle d’approche ascendante (bottom-up).

Comme montré ci-dessous :

• On commence par considérer chaque animal comme son propre cluster.
• Puis on forme trois clusters à partir de ces animaux selon leurs similarités :
• Oiseaux : aigle et paon
• Mammifères : lion et ours
• Plus de trois pattes : araignée et scorpion
• On répète la fusion pour créer le cluster des vertébrés en combinant les deux clusters les plus proches : Oiseaux et Mammifères.
• Enfin, les deux clusters restants, Vertébrés et Plus de trois pattes, sont fusionnés pour former un seul cluster : Animaux.

Dendrogramme de l’approche agglomérative

Clustering divisif

À l’inverse, le clustering divisif est descendant (top-down) : on commence par considérer l’ensemble des points comme un seul cluster, puis on le scinde progressivement jusqu’à obtenir des éléments uniques.

Sur le schéma de l’approche divisive :

• On considère d’abord l’ensemble des animaux comme un seul bloc.
• Puis on divise ce bloc en deux clusters : Vertébrés et Plus de 3 pattes.
• On répète la division sur les clusters précédents jusqu’à obtenir des animaux uniques.

Dendrogramme de l’approche divisive

Choisir la bonne mesure de distance

Le choix de la distance est crucial et dépend du problème à résoudre. Par exemple, on peut regrouper des étudiants selon :

• Leur pays d’origine
• Leur genre, masculin ou féminin
• Leur parcours académique

Ces regroupements sont tous valables, mais ils n’ont pas la même signification.

Même si la distance euclidienne est la plus courante, d’autres mesures existent : Manhattan, Canberra, corrélations de Pearson ou Spearman, distance de Minkowski, etc.

Mesurer les clusters avant de les fusionner

Les distances évoquées ci-dessus concernent les éléments. Voici trois façons standard (non exhaustives) de mesurer la proximité de deux clusters avant leur fusion : (1) chaînage simple (single linkage), (2) chaînage complet (complete linkage), (3) chaînage moyen (average linkage).

Chaînage simple (single linkage)

Parmi toutes les distances par paires entre les éléments des deux clusters C1 et C2, le chaînage simple retient comme distance entre clusters la distance minimale.

Distance (C1, C2) = Min { d(i, j), où l’élément i est dans C1 et l’élément j est dans C2 }

Parmi toutes les paires provenant des deux clusters, celles mises en vert ont la distance minimale.

Illustration du chaînage simple

Chaînage complet (complete linkage)

Parmi toutes les distances par paires entre les éléments des deux clusters C1 et C2, le chaînage complet retient comme distance entre clusters la distance maximale.

Distance (C1, C2) = Max { d(i, j), où l’élément i est dans C1 et l’élément j est dans C2 }

Parmi toutes les paires, celles en vert ont la distance maximale.

Illustration du chaînage complet

Chaînage moyen (average linkage)

En chaînage moyen, la distance entre deux clusters C1 et C2 correspond à la moyenne des distances entre toutes les paires d’éléments des deux clusters.

Distance (C1, C2) = Somme{ d(i, j) } / Nombre total de distances

Illustration du chaînage moyen

Puis, le chaînage moyen se calcule ainsi :

d(a,j) + d(a,h) + d(a,n) + d(d,j) + d(d,h) + d(d,n)

—-----------------------------------------------------------, où le nombre total de distances = 6

  Nombre total de distances

Implémenter le clustering hiérarchique en Python

Vous comprenez désormais le fonctionnement du clustering hiérarchique. Passons à l’implémentation technique en Python.

Si vous préférez R, notre tutoriel Hierarchical clustering in R est un bon point de départ.

Préparer l’environnement

Commencez par installer Python sur votre ordinateur, ainsi que les bibliothèques suivantes :

• Pandas pour charger les DataFrames
• Scikit-learn pour la normalisation des données
• Seaborn et matplotlib pour la visualisation
• Scipy pour appliquer le clustering

Vous pouvez les installer avec pip, le gestionnaire de paquets Python :

pip install scikit-learn
pip install pandas

pip install matplotlib seaborn

pip install scipy

Importons ensuite les modules nécessaires et chargeons les données. Nous utiliserons au départ le jeu de données iris de scikit-learn, qui contient des informations sur différentes espèces d’iris.

Pour une illustration plus parlante, nous utiliserons les Loan Data disponibles sur DataLab. Tout le code de ce tutoriel est disponible dans ce workbook DataLab : créez facilement votre copie pour exécuter le code dans le navigateur, sans rien installer.

Comprendre les données

Le jeu de données contient 9 500 prêts avec des informations sur la structure du prêt, l’emprunteur, et s’il a remboursé intégralement. Nous supprimerons la colonne cible not.fully.paid afin de respecter le cadre non supervisé.

import pandas as pd
loan_data = pd.read_csv("loan_data.csv")
loan_data.head()

Premières cinq lignes des données

L’instruction suivante montre que les données comptent 9 578 lignes et 14 colonnes numériques, à l’exception de purpose (objet), de type texte, qui décrit la finalité du prêt.

loan_data.info()

Informations sur les données

Prétraiter les données

Avant d’appliquer le clustering, il faut gérer les valeurs manquantes, normaliser les variables et supprimer les colonnes non pertinentes.

Gérer les valeurs manquantes

Comme le montre la sortie ci-dessous, il n’y a pas de valeur manquante.

percent_missing =round(100*(loan_data.isnull().sum())/len(loan_data),2)
percent_missing

Pourcentage de valeurs manquantes

Supprimer les colonnes non souhaitées

Nous allons analyser les prêts en utilisant toutes les colonnes sauf :

• purpose
• not.fully.paid, car c’est le label qui indique si l’emprunteur a remboursé en totalité.

cleaned_data correspond aux données sans ces colonnes.

cleaned_data = loan_data.drop(['purpose', 'not.fully.paid'], axis=1)
cleaned_data.info()

L’image ci-dessous présente les informations du nouveau jeu de données.

Nouvelles données sans les colonnes supprimées

Analyse des valeurs aberrantes

Une faiblesse du clustering hiérarchique est sa sensibilité aux outliers. La distribution de chaque variable est visualisée via un boxplot.

def show_boxplot(df):
plt.rcParams['figure.figsize'] = [14,6]
sns.boxplot(data = df, orient="v")
plt.title("Outliers Distribution", fontsize = 16)
plt.ylabel("Range", fontweight = 'bold')
plt.xlabel("Attributes", fontweight = 'bold')
   
show_boxplot(cleaned_data)

Boxplot de toutes les variables

Le solde renouvelable de l’emprunteur (revol_bal) est la seule variable avec des points très éloignés du reste.

En utilisant l’intervalle interquartile (IQR), on peut supprimer les points hors de la plage définie par quartiles +/- 1,5 * IQR, où IQR est l’écart interquartile.

Voici la fonction utilitaire correspondante.

def remove_outliers(data):
   
df = data.copy()
   
for col in list(df.columns):
 
      Q1 = df[str(col)].quantile(0.05)
      Q3 = df[str(col)].quantile(0.95)
      IQR = Q3 - Q1
      lower_bound = Q1 - 1.5*IQR
      upper_bound = Q3 + 1.5*IQR
 
      df = df[(df[str(col)] >= lower_bound) & 

        (df[str(col)] <= upper_bound)]
   
return df

Appliquons-la au jeu de données.

without_outliers = remove_outliers(cleaned_data)

Vérifions le nouveau boxplot et comparons-le au précédent.

show_boxplot(without_outliers)

Plus aucun point ne se situe hors de l’intervalle interquartile.

without_outliers.shape

Les données font désormais 9 319 lignes et 12 colonnes. Cela signifie que 259 observations, identifiées comme outliers, ont été supprimées.

Mettre les données à l’échelle

Comme le clustering hiérarchique repose sur la distance euclidienne, très sensible aux différences d’échelle entre variables, il est recommandé de tout remettre à l’échelle avant de calculer les distances.

Nous utiliserons pour cela StandardScaler de sklearn.

from sklearn.preprocessing import StandardScaler

data_scaler = StandardScaler()

scaled_data = data_scaler.fit_transform(without_outliers)
scaled_data.shape

La forme des données reste la même (9 319 lignes, 12 colonnes), la normalisation n’affectant pas les dimensions.

Appliquer l’algorithme de clustering hiérarchique

Nous avons tout le nécessaire pour passer à l’implémentation.

À ce stade, on peut choisir la méthode de chaînage via l’attribut method de linkage(). Nous couvrirons ici les trois techniques avec la distance euclidienne.

Voici le code après import des bibliothèques pertinentes.

from scipy.cluster.hierarchy import linkage, dendrogram

complete_clustering = linkage(scaled_data, method="complete", metric="euclidean")
average_clustering = linkage(scaled_data, method="average", metric="euclidean")
single_clustering = linkage(scaled_data, method="single", metric="euclidean")

Une fois les trois clusterings calculés, traçons les dendrogrammes correspondants, en commençant par le chaînage complet.

dendrogram(complete_clustering)
plt.show()

Dendrogramme de l’approche par chaînage complet

dendrogram(average_clustering)
plt.show()

Dendrogramme de l’approche par chaînage moyen

dendrogram(single_clustering)
plt.show()

Dendrogramme de l’approche par chaînage simple

Interpréter les résultats (visualiser le dendrogramme, déterminer le nombre de clusters)

Quel que soit le chaînage, le dendrogramme montre comment chaque point finit par appartenir à un unique cluster.

• L’axe des x représente les échantillons.
• L’axe des y représente la distance entre échantillons/clusters. Plus la ligne est haute, plus les groupes sont dissemblables.
• Pour obtenir le nombre de clusters, on trace une ligne horizontale au niveau de la plus haute ligne verticale et on compte les intersections.

Le nombre optimal de clusters correspond à la plus haute ligne verticale qui n’intersecte aucun autre cluster (ligne horizontale). Elle est indiquée ci-dessous par un cercle rouge et une coche verte.

• Pour le chaînage complet, c’est la ligne bleue de droite, qui donne trois clusters.

Nombre optimal de clusters sans intersection (chaînage complet)

• Pour le chaînage moyen, c’est la première ligne verticale bleue, qui donne deux clusters.

Nombre optimal de clusters sans intersection (chaînage moyen)

• Pour le chaînage simple, c’est la première ligne verticale, qui aboutit à un seul cluster.

Nombre optimal de clusters sans intersection (chaînage simple)

D’après ces observations, le chaînage moyen semble fournir le meilleur partitionnement, contrairement au chaînage simple et complet qui suggèrent respectivement un et trois clusters. Par ailleurs, le nombre optimal de deux correspond à notre connaissance a priori du jeu de données : deux types d’emprunteurs.

Maintenant que nous avons le nombre optimal de clusters, voyons ce qu’ils signifient au regard du score de crédit (fico) des emprunteurs.

cluster_labels = cut_tree(average_clustering, n_clusters=2).reshape(-1, )
without_outliers["Cluster"] = cluster_labels

sns.boxplot(x='Cluster', y='fico', data=without_outliers)

On observe que :

• Les emprunteurs du cluster 0 ont les meilleurs scores de crédit.
• Ceux du cluster 1 ont des scores plus faibles.

Cluster Analysis in Python est une bonne prochaine étape pour approfondir K-means et le clustering hiérarchique avec Scipy.

Conclusion

Nous avons vu ce qu’est le clustering hiérarchique, ses forces et faiblesses, et sa comparaison avec K-means et le clustering basé sur des modèles.

Nous espérons que cet article vous donne les compétences nécessaires pour regrouper efficacement vos données non étiquetées et prendre des décisions actionnables.