Algorithme de Clustering DBSCAN

Density-Based Spatial Clustering of Applications with Noise

AFOUDA Andréa, AMOUZOUVI Christel, APLOGAN

DJIBODE Médard, FAKEYE Grâce,
GUENDEHOU Larissa, KOUFFOSSI Sylvère, SANYA Fèmi
Encadré par: Mme. TONOU Mélène

Institut de Formation et de Recherche en Informatique

Université d’Abomey-Calavi

January 5, 2026
Plan de la Présentation
Introduction

Définition de DBSCAN

Paramètres de DBSCAN

Types de points

Fonctionnement de l’algorithme

Avantages

Limites

Comparaison avec K-means

Applications

Conclusion
Contexte du Clustering
Qu’est-ce que le clustering ?
Le clustering (ou partitionnement de données) est une méthode
d’apprentissage non supervisé qui vise à regrouper des objets
similaires ensemble.

Méthodes classiques :
K-means : partitionnement par centroı̈des
Clustering hiérarchique : construction d’une hiérarchie
DBSCAN : clustering basé sur la densité

Limites des méthodes traditionnelles

Nécessitent de fixer le nombre de clusters à l’avance
Difficulté avec les formes non-sphériques
Sensibles aux points aberrants (outliers)
Problème traité par DBSCAN
Questions fondamentales :
1. Comment identifier des clusters de formes arbitraires ?
2. Comment détecter automatiquement le nombre de clusters ?
3. Comment gérer les points aberrants (bruit) ?

Idée clé de DBSCAN

Les clusters sont des régions de forte densité séparées par des
régions de faible densité.
Définition de DBSCAN
DBSCAN
Density-Based Spatial Clustering of Applications with Noise
Cet algorithme a été proposé par Martin Ester, Hans-Peter Kriegel,
Jörg Sander et Xiaowei Xu en 1996.

Principe du clustering par densité :

Un cluster = région où la densité de points dépasse un certain
seuil
La densité est mesurée par le nombre de points dans un
voisinage donné
Les zones de faible densité séparent les clusters
Les points isolés sont considérés comme du bruit

“Un cluster est un ensemble maximal de points connectés par

densité”
Paramètres de DBSCAN
DBSCAN nécessite deux paramètres principaux :

ε (Epsilon)
Rayon du voisinage
C’est la distance maximale pour qu’un point soit considéré
comme voisin d’un autre
-Si Eps est trop petit, de nombreux points risquent d’être classés
comme bruit, et les clusters pourraient être fragmentés.
-Si Eps est trop grand, les clusters pourraient fusionner et en-
glober des points de bruit.

MinPts
Nombre minimum de points
Nombre minimal de points dans le voisinage ε (incluant le point
lui-même)
Généralement : MinPts ≥ dimension + 1
Voisinage ε - Définition formelle
Definition (Voisinage ε)
Pour un point p dans un ensemble de données D, le voisinage ε est
défini comme :

Nε (p) = {q ∈ D | dist(p, q) ≤ ε}

Distance euclidienne (la plus couramment utilisée) :

Pour deux points p = (p1 , p2 , ..., pd ) et q = (q1 , q2 , ..., qd ) :
v
u d
uX
dist(p, q) = t (p − q )2 i i
i=1

Remarque
Le choix de la fonction de distance dépend de la nature des
données (Euclidienne, Manhattan, Cosinus, etc.)
Types de points
DBSCAN classifie chaque point en trois catégories :

Point cœur (Core point)

Un point p est un point cœur si :

|Nε (p)| ≥ MinPts

C’est-à-dire qu’il a au moins MinPts points dans son voisinage ε

(lui-même inclus).

Point frontière (Border point)

Un point qui :
N’est pas un point cœur
Se trouve dans le voisinage ε d’au moins un point cœur

Point bruit (Noise point)

Un point qui n’est ni un point cœur ni un point frontière.
Illustration des types de points
Point cœur
Point frontière
n2
Point bruit
n1 p1
p2 p3
q2
q1

Avec ε = 0.7 et MinPts = 4

Relations de densité
Definition (Directement accessible depuis la densité)
Un point q est directement accessible depuis p si :
1. q ∈ Nε (p) (q est dans le voisinage de p)
2. |Nε (p)| ≥ MinPts (p est un point cœur)
Notation : p →ε q

Definition (Accessible depuis la densité)

Un point q est accessible depuis p s’il existe une chaı̂ne de points
p1 , p2 , ..., pn telle que :

p1 = p, pn = q, pi+1 est directement accessible depuis pi

Notation : p ⇝ q

Definition (Connecté par densité)

Deux points p et q sont connectés par densité s’il existe un point
o tel que p et q sont accessibles depuis o.
Étapes principales de DBSCAN
1. Initialisation
Marquer tous les points comme non visités
Initialiser le compteur de clusters à 0

2. Parcours des points

Pour chaque point non visité p :
Calculer son voisinage Nε (p)
Si |Nε (p)| < MinPts : marquer comme bruit
Sinon : créer un nouveau cluster et l’étendre

3. Expansion récursive
Explorer les voisinages des points cœurs trouvés
Ajouter tous les points accessibles au cluster courant
Continuer jusqu’à épuisement de la région dense
Exemple pratique
Données : Points A(1,1), B(1,2), C(2,1), D(2,2), E(2,3), F(6,6),
G(6,7), H(7,6), I(7,7), J(10,10)
Paramètres : ε = 1.5, MinPts = 3

Étape 1 : Calcul des voisinages

Nε (A) = {A, B, C , D}  |N (A)| = 4 ≥ 3 Point cœur
N (B) = {A, B, C , D, E }  |N (B)| = 5 ≥ 3 Point cœur
ε

N (E ) = {B, D, E }  |N (E )| = 3 ≥ 3 Point cœur

ε ε

N (J) = {J}  |N (J)| = 1 < 3 Bruit

ε ε

ε ε

Résultat :
Cluster 1 : {A, B, C, D, E}
Cluster 2 : {F, G, H, I}
Bruit : {J}
Avantages de DBSCAN
1. Découverte automatique du nombre de clusters
Pas besoin de spécifier k à l’avance

2. Détection de formes arbitraires

Clusters non-convexes, en forme de S, anneaux, etc.

3. Robustesse au bruit
Identification et isolation des points aberrants ou bruit

4. Un seul passage sur les données

Efficace avec de grands ensembles de données

5. Déterministe
Résultats reproductibles (sauf pour l’ordre des étiquettes)
Limites de DBSCAN
1. Sensibilité aux paramètres
Choix de ε et MinPts crucial
Pas de méthode universelle pour les déterminer

2. Difficultés avec les densités variables

Un seul ε pour toute la base de données
Problèmes si les clusters ont des densités très différentes

3. Malédiction de la dimensionnalité
Moins performant en haute dimension
Notion de densité devient moins pertinente

4. Complexité temporelle
O(n2 ) sans indexation spatiale
O(n log n) avec R-tree ou KD-tree
Choix des paramètres - Méthode pratique
Méthode du k-distance graph :
1. Calculer la distance au k-ème plus proche voisin pour chaque
point (k = MinPts)
2. Trier ces distances par ordre décroissant
3. Tracer le graphe
4. Chercher le ”coude” : point d’inflexion maximal
5. ε = distance correspondant au coude

Règle empirique pour MinPts :

MinPts ≥ dimension + 1
Souvent : MinPts = 4 pour les données 2D
Pour des données bruitées : augmenter MinPts
Comparaison : DBSCAN vs K-means

Critère K-means DBSCAN

Nombre de clusters Doit être spécifié Découvert automatique
ment
Forme des clusters Sphérique/convexe Arbitraire
Gestion du bruit Tous les points assignés Détection du bruit
Paramètres k (nb clusters) ε, MinPts
Complexité O(nkdi) O(n2 ) ou O(n log n)
Performances Efficace sur grands jeux de Lent et moins efficaces su
données les grands datasets

n = nombre de points, k = nombre de clusters, d = dimension, i

= itérations

Quand utiliser quoi ?

K-means : Clusters sphériques, nombre connu, rapidité
DBSCAN : Formes complexes, bruit, nombre inconnu
Applications de DBSCAN
Domaines d’utilisation variés :

1. Géomatique et SIG
Identification de zones urbaines denses
Détection de points chauds criminels
Analyse de données GPS
Segmentation de terrains

2. Astronomie
Détection d’amas d’étoiles et de galaxies
Identification de structures cosmiques
Analyse de données de télescopes
Segmentation d’images astronomiques

3. IA et data mining
Prétraitement pour d’autres algorithmes
Analyse de réseaux sociaux
Recommandation de produits
Applications (suite)
1. Vision par ordinateur et bioinformatique
Traitement d’images médicales
Analyse de séquences génomiques
Détection de cellules anormales
Segmentation d’images

2. Recherche opérationnelle et logistique

Optimisation des itinéraires
Regroupement de clients
Localisation de dépôts
Analyse de la chaı̂ne d’approvisionnement

3. Détection d’anomalies
Cybersécurité : détection d’intrusions
Finance : détection de fraudes
Maintenance prédictive
Variantes
Améliorations et extensions de DBSCAN :

HDBSCAN (Hierarchical DBSCAN)

Gère les densités variables
Construction d’une hiérarchie de clusters

OPTICS (Ordering Points To Identify the Clustering

Structure)
Produit un ordre des points pour différents niveaux de
densité
Pas besoin de fixer ε à l’avance

ST-DBSCAN (Spatio-Temporal DBSCAN)

Extension pour données spatio-temporelles
Deux paramètres ε (spatial et temporel)
Conclusion
Résumé
DBSCAN est un algorithme de clustering basé sur la densité qui
identifie automatiquement les clusters et détecte le bruit, même
pour des formes de clusters arbitraires. Il repose sur deux
paramètres clés, ε et MinPts, et distingue les points cœurs,
frontières et bruit. Sa grande force réside dans sa flexibilité, sa
robustesse et le fait qu’il ne nécessite pas de connaı̂tre le nombre
de clusters à l’avance. En revanche, il reste sensible aux
paramètres et peut rencontrer des difficultés lorsque les densités
varient. Pour pallier ces limites, plusieurs extensions comme
HDBSCAN, OPTICS, DENCLUE ou ST-DBSCAN ont été
développées, offrant une meilleure adaptabilité et une détection
plus fine des structures complexes.
Questions ?

Merci de votre attention !

Des questions ?
Références I

Références principales :
Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A
density-based algorithm for discovering clusters in large spatial
databases with noise. In KDD (Vol. 96, No. 34, pp. 226-231).
Han, J., Kamber, M., & Pei, J. (2011). Data mining:
concepts and techniques. Elsevier.
Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X.
(2017). DBSCAN revisited, revisited: why and how you
should (still) use DBSCAN. ACM Transactions on Database
Systems (TODS), 42(3), 1-21.