Méthode de clustering

<< Revenir au glossaire

Le DBS CAN (Density-Based Spatial Clustering of Applications with Noise) est une méthode de clustering, c’est-à-dire une technique qui permet de regrouper des données en fonction de leur similarité ou de leur proximité. Contrairement à d’autres méthodes de clustering comme le k-means, DBS CAN n’a pas besoin de connaître à l’avance le nombre de clusters et peut identifier des formes de clusters de n’importe quelle forme, même si elles sont non convexes.

Voici comment fonctionne DBS CAN de manière simplifiée :

  1. Points voisins : Le DBS CAN commence par choisir un point au hasard et regarde tous les points qui sont à une certaine distance de celui-ci (appelée epsilon, ε). Tous les points dans cette distance sont considérés comme des voisins.
  2. Points principaux et bords : Si un point a suffisamment de voisins (plus qu’un nombre minimum de points, minPts), il est considéré comme un « point central ». Les points dans la zone d’epsilon autour de ce point central sont les « points bord ».
  3. Expansion du cluster : Le cluster commence avec ce point central et inclut tous ses voisins. Si un de ses voisins est lui-même un point central, le cluster s’étend pour inclure également les voisins de ce point, et ainsi de suite.
  4. Bruit : Les points qui ne sont pas assez proches d’aucun point central pour être inclus dans un cluster sont considérés comme du bruit.
Exemple concret

maginons que nous ayons un ensemble de données représentant des emplacements de magasins dans une ville. Voici un exemple simplifié pour illustrer le concept de DBS CAN :

  1. Les données : Supposons que nous avons les coordonnées des magasins (en x, y) :
(1,2),(2,2),(2,3),(8,7),(8,8),(25,80)
  1. Paramètres : Nous définissons ε = 3 (donc une distance de 3 unités) et minPts = 2 (un point doit avoir au moins 2 voisins pour être un point central).
  2. Processus de clustering :
    • Le point (1, 2) est choisi au hasard. Ses voisins dans un rayon de 3 unités sont (2, 2) et (2, 3), donc c’est un point central.
    • Le cluster commence avec (1, 2) et inclut (2, 2) et (2, 3). Comme (2, 2) et (2, 3) ont eux-mêmes suffisamment de voisins, le cluster s’étend pour inclure ces voisins.
    • Les points (8, 7) et (8, 8) forment un autre cluster car ils sont voisins et chaque point a suffisamment de voisins dans un rayon de 3 unités.
    • Le point (25, 80) est isolé et n’a pas de voisins dans un rayon de 3 unités, donc il est considéré comme du bruit.
  3. Résultat :
    • Nous avons deux clusters : { (1, 2), (2, 2), (2, 3) } et { (8, 7), (8, 8) }.
    • Le point (25, 80) est classé comme bruit.

DBS CAN est particulièrement utile pour détecter des formes de clusters complexes et pour travailler avec des ensembles de données qui contiennent du bruit.

<< Revenir au glossaire