DBSCAN clustering : Guide complet — Principes, Exemples et Implémentation Python

Résumé

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est l’un des algorithmes de clustering les plus puissants du machine learning non supervisé. Contrairement au K-Means qui impose des clusters sphériques et exige de connaître à l’avance leur nombre, DBSCAN découvre automatiquement des clusters de forme quelconque en se basant sur la densité locale des données. Il identifie également les points de bruit (outliers) sans paramètre supplémentaire. Ce guide couvre en détail le principe mathématique, l’implémentation pratique en Python avec scikit-learn, le réglage des hyperparamètres et les cas d’usage concrets.

Principe mathématique de DBSCAN

Les trois types de points

DBSCAN classe chaque point de l’ensemble de données en l’une des trois catégories suivantes :

Point cœur (core point) — Un point est dit cœur si son voisinage de rayon eps contient au moins min_samples points (lui-même inclus). En d’autres termes, un point cœur se trouve dans une région suffisamment dense pour justifier la création ou l’extension d’un cluster.

Point frontière (border point) — Un point est frontière s’il n’est pas un point cœur, mais il se trouve dans le voisinage eps d’au moins un point cœur. Il appartient donc au cluster de ce point cœur sans en être un élément central.

Point de bruit (noise point) — Un point qui n’est ni cœur ni frontière. Il est isolé de toute région dense et se voit attribué le label -1, signifiant qu’il ne fait partie d’aucun cluster.

Le paramètre eps : rayon de voisinage

Le paramètre eps (epsilon) définit le rayon du voisinage autour de chaque point. Pour un point p, son voisinage eps comprend tous les points q tels que la distance entre p et q est inférieure ou égale à eps :

N_eps(p) = { q ∈ D | distance(p, q) ≤ eps }

Où D est l’ensemble de toutes les données. Plus eps est grand, plus le voisinage est large et plus il est facile d’étendre un cluster. À l’inverse, un eps trop petit fragmente les clusters naturels en de nombreux petits groupes.

Le paramètre min_samples : densité minimale

Le paramètre min_samples détermine le nombre minimal de points requis dans le voisinage eps pour qu’un point soit considéré comme point cœur. Une valeur courante par défaut est min_samples = 5, mais elle doit être ajustée selon la dimensionalité et la densité du jeu de données.

Expansion de cluster par reachabilité

Le cœur de l’algorithme repose sur la notion de reachabilité par densité :

1. Un point q est directement reachable depuis un point cœur p si q ∈ N_eps(p).
2. Un point q est reachable par densité depuis p s’il existe une chaîne de points p_1, p_2, …, p_n où p_1 = p, p_n = q, et chaque p_{i+1} est directement reachable depuis p_i (tous les points intermédiaires étant des points cœurs).
3. Deux points sont connectés par densité s’ils sont tous deux reachable par densité depuis un même point cœur.

Un cluster est alors défini comme l’ensemble maximal de points mutuellement connectés par densité. L’algorithme procède en parcourant les données et, pour chaque point cœur non encore visité, en lançant une expansion DFS ou BFS qui récupère tous les points reachable par densité.

Complexité algorithmique

La complexité temporelle de DBSCAN dépend de la méthode utilisée pour la recherche de voisinage :

• Naïve (recherche linéaire) : O(n²) où n est le nombre de points.
• Avec arbre spatial (BallTree, KDTree) : O(n · log n) en moyenne dans des espaces de faible dimension.
• Pour des dimensions élevées, la performance décline en raison de la malédiction de la dimensionalité.

Intuition : comprendre DBSCAN simplement

Imaginez que vous survolez une carte de population mondiale vue d’avion, de nuit. Vous voyez des zones lumineuses denses (les villes), des périphéries moins denses (banlieues) et de vastes zones sombres (campagnes, déserts, océans).

DBSCAN fonctionne exactement de la même manière dans un espace de données :

• Les zones denses forment des clusters — comme des îles de population dans un océan de données. Peu importe leur forme : un cluster peut être circulaire, allongé, en croissant, en anneau… DBSCAN les détecte tous.
• Les zones vides sont du bruit — les points isolés dans des régions peu denses sont simplement étiquetés comme outliers.
• Pas besoin de fixer le nombre de clusters — contrairement au K-Means où vous devez choisir k, DBSCAN détermine seul combien de structures denses existent dans vos données.

Cette intuition est précieuse : si vos données contiennent des structures de densité distincte séparées par des régions peu denses, DBSCAN est un excellent candidat. Si les données sont uniformément distribuées, aucun algorithme de clustering ne produira de résultat significatif.

Implémentation Python avec scikit-learn

Exemple de base avec make_moons

Le jeu de données make_moons illustre parfaitement l’avantage de DBSCAN sur K-Means. Les deux clusters ont une forme de croissant imbriqués — une structure que K-Means ne peut pas capturer parce qu’il suppose que les clusters sont convexes et sphériques.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import silhouette_score

# Générer les données en forme de croissants
X, y_true = make_moons(n_samples=500, noise=0.05, random_state=42)

# DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=5)
dbscan_labels = dbscan.fit_predict(X)

# Compter les clusters et le bruit
n_clusters_dbscan = len(set(dbscan_labels)) - (1 if -1 in dbscan_labels else 0)
n_noise_dbscan = list(dbscan_labels).count(-1)

# KMeans pour comparaison
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans_labels = kmeans.fit_predict(X)

# Silhouette scores
# On exclut les points de bruit du calcul
mask = dbscan_labels != -1
if n_clusters_dbscan > 1 and mask.sum() > n_clusters_dbscan:
    sil_dbscan = silhouette_score(X[mask], dbscan_labels[mask])
    print(f"DBSCAN Silhouette : {sil_dbscan:.4f}")

sil_kmeans = silhouette_score(X, kmeans_labels)
print(f"KMeans Silhouette : {sil_kmeans:.4f}")

# Visualisation
fig, axes = plt.subplots(1, 3, figsize=(15, 4))

axes[0].scatter(X[:, 0], X[:, 1], c=y_true, cmap='viridis', s=10)
axes[0].set_title('Vérité terrain')

axes[1].scatter(X[:, 0], X[:, 1], c=dbscan_labels, cmap='plasma', s=10)
axes[1].set_title(f'DBSCAN ({n_clusters_dbscan} clusters, {n_noise_dbscan} bruit)')

axes[2].scatter(X[:, 0], X[:, 1], c=kmeans_labels, cmap='plasma', s=10)
axes[2].set_title('KMeans (k=2)')

plt.tight_layout()
plt.savefig('dbscan_vs_kmeans_moons.png', dpi=150)
plt.show()

Sur ce jeu de données, DBSCAN retrouve parfaitement les deux croissants avec un silhouette score supérieur à celui de K-Means. Ce dernier coupe les croissants en deux selon une frontière linéaire, ce qui est une mauvaise partition.

Détection de bruit avec des données synthétiques

from sklearn.datasets import make_blobs

# Créer des blobs avec des outliers
X_blobs, _ = make_blobs(n_samples=300, centers=3, cluster_std=0.8,
                        random_state=42)
outliers = np.random.uniform(-12, 12, size=(20, 2))
X_all = np.vstack([X_blobs, outliers])

dbscan = DBSCAN(eps=1.0, min_samples=5)
labels = dbscan.fit_predict(X_all)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print(f"Clusters détectés : {n_clusters}")
print(f"Points de bruit : {n_noise}")
print(f"Labels uniques : {set(labels)}")

DBSCAN identifie automatiquement les 20 outliers comme bruit (label -1) tout en préservant les trois clusters naturels. K-Means, lui, forcerait chaque outlier dans l’un des trois clusters, ce qui déplacerait les centroïdes et dégraderait la qualité du partitionnement.

Hyperparamètres de DBSCAN

eps (epsilon)

Description : Rayon maximum du voisinage pour considérer deux points comme voisins.

Impact :
– eps trop petit : la majorité des points sont classés comme bruit. L’algorithme sur-découpe les données.
– eps trop grand : des clusters distincts se fusionnent en un seul groupe massif.
– Valeur recommandée : utilisez la méthode de la courbe k-distances pour un choix éclairé.

from sklearn.neighbors import NearestNeighbors

# Courbe k-distances pour choisir eps
k = 5
nn = NearestNeighbors(n_neighbors=k)
nn.fit(X_all)
distances, indices = nn.kneighbors(X_all)

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

plt.figure(figsize=(8, 4))
plt.plot(distances_k)
plt.axhline(y=1.0, color='r', linestyle='--', label='eps=1.0')
plt.xlabel('Points triés')
plt.ylabel(f'Distance au {k}-ième voisin')
plt.title('Courbe k-distances pour le choix de eps')
plt.legend()
plt.show()

Le coude (elbow) de cette courbe indique une bonne valeur de eps.

min_samples

Description : Nombre minimum de points dans le voisinage eps pour qu’un point soit considéré comme point cœur.

Règle pratique : une valeur courante est min_samples ≥ D + 1 où D est la dimensionalité des données. Pour des données 2D, min_samples = 5 est un bon point de départ. Pour des données bruitées, augmentez cette valeur.

metric

Description : Distance utilisée pour la recherche de voisinage.

Options courantes :
– 'euclidean' (défaut) : distance euclidienne standard.
– 'manhattan' : distance de Manhattan (somme des différences absolues).
– 'cosine' : similarité cosinus, utile pour les données textuelles.
– 'haversine' : distance géodésique sur une sphère, idéale pour les coordonnées GPS.

algorithm

Description : Méthode de recherche des voisins.

Options :
– 'auto' (défaut) : scikit-learn choisit automatiquement le meilleur algorithme.
– 'ball_tree' : efficace pour les dimensions modérées.
– 'kd_tree' : rapide en faible dimension.
– 'brute' : recherche exhaustive, nécessaire pour certaines métriques comme ‘haversine’.

Avantages et limites de DBSCAN

Avantages

1. Pas besoin de spécifier le nombre de clusters — l’algorithme le détermine automatiquement à partir de la structure des données.
2. Détection de clusters de forme arbitraire — contrairement au K-Means qui ne trouve que des clusters convexes, DBSCAN détecte des formes complexes, allongées, en anneaux, etc.
3. Détection intrinsèque du bruit — les outliers sont identifiés naturellement sans paramètre supplémentaire ni algorithme séparé.
4. Résultats déterministes — contrairement au K-Means dont le résultat dépend de l’initialisation aléatoire, DBSCAN produit toujours le même résultat pour des données et paramètres donnés.
5. Peu d’hypothèses sur la distribution — ne suppose ni une distribution gaussienne ni une forme particulière des clusters.

Limites

1. Difficulté avec les densités variables — si vos clusters ont des densités très différentes (un cluster très dense et un cluster très diffus), un seul couple (eps, min_samples) ne peut pas bien les capturer simultanément. Des algorithmes comme HDBSCAN résolvent ce problème.
2. Sensibilité aux hyperparamètres — le choix de eps est critique et non trivial. Une mauvaise valeur conduit soit à trop de bruit, soit à une fusion excessive de clusters.
3. Performance en haute dimension — comme tous les algorithmes basés sur la distance, DBSCAN souffre de la malédiction de la dimensionalité. Au-delà de quelques dizaines de dimensions, les distances perdent leur pouvoir discriminant.
4. Points frontières ambigus — un point frontière appartenant au voisinage de plusieurs points cœurs de clusters différents peut être attribué arbitrairement à l’un des clusters selon l’ordre de parcours des données.

4 cas d’usage concrets de DBSCAN

1. Géolocalisation et analyse spatiale

DBSCAN excelle naturellement dans les données géographiques. La métrique 'haversine' permet de calculer des distances réelles sur la surface terrestre. On l’utilise pour détecter des zones de forte concentration : points d’intérêt touristiques, zones de criminalité, clusters de livraisons, ou encore détection de trajectoires anormales dans les données GPS.

# Exemple approximatif avec coordonnées GPS
from sklearn.preprocessing import StandardScaler

coordonnees_gps = np.array([
    [48.8566, 2.3522],  # Paris
    [48.8600, 2.3400],
    [45.7640, 4.8357],  # Lyon
    [45.7700, 4.8300],
    [43.2965, 5.3698],  # Marseille
])

# Pour des données réelles, utiliser metric='haversine'
scaler = StandardScaler()
X_scaled = scaler.fit_transform(coordonnees_gps)

dbscan_geo = DBSCAN(eps=0.5, min_samples=2, metric='euclidean')
labels_geo = dbscan_geo.fit_predict(X_scaled)

2. Détection d’anomalies en cybersécurité

En analysant les logs réseau, les connexions normales forment des clusters denses de comportements typiques. Les activités suspectes — tentatives d’intrusion, exfiltration de données, mouvements latéraux — apparaissent comme des points isolés ou de micro-clusters. DBSCAN identifie automatiquement ces anomalies sans qu’on ait besoin de définir des règles explicites.

3. Analyse d’images et segmentation

En vision par ordinateur, DBSCAN peut être utilisé pour segmenter des images basées sur la similarité des pixels (couleur, texture, position spatiale). Contrairement au K-Means qui impose un nombre fixe de segments, DBSCAN découvre le nombre naturel de régions homogènes et isole les pixels aberrants. C’est particulièrement utile pour la détection de contours ou l’extraction d’objets.

4. Analyse de données génomiques

En bioinformatique, le clustering de données d’expression génique repose souvent sur DBSCAN. Les gènes co-exprimés forment des clusters denses dans l’espace des mesures, tandis que les gènes au comportement atypique sont identifiés comme bruit. Cela permet aux chercheurs de découvrir des groupes de gènes fonctionnellement liés sans présupposer du nombre de groupes biologiques pertinents.

Tableau comparatif : DBSCAN vs K-Means

Conclusion

DBSCAN est un algorithme de clustering fondamental qui résout deux problèmes majeurs du K-Means : la nécessité de connaître le nombre de clusters et l’incapacité à détecter des formes non convexes. Son principe basé sur la densité lui permet de distinguer naturellement les structures significatives du bruit, ce qui en fait un outil précieux pour l’exploration de données.

La clé du succès avec DBSCAN repose sur un réglage judicieux de eps et min_samples. La courbe k-distances est votre meilleure alliée pour ce choix. Si vos données présentent des densités très hétérogènes, envisagez HDBSCAN, une extension moderne qui surmonte cette limitation.

Voir aussi

• Calculer la Surface Minimale d’un Polygone Convexe en Grille avec Python
• Calcul des Sommes des Carrés des Diviseurs Unitaires en Python : Guide Complet et Code Optimisé