OPTICS
# 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 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.

