Chapitre 5 : Méthodes de Regroupement Non upervisé : Clustering
Dans ce chapitre, vous allez apprendre à développer des modèles de clustering. En machine learning, ce type de
modèle est utilisé lorsque l’on souhaite classer nos données de manière non supervisée. Contrairement à ce que
nous avons vu dans le chapitre précédent, Le clustering regroupe les données en fonction de ce qu’elles se
ressemblent, sans avoir besoin d’étiquettes ou de catégories prédéfinies.
Par exemple :
• Classer des images ou des objets selon leur ressemblance
• Segmenter une base de données de clients, selon leurs habitudes de consommation
• Regrouper des documents selon leur contenu.
• etc.
Le clustering est donc une méthode intéressante lorsqu’on souhaite laisser à la machine le pouvoir
de proposer sa propre solution, et ainsi découvrir une approche différente de la nôtre.
Mise en situation
Ces formes n’ont pas de sens défini (elles peuvent rappeler des étoiles). Imaginez ce qu’elles représentent et
regroupez-les uniquement d’après leurs ressemblances.
Pr Youssef BALOUKI 1
Votre objectif est maintenant de classer ces formes en fonction de leur ressemblance, de
manière à obtenir trois groupes distincts. Dans la plupart des cas, les personnes
identifient spontanément les trois regroupements suivants ::
Les caractéristiques qui vous ont probablement permis de trier ces objets sont la taille et
le nombre de branches de chaque forme. Ainsi, en mesurant ces attributs pour chaque
objet et en les plaçant sur un graphique, on obtient le résultat suivant :
Pr Youssef BALOUKI 2
Sur ce graphique, on distingue très facilement la présence de trois groupes. Est-il alors néces-
saire de superviser l’apprentissage de la machine en désignant des classes y pour que celle-ci
puisse classer ces points? La réponse est non.
Le principe du clustering est d’analyser les différentes variables X qui caractérisent nos données,
afin de regrouper les points en clusters, sans pour autant connaître la nature de ces points.
De nombreux algorithmes permettent de réaliser du clustering :
• Le K-Means Clustering
• Le Clustering hierarchique
• DBSCAN
• OPTICS
• etc.
Fonctionnement du modèle de K-Means Clustering
Le K-Means Clustering est un algorithme itératif, dans lequel on demande à notre machine
de trouver un nombre K de clusters au sein de notre jeu de données. Pour cela, elle place au
hasard K points dans l’espace, puis déplace ces points pour qu’ils deviennent les barycentres
de nos clusters.
Prenons un exemple avec K=3 clusters.
Pour commencer, on place trois points aléa-
toires au sein de nos données. Ces points sont
appelés centroïdes et sont les futurs centres de
masse des clusters que l’on veut former.
Ensuite, on associe chaque point de notre jeu de
données au centroïde dont il est le plus proche,
en calculant la distance euclidienne.
Pr Youssef BALOUKI 3
Ensuite, on déplace chaque centroïde au centre
de son groupe, ce qui explique son nom de ”cen-
troïde”. Pour ce faire, on calcule la moyenne des
points du cluster, et cette moyenne depuis la
nouvelle position du centroïde, d’où le nom de
”K-Means”.
Comme la position de chaque centroïde a
changé, les centroïdes ont désormais des plus
proches voisins différents. Ainsi, nous réitérons
notre algorithme...
... Nous réassignons chaque point à son cen-
troïde le plus proche (notez bien que cela pro-
duit des résultats différents de ceux de la pre-
mière itération !).
... Puis on déplace chaque centroïde au centre
de son groupe.
Pr Youssef BALOUKI 4
Et cet algorithme se répète ainsi jusqu’à ce que
les centroïdes ne bougent plus. C’est alors que
l’algorithme se termine.
Et voilà, c’est ainsi que fonctionne l’algorithme du K-Means clustering. Il vous suffit de
déclarer le nombre de clusters que vous souhaitez obtenir, et l’algorithme s’occupe du reste.
Exemple Complet : K-Means (K = 2)
1) Données de départ
Nous utilisons 6 points en 2 dimensions :
A(1,1), B(1,2), C(2,1), D(8,8), E(9,8), F(8,9).
Ces points forment visuellement deux groupes distincts.
2) Étape 1 : Initialisation des centroïdes
On fixe le nombre de clusters K = 2.
On sélectionne aléatoirement deux points comme centroïdes initiaux :
- μ₁ = (1,1)
- μ₂ = (9,8)
3) Étape 2 : Affectation des points (on attribue chaque point au centroïde le
plus proche)
Chaque point est affecté au cluster dont le centroïde est le plus proche (distance
euclidienne).
Cluster du centroïde μ1= (1,1)
• A → distance = 0
• B = (1,2) → distance = 1
• C = (2,1) → distance = 1
=> vont dans le cluster 1
Cluster du centroïde μ2=(9,8)
• D = (8,8) → distance = 1
• E = (9,8) → distance = 0
• F = (8,9) → distance ≈ 1.41
Pr Youssef BALOUKI 5
=> vont dans le cluster 2
Résultats :
- Cluster 1 : A, B, C
- Cluster 2 : D, E, F
4) Étape 3 : Mise à jour des centroïdes
On recalcule les centroïdes en prenant la moyenne des points de chaque cluster.
Cluster 1 :
μ₁ = ((1+1+2)/3 , (1+2+1)/3) = (1.33 , 1.33)
Cluster 2 :
μ₂ = ((8+9+8)/3 , (8+8+9)/3) = (8.33 , 8.33)
5) Étape 4 : Nouvelle affectation
On recalcule les distances avec les nouveaux centroïdes.
Aucun point ne change de cluster : le modèle a convergé.
6) Résultat final
- Cluster 1 : A, B, C → μ₁ = (1.33 , 1.33)
- Cluster 2 : D, E, F → μ₂ = (8.33 , 8.33)
L’algorithme K-Means a correctement séparé les deux groupes.
Comment choisir le nombre de centroïdes (K) ?
Dans l’exemple ci-dessus, le choix était intuitif : la distribution des points laisse apparaître trois groupes visibles à
l’œil nu, avant même d’entraîner le modèle.
En situation réelle, c’est rarement aussi simple : sur une base clients riche (centaines de variables : habitudes d’achat,
âge, localisation, genre, etc.), la visualisation directe est impossible et il devient difficile d’estimer K.
Dans ce cas, on s’appuie sur une approche objective, la méthode du coude, qui aide à déterminer un nombre de
clusters raisonnable sans inspection visuelle du nuage de points.
Pr Youssef BALOUKI 6
La méthode du coude
La méthode du coude consiste à tester différentes valeurs de K pour l’algorithme du K-Means
Clustering, en mesurant à chaque fois la variance finale de chaque clustering, puis en traçant
sur un graphique l’évolution de cette variance en focntion de K pour identifier une forme de
coude dans le graphique.
Commençons par nous rappeler ce qu’est la variance. Il s’agit de l’écart des points par
rapport à leur moyenne, autrement dit, la distance globale des points d’un cluster par rapport
à leur centroïde.
Variance faible Variance élevée
Maintenant que nous nous rappelons de ce qu’est la variance, reprenons notre jeu de données et
voyons ce qu’il se passe lorsque nous fixons K=1. On observe une grande distance entre les
Pr Youssef BALOUKI 7
points et leur centroïde, ce qui signifie que la variance est donc élevée. Enregistrons cette
valeur de variance sur le graphique de droite, sous la valeur K=1.
En passant à K=2 clusters, la distance moyenne entre les points et leur centroïde respectif
diminue par rapport au cas précédent. Nous ajoutons cette nouvelle valeur à notre graphique
précédent.
En poursuivant avec K=3 clusters, la variance continue de diminuer...
Pr Youssef BALOUKI 8
C’est à partir de maintenant que les choses changent. Pour K=4 clusters, la variance n’est pas
très différente de celle pour K=3. Cela nous indique que nous commençons à diviser un cluster
qui avait déjà une variance assez faible. Nous entrons donc dans un phénomène de sur-
optimisation, ce que nous souhaitons éviter.
On continue de voir ce phénomène pour K-5...
En continuant ainsi jusqu’à K=9, on observe sur notre graphique l’apparition d’une forme de
coude. C’est à ce point que K semble être optimal, ce qui est cohérent avec nos données.
Pr Youssef BALOUKI 9
Dans la pratique, les choses ne sont pas aussi évidentes qu’ici, mais la technique du coude
(elbow method en anglais) est très populaire en clustering pour découvrir comment segmenter un
jeu de données complexe et riche.
Implémentation en Python
Pour développer un modèle de K-Means clustering, nous allons une fois de plus utiliser scikit-
learn, en chargeant le modèle KMeans depuis le module cluster.
1 import numpy as np
2 import m a t p l o t l i b . pyplot as p l t
3 from s k l e a r n . d a t a s e t s import make_blobs
4 from s k l e a r n . c l u s t e r import KMeans
Pour vous démontrer l’efficacité de la méthode du coude, nous allons générer un jeu de
données avec un nombre aléatoire de clusters. Ce nombre nous sera inconnu, et nous devrons
le découvrir à l’aide de la méthode du coude.
1 k = np . random . choice ( [ 2 , 3 , 4 , 5 , 6 , 7 , 8 ] )
2
3 X, _ = make_blobs ( n_samples=200, c e n t e r s=k , n_features =2, c l u s t e r _s t d =0.5)
Pour programmer cette méthode, nous allons utiliser une boucle for, qui nous permettra
d’entraîner un modèle de KMeans pour différentes valeurs de K allant de 1 à 9.
1 k_range = range ( 1 , 10)
2 k _i n e r t i a s = [ ]
3
4 f o r k i n k_range :
5 model = KMeans( n _c l u s t e r s=k ) . f i t (X)
6 k _i n e r t i a s . append ( model . i n e r t i a _ )
7
8 p l t . p l o t ( k_range , k _i n e r t i a s , lw=3)
9 p l t . show ()
Le graphique résultant de cette expérience semble montrer un coude pour la valeur de K = 4
Pr Youssef BALOUKI 10
(Note : Parfois, la position du coude peut être difficile à identifier...)
Ainsi, nous allons créer un modèle KMeans avec un nombre de clusters égal à 4,
l’entraîner sur les données X et observer les résultats.
1 model = KMeans( n _c l u s t e r s =4)
2 model . f i t (X)
3 p r e d i c t i o n s = model . p r e d i c t (X)
4
5 p l t . s c a t t e r (X[ : , 0 ] , X[ : , 1 ] , c=p r e d i c t i o n s )
6 p l t . show ()
On constate que notre jeu de données comprenait bien 4 clusters, et nous avons pu les
identifier grâce à la méthode du coude.
Pr Youssef BALOUKI 11