Regroupement Dbscan

DBSCAN (Clustering Spatial Basé sur la Densité d'Applications avec Bruit) est un algorithme populaire basé sur la densité en apprentissage automatique et en fouille de données. Il est particulièrement utile pour identifier des clusters de forme arbitraire dans des données contenant du bruit ou des valeurs aberrantes. L'algorithme fonctionne en définissant des clusters comme des régions denses de points séparées par des régions moins denses. L'algorithme DBSCAN prend deux paramètres principaux : epsilon (eps) et min_samples. Epsilon définit le rayon autour de chaque point, et min_samples définit le nombre minimum de points requis pour former une région dense.

L'algorithme fonctionne avec trois types de points différents :

point central a au moins min_samples points dans son rayon eps ;
point de bordure a moins de min_samples points dans son rayon eps, mais au moins un de ces points à l'intérieur du rayon est le point central ;
point de bruit est le même que le point de bordure mais n'a pas de point central dans son rayon eps.

En classifiant les points comme centraux, de bordure ou de bruit, l'algorithme DBSCAN peut identifier et séparer les clusters des points de bruit.

Pour comprendre DBSCAN, nous devons également mentionner deux définitions :

Atteignabilité en termes de densité établit qu'un point est atteignable à partir d'un autre s'il se trouve à une certaine distance (eps) de celui-ci. Mais l'atteignabilité a également été utilisée dans le clustering par déplacement moyen : dans les chapitres précédents, nous avons vérifié que cet algorithme ne pouvait pas fonctionner avec des clusters de forme arbitraire.

Pour détecter des clusters de forme arbitraire, nous avons besoin de connectivité : cela implique une approche basée sur la transitivité pour déterminer si des points sont situés dans un cluster particulier. Par exemple, les points p et q pourraient être connectés si q->p1->p2->p3->p, où x->y signifie que y est atteignable à partir de x.

Pour implémenter DBSCAN, vous devez effectuer les étapes suivantes :

Étape 1. Classifiez les points comme noyau, frontière et bruit ;

Étape 2. Éliminer le bruit (ou attribuer le bruit à un cluster séparé);

Étape 3. Assigner un cluster à un point central;

Étape 4. Fusionner tous les points centraux connectés d'un point choisi à l'étape 3 avec le cluster de ce point;

Étape 5. Visitez le prochain point central non clusterisé et répétez les étapes 3-4 jusqu'à ce qu'il n'y ait plus de points centraux non clusterisés dans le jeu de données;

Étape 6. Fusionner les points de frontière avec le cluster de points centraux le plus proche.

Voyons comment implémenter DBSCAN en Python :


              1234567891011121314
            
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
# Create blobs dataset for clustering
X, y = make_blobs(n_samples=500, centers=3)
# Specify eps and min_samples paremeters of DBSCAN model and train model
clustering = DBSCAN(eps=0.85, min_samples=20).fit(X)
# Visualize results
fig, axes = plt.subplots(1, 2)
axes[0].scatter(X[:, 0], X[:, 1], c=y, cmap='tab20b')
axes[0].set_title('Real clusters')
axes[1].scatter(X[:, 0], X[:, 1], c=clustering.labels_, cmap='tab20b')
axes[1].set_title('Clusters with DBSCAN')
print('Clustering labels are: ', set(clustering.labels_))

Remarque

L'algorithme DBSCAN attribue le bruit à un cluster séparé avec l'étiquette -1.

Dans le code ci-dessus, nous avons utilisé la classe DBSCAN du module sklearn.cluster pour implémenter l'algorithme DBSCAN. Nous avons également spécifié deux paramètres :

Le paramètre eps détermine le rayon de portée ;
Le paramètre min_samples détermine le nombre minimum d'échantillons dans le rayon de portée pour classer les points comme noyau, bordure ou bruit ;
nous utilisons la méthode .fit() pour effectuer le clustering.

Remarque

La classe DBSCAN n'a pas d'implémentation pour la méthode .predict(), donc nous ne pouvons pas effectuer de clustering pour de nouveaux points sans réentraîner le modèle.

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 6