OPTICS 📖 Wikipedia

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.

 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.

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.

•   Portail de l’informatique