Algoritm OPTICS - OPTICS algorithm

Punctele de comandă pentru identificarea structurii de grupare ( OPTICS ) este un algoritm pentru găsirea clusterelor bazate pe densitate în datele spațiale. A fost prezentat de Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel și Jörg Sander. Ideea sa de bază este similară cu DBSCAN , dar abordează una dintre slăbiciunile majore ale DBSCAN: problema detectării clusterelor semnificative în date cu densitate variabilă. Pentru a face acest lucru, punctele bazei de date sunt (liniar) ordonate astfel încât punctele cele mai apropiate spațial să devină vecine în ordonare. În plus, este stocată o distanță specială pentru fiecare punct care reprezintă densitatea care trebuie acceptată pentru un cluster, astfel încât ambele puncte să aparțină aceluiași cluster. Aceasta este reprezentată ca o dendrogramă .

Idee de bază

La fel ca DBSCAN , OPTICS necesită doi parametri: $ε$ , care descrie distanța maximă (raza) de luat în considerare și $MinPts$ , care descrie numărul de puncte necesare pentru a forma un cluster. Un punct $p$ este un punct de bază în cazul în care cel puțin $MinPts$ puncte se găsesc în ei $ε$ -neighborhood (inclusiv punctul $p$ în sine). Spre deosebire de DBSCAN , OPTICS ia în considerare și punctele care fac parte dintr-un cluster mai dens, așa că fiecărui punct i se atribuie o distanță de bază care descrie distanța până la $cel$ mai apropiat punct $MinPts$ : ${\ displaystyle N _ {\ varepsilon} (p)}$

{\ displaystyle {\ text {core-dist}} _ {\ mathit {\ varepsilon, MinPts}} (p) = {\ begin {cases} {\ text {UNDEFINED}} & {\ text {if}} | N_ {\ varepsilon} (p) | <{\ mathit {MinPts}} \\ {\ mathit {MinPts}} {\ text {-a cea mai mică distanță în}} N _ {\ varepsilon} (p) și {\ text {altfel }} \ end {cases}}}

Distanța de accesibilitate a unui alt punct $o de$ la un punct $p$ este fie distanța dintre $o$ și $p$ , fie distanța de bază a lui $p$ , oricare dintre acestea este mai mare:

{\ displaystyle {\ text {reachability-dist}} _ {\ mathit {\ varepsilon, MinPts}} (o, p) = {\ begin {cases} {\ text {UNDEFINED}} și {\ text {if}} | N _ {\ varepsilon} (p) | <{\ mathit {MinPts}} \\\ max ({\ text {core-dist}} _ {\ mathit {\ varepsilon, MinPts}} (p), {\ text {dist}} (p, o)) și {\ text {altfel}} \ end {cases}}}

Dacă $p$ și $o$ sunt cei mai apropiați vecini, acesta este cel pe care trebuie să-l presupunem că $p$ și $o$ aparțin aceluiași grup. ${\ displaystyle \ varepsilon '<\ varepsilon}$

Atât distanța nucleului, cât și distanța de accesibilitate sunt nedefinite dacă nu este disponibil un cluster suficient de dens (wrt $ε$ ). Având în vedere un $ε$ suficient de mare , acest lucru nu se întâmplă niciodată, dar apoi fiecare interogare $ε-$ vecinătate returnează întreaga bază de date, rezultând un timp de execuție. Prin urmare, parametrul $ε$ este necesar pentru a tăia densitatea clusterelor care nu mai sunt interesante și pentru a accelera algoritmul. ${\ displaystyle O (n ^ {2})}$

Parametrul $ε nu$ este, strict vorbind, necesar. Poate fi setat pur și simplu la valoarea maximă posibilă. Cu toate acestea, atunci când este disponibil un indice spațial, acesta joacă un rol practic în ceea ce privește complexitatea. OPTICS rezumă din DBSCAN eliminând acest parametru, cel puțin în măsura în care trebuie doar să dai valoarea maximă.

Pseudo cod

Abordarea de bază a OPTICS este similară cu DBSCAN , dar în loc să mențină membrii cluster cunoscuți, dar până acum neprocesați într-un set, aceștia sunt menținuți într-o coadă prioritară (de exemplu, folosind o grămadă indexată ).

function OPTICS(DB, eps, MinPts) is
    for each point p of DB do
        p.reachability-distance = UNDEFINED
    for each unprocessed point p of DB do
        N = getNeighbors(p, eps)
        mark p as processed
        output p to the ordered list
        if core-distance(p, eps, MinPts) != UNDEFINED then
            Seeds = empty priority queue
            update(N, p, Seeds, eps, MinPts)
            for each next q in Seeds do
                N' = getNeighbors(q, eps)
                mark q as processed
                output q to the ordered list
                if core-distance(q, eps, MinPts) != UNDEFINED do
                    update(N', q, Seeds, eps, MinPts)

În update (), coada de prioritate Seeds este actualizată cu -vecinătatea și , respectiv: ${\ displaystyle \ varepsilon}$ ${\ displaystyle p}$ ${\ displaystyle q}$

function update(N, p, Seeds, eps, MinPts) is
    coredist = core-distance(p, eps, MinPts)
    for each o in N
        if o is not processed then
            new-reach-dist = max(coredist, dist(p,o))
            if o.reachability-distance == UNDEFINED then // o is not in Seeds
                o.reachability-distance = new-reach-dist
                Seeds.insert(o, new-reach-dist)
            else               // o in Seeds, check for improvement
                if new-reach-dist < o.reachability-distance then
                    o.reachability-distance = new-reach-dist
                    Seeds.move-up(o, new-reach-dist)

OPTICS scoate, prin urmare, punctele dintr-o anumită ordonare, adnotate cu cea mai mică distanță de accesibilitate (în algoritmul original, distanța de bază este, de asemenea, exportată, dar aceasta nu este necesară pentru procesarea ulterioară).

Extragerea clusterelor

Folosind un grafic de accesibilitate (un tip special de dendrogramă ), structura ierarhică a clusterelor poate fi obținută cu ușurință. Este un grafic 2D, cu ordonarea punctelor procesate de OPTICS pe axa x și distanța de accesibilitate pe axa y. Deoarece punctele aparținând unui cluster au o distanță de accesibilitate redusă față de cel mai apropiat vecin, clusterele apar ca văi în graficul de accesibilitate. Cu cât valea este mai adâncă, cu atât este mai dens grupul.

Imaginea de mai sus ilustrează acest concept. În zona sa din stânga sus, este prezentat un exemplu sintetic de date. Partea din dreapta sus vizualizează arborele de întindere produs de OPTICS, iar partea de jos arată graficul de accesibilitate calculat de OPTICS. Culorile din acest grafic sunt etichete și nu sunt calculate de algoritm; dar este bine vizibil cum văile din complot corespund grupurilor din setul de date de mai sus. Punctele galbene din această imagine sunt considerate zgomot și nu se găsește nicio vale în graficul lor de accesibilitate. De obicei, acestea nu sunt alocate clusterelor, cu excepția clusterului omniprezent „toate datele” într-un rezultat ierarhic.

Extragerea clusterelor din acest grafic se poate face manual selectând un interval pe axa x după inspecția vizuală, selectând un prag pe axa y (rezultatul este apoi similar cu un rezultat de cluster DBSCAN cu aceiași parametri și minPts; aici o valoare de 0,1 poate produce rezultate bune), sau prin diferiți algoritmi care încearcă să detecteze văile prin abrupte, detectarea genunchiului sau maxime locale. Clusterurile obținute în acest mod sunt de obicei ierarhizate și nu pot fi realizate printr-o singură rundă DBSCAN. ${\ displaystyle \ varepsilon}$

Complexitate

La fel ca DBSCAN , OPTICS prelucrează fiecare punct o dată și efectuează o interogare de vecinătate în timpul acestei procesări. Având în vedere un indice spațial care acordă o interogare de cartier în timp de rulare, se obține un timp de rulare global de . Autorii lucrării originale OPTICS raportează un factor de încetinire constantă reală de 1,6 în comparație cu DBSCAN. Rețineți că valoarea lui ar putea influența puternic costul algoritmului, deoarece o valoare prea mare ar putea ridica costul unei interogări de vecinătate la complexitate liniară. ${\ displaystyle \ varepsilon}$ ${\ displaystyle O (\ log n)}$ ${\ displaystyle O (n \ cdot \ log n)}$ ${\ displaystyle \ varepsilon}$

În special, alegerea (mai mare decât distanța maximă din setul de date) este posibilă, dar duce la complexitate pătratică, deoarece fiecare interogare de cartier returnează setul complet de date. Chiar și atunci când nu este disponibil un indice spațial, acest lucru are un cost suplimentar în gestionarea heap-ului. Prin urmare, ar trebui să fie ales în mod corespunzător pentru setul de date. ${\ displaystyle \ varepsilon> \ max _ {x, y} d (x, y)}$ ${\ displaystyle \ varepsilon}$

Extensii

OPTICS-OF este un algoritm de detectare anterioară bazat pe OPTICS. Principala utilizare este extragerea valorilor aberante dintr-o serie existentă de OPTICS la un cost redus comparativ cu utilizarea unei metode diferite de detectare a valorilor aberante. Versiunea mai cunoscută LOF se bazează pe aceleași concepte.

DeLi-Clu, Density-Link-Clustering combină ideile din clusterizarea cu o singură legătură și OPTICS, eliminând parametrul și oferind îmbunătățiri ale performanței față de OPTICS. ${\ displaystyle \ varepsilon}$

HiSC este o metodă ierarhică de clusterizare sub - spațiu (ax-paralelă) bazată pe OPTICS.

HiCO este un algoritm ierarhic de grupare a corelației bazat pe OPTICS.

DiSH este o îmbunătățire față de HiSC, care poate găsi ierarhii mai complexe.

FOPTICS este o implementare mai rapidă utilizând proiecții aleatorii.

HDBSCAN * se bazează pe un rafinament al DBSCAN, excluzând punctele de graniță din clustere și urmând astfel mai strict definiția de bază a nivelurilor de densitate de către Hartigan.

Disponibilitate

Implementările Java ale OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO și DiSH sunt disponibile în cadrul de extragere a datelor ELKI (cu accelerația indexului pentru mai multe funcții la distanță și cu extracție automată de cluster folosind metoda de extracție ξ). Alte implementări Java includ extensia Weka (fără suport pentru extracția ξ cluster).

R Pachetul „dbscan“ include C ++ implementarea OPTICS (atât extracție tradițională dbscan-like și ξ de cluster) folosind un copac kd pentru accelerare index numai distanța euclidiană.

Implementările Python ale OPTICS sunt disponibile în biblioteca PyClustering și în scikit-learn . HDBSCAN * este disponibil în biblioteca hdbscan .

Languages

In other projects