Le clustering en apprentissage automatique : 5 algorithmes essentiels

Le clustering n’est pas un algorithme unique mais un objectif général. On peut l’atteindre avec divers algorithmes, qui diffèrent sensiblement dans leur définition d’un cluster et dans la manière de les trouver efficacement. 

Se forger une intuition du clustering

Avant d’entrer dans les détails, construisons l’intuition avec un jeu de données jouet sur des fruits. Imaginons une grande collection d’images contenant trois fruits : (i) fraises, (ii) poires et (iii) pommes. 

Dans ce jeu, toutes les images sont mélangées. Votre objectif métier : regrouper les fruits similaires, c’est‑à‑dire former trois groupes, chacun ne contenant qu’un type de fruit. C’est précisément ce que fait un algorithme de clustering. 

Critères clés de réussite pour une analyse de clustering

Contrairement à des cas supervisés comme la classification ou la régression, le clustering ne s’automatise pas de bout en bout. C’est un processus itératif de découverte d’information qui requiert expertise métier et jugement humain, avec des ajustements fréquents des données et des paramètres pour atteindre le résultat souhaité. 

Surtout, comme le clustering est non supervisé et n’utilise pas de données étiquetées, on ne peut pas calculer des métriques telles que l’accuracy, l’AUC, le RMSE, etc., pour comparer des algorithmes ou des techniques de prétraitement. L’évaluation devient donc délicate et en partie subjective. 

Les critères de succès d’un modèle de clustering se résument à :

• Est‑il interprétable ?
• Le résultat est‑il utile pour l’activité ?
• Avez‑vous appris quelque chose de nouveau ou découvert des motifs ignorés avant le clustering ?

Mesurer la qualité d’un clustering

Sans données étiquetées, impossible de calculer accuracy ou AUC. Deux métriques aident à quantifier la séparation des clusters. Deux mesures courantes :

• Le Silhouette Score mesure la similarité d’un point avec son propre cluster par rapport au cluster voisin le plus proche. Il varie de -1 à 1 ; au‑delà de 0,5, les clusters sont généralement bien séparés.
• L’indice de Davies-Bouldin mesure la similarité moyenne entre chaque cluster et son cluster le plus proche — plus c’est faible, mieux c’est.

Ces deux métriques sont disponibles dans scikit-learn : sklearn.metrics.silhouette_score(X, labels) et sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means est l’algorithme de clustering le plus répandu, notamment parce que ses étapes sont simples et son implémentation scikit-learn immédiate. C’est un algorithme à centroïdes pour lequel l’utilisateur doit définir le nombre de clusters à créer. 

Ce nombre peut découler d’un besoin métier ou d’essais de plusieurs valeurs, puis d’une évaluation des résultats. 

K-Means est un algorithme itératif qui produit des clusters non superposés : chaque instance n’appartient qu’à un seul cluster. Pour en saisir l’intuition, suivez les étapes ci‑dessous avec le schéma. Vous trouverez une description détaillée dans nos tutoriels K-Means Clustering in Python et K-Means Clustering in R. 

1. Définir le nombre de clusters.
2. Initialiser aléatoirement les centroïdes en fonction de ce nombre. Dans l’itération 1 ci‑dessous, trois centroïdes aléatoires sont en bleu, rouge et vert.
3. Calculer la distance entre chaque point et chaque centroïde, puis affecter chaque point au centroïde le plus proche.
4. Recalculer la moyenne du centroïde sur la base des points qui lui sont affectés ; sa position évolue au fil des itérations 2 à 9 jusqu’à convergence.
5. Répéter jusqu’à stabilisation de la moyenne des centroïdes ou jusqu’à atteindre le paramètre max_iter (par défaut 300 dans scikit-learn).

Source : Learnbymarketing.com

2. MeanShift

Contrairement à K-Means, l’algorithme MeanShift n’exige pas de préciser le nombre de clusters. Il le détermine automatiquement — un avantage clair quand ce nombre est inconnu. 

MeanShift est également centré sur des centroïdes et affecte itérativement chaque point à des clusters. Son cas d’usage le plus courant : la segmentation d’images.

MeanShift repose sur l’estimation de densité par noyau. Comme K-Means, il déplace itérativement chaque point vers le centroïde le plus proche, initialisé aléatoirement, et fait évoluer la position des points vers la zone la plus dense, c’est‑à‑dire la Mode (la densité la plus élevée de points dans la région, au sens de MeanShift). 

D’où son autre nom : algorithme « chercheur de modes ». Ses étapes :

• Choisir un point aléatoire et créer une fenêtre autour de ce point.
• Calculer la moyenne de tous les points dans cette fenêtre.
• Déplacer la fenêtre dans la direction de la mode. 
• Répéter jusqu’à convergence.

Source : ResearchGate

Pour un pas‑à‑pas de MeanShift en pratique, consultez notre Mean Shift Clustering tutorial.

3. DBSCAN

DBSCAN, pour Density‑Based Spatial Clustering of Applications with Noise, est un algorithme non supervisé fondé sur l’idée que les clusters sont des zones denses séparées par des régions moins denses. 

Son plus grand avantage sur K-Means et MeanShift : il est robuste aux valeurs aberrantes, qu’il n’intègre dans aucun cluster. 

DBSCAN ne demande que deux paramètres : 

• Le rayon du cercle autour de chaque point, appelé epsilon

• minPoints, soit le nombre minimal de points requis dans ce cercle pour classer ce point comme « cœur » (Core).

Chaque point est entouré d’un cercle de rayon epsilon. DBSCAN les identifie comme point « cœur », « bord » (Border) ou « bruit ». Un point est « cœur » si son cercle contient au moins minPoints. Il est « bord » si ce nombre est inférieur, et « bruit » s’il n’y a aucun autre point à une distance epsilon de quelque point que ce soit. Les points bruit ne sont rattachés à aucun cluster (ce sont des outliers).

Cas d’usage fréquents de DBSCAN :

• Excellente séparation entre zones de forte et de faible densité ;
• Efficace sur des jeux de données non linéaires ;
• Utile pour la détection d’anomalies, car il isole les points bruit sans les affecter.

DBSCAN vs K-Means

Principales différences entre DBSCAN et K-Means : 

• K-Means regroupe toutes les instances, alors que DBSCAN n’affecte pas les points bruit (outliers) à un cluster
• K-Means gère mal des clusters non « globaux », DBSCAN s’en sort bien
• K-Means suppose des données issues d’une distribution gaussienne, DBSCAN n’émet pas d’hypothèse sur les données.

Pour aller plus loin, consultez notre guide sur l’algorithme DBSCAN, avec réglage des paramètres et exemples commentés. 

Source : Medium

4. Clustering hiérarchique

Le clustering hiérarchique construit une hiérarchie de clusters. Deux variantes existent. 

• Agglomératif : approche « bottom‑up » où chaque observation est d’abord son propre cluster, puis des paires sont fusionnées progressivement en clusters plus grands. 
• Divisif : approche « top‑down » : toutes les observations commencent dans un même cluster, puis sont scindées récursivement.

Pour l’analyse de données issues des réseaux sociaux, le clustering hiérarchique est particulièrement courant. Les nœuds (branches) d’un graphe sont comparés selon leur similarité, et de petits groupes apparentés se rassemblent en ensembles plus grands.

Son principal avantage : simplicité de compréhension et de mise en œuvre. Le résultat s’analyse souvent via une image appelée dendrogramme.

Apprenez‑en davantage avec notre tutoriel sur le clustering hiérarchique, qui explique la construction et la lecture de dendrogrammes en Python. 

Source : ResearchGate

5. BIRCH

BIRCH signifie Balanced Iterative Hierarchical Based Clustering. Il s’applique à des jeux de données très volumineux, là où K-Means ne passe plus à l’échelle. L’algorithme scinde les données en petits clusters en conservant un maximum d’information. Ces groupes sont ensuite re‑clusterisés pour produire le résultat final, au lieu de traiter d’emblée l’ensemble massif. 

BIRCH est souvent utilisé en complément d’autres algorithmes, en leur fournissant un résumé exploitable. Comme pour K-Means, il faut définir le nombre de clusters à l’entraînement.

Un bénéfice clé : il clusterise de manière progressive et dynamique des points multi‑dimensionnels, pour obtenir la meilleure qualité possible sous des contraintes de mémoire et de temps. Dans la plupart des cas, un seul passage sur la base suffit, ce qui le rend très scalable. 

Cas d’usage typique : alternative économe en mémoire à K-Means pour regrouper de très grands jeux de données que K-Means ne peut traiter pour des raisons de mémoire ou de calcul.

Applications métier du clustering

Le clustering s’applique largement : médias, santé, industrie, retail — partout où vous disposez de grandes quantités de données non étiquetées. Exemples concrets :

Segmentation client

On catégorise les clients selon leurs comportements d’achat ou centres d’intérêt pour concevoir des campagnes marketing ciblées. 

Imaginons 10 millions de clients et le besoin de campagnes personnalisées. Il est irréaliste d’en créer 10 millions : on peut regrouper ces clients en 25 clusters, puis concevoir 25 campagnes au lieu de 10 millions.

Source : Medium

Clustering pour le retail

Les opportunités sont nombreuses dans le commerce. Par exemple, collectez des données par magasin et regroupez au niveau magasin pour repérer des points de vente similaires selon le trafic, le panier moyen, le nombre de références, etc. 

Autre exemple : le clustering par catégorie. Dans le schéma ci‑dessous, nous avons huit magasins. Les couleurs indiquent des clusters différents. On en compte quatre dans cet exemple. 

Remarquez que la catégorie « déodorants » du magasin 1 est en rouge, tandis que celle du magasin 2 est en bleu : ces deux magasins n’adressent pas le même marché cible pour cette catégorie.

Source : dotactiv.com

Clustering en soins cliniques / gestion des maladies

La santé et la recherche clinique offrent des cas particulièrement pertinents. Par exemple, dans l’étude de Komaru & Yoshida et al., 2020, démographie et données de laboratoire de 101 patients sont segmentées en 3 clusters. 

Chaque cluster reflète des conditions différentes. Par exemple, le cluster 1 regroupe des patients avec faible WBC & CRP, le cluster 2 des patients avec BMP & sérum élevés, et le cluster 3 des patients avec sérum faible. Chaque cluster suit une trajectoire de survie différente, à un an après hémodialyse.

Source : elsevierhealth.com

Segmentation d’images

La segmentation d’images consiste à classer une image en groupes distincts. Le clustering y est très étudié : il permet d’isoler des objets pour les analyser individuellement. 

Dans l’exemple ci‑dessous, à gauche l’image d’origine, à droite le résultat du clustering. On distingue clairement 4 clusters, correspondant à 4 objets identifiés via les pixels (tigre, herbe, eau, sable).

Comparer les algorithmes de clustering

scikit-learn, bibliothèque Python de machine learning, implémente 10 algorithmes de clustering non supervisé. Ils diffèrent fondamentalement dans leur manière de définir et d’affecter les clusters. 

Ces différences mathématiques se résument à quatre axes de comparaison :

• Paramètres requis 
• Scalabilité 
• Cas d’usage 
• Géométrie, c’est‑à‑dire la métrique de distance utilisée. 

Dans le schéma ci‑dessous, chaque colonne présente la sortie d’un algorithme différent (K-Means, Affinity Propagation, MeanShift, etc.). Dix algorithmes sont entraînés sur le même jeu de données.

Certains produisent le même résultat : Agglomerative Clustering, DBSCAN, OPTICS et Spectral Clustering donnent ici des clusters identiques. 

En revanche, K-Means et MeanShift diffèrent : K-Means produit deux groupes (bleu et orange), tandis que MeanShift en produit trois (bleu, vert, orange). 

Source : scikit-learn

Il n’y a pas de bonne ou de mauvaise réponse en clustering. On aimerait pouvoir dire « tel algorithme est le meilleur ici ». 

C’est impossible, et c’est précisément ce qui rend le clustering exigeant. 

Au final, le choix de l’algorithme dépend moins d’une métrique simple que de l’interprétation et de l’utilité du résultat pour le cas d’usage.

Comment choisir le bon algorithme de clustering

Chaque algorithme s’adapte à des conditions de données différentes. Utilisez ce tableau comme point de départ, puis testez au moins deux options sur vos données réelles avant de trancher.

Point de départ pratique : essayez d’abord K-Means pour la rapidité, passez à DBSCAN si vos données ont des formes irrégulières ou des outliers, et utilisez le clustering hiérarchique si vous souhaitez explorer visuellement la structure via un dendrogramme avant de choisir k.

Dernières réflexions

Le clustering est plus difficile à mettre en œuvre que des techniques supervisées comme la classification et la régression pour deux raisons : on ne peut pas mesurer la performance contre des cibles étiquetées, et des paramètres comme le nombre de clusters exigent un jugement métier plutôt qu’une sélection algorithmique. 

Le clustering est une compétence précieuse pour de nombreux rôles : data scientists, ingénieurs ML et analystes y sont régulièrement confrontés. 

Pour approfondir le clustering et l’apprentissage non supervisé, et apprendre l’implémentation en Python et R, ces cours vous aideront à progresser : 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R