DBSCAN

Intermédiaire 40 min 13 sections

La densité remplace le nombre de groupes à fixer d'avance, et ce qui reste isolé est étiqueté bruit.

Télécharger le CSV Télécharger le script Python

Objectifs d'apprentissage

Comprendre le clustering basé sur la densité
Distinguer DBSCAN de K-Means
Détecter les outliers automatiquement
Régler les paramètres eps et min_samples

Prérequis

Module K-Means Clustering recommandé

Théorie

K-Means vs DBSCAN

K-Means fonctionne bien pour des clusters sphériques de taille similaire. Mais que faire si:

Les clusters ont des formes irrégulières?
Il y a des outliers/anomalies?
On ne connaît pas le nombre de clusters?

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) résout ces problèmes!

Concepts clés:

Epsilon (eps): Rayon de voisinage
Min_samples: Minimum de voisins pour être un "core point"
Core point: Point avec >= min_samples voisins dans son eps
Border point: Point dans le voisinage d'un core point
Noise point: Ni core ni border (outlier!)

Avantages:

Détecte automatiquement le nombre de clusters
Trouve des clusters de formes arbitraires
Identifie les outliers
Pas besoin de spécifier k

Inconvénients:

Difficulté avec des densités variables
Sensible aux paramètres eps et min_samples

Théorie

Schéma: Fonctionnement de DBSCAN

Types de points:

flowchart TD subgraph Points ["Classification des Points"] CP["Core Point
(>= min_samples voisins)
ROUGE"] BP["Border Point
(voisin d'un core point)
ORANGE"] NP["Noise Point
(outlier)
GRIS"] end class CP ml-node-accent class BP ml-node-brand class NP ml-node-muted

Algorithme:

flowchart TD S["Choisir un point
non visite"] V["Compter les voisins
dans eps"] C{">= min_samples?"} CORE["Core Point
Commencer cluster"] CHECK["Border ou Noise?"] EXPAND["Etendre le cluster
aux voisins"] S --> V --> C C -->|OUI| CORE --> EXPAND C -->|NON| CHECK EXPAND --> S class CORE ml-node-accent

Comparaison avec K-Means:

flowchart LR subgraph KM ["K-Means"] K1["Clusters sphériques"] K2["Nombre k requis"] K3["Pas d'outliers"] end subgraph DB ["DBSCAN"] D1["Formes arbitraires"] D2["k automatique"] D3["Détecte outliers"] end class K1 ml-node-muted class K2 ml-node-muted class K3 ml-node-muted class D1 ml-node-success class D2 ml-node-success class D3 ml-node-success

Exemple concret avec code couleur - Classification d'un point:

Nouveau point P: $\textcolor{#3498db}{x = 3.0}$, $\textcolor{#e67e22}{y = 2.5}$ Paramètres: $\textcolor{#9B7AC4}{eps = 0.5}$, $\textcolor{#F7E64D}{min\_samples = 3}$

Étape 1 - Compter les voisins dans le rayon eps:

Points dans le rayon $\textcolor{#9B7AC4}{eps = 0.5}$ autour de P:

$\textcolor{#27ae60}{P_1}$: distance = $\textcolor{#27ae60}{0.3}$ ✓
$\textcolor{#27ae60}{P_2}$: distance = $\textcolor{#27ae60}{0.4}$ ✓
$\textcolor{#27ae60}{P_3}$: distance = $\textcolor{#27ae60}{0.2}$ ✓
$\textcolor{#e74c3c}{P_4}$: distance = $\textcolor{#e74c3c}{0.8}$ ✗ (hors rayon)

Étape 2 - Vérifier min_samples:

Voisins trouves: $\textcolor{#27ae60}{3}$ (incluant P lui-même = 4) $\textcolor{#27ae60}{4} \geq \textcolor{#F7E64D}{3}$ → Condition satisfaite!

Résultat: P est un $\textcolor{#27ae60}{\mathbf{CORE\ POINT}}$

Si voisins < min_samples:

Voisin d'un core point → $\textcolor{#e67e22}{\mathbf{BORDER\ POINT}}$
Aucun core point proche → $\textcolor{#e74c3c}{\mathbf{NOISE\ (outlier)}}$

Légende des couleurs:

$\textcolor{#3498db}{Bleu}$: coordonnée X du point
$\textcolor{#e67e22}{Orange}$: coordonnée Y du point
$\textcolor{#9B7AC4}{Violet}$: paramètre eps (rayon)
$\textcolor{#F7E64D}{Jaune}$: paramètre min_samples
$\textcolor{#27ae60}{Vert}$: voisins valides / core point
$\textcolor{#e74c3c}{Rouge}$: point hors rayon / noise

Avancé Exercice manuel: À vous de calculer!

Objectif: Appliquer DBSCAN à la main (voisinage, points cœur, clusters).

CONTEXTE

5 points en 1D : A=1, B=2, C=3, D=10, E=11

Paramètres DBSCAN :

epsilon (eps) = 1.5 (rayon du voisinage)
min_samples = 2

PARTIE 1 : Voisinages

1.1) Listez les voisins de chaque point (distance <= eps) 1.2) Combien de voisins à chaque point (lui-même inclus) ?

PARTIE 2 : Classification des points

Un point est "cœur" si |voisinage| >= min_samples

2.1) Quels points sont des points cœur ? 2.2) Quels points sont des points frontière ? 2.3) Y a-t-il des points bruit ?

PARTIE 3 : Formation des clusters

3.1) Combien de clusters DBSCAN trouve-t-il ? 3.2) Quels points sont dans chaque cluster ?

Avancé Solution de l'exercice manuel

SOLUTION DÉTAILLÉE

Points : A=1, B=2, C=3, D=10, E=11, eps=1.5, min_samples=2

PARTIE 1 : Voisinages

1.1) Voisins (distance <= 1.5) :

A(1) : {A, B} (B à distance 1)
B(2) : {A, B, C} (A à dist 1, C à dist 1)
C(3) : {B, C} (B à distance 1)
D(10) : {D, E} (E à distance 1)
E(11) : {D, E} (D à distance 1)

1.2) Nombre de voisins :

Point	Voisins	Nb
A	{A,B}	2
B	{A,B,C}	3
C	{B,C}	2
D	{D,E}	2
E	{D,E}	2

PARTIE 2 : Classification des points

2.1) Points cœur (>= 2 voisins) :

$\textcolor{#e74c3c}{\text{Tous les points sont des points cœur !}}$

(A, B, C, D, E ont tous >= 2 voisins)

2.2) Points frontière : $\textcolor{#27ae60}{\text{Aucun}}$

2.3) Points bruit : $\textcolor{#27ae60}{\text{Aucun}}$

PARTIE 3 : Formation des clusters

3.1) Nombre de clusters : $\boxed{2}$

3.2) Composition :

$\textcolor{#3498db}{Cluster 1}$ : A, B, C (connectes via B)
$\textcolor{#e67e22}{Cluster 2}$ : D, E (connectes directement)

Les clusters 1 et 2 sont séparés car aucun point de {A,B,C} n'est à distance <= 1.5 de {D,E}.

Distance minimale : |C - D| = |3 - 10| = 7 > 1.5

$\boxed{\text{DBSCAN détecte automatiquement 2 groupes naturels}}$

Légende : $\textcolor{#3498db}{Bleu}$: Cluster 1, $\textcolor{#e67e22}{Orange}$: Cluster 2

Code

Explorer les données

Ctrl+Entrée

Cliquez sur "Exécuter" pour voir le résultat