OPTICS
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Circle-icons-computer.svg/35px-Circle-icons-computer.svg.png)
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/OPTICS.svg/langfr-260px-OPTICS.svg.png)
Type | Algorithme de partitionnement de données (d) ![]() |
---|
modifier - modifier le code - modifier Wikidata
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 : , définissant un rayon maximum à considérer, et , 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 appartient à un groupe si au moins points existent dans son -voisinage . Par contre, à l'inverse de DBSCAN, le paramètre 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 ème point le plus proche :
La reachability-distance du point à un autre point est la distance entre et , ou la core-distance de :
La core-distance et la reachability-distance sont indéfinis si le groupe de points n'est pas suffisamment dense. Si est suffisamment grand, cela n'arrive jamais, mais toutes les requêtes d'-voisinage retourneront l'ensemble des points, la complexité étant alors en . Le paramètre 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
- ↑ Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander « OPTICS: Ordering Points To Identify the Clustering Structure » () (lire en ligne)
—ACM SIGMOD international conference on Management of data
v · m Apprentissage automatique et exploration de données | |||||||||
---|---|---|---|---|---|---|---|---|---|
Paradigmes d'apprentissage |
| ||||||||
Problèmes |
| ||||||||
Apprentissage supervisé |
| ||||||||
Apprentissage non supervisé et auto-supervisé |
| ||||||||
Métaheuristique d'optimisation | |||||||||
Théorie | |||||||||
Logiciels |
|
Portail de l’informatique