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. Comme DBSCAN, OPTICS demande deux paramètres : ε {\displaystyle \varepsilon } , définissant un rayon maximum à considérer, et M i n P t s {\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 p {\displaystyle p} appartient à un groupe si au moins M i n P t s {\displaystyle MinPts} points existent dans son ε {\displaystyle \varepsilon } -voisinage N ε ( p ) {\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 M i n P t s {\displaystyle MinPts} ème point le plus proche : La reachability-distance du point p {\displaystyle p} à un autre point o {\displaystyle o} est la distance entre o {\displaystyle o} et p {\displaystyle p} , ou la core-distance de p {\displaystyle p} : 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 O ( n 2 ) {\displaystyle O(n^{2})} .