Travaux Pratiques
Clustering Hiérarchique et DBSCAN
Classes SPE - Institut Préparatoire aux Études
Scientifiques et Techniques (IPEST)
Encadré par :
Mohamed Amine BEN AMOR
Date : 3 décembre 2024
IPEST - Classes SPE Travaux Pratiques
Introduction
Ce cours-TP introduit deux nouveaux algorithmes de clustering et de classification
qui complètent les concepts que vous avez déjà étudiés avec K-means.
Objectifs :
— Comprendre les principes du clustering hiérarchique, une méthode basée sur la
construction de structures arborescentes (dendrogrammes).
— Découvrir DBSCAN, un algorithme de clustering basé sur la densité qui peut
identifier des clusters de forme arbitraire et détecter les points de bruit.
Ces algorithmes sont :
— Relativement simples à implémenter, ce qui les rend accessibles pour une ap-
plication pratique.
— Flexibles, car ils ne nécessitent pas toujours de spécifier un nombre de clusters à
l’avance.
— De bons candidats pour des sujets de concours en raison de leur structure
logique et de leur utilisation dans des problèmes réels.
Pourquoi sont-ils importants ? Comme K-means, ces algorithmes permettent d’ex-
traire des structures intéressantes dans les données, mais ils offrent des approches complémentaires :
— Le clustering hiérarchique aide à explorer les relations entre les clusters grâce
à une vision hiérarchique.
— DBSCAN est adapté aux ensembles de données bruyants et aux clusters de densité
variable.
Ce cours vous guidera pas à pas dans la compréhension et l’implémentation de ces algo-
rithmes, tout en renforçant vos compétences en programmation et en analyse de données.
1 Qu’est-ce que le clustering hiérarchique ?
Le clustering hiérarchique est une méthode d’analyse des données qui construit
une hiérarchie de clusters. Cette approche peut être représentée sous forme d’un dendro-
gramme, une structure en arbre illustrant les regroupements successifs.
Applications :
— Bio-informatique (classification des espèces).
— Analyse de documents (groupement de textes similaires).
— Marketing (segmentation de la clientèle).
1.1 Deux types de clustering hiérarchique
Le clustering hiérarchique se divise en deux catégories principales :
— Agglomératif : commence par des clusters individuels et les fusionne successive-
ment.
— Divisif : commence par un cluster global et divise les données en sous-clusters.
1
IPEST - Classes SPE Travaux Pratiques
1.2 Méthodes de liaison (linkage)
La méthode de liaison définit comment la distance entre deux clusters est calculée.
Voici les trois principales méthodes :
— Liaison simple (Single Linkage) : distance minimale entre deux points appar-
tenant à des clusters différents.
— Liaison complète (Complete Linkage) : distance maximale entre deux points
appartenant à des clusters différents.
— Liaison moyenne (Average Linkage) : moyenne des distances entre tous les
points des deux clusters.
1.3 Dendrogramme
Un dendrogramme est un graphique qui représente les étapes de regroupement des
clusters. Voici un exemple de dendrogramme :
Distance
A B C D E Points
Lecture :
— L’axe vertical représente les distances de regroupement.
— Plus la distance est grande, plus les clusters sont dissemblables.
1.4 Algorithme
Voici les étapes principales pour le clustering hiérarchique agglomératif :
1. Initialisez chaque point comme un cluster individuel.
2. Calculez les distances entre tous les clusters.
2
IPEST - Classes SPE Travaux Pratiques
3. Fusionnez les deux clusters les plus proches.
4. Répétez jusqu’à ce qu’il ne reste qu’un seul cluster.
Complexité : L’algorithme a une complexité en temps de O(n3 ) pour un ensemble de
n points.
1.5 Avantages et inconvénients
— Avantages :
— Pas besoin de définir le nombre de clusters à l’avance.
— Facile à interpréter grâce au dendrogramme.
— Inconvénients :
— Sensible aux valeurs aberrantes.
— Coût de calcul élevé pour des ensembles de données volumineux.
2 Qu’est-ce que DBSCAN ?
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est
un algorithme de clustering basé sur la densité. Il regroupe des points proches en fonction
d’une densité minimale et marque les points isolés comme du bruit.
2.1 Concepts clés
DBSCAN repose sur trois notions importantes :
— Éps (eps) : Rayon d’un voisinage autour d’un point.
— MinPts (min samples) : Nombre minimum de points requis pour qu’un voisinage
soit considéré comme dense.
— Types de points :
— Core Point : Point ayant au moins MinPts voisins dans un rayon eps.
— Border Point : Point situé dans le voisinage d’un Core Point, mais n’étant
pas lui-même un Core Point.
— Noise Point : Point qui n’est ni Core ni Border.
2.2 Illustration des concepts
L’illustration ci-dessous montre les différents types de points selon DBSCAN :
Border Point
Core Point Noise Point
Éps
3
IPEST - Classes SPE Travaux Pratiques
2.3 Algorithme
1. Choisir un point non visité.
2. Trouver tous les voisins dans un rayon eps.
3. Si le point est un Core Point :
— Créer un nouveau cluster et inclure ses voisins directs.
— Étendre le cluster en ajoutant les voisins des Core Points connectés.
4. Si le point n’est pas un Core Point, le marquer comme bruit ou Border Point.
5. Répéter jusqu’à ce que tous les points soient visités.
2.4 Avantages et inconvénients
— Avantages :
— Détecte les clusters de forme arbitraire.
— Identifie les points de bruit (outliers).
— Inconvénients :
— Sensible au choix des hyperparamètres (eps et MinPts).
— Performances limitées pour les grands ensembles de données.
4
IPEST - Classes SPE Travaux Pratiques
3 Le TP
3.1 Objectifs
Dans ce TP, vous allez :
— Générer des données synthétiques pour des algorithmes de clustering.
— Comprendre et implémenter le clustering hiérarchique avec la méthode de liai-
son simple.
— Appliquer l’algorithme DBSCAN pour détecter des clusters de densité variable.
— Visualiser et interpréter les résultats.
3.2 Matériel autorisé
— Utilisation des bibliothèques NumPy et Matplotlib.
— Vous ne devez pas utiliser des bibliothèques de clustering externes (comme Scikit-
learn pour les algorithmes).
3.3 Exercice 1 : Génération de données
Question 1 : Écrivez une fonction generate data qui génère des données 2D aléatoires
organisées en plusieurs clusters.
— Les données doivent être centrées autour de centres donnés, avec une dispersion
aléatoire.
— La fonction prendra en paramètres :
— n samples per cluster : Nombre de points par cluster.
— cluster centers : Liste des centres des clusters.
— cluster std : Dispersion des points autour des centres.
Question 2 : Affichez les données générées à l’aide d’un nuage de points.
5
IPEST - Classes SPE Travaux Pratiques
3.4 Exercice 2 : Clustering Hiérarchique
Question 1 : Implémentez une fonction calculate distances qui calcule la matrice
des distances carrées entre chaque paire de points.
Question 2 : Implémentez une fonction single linkage qui réalise le clustering hiérarchique
avec la méthode de liaison simple :
— Recherchez les deux clusters les plus proches à chaque étape.
— Fusionnez ces clusters en un seul.
— Gardez une trace de l’historique des fusions.
Question 3 : Implémentez une fonction plot dendrogram pour tracer le dendrogramme
basé sur l’historique des fusions.
Question 4 : Appliquez votre clustering hiérarchique sur les données générées à l’Exer-
cice 1 et visualisez les résultats.
3.5 Exercice 3 : DBSCAN
Question 1 : Implémentez une fonction get neighbors qui identifie les voisins proches
d’un point donné en fonction d’un seuil eps.
Question 2 : Implémentez l’algorithme DBSCAN en suivant ces étapes :
— Déterminez si un point est un core point, un border point, ou du bruit.
— Étendez les clusters en connectant les core points.
Question 3 : Appliquez votre algorithme DBSCAN sur les données générées à l’Exercice
1 et visualisez les résultats.
3.6 Résultats attendus
— Un dendrogramme décrivant les fusions successives des clusters.
— Une visualisation des clusters obtenus par DBSCAN, incluant les points de bruit.
3.7 Conclusion
Expliquez brièvement les différences entre le clustering hiérarchique et DBSCAN :
— Leur approche pour détecter les clusters.
— Leurs avantages et inconvénients respectifs.
