Accueil › Glossaire › DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN est un algorithme de clustering basé sur la densité qui identifie les clusters comme des zones de haute densité séparées par des zones de faible densité, sans nécessiter de fixer le nombre de clusters à l’avance et en détectant automatiquement les outliers.

Publié en 1996 par Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei Xu, DBSCAN est devenu la référence du clustering par densité. Contrairement à K-Means (qui cherche des clusters sphériques compacts), DBSCAN découvre des clusters de forme arbitraire : croissants, spirales, formes irrégulières. C’est le choix idéal quand vous ne connaissez pas le nombre de groupes, quand vos données contiennent du bruit, ou quand les clusters ont des géométries complexes.

Les concepts fondamentaux de DBSCAN

DBSCAN repose sur trois types de points, définis par deux paramètres : epsilon (ε, le rayon de voisinage) et min_samples (le nombre minimum de points pour former une zone dense).

Points noyaux (Core Points)

Un point est un point noyau si son ε-voisinage (le cercle de rayon ε autour de lui) contient au moins min_samples points (lui-même inclus). Les points noyaux sont au cœur des clusters : ce sont les régions de haute densité.

Points frontières (Border Points)

Un point est un point frontière s’il est dans le ε-voisinage d’un point noyau, mais que son propre ε-voisinage contient moins de min_samples points. Il appartient au cluster mais n’est pas assez dense pour être un noyau. Il est en « bordure » du cluster.

Points de bruit (Noise / Outliers)

Un point est du bruit s’il n’est ni point noyau ni point frontière. Il est dans une zone de faible densité, trop éloigné de tout cluster. DBSCAN lui attribue le label -1. C’est ce qui rend DBSCAN naturellement apte à la détection d’anomalies.

L’algorithme DBSCAN pas à pas

Étape 1 : Choisir un point non visité du dataset.

Étape 2 : Calculer son ε-voisinage (tous les points à une distance ≤ ε).

Étape 3 : Si le voisinage contient ≥ min_samples points, ce point est un point noyau. Créer un nouveau cluster et y ajouter ce point et tous ses voisins.

Étape 4 : Pour chaque voisin qui est aussi un point noyau, ajouter récursivement ses propres voisins au cluster. C’est cette expansion récursive qui permet de construire des clusters de forme arbitraire.

Étape 5 : Si le voisinage contient < min_samples points, marquer temporairement le point comme bruit. (Il pourra être reclassé comme point frontière si un cluster ultérieur l’englobe.)

Étape 6 : Répéter jusqu’à ce que tous les points soient visités.

Les deux paramètres de DBSCAN

eps (epsilon) : le rayon de voisinage

Epsilon définit la distance maximale entre deux points pour qu’ils soient considérés comme voisins. C’est le paramètre le plus critique. Un epsilon trop petit crée trop de clusters fragmentés et trop de bruit. Un epsilon trop grand fusionne des clusters distincts en un seul.

Méthode du k-distance graph pour choisir epsilon : calculez la distance au k-ième plus proche voisin pour chaque point (k = min_samples), triez ces distances par ordre croissant et tracez le graphique. Le « coude » de la courbe indique la valeur optimale d’epsilon.

from sklearn.neighbors import NearestNeighbors
import numpy as np
import matplotlib.pyplot as plt

# Calcul des distances au k-ième voisin
k = 5  # = min_samples
neighbors = NearestNeighbors(n_neighbors=k)
neighbors.fit(X_scaled)
distances, _ = neighbors.kneighbors(X_scaled)

# Trier les distances au k-ième voisin
k_distances = np.sort(distances[:, k-1])

# Tracer le k-distance graph
plt.figure(figsize=(8, 5))
plt.plot(k_distances, color='#7c3aed', lw=2)
plt.xlabel('Points (triés par distance)')
plt.ylabel(f'Distance au {k}-ième voisin')
plt.title('K-Distance Graph (coude = epsilon optimal)')
plt.grid(alpha=0.3)
plt.tight_layout()
plt.show()

min_samples : la densité minimale

Le nombre minimum de points dans le ε-voisinage d’un point pour qu’il soit considéré comme point noyau. Règles de pouce :

min_samples ≥ nombre de dimensions + 1 : règle classique de la littérature. Pour des données 2D, min_samples = 3 minimum.

Valeurs plus élevées (10-20) : produisent des clusters plus denses et plus de points classés comme bruit. Plus robuste mais risque de manquer de petits clusters.

Valeurs basses (3-5) : détectent des clusters moins denses et classent moins de points comme bruit. Risque de connecter des clusters distincts.

En pratique, commencez avec min_samples = 5 (défaut scikit-learn) et ajustez en fonction des résultats.

DBSCAN en Python avec scikit-learn

Usage de base

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
import numpy as np

# Standardiser les données
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X_scaled)

# Résultats
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = (labels == -1).sum()
print(f"Clusters trouvés : {n_clusters}")
print(f"Points de bruit : {n_noise}")
print(f"Points noyaux : {len(dbscan.core_sample_indices_)}")

Visualisation avec distinction core/border/noise

import matplotlib.pyplot as plt

# Masque des points noyaux
core_mask = np.zeros(len(labels), dtype=bool)
core_mask[dbscan.core_sample_indices_] = True

# Visualisation
fig, ax = plt.subplots(figsize=(10, 7))

# Points noyaux (gros)
ax.scatter(X_scaled[core_mask, 0], X_scaled[core_mask, 1],
           c=labels[core_mask], cmap='viridis', s=40, alpha=0.8,
           label='Noyaux')

# Points frontières (petits)
border_mask = ~core_mask & (labels != -1)
ax.scatter(X_scaled[border_mask, 0], X_scaled[border_mask, 1],
           c=labels[border_mask], cmap='viridis', s=15, alpha=0.5,
           label='Frontières')

# Bruit (croix noires)
noise_mask = labels == -1
ax.scatter(X_scaled[noise_mask, 0], X_scaled[noise_mask, 1],
           c='black', marker='x', s=20, alpha=0.5,
           label='Bruit')

ax.legend()
ax.set_title(f'DBSCAN : {n_clusters} clusters, {n_noise} outliers')
plt.tight_layout()
plt.show()

Recherche des meilleurs paramètres

from sklearn.metrics import silhouette_score

best_score = -1
best_params = {}

for eps in [0.3, 0.5, 0.7, 1.0, 1.5]:
    for ms in [3, 5, 10, 15]:
        db = DBSCAN(eps=eps, min_samples=ms)
        labels = db.fit_predict(X_scaled)
        n_clusters = len(set(labels)) - (1 if -1 in labels else 0)

        if n_clusters >= 2:
            # Silhouette seulement sur les points non-bruit
            mask = labels != -1
            if mask.sum() > n_clusters:
                score = silhouette_score(X_scaled[mask], labels[mask])
                if score > best_score:
                    best_score = score
                    best_params = {'eps': eps, 'min_samples': ms,
                                   'clusters': n_clusters}

print(f"Meilleurs paramètres : {best_params}")
print(f"Silhouette score : {best_score:.4f}")

DBSCAN vs K-Means : quand utiliser lequel

En résumé : K-Means quand vous connaissez K et que vos clusters sont globalement sphériques. DBSCAN quand K est inconnu, que les formes sont irrégulières, ou que les données contiennent du bruit.

Limites de DBSCAN

Clusters de densité variable

Le principal talon d’Achille de DBSCAN : comme epsilon est un paramètre global, il ne peut pas gérer des clusters de densités très différentes. Un epsilon adapté au cluster dense va fragmenter le cluster peu dense, et inversement. C’est pour cette raison qu’HDBSCAN a été développé.

Haute dimension

En haute dimension, la distance euclidienne perd son pouvoir discriminant (fléau de la dimensionnalité). Les voisinages ε deviennent soit vides (epsilon trop petit) soit englobent tout (epsilon trop grand). Solution : appliquer PCA ou UMAP avant DBSCAN.

Pas de prédiction sur de nouvelles données

L’implémentation scikit-learn de DBSCAN n’a pas de méthode .predict(). Pour assigner de nouveaux points, il faut soit relancer l’algorithme sur l’ensemble complet, soit utiliser une heuristique (distance au centroïde ou au point noyau le plus proche).

Sensibilité aux paramètres

Un mauvais choix d’epsilon ou de min_samples peut produire des résultats très différents : un seul cluster géant ou des milliers de micro-clusters. Le k-distance graph aide, mais ne remplace pas l’expérimentation.

Alternatives et évolutions

HDBSCAN (Hierarchical DBSCAN)

L’évolution majeure de DBSCAN. HDBSCAN construit une hiérarchie de clusters à différents niveaux de densité, puis extrait les clusters les plus persistants. Avantages : un seul paramètre principal (min_cluster_size), gère les densités variables, souvent de meilleurs résultats que DBSCAN. C’est souvent le premier choix pour le clustering exploratoire.

OPTICS

Produit un ordonnancement des points par densité plutôt qu’un clustering fixe. Cet ordonnancement peut être coupé à différents niveaux pour extraire des clusters. Plus flexible que DBSCAN mais plus complexe à interpréter. Disponible dans scikit-learn : sklearn.cluster.OPTICS.

Applications de DBSCAN

Détection d’anomalies : les points classés bruit (label -1) sont des anomalies candidates. Utilisé en détection de fraude, sécurité réseau, contrôle qualité.

Analyse géospatiale : clustering de coordonnées GPS (incidents, transactions, check-ins) pour identifier les zones d’activité. La métrique Haversine est adaptée aux coordonnées géographiques.

Traitement d’images : segmentation de pixels par couleur ou texture, regroupement de points d’intérêt en computer vision.

Bioinformatique : clustering de séquences génétiques, identification de sous-populations cellulaires. Souvent après une réduction par PCA + UMAP.

NLP : clustering de documents ou d’embeddings de phrases pour la découverte de thèmes, souvent via UMAP + HDBSCAN.

Verdict

DBSCAN est l’algorithme de référence quand vous ne savez pas combien de clusters existent, quand les clusters ont des formes non convexes, ou quand vos données contiennent des outliers à identifier. Sa force principale : il ne force pas les données dans un nombre prédéfini de groupes, ce qui en fait un outil d’exploration honnête.

Sa limite principale (densité globale fixe) est résolue par HDBSCAN, qui est souvent le meilleur premier choix pour le clustering exploratoire. En pratique, essayez les deux : DBSCAN pour sa simplicité (deux paramètres), HDBSCAN pour sa robustesse (un seul paramètre clé). Et dans les deux cas, réduisez d’abord la dimensionnalité avec PCA ou UMAP si vous avez plus de 50 features.