Explorez vos données avec des algorithmes non supervisés

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.

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.

Un peu de vocabulaire maintenant...

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

 

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

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' $\$\backslash (\backslash epsilon\backslash )\$$-voisinages contenant chacun au moins   $\$\backslash (n\_\backslash min\backslash )\$$   points. Autrement dit, il existe une suite de points intérieurs   $\$\backslash (v\_1,\; v\_2,\; \backslash dots\; v\_m\backslash )\$$   tels que  $\$\backslash (v\_1\backslash )\$$   appartient à l' $\$\backslash (\backslash epsilon\backslash )\$$-voisinage de u,   $\$\backslash (v\_2\backslash )\$$   appartient à l' $\$\backslash (\backslash epsilon\backslash )\$$-voisinage de   $\$\backslash (v\_1\backslash )\$$  , et ainsi de suite, jusqu'à ce que x appartienne au voisinage de   $\$\backslash (v\_m\backslash )\$$  . 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   $\$\backslash (\backslash epsilon\backslash )\$$   et   $\$\backslash (n\_\backslash min\backslash )\$$   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   $\$\backslash (n\_\backslash min\backslash )\$$   est trop grand ou   $\$\backslash (\backslash epsilon\backslash )\$$   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.