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. 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 : $\varepsilon$, définissant un rayon maximum à considérer, et $MinPts$, 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 $p$ appartient à un groupe si au moins $MinPts$ points existent dans son $\varepsilon$-voisinage $N_{\varepsilon }(p)$. Par contre, à l'inverse de DBSCAN, le paramètre $\varepsilon$ 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 $MinPts$ème point le plus proche :

${\text{core-distance}}_{\varepsilon ,MinPts}(p)={\begin{cases}{\text{Indéfini}}&{\text{si }}|N_{\varepsilon }(p)|<MinPts\\{\text{distance au }}MinPts{\text{-ème point le plus proche}}&{\text{sinon}}\end{cases}}$

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

${\text{reachability-distance}}_{\varepsilon ,MinPts}(o,p)={\begin{cases}{\text{Indéfini}}&{\text{si }}|N_{\varepsilon }(p)|<MinPts\\\max({\text{core-distance}}_{\varepsilon ,MinPts}(p),{\text{distance}}(p,o))&{\text{sinon}}\end{cases}}$

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

Pseudocode

 OPTICS(DB, ε, MinPts)
    pour chaque point p de DB
       p.reachability-distance = INDÉFINI
    pour chaque point non visité p de DB
       N = voisinage(p, ε)
       marquer p comme visité
       émettre p dans la liste ordonnée
       si (core-distance(p, ε, Minpts) != INDÉFINI)
          Seeds = queue prioritaire vide
          modifier(N, p, Seeds, ε, Minpts)
          pour chaque q prioritaire dans Seeds
             N' = voisinage(q, ε)
             marquer q comme visité
             émettre q dans la liste ordonnée
             si (core-distance(q, ε, Minpts) != INDÉFINI)
                modifier(N', q, Seeds, ε, Minpts)

 modifier(N, p, Seeds, ε, Minpts)
    coredist = core-distance(p, ε, 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 == INDÉFINI)
              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

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.