Algorisme OPTICS

L'ordenació de punts per identificar l'estructura de clúster (OPTICS) és un algorisme per trobar clústers basats en la densitat en dades espacials. El van presentar Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel i Jörg Sander. La seva idea bàsica és similar a DBSCAN, però aborda una de les principals debilitats de DBSCAN: el problema de detectar clústers significatius en dades de densitat variable. Per fer-ho, els punts de la base de dades s'ordenen (linealment) de manera que els punts més propers espacialment es converteixin en veïns en l'ordenació. A més, s'emmagatzema una distància especial per a cada punt que representa la densitat que s'ha d'acceptar per a un clúster perquè tots dos punts pertanyin al mateix clúster. Això es representa com un dendrograma.

Idea bàsica

Igual que DBSCAN, OPTICS requereix dos paràmetres: Plantilla:Mvar, que descriu la distància màxima (radi) a considerar, i Plantilla:Mvar, que descriu el nombre de punts necessaris per formar un clúster. Un punt Plantilla:Mvar és un punt central si almenys els punts Plantilla:Mvar es troben dins del seu veïnat Plantilla:Mvar $N_{\epsilon }(p)$ (inclòs el propi punt Plantilla:Mvar ). A diferència de DBSCAN, OPTICS també considera els punts que formen part d'un clúster més densament empaquetat, de manera que a cada punt se li assigna una distància central que descriu la distància al punt més proper de Plantilla:Mvar :

${\text{core-dist}}_{\mathit{\epsilon },𝑀𝑖𝑛𝑃𝑡𝑠}(p)=\{\begin{array}{cc}\text{INDEFINIT}& \text{si }|N_{\epsilon }(p)|<𝑀𝑖𝑛𝑃𝑡𝑠\\ 𝑀𝑖𝑛𝑃𝑡𝑠\text{-è distància més petita a }{N}_{\epsilon }(p)& \text{altrament}\end{array}\acute{a}$

La distància d'accessibilitat d'un altre punt Plantilla:Mvar des d'un punt Plantilla:Mvar és la distància entre Plantilla:Mvar i Plantilla:Mvar, o la distància central de Plantilla:Mvar, la que sigui més gran:

${\text{reachability-dist}}_{\mathit{\epsilon },𝑀𝑖𝑛𝑃𝑡𝑠}(o,p)=\{\begin{array}{cc}\text{INDEFINIT}& \text{si }|N_{\epsilon }(p)|<𝑀𝑖𝑛𝑃𝑡𝑠\\ \max ({\text{core-dist}}_{\mathit{\epsilon },𝑀𝑖𝑛𝑃𝑡𝑠}(p),\text{dist}(p,o))& \text{altrament}\end{array}$

Si Plantilla:Mvar i Plantilla:Mvar són els veïns més propers, aquest és el ${\epsilon }^{\prime }<\epsilon$ hem de suposar que Plantilla:Mvar i Plantilla:Mvar pertanyen al mateix clúster.

Tant la distància del nucli com la distància d'accessibilitat no es defineixen si no hi ha cap clúster prou dens (wrt Plantilla:Mvar). Donat un Plantilla:Mvar prou gran, això no passa mai, però aleshores cada consulta Plantilla:Mvar -neighborhood retorna tota la base de dades, donant com a resultat $O(n^2)$ temps d'execució. Per tant, el paràmetre Plantilla:Mvar és necessari per tallar la densitat de clústers que ja no són interessants i per accelerar l'algorisme.

El paràmetre Plantilla:Mvar no és, estrictament parlant, necessari. Simplement es pot configurar al valor màxim possible. Tanmateix, quan hi ha un índex espacial disponible, juga un paper pràctic pel que fa a la complexitat. L'OPTICA s'abstraeix de DBSCAN eliminant aquest paràmetre, almenys fins al punt d'haver de donar només el valor màxim.

L'enfocament bàsic d'OPTICS és similar a DBSCAN, però en comptes de mantenir els membres del clúster coneguts, però fins ara no processats en un conjunt, es mantenen en una cua de prioritat (per exemple, utilitzant un munt indexat).

Per tant, ÒPTICA produeix els punts en un ordre particular, anotats amb la seva distància d'accessibilitat més petita (en l'algorisme original, la distància central també s'exporta, però això no és necessari per a un processament posterior).

Extracció dels clústers

Utilitzant un diagrama d'accessibilitat (un tipus especial de dendrograma), l'estructura jeràrquica dels clústers es pot obtenir fàcilment. És una gràfica 2D, amb l'ordenació dels punts tal com el processa ÒPTICA en l'eix x i la distància d'accessibilitat a l'eix y. Com que els punts que pertanyen a un cúmul tenen una distància d'accessibilitat baixa al seu veí més proper, els cúmuls apareixen com a valls a la trama d'accessibilitat. Com més profunda és la vall, més dens és el cúmul.

La imatge de dalt il·lustra aquest concepte. A la seva àrea superior esquerra, es mostra un conjunt de dades d'exemple sintètic. La part superior dreta visualitza l'arbre d'abast produït per OPTICS, i la part inferior mostra la trama d'accessibilitat calculada per OPTICS. Els colors d'aquesta trama són etiquetes i no els calcula l'algorisme; però és ben visible com les valls de la parcel·la es corresponen amb els clústers del conjunt de dades anterior. Els punts grocs d'aquesta imatge es consideren sorolls i no es troba cap vall a la seva trama d'accessibilitat. Normalment no s'assignen als clústers, excepte l'omnipresent clúster "totes les dades" en un resultat jeràrquic.

L'extracció de clústers d'aquesta gràfica es pot fer manualment seleccionant intervals a l'eix x després de la inspecció visual, seleccionant un llindar a l'eix y (el resultat és semblant a un resultat de clúster DBSCAN amb el mateix $\epsilon$ i paràmetres Plantilla:Literal ; aquí un valor de 0,1 pot donar bons resultats), o per diferents algorismes que intenten detectar les valls per inclinació, detecció de genolls o màxims locals. Una franja de la parcel·la que comença amb un fort descens i acaba amb una forta pujada es considera vall, i correspon a una zona contigua de gran densitat. Cal tenir cura addicional dels últims punts d'una vall per assignar-los al clúster interior o exterior, això es pot aconseguir tenint en compte el predecessor. Els agrupaments obtinguts d'aquesta manera solen ser jeràrquics i no es poden aconseguir amb una sola execució de DBSCAN.