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

Résumé

HDBSCAN (Hierarchical Density-Based Spatial Clustering of Applications with Noise) est un algorithme de clustering non supervisé qui combine les idées du DBSCAN et du clustering hiérarchique. Contrairement au K-Means qui nécessite de fixer le nombre de clusters K à l’avance, ou au DBSCAN qui exige un rayon ε soigneusement calibré, HDBSCAN explore automatiquement la structure hiérarchique des données à travers toutes les échelles de densité et extrait les clusters les plus stables. Résultat : il détecte des clusters de formes arbitraires et de densités variables, identifie naturellement les points aberrants (bruit), et ne requiert aucun choix du nombre de clusters. Cet article détaille les fondements mathématiques, l’intuition algorithmique, l’implémentation pratique en Python, et les cas d’usage concrets d’HDBSCAN.

Principe mathématique

Le fonctionnement d’HDBSCAN repose sur une chaîne de transformations mathématiques rigoureuses qui convertissent l’espace de données d’origine en une hiérarchie de clusters. Comprendre chacune de ces étapes est essentiel pour maîtriser l’algorithme.

1. Distance de cœur (core distance)

Pour chaque point x, on calcule sa distance de cœur core_dist(x), définie comme la distance au k-ième plus proche voisin, où k = min_samples. Cette notion, héritée du DBSCAN, quantifie la densité locale autour de chaque point : un point situé dans une région dense aura une petite distance de cœur, tandis qu’un point dans une région clairsemée aura une distance de cœur élevée.

Formellement :

core_dist(x) = d(x, k-NN(x))

où k-NN(x) désigne le k-ième voisin le plus proche de x et d est la métrique de distance choisie (généralement la distance euclidienne).

2. Distance d’atteinte mutuelle (mutual reachability distance)

C’est la pierre angulaire d’HDBSCAN. Pour toute paire de points (x, y), on définit la distance d’atteinte mutuelle comme :

d_mréachable(x, y) = max(core_dist(x), core_dist(y), d(x, y))

Cette formule est fondamentale. Examinons pourquoi :

• Si les deux points sont dans une région dense : leurs distances de cœur sont petites, donc d(x, y) domine et d_mréachable(x, y) ≈ d(x, y). Les points proches restent proches.
• Si un ou les deux points sont dans une région clairsemée : leurs distances de cœur sont grandes, donc d_mréachable(x, y) est au moins égale à la plus grande distance de cœur. Cela « éloigne artificiellement » les points peu denses de leurs voisins, ce qui a pour effet de dissoudre les ponts fins entre des clusters potentiels.

En d’autres termes, cette distance transforme l’espace de sorte que les régions de faible densité sont « dilatées » tandis que les régions denses restent contractées. C’est ce mécanisme qui permet à HDBSCAN de distinguer naturellement des clusters de densités différentes.

3. Construction du dendrogramme (clustering hiérarchique single-linkage)

Sur le graphe complet des distances d’atteinte mutuelle, HDBSCAN applique un clustering hiérarchique à liaison simple (single-linkage). Ce processus construit un dendrogramme — un arbre binaire ou multinœud — où :

• Chaque point commence comme son propre cluster (feuille de l’arbre).
• À chaque étape, les deux clusters les plus proches (selon la distance d’atteinte mutuelle minimale entre leurs membres) sont fusionnés.
• Le niveau de fusion correspond à la distance d’atteinte mutuelle entre les points qui déclenchent la fusion.

Le résultat est une hiérarchie complète : en coupant l’arbre à différents niveaux, on obtient des partitions avec un nombre différent de clusters. Plus on monte dans l’arbre (seuil élevé), plus les clusters sont grands et peu nombreux ; plus on descend (seuil bas), plus les clusters sont nombreux et fins.

4. Extraction plate via persistance et stabilité des clusters

C’est l’étape qui distingue HDBSCAN du simple clustering hiérarchique. Au lieu de demander à l’utilisateur de choisir un niveau de coupe (ce qui serait arbitraire), HDBSCAN évalue automatiquement la stabilité de chaque cluster candidat à travers la hiérarchie.

Pour un cluster C donné, on définit :

λ_min = 1 / distance_d'entrée_dans_C    (inverse de la distance à laquelle C apparaît)
λ_max = 1 / distance_de_sortie_de_C     (inverse de la distance à laquelle C se scinde)
stabilité(C) = Σ_{x ∈ C} (λ_max - λ_min(x))

Plus précisément, pour chaque point x du cluster, on mesure combien de temps (en termes d’inverse de distance λ = 1/d) il reste fidèle à ce cluster avant de passer à un cluster enfant ou de devenir du bruit. La stabilité totale d’un cluster est la somme de ces contributions individuelles.

L’algorithme effectue alors un parcours descendant de l’arbre : pour chaque cluster parent, il compare sa stabilité à la somme des stabilités de ses enfants. Si le parent est plus stable, il est conservé ; sinon, ce sont les enfants qui sont retenus. Cette approche garantit que seuls les clusters véritablement persistants à travers les échelles sont sélectionnés.

5. Points non assignés = bruit

Les points qui ne peuvent être attribués de manière fiable à aucun cluster stable sont étiquetés bruit (noise), avec le label -1. Cette détection de bruit est intrinsèque à l’algorithme et ne nécessite aucun paramètre supplémentaire.

Intuition : DBSCAN amélioré

Pour bien comprendre HDBSCAN, il est utile de le situer par rapport à son prédécesseur, DBSCAN.

DBSCAN repose sur deux paramètres : eps (le rayon de voisinage) et min_samples (le nombre minimal de voisins pour qu’un point soit considéré comme cœur). Le problème est que eps est difficile à choisir :

• Un eps trop petit → trop de bruit, les clusters se fracturent.
• Un eps trop grand → tous les points fusionnent en un seul cluster géant.
• Si les clusters ont des densités différentes, aucun eps unique ne peut capturer correctement toutes les structures. Un eps adapté à un cluster dense sera trop petit pour un cluster peu dense, et vice-versa.

HDBSCAN résout ce dilemme de manière élégante : au lieu de fixer eps manuellement, il explore TOUS les eps possibles simultanément. Pour chaque valeur possible, l’algorithme « voit » une partition différente des données. En assemblant ces partitions à travers toutes les échelles, il construit un arbre hiérarchique complet. Puis, grâce au mécanisme de stabilité décrit ci-dessus, il sélectionne automatiquement les clusters les plus stables à travers les échelles.

Pensez-y ainsi : au lieu de prendre une seule photo floue de vos données avec un objectif mal réglé (eps fixe), HDBSCAN fait un film complet de vos données à toutes les zooms, puis identifie les structures qui persistent à travers le film. C’est cette approche multi-échelle qui rend HDBSCAN si puissant pour les données du monde réel.

Implémentation Python

Installation

pip install hdbscan scikit-learn matplotlib seaborn

La bibliothèque hdbscan est l’implémentation de référence, développée par les auteurs originaux de l’algorithme (Leland McInnes et John Healy).

Exemple fondamental avec des densités variées

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import hdbscan
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

# ------------------------------------------------------------------
# Création de données avec 3 clusters de densités différentes
# ------------------------------------------------------------------
centers = [[1, 1], [-1, -1], [1, -1]]
cluster_sizes = [200, 80, 40]      # tailles très variées
cluster_stds = [0.2, 0.5, 0.9]     # écarts-types différents = densités différentes

X_parts = []
labels_true = []
for i, (center, size, std) in enumerate(zip(centers, cluster_sizes, cluster_stds)):
    np.random.seed(42 + i)
    blob = np.random.randn(size, 2) * std + center
    X_parts.append(blob)
    labels_true.extend([i] * size)

# Ajout de points de bruit uniformes
noise = np.random.uniform(low=-3, high=3, size=(30, 2))
X_parts.append(noise)

X = np.vstack(X_parts)
X = StandardScaler().fit_transform(X)

# ------------------------------------------------------------------
# Clustering HDBSCAN
# ------------------------------------------------------------------
clusterer = hdbscan.HDBSCAN(
    min_cluster_size=15,   # taille minimale d'un cluster
    min_samples=10,        # conservatisme de la distance de cœur
    metric='euclidean',
    cluster_selection_method='eom',  # Excess of Mass (défaut)
    gen_min_span_tree=True   # requis pour plot_hierarchy()
)
clusterer.fit(X)
labels = clusterer.labels_
probas = clusterer.probabilities_  # probabilité d'appartenance au cluster

# ------------------------------------------------------------------
# Visualisation
# ------------------------------------------------------------------
palette = sns.color_palette('deep', np.unique(labels).max() + 1)
colors = [palette[int(l)] if l >= 0 else (0.5, 0.5, 0.5) for l in labels]

fig, axes = plt.subplots(1, 3, figsize=(18, 5))

# Scatter plot par cluster
axes[0].scatter(X[:, 0], X[:, 1], c=colors, s=8, alpha=0.7)
axes[0].set_title(f'HDBSCAN — {labels.max() + 1} clusters détectés\n'
                  f'{(labels == -1).sum()} points de bruit')
axes[0].set_xlabel('X1')
axes[0].set_ylabel('X2')

# Visualisation hiérarchique (dendrogramme)
clusterer.condensed_tree_.plot(select_clusters=True,
                                selection_palette=palette)
axes[1].set_title('Arbre condensé HDBSCAN')

# Single-linkage tree
clusterer.single_linkage_tree_.plot(cmap='viridis',
                                     colorbar=True)
axes[2].set_title('Single-Linkage Tree')

plt.tight_layout()
plt.savefig('hdbscan_demo.png', dpi=150, bbox_inches='tight')
plt.close()

# ------------------------------------------------------------------
# Affichage des résultats
# ------------------------------------------------------------------
for cluster_id in range(labels.max() + 1):
    mask = labels == cluster_id
    print(f"Cluster {cluster_id} : {mask.sum()} points, "
          f"probabilité moyenne = {probas[mask].mean():.3f}")
print(f"Bruit : {(labels == -1).sum()} points")

Appartenance probabiliste

L’une des fonctionnalités les plus utiles d’HDBSCAN est la probabilité d’appartenance souple (soft clustering) :

# Afficher les points ambigus (probabilité entre 0.4 et 0.7)
ambiguous = (probas > 0.4) & (probas < 0.7) & (labels >= 0)
print(f"Points ambigus : {ambiguous.sum()}")

# Ces points sont aux frontières des clusters.
# On peut les visualiser séparément pour comprendre les transitions.

Contrairement au K-Means qui attribue chaque point à un cluster unique de manière déterministe, HDBSCAN fournit une confiance pour chaque attribution. Un point au centre d’un cluster dense aura une probabilité proche de 1.0, tandis qu’un point à la frontière entre deux clusters aura une probabilité plus faible.

Comparaison avec DBSCAN sur les mêmes données

from sklearn.cluster import DBSCAN

# DBSCAN — il faut choisir eps manuellement
dbscan = DBSCAN(eps=0.5, min_samples=10)
dbscan_labels = dbscan.fit_predict(X)

n_clusters_db = len(set(dbscan_labels)) - (1 if -1 in dbscan_labels else 0)
n_noise_db = list(dbscan_labels).count(-1)

print(f"DBSCAN (eps=0.5) : {n_clusters_db} clusters, {n_noise_db} points de bruit")
print(f"HDBSCAN          : {labels.max() + 1} clusters, {(labels == -1).sum()} points de bruit")

Sur des données à densités variables, HDBSCAN détectera généralement plus correctement les trois clusters, tandis que DBSCAN en manquera un ou deux selon le eps choisi. Cette comparaison illustre concrètement l’avantage de l’approche multi-échelle d’HDBSCAN.

Hyperparamètres détaillés

Maîtriser les hyperparamètres d’HDBSCAN est crucial pour obtenir des résultats pertinents. Voici un guide détaillé de chacun :

min_cluster_size (requis, entier ≥ 2)

C’est le paramètre le plus important. Il fixe la taille minimale d’un cluster valide. Un cluster est tout groupe de points qui persiste dans l’arbre hiérarchique avec au moins min_cluster_size membres.

• Petite valeur (5-10) : détecte des structures fines, mais risque de sur-segmentation.
• Grande valeur (50+) : ne capture que les gros clusters, peut fusionner des structures distinctes.
• Règle pratique : commencez par 5-10 % de la taille totale des données, puis ajustez.

min_samples (entier ≥ 1)

Détermine le k utilisé pour calculer les distances de cœur. Ce paramètre contrôle le conservatisme de la métrique de densité :

• Égal à min_cluster_size (valeur par défaut) : comportement standard, bien équilibré.
• Plus petit que min_cluster_size : rend la métrique plus « permissive », les clusters se forment plus facilement.
• Plus grand que min_cluster_size : rend la métrique plus « conservatrice », seuls les cœurs très denses sont identifiés, ce qui augmente la détection de bruit.

Une bonne pratique est de fixer min_samples ≥ min_cluster_size pour accentuer la séparation entre clusters denses et bruit.

cluster_selection_method (chaîne)

Deux méthodes disponibles :

• 'eom' (Excess of Mass, par défaut) : favorise la persistance à travers les échelles. Sélectionne les clusters qui survivent le plus longtemps dans l’arbre hiérarchique. Idéal quand on cherche des structures globales cohérentes.
• 'leaf' : parcourt les feuilles de l’arbre (les clusters les plus fins) et remonte seulement si nécessaire. Produit généralement plus de clusters, plus petits. Utile quand la data contient des sous-structures fines intéressantes.

cluster_selection_epsilon (flottant ≥ 0)

Fixe une échelle maximale pour l’extraction des clusters. Tout cluster dont la stabilité se situe au-delà de cette distance (en termes de 1/distance) sera scindé. Par défaut (0), l’algorithme explore toute la hiérarchie. Ce paramètre est utile quand on sait approximativement l’échelle maximale des structures d’intérêt.

allow_single_cluster (booléen)

Quand True, permet le cas où tous les points forment un unique cluster (cas dégénéré). Par défaut, c’est False, ce qui signifie que si la racine de l’arbre est le seul cluster, l’algorithme retourne uniquement du bruit. Activez cette option seulement si vous êtes certain que vos données forment un groupe unique cohérent.

metric (chaîne ou callable)

La métrique de distance utilisée pour construire l’espace d’atteinte mutuelle. Options courantes :

• 'euclidean' : distance euclidienne standard (défaut).
• 'manhattan' : distance L1, robuste aux outliers.
• 'cosine' : similarité cosinus, idéale pour les données textuelles ou de haute dimension.
• 'hamming' : pour les données binaires/catégorielles.
• Fonction personnalisée : callable accepting two arrays and returning a float.

Le choix de la métrique est critique : HDBSCAN ne peut trouver que les structures qui existent dans l’espace métrique choisi.

Avantages et limites

Avantages

1. Pas de nombre de clusters à fixer — contrairement au K-Means ou au clustering hiérarchique classique.
2. Gère les densités variables — là où DBSCAN échoue, HDBSCAN excelle grâce à la distance d’atteinte mutuelle.
3. Détection naturelle du bruit — les points non assignés sont automatiquement identifiés, sans seuil supplémentaire.
4. Appartenance probabiliste — fournit une mesure de confiance pour chaque attribution, pas seulement un label binaire.
5. Structure hiérarchique exploitable — l’arbre condensé révèle des sous-structures à différentes échelles.
6. Robustesse — moins sensible aux choix de paramètres que DBSCAN grâce à son exploration multi-échelle.

Limites

1. Complexité computationnelle — O(n²) dans le pire cas, bien qu’en pratique la complexité soit nettement meilleure grâce aux optimisations (k-d trees, Borůvka’s algorithm). Pour des millions de points, des approximations ou le sampling sont souvent nécessaires.
2. Sensibilité à min_cluster_size — bien que plus facile à régler que le eps de DBSCAN, ce paramètre reste influent. Un mauvais choix peut sous ou sur-segmenter.
3. Métrique de distance critique — comme tous les algorithmes basés sur la distance, des données mal mises à l’échelle ou en très haute dimension (>100) peuvent donner des résultats médiocres.
4. Non déterministe sur certains jeux de données — des ambiguïtés dans la construction de l’arbre peuvent mener à de légères variations entre deux exécutions.
5. Pas d’incrémentation naturelle — comme la plupart des algorithmes de clustering, ajouter de nouvelles données nécessite un recalcul (ou l’utilisation du approximate_predict de la bibliothèque hdbscan).

4 cas d’usage concrets

Cas d’usage 1 : Détection d’anomalies en cybersécurité

Dans un flux réseau, la majorité des connexions forment des clusters denses (trafic normal). HDBSCAN identifie naturellement les connexions atypiques comme du bruit. La probabilité d’appartenance permet de trier les alertes par sévérité : les points avec une probabilité très faible sont les plus suspects.

# Scénisme simplifié : détection d'intrusions
anomalies = X[labels == -1]
print(f"{len(anomalies)} connexions suspectes détectées sur {len(X)}")

Cas d’usage 2 : Segmentation client en marketing

Les clients ne se répartissent pas en groupes parfaitement séparés. Certains sont des acheteurs fidèles (cluster dense), d’autres des navigateurs occasionnels (cluster diffus), et quelques-uns des anomalies (achats suspects ou erreurs de data). HDBSCAN capture cette réalité bien mieux que le K-Means qui forcerait une partition artificielle.

Cas d’usage 3 : Analyse de documents et NLP

Après avoir plongé des textes dans un espace vectoriel (via TF-IDF, Word2Vec ou des embeddings modernes comme BERT), HDBSCAN regroupe les documents par thème sémantique. La métrique cosine est alors idéale. Les documents « bruit » sont ceux qui ne correspondent clairement à aucun thème — potentiellement des documents multi-thématiques ou atypiques.

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_distances

texts = ["article sur le ML", "recette de cuisine", ...]
vectorizer = TfidfVectorizer()
X_tfidf = vectorizer.fit_transform(texts)

clusterer = hdbscan.HDBSCAN(
    min_cluster_size=5,
    metric='precomputed',
    cluster_selection_method='leaf'
)
labels = clusterer.fit_predict(cosine_distances(X_tfidf))

Cas d’usage 4 : Biologie computationnelle — regroupement de cellules uniques

En scRNA-seq (séquençage d’ARN sur cellules uniques), chaque cellule est un point en haute dimension. Les populations cellulaires ont des densités très différentes (certaines cellules sont rares, d’autres abondantes). HDBSCAN est devenu un standard dans ce domaine car il détecte à la fois les populations majeures et les sous-populations rares, tout en identifiant les cellules de mauvaise qualité comme bruit. L’outil Scanpy pour l’analyse de données single-cell intègre d’ailleurs HDBSCAN nativement.

Bonnes pratiques

1. Normalisez toujours vos données — HDBSCAN est sensible à l’échelle des caractéristiques. Utilisez StandardScaler ou MinMaxScaler avant le clustering.
2. Réduisez la dimension si nécessaire — pour des données > 50 dimensions, appliquez d’abord une UMAP ou une PCA. La malédiction de la dimensionnalité affecte toutes les métriques de distance.
3. Commencez par min_cluster_size ≈ n/20 — une règle empirique raisonnable pour un premier essai.
4. Visualisez l’arbre condensé — c’est le meilleur diagnostic pour comprendre si les clusters détectés sont robustes ou artefacts.
5. Comparez avec DBSCAN — si HDBSCAN et DBSCAN donnent des résultats similaires avec les mêmes données, c’est bon signe. S’ils diffèrent radicalement, investigatez la structure de vos données.
6. Utilisez cluster_selection_method='leaf' quand vous soupçonnez des sous-structures fines au sein de vos clusters principaux.

Conclusion

HDBSCAN représente une avancée majeure dans l’arsenal du clustering non supervisé. En combinant la rigueur de la distance d’atteinte mutuelle avec l’exploration systématique de la hiérarchie à toutes les échelles, il offre une robustesse que peu d’algorithmes égalent. Son principal atout — ne pas avoir à deviner le nombre de clusters — en fait un outil de choix pour l’exploration de données réelles, où la structure sous-jacente est rarement connue à l’avance. Avec des bibliothèques Python accessibles et une communauté active, HDBSCAN est aujourd’hui un standard de facto pour le clustering exploratoire en science des données.

Voir aussi

• Calcul de l’Plus Petit Commun Multiple (PPCM) Moyen en Python : Guide Complet et Astuces
• Maîtriser les Roues Dentées Planétaires avec Python : Simulations et Applications Pratiques