OPTICS

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

${\displaystyle {\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 ${\displaystyle p}$ à un autre point ${\displaystyle o}$ est la distance entre ${\displaystyle o}$ et ${\displaystyle p}$, ou la core-distance de ${\displaystyle p}$:

${\displaystyle {\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 ${\displaystyle \varepsilon }$ est suffisamment grand, cela n'arrive jamais, mais toutes les requêtes d'${\displaystyle \varepsilon }$-voisinage retourneront l'ensemble des points, la complexité étant alors en ${\displaystyle O(n^{2})}$. Le paramètre ${\displaystyle \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.

Références

• Portail de l’informatique