Classification non-supervisée
Le clustering
Plan
✓Hierarchical Model
✓DBSCAN
2
Clustering
En machine learning, le clustering permet de regrouper automatiquement les données qui
se ressemblent. On parle d’apprentissage non supervisé car aucune étiquette n’est fournie
à l’avance.
Ici, pas besoin de savoir à l’avance à quelle catégorie appartient chaque donnée : le
regroupement se fait automatiquement par ressemblance.
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.
3
Clustering : Mise en situation
L’image contient différentes espèces d’animaux. Même si
vous ne connaissez pas leurs noms, vous pouvez les
différencier en vous basant sur des caractéristiques
visuelles, comme :
✓ la taille ou la forme du corps,
✓ le type de pattes ou d’ailes,
✓ la posture ou la silhouette générale
Votre tâche consiste à regrouper les animaux qui se ressemblent selon ces critères, sans
indication préalable.
➔C’est exactement ce que fait un algorithme de clustering non supervisé. 4
Clustering : Mise en situation
Les caractéristiques qui vous ont probablement permis
de regrouper ces animaux sont leur silhouette, leur type
de déplacement (vol, marche, reptation) ou encore leur
forme générale.
En représentant ces attributs de manière visuelle ou
numérique, on peut obtenir une répartition naturelle qui
permet de distinguer facilement plusieurs groupes.
Sur cette image, on distingue très facilement la présence de trois
groupes. Est-il alors nécessaire 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.
5
Clustering : Mise en situation
6
Clustering
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
• etc.
7
Le modèle hiérarchique
Qu’est-ce qu’une analyse de regroupement hiérarchique ?
Et comment est-elle calculée ?
Une analyse de regroupement qui crée un arbre hiérarchique
hiérarchique est une méthode de (dendrogramme) d’objets à
clustering, regrouper.
8
Le modèle hiérarchique
L’arbre représente les relations entre les objets, et montre comment
les objets sont regroupés à différents niveaux.
9
Le modèle hiérarchique
Nous voulons maintenant savoir
Ce jeu de données montre
s’il existe des groupes (clusters)
combien d’heures par semaine les
dans ce jeu de données et
gens passent sur les réseaux
effectuer une analyse de
sociaux et à la salle de sport.
regroupement hiérarchique.
Social media Gym
Personne 3 2 3
Personne 1 5 2
Personne 2 5 3
Personne 4 1 4
Personne 5 4 5
10
Comment calcule-t-on une analyse de
regroupement hiérarchique ?
1-La première étape consiste à attribuer un 2-L’objectif maintenant est de fusionner
cluster à chaque point individuel. progressivement de plus en plus de clusters.
Ainsi, nous avons autant de clusters que de
personnes.
P5
P5
P4
P4
P3 P2
P3 P2 P5
P1
P1 P4
P3 P2
P1
3-jusqu’à ce que finalement tous les points soient
dans un seul cluster. 11
Comment calcule-t-on une analyse de
regroupement hiérarchique ?
A chaque étape, les clusters les plus proches sont toujours fusionnés.
Pour cela, nous devons définir deux éléments : P2
1- Comment mesurer la distance entre deux points ? P1
Voici les méthodes les plus populaires :
✓ La distance Euclidienne
✓ La distance de Manhatan
✓ La distance Maximum P3 P2
2- Comment mesurer la distance entre deux clusters composés de plusieurs points ?
Voici les méthodes les plus populaires : P4 P1
✓ Liaison simple (Single-linkage)
✓ Liaison complète (Complete-linkage)
✓ Liaison moyenne (Average-linkage)
12
Comment mesurer la distance entre deux clusters composés de plusieurs points ?
La méthode de liaison simple (Single-linkage) utilise la distance P1 P3
entre les éléments les plus proches dans les clusters.
P2 P4
La méthode de liaison complète (Complete-linkage) utilise la P1 P3
distance entre les éléments les plus éloignés des deux clusters.
P2 P4
La méthode de liaison moyenne (Average-linkage) utilise la P1 P3
moyenne de toutes les distances entre les paires de points des
deux clusters. P2 P4
13
Exemple
Dans notre exemple, nous utilisons la distance euclidienne et la méthode de liaison simple.
Nous avons donc maintenant besoin de la distance de chaque cluster aux autres clusters.
Pour cela, nous devons d’abord calculer la matrice de distances.
P5
P3 P1 P2 P4 P5
P4
P3 0
P2
P1 3.16 0 P3
P2 3.00 1.00 0 P1
P4 1.41 4.47 4.12 0
P5 2.83 3.16 2.24 3.16 0
P5
P4
P3 P2 Dans notre diagramme en
arbre, ou dendrogramme,
P1 nous pouvons tracer la
première connexion.
14
Exemple
Mise à jour de la matrice de distances P5
P4
P3 P1,P2 P4 P5
P2
P3 0 P3
P1,P2 ??? 0 P1
P4 1.41 ??? 0
P5 2.83 ??? 3.16 0
Nous avons décidé d’utiliser la méthode de liaison simple (single-linkage).
Ainsi, la distance entre deux clusters est déterminée par les éléments les
plus proches l’un de l’autre.
P3 P1,P2 P4 P5 P5
P4
P3 0
P3 P2
P1,
3 0
P2 P1
P4 1.41 4.12 0
P5 2.83 2.24 3.16 0
15
Exemple
Mise à jour de la matrice de distances
P5
P3,P4 P1,P2 P5 P4
P3 P2
P3,P4 0
P1
P1,P2 3 0
P5 2.83 2.24 0
P5
P4
P3 P2
P1
16
Exemple
Mise à jour de la matrice de distances
P5
P3,P4 P1,P2,P5 P4
P3 P2
P3,P4 0
P1
P1,P2,
2.83 0
P5
P5
P4
P3 P2
P1
17
Avantages Vs. Inconvénients
Le nombre de clusters correspond au nombre de
branches coupées par une droite horizontale.
Avantages :
✓ Pas besoin de spécifier le nombre de clusters à l’avance
Contrairement à K-Means, on peut observer le
dendrogramme et choisir ensuite où couper.
✓ Convient aux petites bases de données
➔Très utile quand on a peu d’observations mais qu’on veut comprendre leur structure.
✓ Chaque fusion est mémorisée, ce qui permet d’analyser toute la hiérarchie.
Inconvénients :
✓ Sensibilité au bruit et aux valeurs aberrantes
✓ Une fois que deux clusters sont fusionnés, on ne peut plus revenir en arrière.
✓ Moins efficace pour des données de grande dimension ou en grand volume.
✓ Résultat dépend du choix de la méthode de liaison (linkage).
✓ Incapacité à classer de nouvelles données sans tout recalculer. 18
DBSCAN (Density-Based Spatial Clustering of
Applications with Noise)
•Il regroupe les points densément connectés ensemble
(zones à forte densité).
•Il identifie les outliers (bruit) comme les points isolés.
•Il ne nécessite pas de spécifier le nombre de clusters à
l’avance (contrairement à K-Means).
• Il fonctionne très bien dans des situations de non-
linéarité, c’est-à-dire lorsque les clusters ont des
formes complexes ou irrégulières.
19
DBSCAN Vs. K-means
K-means DBSCAN
outilier
20
Fonctionnement de DBSCAN
Epsilon
Epsilon est un hyperparamètre qu’il
faut déterminer.
Par exemple : 𝜀 = 2
Core Point
Min_points est aussi un hyperparamètre
qu’il faut déterminer (Le nombre
minimum de voisins).
Par exemple : Min_points = 5. 𝜀
Si ce point rouge a plus de 5 voisins, on
peut l’appelé core point.
➔ Le point rouge devient un point du
premier cluster
Ensuite, on examine ses voisins pour
vérifier s’ils doivent, eux aussi, être inclus
dans ce même cluster. 21
Fonctionnement de DBSCAN
Epsilon
Epsilon est un hyperparamètre qu’il
faut déterminer.
Par exemple : 𝜀 = 2
Core Point
Min_points est aussi un hyperparamètre
qu’il faut déterminer (Le nombre
minimum de voisins).
Par exemple : Min_points = 5. 𝜀
Si ce point rouge a plus de 5 voisins, on
peut l’appelé core point.
➔ Le point rouge devient un point du
premier cluster.
Ensuite, on examine ses voisins pour
vérifier s’ils doivent, eux aussi, être inclus
dans ce même cluster. 22
Fonctionnement de DBSCAN
𝜀 2
23
DBSCAN
Ici, on dessine un cercle autour du
point, mais il ne contient que 4
voisins. Cela signifie que ce point
n’est pas un point central (core
point), mais un point de bordure
(border point). Par conséquent, ses
voisins ne seront pas explorés pour
rejoindre le premier cluster.
24
DBSCAN
Lorsqu’il n’y a plus de points à explorer dans le cluster en cours, on sélectionne un nouveau
point, encore non visité, pour recommencer le processus et trouver le prochain cluster.
Pour ce point rouge, on
remarque qu’il n’y a
aucun voisin, donc cette
observation ne sera ni
core point ni border
point mais un noise point
25
DBSCAN
26
Validation d’un modèle de clustering
Tightness ou tension
Pour ce jeu de données, on
a une tightness
relativement faible parce
que les données sont
regroupées très proches les
unes des autres
Pour ce jeu de données, on
a une tightness plus élevée
parce que les observations
sont loins les unes des
autres 27
Validation d’un modèle de clustering
Tightness ou tension (distance intra-cluster)
28
Validation d’un modèle de clustering
Séparation des clusters (distance inter-cluster)
On peut ajouter une mesure de séparation des clusters pour juger la pertinence
d’un modèle. Pour chaque cluster, on va calculer son centroid et puis on va calculer
la distance 𝑆𝑘𝑙 qui représente la distance entre chaque centroide. Plus les centroides
sont éloignés plus le modèle a de chance d’être performant.
➔ Modèle performant
➔ Modèle moins performant 29
Exercice
Imaginons 5 amis dans une salle, avec leurs positions sur une carte : A(1, 1.5), B(1.2, 2), C(3,
0.7), D(3.5, 2.2), E(4, 3.5).
Voici à quoi cela ressemble sur une carte :
[Link] la matrice des distances (matrice de dissimilarité) entre les points en utilisant la
distance de Manhattan.
2. Appliquez l’algorithme de regroupement hiérarchique en utilisant la liaison complète.
3. Représentez l’arbre de regroupement sous forme de dendrogramme.
4. En vous basant sur le dendrogramme, proposez un nombre raisonnable de clusters.