DBSCAN

Intermediaire 40 min 13 sections

Maitrisez DBSCAN, un algorithme de clustering base sur la densite qui detecte automatiquement les anomalies.

Telecharger CSV Telecharger Script Python

Objectifs d'apprentissage

Comprendre le clustering base sur la densite
Distinguer DBSCAN de K-Means
Detecter les outliers automatiquement
Tuner les parametres eps et min_samples

Prerequis

Module K-Means Clustering recommande

Theorie

K-Means vs DBSCAN

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

Les clusters ont des formes irregulieres?
Il y a des outliers/anomalies?
On ne connait pas le nombre de clusters?

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) resout ces problemes!

Concepts cles:

Epsilon (eps): Rayon de voisinage
Min_samples: Minimum de voisins pour etre 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:

Detecte automatiquement le nombre de clusters
Trouve des clusters de formes arbitraires
Identifie les outliers
Pas besoin de specifier k

Inconvenients:

Difficulte avec des densites variables
Sensible aux parametres eps et min_samples

Theorie

Schema: 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 style CP fill:#F7E64D,color:#1A1A1A style BP fill:#C09CF0,color:#1A1A1A style NP fill:#6B6B6B,color:#FFFFFF

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 style CORE fill:#F7E64D,color:#1A1A1A

Comparaison avec K-Means:

flowchart LR subgraph KM ["K-Means"] K1["Clusters spheriques"] K2["Nombre k requis"] K3["Pas d'outliers"] end subgraph DB ["DBSCAN"] D1["Formes arbitraires"] D2["k automatique"] D3["Detecte outliers"] end style D1 fill:#F7E64D,color:#1A1A1A style D2 fill:#F7E64D,color:#1A1A1A style D3 fill:#F7E64D,color:#1A1A1A

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

Nouveau point P: $\textcolor{#3498db}{x = 3.0}$, $\textcolor{#e67e22}{y = 2.5}$

Parametres: $\textcolor{#9B7AC4}{eps = 0.5}$, $\textcolor{#F7E64D}{min\_samples = 3}$

Etape 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)

Etape 2 - Verifier min_samples:

Voisins trouves: $\textcolor{#27ae60}{3}$ (incluant P lui-meme = 4)

$\textcolor{#27ae60}{4} \geq \textcolor{#F7E64D}{3}$ → Condition satisfaite!

Resultat: 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)}}$

Legende des couleurs:

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

Avance Exercice manuel: A vous de calculer!

Objectif: Appliquer DBSCAN a la main (voisinage, points coeur, clusters).

CONTEXTE

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

Parametres 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 a chaque point (lui-meme inclus) ?

PARTIE 2 : Classification des points

Un point est "coeur" si |voisinage| >= min_samples

2.1) Quels points sont des points coeur ?

2.2) Quels points sont des points frontiere ?

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 ?

Avance Solution de l'exercice manuel

SOLUTION DETAILLEE

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 a distance 1)
B(2) : {A, B, C} (A a dist 1, C a dist 1)
C(3) : {B, C} (B a distance 1)
D(10) : {D, E} (E a distance 1)
E(11) : {D, E} (D a 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 coeur (>= 2 voisins) :

$\textcolor{#e74c3c}{\text{Tous les points sont des points coeur !}}$

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

2.2) Points frontiere : $\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 separes car aucun point de {A,B,C} n'est a distance <= 1.5 de {D,E}.

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

$\boxed{\text{DBSCAN detecte automatiquement 2 groupes naturels}}$

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

Code

Explorer les donnees

Cliquez sur "Executer" pour voir le resultat