Guide de l'algorithme de clustering DBSCAN

Dans le domaine de la science des données et de l'apprentissage automatique, la capacité à découvrir des modèles cachés et à regrouper des points de données similaires est une compétence importante. Les algorithmes de regroupement jouent un rôle clé dans ce processus. 

Le clustering est une technique fondamentale d'apprentissage automatique et de science des données qui consiste à regrouper des points de données similaires. Il s'agit d'une méthode d 'apprentissage non supervisée, ce qui signifie qu'elle ne nécessite pas de données étiquetées pour trouver des modèles. 

L'objectif principal du regroupement est de :

• Simplifier les grands ensembles de données en sous-groupes significatifs
• Identifier les regroupements naturels dans les données
• Révéler les modèles et les structures cachés

Bien qu'il existe de nombreux algorithmes de regroupement (vous avez peut-être entendu parler des K-moyennes ou du regroupement hiérarchique), DBSCAN offre des avantages uniques. En tant que méthode basée sur la densité, DBSCAN possède plusieurs atouts :

1. Flexibilité dans la forme des grappes
2. Pas de nombre prédéfini de grappes
3. Traitement du bruit
4. Aperçu basé sur la densité

Dans cet article, nous allons voir ce qu'est l'algorithme DBSCAN, comment il fonctionne, comment le mettre en œuvre en Python et quand l'utiliser dans vos projets de science des données.

Qu'est-ce que DBSCAN ?

DBSCAN, qui signifie Density-Based Spatial Clustering of Applications with Noise, est un puissant algorithme de clustering qui regroupe des points très proches les uns des autres dans l'espace de données. Contrairement à d'autres algorithmes de clustering, DBSCAN ne vous oblige pas à spécifier le nombre de clusters au préalable, ce qui le rend particulièrement utile pour l'analyse exploratoire des données.

L'algorithme fonctionne en définissant les grappes comme des régions denses séparées par des régions de moindre densité. Cette approche permet à DBSCAN de découvrir des grappes de forme arbitraire et d'identifier les valeurs aberrantes comme du bruit.

DBSCAN s'articule autour de trois concepts clés :

1. Points essentiels: Il s'agit de points qui ont au moins un nombre minimum d'autres points (MinPts) à une distance spécifiée (ε ou epsilon).
2. Points frontières: Il s'agit de points qui se trouvent à une distance ε d'un point central mais qui n'ont pas de MinPts voisins eux-mêmes.
3. Points de bruit: Il s'agit de points qui ne sont ni des points centraux ni des points frontières. Ils ne sont pas assez proches d'un groupe pour être inclus.

Image de l'auteur

Le diagramme ci-dessus illustre ces concepts. Les points centraux (bleus) forment le cœur des grappes, les points frontières (orange) se trouvent à la périphérie des grappes et les points de bruit (rouges) sont isolés.

DBSCAN utilise deux paramètres principaux :

• ε (epsilon): La distance maximale entre deux points pour qu'ils soient considérés comme voisins.
• MinPts : Le nombre minimum de points requis pour former une région dense.

En ajustant ces paramètres, vous pouvez contrôler la façon dont l'algorithme définit les grappes, ce qui lui permet de s'adapter à différents types d'ensembles de données et d'exigences en matière de grappes.

Dans la section suivante, nous verrons comment fonctionne l'algorithme DBSCAN, en explorant son processus d'identification des grappes dans les données, étape par étape.

Comment fonctionne DBSCAN ?

DBSCAN fonctionne en examinant le voisinage de chaque point de l'ensemble de données. L'algorithme suit un processus étape par étape pour identifier les grappes sur la base de la densité des points de données. Voyons comment fonctionne DBSCAN :

1. Sélection des paramètres
• Choisissez ε (epsilon) : La distance maximale entre deux points pour qu'ils soient considérés comme voisins.
• Choisissez MinPts : Le nombre minimum de points requis pour former une région dense.
2. Sélectionnez un point de départ
• L'algorithme commence par un point arbitraire non visité dans l'ensemble de données.
3. Examiner le quartier
• Il récupère tous les points situés à une distance ε du point de départ.
• Si le nombre de points voisins est inférieur à MinPts, le point est étiqueté comme bruit (pour l'instant).
• S'il y a au moins MinPts points à moins de ε de distance, le point est marqué comme un point central et un nouveau groupe est formé.
4. Développer le cluster
• Tous les voisins du point central sont ajoutés à la grappe.
• Pour chacun de ces voisins :
• S'il s'agit d'un point central, ses voisins sont ajoutés à la grappe de manière récursive.
• S'il ne s'agit pas d'un point central, il est marqué comme point frontalier et l'expansion s'arrête.
5. Répétez le processus
• L'algorithme passe au prochain point non visité de l'ensemble de données.
• Les étapes 3 et 4 sont répétées jusqu'à ce que tous les points aient été visités.
6. Finaliser les regroupements
• Une fois que tous les points ont été traités, l'algorithme identifie tous les groupes.
• Les points initialement étiquetés comme étant du bruit peuvent maintenant être des points frontières s'ils se trouvent à moins de ε de distance d'un point central.
7. Bruit de manipulation
• Les points n'appartenant à aucune grappe restent classés comme du bruit.

Ce processus permet à DBSCAN de former des grappes de formes arbitraires et d'identifier efficacement les valeurs aberrantes. La capacité de l'algorithme à trouver des grappes sans en spécifier le nombre au préalable est l'un de ses principaux atouts.

Il est important de noter que le choix de ε et MinPts peut affecter de manière significative les résultats du regroupement. Dans la section suivante, nous verrons comment choisir ces paramètres de manière efficace et nous présenterons des méthodes telles que le graphe de k-distance pour la sélection des paramètres.

Concepts et paramètres clés de DBSCAN

Pour bien comprendre comment DBSCAN forme des grappes, il est important de comprendre deux concepts clés : l'accessibilité de la densité et la connectivité de la densité.

Accessibilité de la densité

Un point q est accessible en densité à partir d'un point p si :

1. p est un point central (il y a au moins MinPts à moins de ε de distance)

2. Il existe une chaîne de points p = p₁, ..., p_n = q où chaque p_i+1 est directement accessible en densité à partir de p_i.

En termes plus simples, vous pouvez atteindre q à partir de p en passant par des points centraux, où chaque étape n'est pas plus grande que ε.

Connectivité de la densité

Deux points p et q sont reliés par densité s'il existe un point o tel que p et q sont accessibles par densité à partir de o.

La connectivité de la densité est la base de la formation des grappes dans DBSCAN. Tous les points d'une grappe sont reliés entre eux par la densité, et si un point est relié par la densité à n'importe quel point de la grappe, il appartient également à cette grappe.

Choix des paramètres DBSCAN

L'efficacité de DBSCAN dépend fortement du choix de ses deux principaux paramètres : ε (epsilon) et MinPts. Voici comment procéder à la sélection de ces paramètres :

Sélection de ε (Epsilon)

Le paramètre ε détermine la distance maximale entre deux points pour qu'ils soient considérés comme voisins. Pour choisir un ε approprié :

1. Utiliser les connaissances du domaine: Si vous avez une idée de la distance significative pour votre problème spécifique, utilisez-la comme point de départ.

2. Graphique K-distance: Il s'agit d'une approche plus systématique :

• Calculez la distance du k-ième plus proche voisin pour chaque point (où k = MinPts).
• Tracez ces k-distances dans l'ordre croissant.
• Recherchez un "coude" dans le graphique - un point où la courbe commence à s'aplanir.
• La valeur ε à ce coude est souvent un bon choix.

Sélection des MinPts

MinPts détermine le nombre minimum de points requis pour former une région dense. Voici quelques lignes directrices :

1. Règle générale: Un bon point de départ consiste à définir MinPts = 2 * num_caractéristiques, où num_caractéristiques est le nombre de dimensions de votre ensemble de données.

2. Prise en compte du bruit: Si vos données sont bruitées ou si vous souhaitez détecter des clusters plus petits, vous pouvez diminuer MinPts.

3. Taille de l'ensemble de données: Pour les ensembles de données plus importants, vous devrez peut-être augmenter le nombre de MinPts pour éviter de créer trop de petits clusters.

N'oubliez pas que le choix des paramètres peut avoir une incidence considérable sur les résultats. Il est souvent utile d'expérimenter avec différentes valeurs et d'évaluer les grappes qui en résultent afin de trouver la meilleure solution pour votre ensemble de données et votre problème spécifique.

Implémentation de DBSCAN en Python

Dans cette section, nous allons examiner la mise en œuvre de DBSCAN à l'aide de Python et de la bibliothèque scikit-learn. Nous utiliserons l' ensemble de données Make Moons pour démontrer le processus.

Mise en place de l'environnement

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors

Ces importations fournissent les outils nécessaires à la manipulation des données, à la visualisation, à la création de jeux de données et à la mise en œuvre de l'algorithme DBSCAN.

Générer des échantillons de données

X, _ = make_moons(n_samples=200, noise=0.05, random_state=42)

Ce code crée un ensemble de données synthétiques à l'aide de la fonctionmake_moons de scikit-learn. Voici une brève description de l'ensemble de données :

La fonction make_moons génère une classification binaire classification qui ressemble à deux demi-lunes imbriquées l'une dans l'autre. Dans notre cas :

• Nous créons 200 échantillons (n_samples=200)
• Nous ajoutons une petite quantité de bruit gaussien (noise=0.05) pour rendre l'ensemble de données plus réaliste
• Nous fixons random_state=42 pour la reproductibilité

Cet ensemble de données est particulièrement utile pour la démonstration de DBSCAN :

1. Il a une forme non convexe que beaucoup de regroupement (comme K-means) ont du mal à s'adapter.
2. Les deux groupes sont clairement séparés mais ont une forme complexe
3. Le bruit ajouté fournit un scénario plus réaliste dans lequel certains points peuvent être classés comme aberrants

Visualisons cet ensemble de données pour mieux comprendre sa structure :

# Visualize the dataset
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1])
plt.title('Moon-shaped Dataset')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Cela vous montrera les deux formes de demi-lune entrelacées dans notre ensemble de données, comme indiqué ci-dessous.

Détermination du paramètre epsilon

Nous utilisons la méthode du graphe de distance k pour nous aider à choisir une valeur d'epsilon appropriée :

1. Nous définissons une fonction plot_k_distance_graph qui calcule la distance au k-ième plus proche voisin pour chaque point.
2. Les distances sont triées et représentées graphiquement.
3. Nous cherchons un "coude" dans le graphe résultant pour choisir epsilon.

# Function to plot k-distance graph
def plot_k_distance_graph(X, k):
    neigh = NearestNeighbors(n_neighbors=k)
    neigh.fit(X)
    distances, _ = neigh.kneighbors(X)
    distances = np.sort(distances[:, k-1])
    plt.figure(figsize=(10, 6))
    plt.plot(distances)
    plt.xlabel('Points')
    plt.ylabel(f'{k}-th nearest neighbor distance')
    plt.title('K-distance Graph')
    plt.show()
# Plot k-distance graph
plot_k_distance_graph(X, k=5)

Sortie

Dans notre exemple, nous choisissons un epsilon de 0,15 sur la base du graphique de la distance k.

Réalisation d'un clustering DBSCAN

Nous utilisons l'implémentation DBSCAN de scikit-learn :

1. Nous définissons epsilon=0.15 sur la base de notre graphe de k-distance.
2. Nous fixons min_samples=5 (2 * num_features, car nos données sont en 2D).
3. Nous adaptons le modèle à nos données et prédisons les grappes.

# Perform DBSCAN clustering
epsilon = 0.15  # Chosen based on k-distance graph
min_samples = 5  # 2 * num_features (2D data)
dbscan = DBSCAN(eps=epsilon, min_samples=min_samples)
clusters = dbscan.fit_predict(X)

Visualiser les résultats

Nous créons un diagramme de dispersion de nos points de données, en les colorant en fonction des groupes qui leur ont été attribués. Les points considérés comme du bruit sont généralement colorés différemment (souvent en noir).

# Visualize the results
plt.figure(figsize=(10, 6))
scatter = plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.colorbar(scatter)
plt.title('DBSCAN Clustering Results')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Sortie

Interprétation des résultats

Enfin, nous imprimons le nombre de grappes trouvées et le nombre de points considérés comme du bruit. Cela nous donne un résumé rapide des résultats du regroupement.

# Print number of clusters and noise points
n_clusters = len(set(clusters)) - (1 if -1 in clusters else 0)
n_noise = list(clusters).count(-1)
print(f'Number of clusters: {n_clusters}')
print(f'Number of noise points: {n_noise}')

Sortie

Nombre de grappes : 2

Nombre de points de bruit : 5

Cette mise en œuvre fournit un flux de travail complet, de la génération des données à l'interprétation des résultats. Il est important de noter que dans des scénarios réels, vous remplaceriez la génération d'échantillons de données par le chargement et le prétraitement de votre ensemble de données réel.

Rappelez-vous que la clé d'un regroupement DBSCAN réussi réside souvent dans la sélection appropriée des paramètres. N'hésitez pas à expérimenter différentes valeurs d'epsilon et de min_samples pour trouver la meilleure adaptation à votre ensemble de données spécifique.

DBSCAN vs. K-Means

Bien que DBSCAN et K-Means soient tous deux des algorithmes de regroupement populaires, ils présentent des caractéristiques distinctes qui les rendent adaptés à différents types de données et de cas d'utilisation. Comparons ces deux algorithmes pour comprendre quand utiliser chacun d'entre eux.

Comparaison visuelle

Pour illustrer ces différences, appliquons les deux algorithmes à notre ensemble de données en forme de lune

from sklearn.cluster import KMeans

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

# K-Means clustering
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans_labels = kmeans.fit_predict(X)

# Visualize the results
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(15, 6))

ax1.scatter(X[:, 0], X[:, 1], c=dbscan_labels, cmap='viridis')
ax1.set_title('DBSCAN Clustering')

ax2.scatter(X[:, 0], X[:, 1], c=kmeans_labels, cmap='viridis')
ax2.set_title('K-Means Clustering')

plt.show()

Ce code applique à la fois DBSCAN et K-Means à notre ensemble de données et visualise les résultats côte à côte.

Sortie

Vous remarquerez que

1. DBSCAN identifie correctement les deux demi-lunes comme des groupes distincts.
2. K-Means a du mal à gérer la forme non convexe et sépare souvent une lune en deux groupes ou combine des parties des deux lunes en un seul groupe.
3. DBSCAN peut identifier certains points comme du bruit (généralement colorés différemment), tandis que K-Means assigne chaque point à un groupe.

Quand utiliser DBSCAN ?

Maintenant que nous avons vu comment fonctionne DBSCAN et que nous l'avons comparé à K-Means, voyons quand DBSCAN est le bon choix pour nos besoins de clustering. Les propriétés uniques de DBSCAN le rendent particulièrement adapté à certains types de données et de domaines.

Formes complexes de grappes 

Dans le prolongement de notre comparaison précédente, DBSCAN brille véritablement lorsqu'il s'agit de formes de grappes non globulaires. Si vos données forment des motifs arbitraires tels que les demi-lunes que nous avons explorées précédemment, DBSCAN sera probablement plus performant que les algorithmes traditionnels tels que K-Means. 

Par exemple, dans l'analyse géographique, les formations naturelles telles que les réseaux fluviaux ou l'expansion urbaine forment souvent des formes irrégulières que DBSCAN peut identifier efficacement.

Nombre inconnu de grappes

L'un des principaux avantages de DBSCAN est sa capacité à déterminer automatiquement le nombre de grappes. Cette fonction est particulièrement utile pour l'analyse exploratoire des données, lorsque vous n'avez pas de connaissances préalables sur la structure sous-jacente de vos données. 

Considérons un problème de segmentation du marché : il se peut que vous ne sachiez pas à l'avance combien de groupes de clients distincts existent. DBSCAN peut vous aider à découvrir ces segments sans que vous ayez à deviner le nombre de clusters.

Ensembles de données avec bruit 

L'approche de DBSCAN pour traiter les points de bruit le rend robuste aux valeurs aberrantes. Ceci est crucial dans de nombreux ensembles de données du monde réel où les erreurs de mesure ou les anomalies sont courantes.

Par exemple, dans les systèmes de détection d'anomalies pour la sécurité des réseaux, DBSCAN peut séparer efficacement les modèles de trafic réseau normaux des menaces de sécurité potentielles.

Densité variable des grappes

Contrairement aux K-Means, qui supposent des grappes de densité similaire, DBSCAN peut identifier des grappes de densités différentes. Ceci est particulièrement utile dans les scénarios où certains groupes de vos données sont plus serrés que d'autres.

Un exemple pourrait être l'analyse de la distribution des galaxies en astronomie, où différentes régions de l'espace ont des densités variables d'objets célestes.

Bien que DBSCAN soit puissant, il est important de connaître ses limites :

1. Sensibilité des paramètres: Comme nous l'avons vu précédemment, le choix de valeurs appropriées pour ε et MinPts est crucial. De mauvais choix peuvent conduire à des résultats de regroupement sous-optimaux.
2. Données à haute dimension: Les performances de DBSCAN peuvent se dégrader avec des données de haute dimension en raison de la "malédiction de la dimensionnalité".
3. Densités variables: Bien que DBSCAN puisse gérer des grappes de différentes densités, des densités extrêmement variables dans le même ensemble de données peuvent encore poser des problèmes.
4. Évolutivité: Pour les très grands ensembles de données, DBSCAN peut s'avérer coûteux en termes de calcul par rapport à des algorithmes tels que K-Means.

Dans la section suivante, nous examinerons quelques applications pratiques de DBSCAN.

Exemples pratiques de DBSCAN

DBSCAN trouve des applications dans différents domaines.

Analyse des données spatiales

Dans les systèmes d'information géographique (SIG), DBSCAN permet d'identifier les zones de forte activité ou d'intérêt. Par exemple, une étude intituléeDécouverte de la mobilité humaine urbaine à partir de données GPS de taxi à grande échellemontre comment DBSCAN peut détecter les points chauds urbains à partir des données GPS des taxis.

Cette application illustre la capacité de DBSCAN à identifier les zones d'activité dense dans les données spatiales, ce qui est crucial pour la planification urbaine et la gestion des transports.

Traitement des images 

DBSCAN peut regrouper les pixels en objets distincts pour des tâches telles que la reconnaissance d'objets dans les images. Une étude intitulée 'Segmentation d'une tumeur cérébrale à partir d'une image IRM - Analyse de K-means et de DBSCAN Clusteringdémontre l'efficacité de DBSCAN dans l'analyse d'images médicales .

Les chercheurs ont utilisé DBSCAN pour segmenter avec précision des tumeurs cérébrales dans des IRM, démontrant ainsi son potentiel en matière de diagnostic assisté par ordinateur et d'imagerie médicale.

Détection des anomalies 

Dans le cadre de la détection des fraudes ou de la surveillance de la santé des systèmes, DBSCAN peut isoler des modèles inhabituels. Une étude intitulée 'Détection incrémentale efficace de valeurs aberrantes dans les flux de données, basée sur la densité et les grappesdémontre l'application d'un algorithme DBSCAN modifié pour la détection d'anomalies en temps réel.

Les chercheurs ont appliqué une version incrémentale de DBSCAN pour détecter les valeurs aberrantes dans les données en continu, ce qui pourrait être appliqué à la détection des fraudes et à la surveillance de l'état des systèmes. 

Cette étude montre comment DBSCAN peut être adapté pour identifier des modèles inhabituels dans des flux de données continus, une capacité cruciale pour les systèmes de détection des fraudes en temps réel.

Systèmes de recommandation

DBSCAN peut regrouper les utilisateurs ayant des préférences similaires, ce qui permet de générer des recommandations plus précises. Par exemple, une étude intitulée "Multi-Cloud Based Service Recommendation System Using DBSCAN Algorithm (Système de recommandation de services basé sur des nuages multiples utilisant l'algorithme DBSCAN)"démontre l'application de DBSCAN dans l'amélioration du filtrage collaboratif pour les systèmes de recommandation. Les chercheurs ont utilisé DBSCAN dans le cadre d'une approche de regroupement pour grouper les utilisateurs en fonction de leurs préférences et de leurs évaluations de films, ce qui a permis d'améliorer la précision des recommandations de films.

Cette approche montre comment DBSCAN peut améliorer les recommandations personnalisées dans des domaines tels que les services de divertissement en continu.

Conclusion

DBSCAN est un outil puissant dans la boîte à outils du scientifique des données, particulièrement utile lorsqu'il s'agit d'ensembles de données complexes et bruyants où le nombre de grappes est inconnu. Toutefois, comme tout algorithme, il ne s'agit pas d'une solution unique. 

La clé d'un regroupement réussi réside dans la compréhension de vos données, des forces et des limites des différents algorithmes et dans le choix de l'outil approprié. Dans de nombreux cas, l'essai de plusieurs approches de regroupement, y compris DBSCAN et K-Means, et la comparaison de leurs résultats peuvent fournir des informations précieuses sur la structure de vos données.

Avec la pratique et l'expérience, vous développerez une intuition pour savoir quand DBSCAN est susceptible de dévoiler les modèles cachés dans vos données.

Vous pouvez en apprendre davantage sur les différentes technologies et méthodes que nous avons abordées dans ce billet sur DataCamp grâce aux ressources suivantes : 

• Scientifique en apprentissage automatique en Python
• Apprentissage automatique non supervisé
• Cours sur l'apprentissage non supervisé en Python