• 15 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 08/01/2024

Partitionnez vos données avec DBSCAN

Comment séparer des cercles imbriqués les uns dans les autres ?

Quel algorithme de clustering utiliser pour former des clusters non convexes, comme des demi-lunes ou des cercles imbriqués les uns dans les autres ? Dans la partie précédente, nous avons vu que le k-means forme nécessairement des clusters convexes, ce qui n'est pas le cas de ce genre de figure. Par exemple, sur l'image ci-dessous, un segment reliant un point en haut du cercle extérieur à un point en bas du même cercle pourra contenir des points des deux autres cercles/clusters.

Quel algorithme de clustering utiliser pour former trois clusters correspondant aux trois cercles de ces données ?
Quel algorithme de clustering utiliser pour former trois clusters correspondant aux trois cercles de ces données ?

Nous avons vu précédemment que le kernel k-means permet de résoudre ce genre de problème. Mais ce n'est pas la seule façon de faire !

Clustering par densité

Les méthodes de clustering par densité sont basées sur l'observation suivante : bien que les deux points que j'ai mentionnés plus haut (notés A et B sur la figure ci-dessous) ne puissent pas être liés l'un à l'autre par un segment sans intersecter les deux autres clusters, on peut créer un chemin pour passer de l'un à l'autre de proche en proche en restant à l'intérieur du même cluster.

On peut connecter A à B par des petits voisinages (les cercles) contenant uniquement des points du cluster extérieur.
On peut connecter A à B par des petits voisinages (les cercles) contenant uniquement des points du cluster extérieur.

Un peu de vocabulaire maintenant...

Étant donné un nombre réel positif  $\(\epsilon\)$  , on appelle epsilon-voisinage d'un point x l'ensemble des points du jeu de données dont la distance à x est inférieure à   $\(\epsilon\)$   :

 $\(N_\epsilon(x) = \{u \in X | d(u, x) < \epsilon \}\)$

Étant donné un entier naturel   $\(n_\min\)$   , on dit que x est un point intérieur (core point, en anglais) si son   $\(\epsilon\)$-voisinage contient au moins   $\(n_\min\)$   points :  $\(|N_\epsilon(x)| \geq n_\min\)$  .

On dit maintenant que deux points u et x sont connectés par densité si l'on peut passer de l'un à l'autre par une suite d' $\(\epsilon\)$-voisinages contenant chacun au moins   $\(n_\min\)$   points. Autrement dit, il existe une suite de points intérieurs   $\(v_1, v_2, \dots v_m\)$   tels que  $\(v_1\)$   appartient à l' $\(\epsilon\)$-voisinage de u,   $\(v_2\)$   appartient à l' $\(\epsilon\)$-voisinage de   $\(v_1\)$  , et ainsi de suite, jusqu'à ce que x appartienne au voisinage de   $\(v_m\)$  . On dit aussi alors que x est atteignable par densité depuis u.

Pourquoi tout ce vocabulaire ? Parce que nous allons maintenant créer des clusters de points atteignables par densité les uns depuis les autres.

DBSCAN

L'algorithme DBSCAN (Density-Based Spatial Clustering of Applications with Noise) a été introduit en 1996 dans ce but. Cet algorithme est très utilisé, raison pour laquelle il a obtenu en 2014 une distinction de contribution scientifique ayant résisté à l'épreuve du temps.

DBSCAN itère sur les points du jeu de données. Pour chacun des points qu'il analyse, il construit l'ensemble des points atteignables par densité depuis ce point : il calcule l'epsilon-voisinage de ce point, puis, si ce voisinage contient plus de n_min points, les epsilon-voisinages de chacun d'entre eux, et ainsi de suite, jusqu'à ne plus pouvoir agrandir le cluster. Si le point considéré n'est pas un point intérieur, c'est-à-dire qu'il n'a pas suffisamment de voisins, il sera alors étiqueté comme du bruit. Cela permet à DBSCAN d'être robuste aux données aberrantes, puisque ce mécanisme les isole.

L'algorithme de DBSCAN est le suivant :

1. Prendre un point x qui n’a pas été visité

2. Construire N = voisinage(eps, x)

3.  If |N| < n_min:

        Marquer x comme bruit

    Else:

        Initaliser C = {x}
        agrandir_cluster(C, N, eps, n_min)

    Ajouter C à la liste des clusters
    Marquer tous les points de C comme visités

4. Repeat 1-3 until tous les points ont été visités

La procédure agrandir_cluster est donnée par :

agrandir_cluster(C, N, eps, n_min):
    For u in N:
        If u n’a pas été visité:
            N’ = N(eps, u)
        If |N’| >= n_min:
            N = union(N, N’)
        If u n’appartient à aucun autre cluster:
            Ajouter u à C

Avantages et inconvénients de DBSCAN

L'algorithme DBSCAN est difficile à utiliser en très grande dimension : souvenez-vous du fléau de la dimensionalité. Les boules de rayon epsilon et de grande dimension ont tendance à ne contenir aucun autre point.

Le choix des paramètres   $\(\epsilon\)$   et   $\(n_\min\)$   peut aussi être délicat : il faut veiller à utiliser des paramètres qui permettent de créer suffisamment de points intérieurs (ce qui n'arrivera pas si   $\(n_\min\)$   est trop grand ou   $\(\epsilon\)$   trop petit). En particulier, cela signifie que DBSCAN ne pourra pas trouver des clusters de densités différentes.

DBSCAN a le grand avantage d'être efficace en temps de calcul sans requérir de prédéfinir le nombre de clusters. Enfin, comme je l'ai dit au début de ce chapitre, il permet de trouver des clusters de forme arbitraire.

Exemple de certificat de réussite
Exemple de certificat de réussite