OPTICS

OPTICS (acronyme de ordering points to identify the clustering structure en anglais) est un algorithme de partitionnement de données. Il a été proposé par Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel and Jörg Sander[1]. Il s'agit d'un algorithme basé densité dont le principe est similaire à DBSCAN mais élimine son principal défaut : l'impossibilité de détecter des partitions de densités différentes.

Principe général

Comme DBSCAN, OPTICS demande deux paramètres : , définissant un rayon maximum à considérer, et , définissant un nombre de points minimum. Ces 2 paramètres définissent donc une densité minimale pour constituer un groupe de données. Un point appartient à un groupe si au moins points existent dans son -voisinage . Par contre, à l'inverse de DBSCAN, le paramètre est optionnel. S'il est omis, il sera alors considéré comme infini. L'algorithme définit pour chaque point une distance, appelée core distance, qui décrit la distance avec le ème point le plus proche :

La reachability-distance du point à un autre point est la distance entre et , ou la core-distance de :


La core-distance et la reachability-distance sont indéfinis si le groupe de points n'est pas suffisamment dense. Si est suffisamment grand, cela n'arrive jamais, mais toutes les requêtes d'-voisinage retourneront l'ensemble des points, la complexité étant alors en . Le paramètre est donc utile pour définir une densité minimale afin d'accélérer l'algorithme.

Pseudocode

 OPTICS(DB, eps, MinPts)
    pour chaque point p de DB
       p.reachability-distance = UNDEFINED
    pour chaque point non visité p de DB
       N = voisinage(p, eps)
       marquer p comme visité
       output p to the ordered list
       si (core-distance(p, eps, Minpts) != UNDEFINED)
          Seeds = priority queue vide
          update(N, p, Seeds, eps, Minpts)
          pour chaque q prioritaire dans Seeds
             N' = voisinage(q, eps)
             marquer q comme visité
             output q to the ordered list
             si (core-distance(q, eps, Minpts) != UNDEFINED)
                update(N', q, Seeds, eps, Minpts)


 update(N, p, Seeds, eps, Minpts)
    coredist = core-distance(p, eps, MinPts)
    pour chaque o dans N
       si (o n'a pas été visité)
          new-reach-dist = max(coredist, dist(p,o))
          si (o.reachability-distance == UNDEFINED)
              o.reachability-distance = new-reach-dist
              Seeds.insert(o, new-reach-dist)
          sinon
              si (new-reach-dist < o.reachability-distance)
                 o.reachability-distance = new-reach-dist
                 Seeds.move-up(o, new-reach-dist)

OPTICS fournit donc une liste ordonnée de point associés à leur plus petite reachability-distance.

Extraire les partitions

OPTICS.svg

La sortie de l'algorithme permet de construire un diagramme appelé reachability-plot. C'est un diagramme en 2D dont l'axe x correspond à la position d'un point dans la liste ordonnée et l'axe y la reachability-distance associée à ce point. Les points d'un même cluster ont une reachability-distance assez basse, les vallées du diagramme représentent donc les différents clusters du jeu de données. Plus les vallées sont profondes, plus les clusters sont denses. L'image ci-dessus en montre le principe.

Références

  1. Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander (1999). « OPTICS: Ordering Points To Identify the Clustering Structure » dans ACM SIGMOD international conference on Management of data : 49–60 p., ACM Press.