DBSCAN

DBSCAN (ingliskeelsest Density Based Spatial Clustering of Applications with Noise) on tiheduspõhine klasterdusalgoritm, mille lõid Martin Ester, Hans-Peter Kriegel, Jörg Sander ja Xiaowei Xu aastal 1996.

Algoritm jaotab andmepunktid tiheduse põhjal klastritesse, paigutades piisavalt tihedalt paiknevad andmepunktid samasse klastrisse, samas kui hõredalt paiknevaid punkte loetakse müraks. DBSCAN on üks teadusartiklites enim viidatud klasterdusalgoritme. Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.

2014. aastal sai algoritm KDD andmekaevekonverentsil SIGKDD auhinna "Test of Time".

 Põhimõte 
DBSCAN jagab andmepunktid kolme klassi: tuumpunktid (core points), kättesaadavad punktid (reachable points) ja müra (noise).
 Punkt  on tuumpunkt, kui vähemalt  punkti (sealhulgas punkt  ise) on sellest kaugusel  või lähemal, kus  on punkti  naabruspiirkonna raadius. Neid punkte loetakse otseselt kättesaadavaks punkti  kaudu.
 Punkt  on otseselt kättesaadav punkti  kaudu, kui punkt  asub punkti  naabruspiirkonnas ja punkt  on tuumpunkt.
 Punkt  on kättesaadav punkti  kaudu, kui leidub ahel , kus  ja  ning punkt  on otseselt kättesaadav punkti  kaudu. Seega kõik punktid ahelas (erandiks võib olla ) on tuumpunktid. 
 Punktid, mis ei ole kättesaadavad ühegi teise punkti kaudu, loetakse müraks.

Kui  on tuumpunkt, moodustab see klastri koos kõigi teiste punktidega, mis on  kaudu kättesaadavad (olenemata sellest, kas need on tuumpunktid või mitte).
pisi|center|400px|Sellel diagrammil on . Punkt A ja teised punased punktid on tuumpunktid, kuna nende naabruspiirkonnas, raadiusega , on kokku 4 (või rohkem) punkti (sealhulgas punkt ise). Kuna nad on kõik kättesaadavad teineteise kaudu, moodustavad nad ühise klastri.

Punktid B ja C ei ole tuumpunktid, aga on kättesaadavad tuumpunktide kaudu ning seega kuuluvad samasse klastrisse. Punkt N on mürapunkt, kuna see pole tuumpunkt, ega ühegi teise punkti kaudu otseselt kättesaadav

 Algoritm 
Järgnev pseudokood kirjeldab originaalset DBSCAN-i implementatsiooni.
 DBSCAN(DB, dist, eps, minPts) {
    C = 0                                              /* Klastriloendur */
    for each point P in database DB {
       if label(P) ≠ undefined then continue           /* Varem töödeldud sisemises tsüklis */
       Neighbors N = RangeQuery(DB, dist, P, eps)      /* Leia naaberpunktid */
       if |N| < minPts then {                          /* Tiheduskontroll */
          label(P) = Noise                             /* Märgenda müraks */
          continue
       }
       C = C + 1                                       /* Järgmine klastri märgend */
       label(P) = C                                    /* Märgenda esialgne punkt */
       Seed set S = N \ {P}                            /* Naabrite hulk, mida töödelda */
       for each point Q in S {                         /* Töötle igat naabrit*/
          if label(Q) = Noise then label(Q) = C        /* Märgenda mürapunkt klastri äärepunktiks (mitte tuumpunktiks) */
          if label(Q) ≠ undefined then continue        /* Varem töödeldud */
          label(Q) = C                                 /* Märgenda naaber */
          Neighbors N = RangeQuery(DB, dist, Q, eps)   /* Leia naaberpunktid */
          if |N| ≥ minPts then {                       /* Tiheduskontroll */
             S = S ∪ N                                 /* Lisa uued naaberpunktid naabrite hulka, mida töödelda */
          }
       }
    }
 }

 Keerukus 
DBSCAN külastab igat andmepunkti vähemalt korra, sõltuvalt sellest, mitmesse klastrisse seda punkti üritatakse sobitada. Samas on naaberpunktide pärimine teatud raadiuse  piires, mida tehakse ainult ühe korra iga punkti jaoks, veelgi aeganõudvam operatsioon. Naaberpunktide pärimise kiirus sõltub sellest, kas punktid on indekseeritud. Juhul kui on, võib naaberpunktide päringu keerukus olla  ning kogu algoritmi keerukus . Ilma mõne kiirendava indeksi struktuurita või muu optimeeritud päringuta oleks DBSCAN-i halvima juhu ajaline keerukus . Selle kiirendamiseks võib luua punktidevaheliste kauguste maatriksi suurusega  (ruumilise keerukusega ), et vähendada kauguste arvutusi, kuid maatriksita lahenduse ruumiline keerukus oleks .

 Eelised 
 Erinevalt paljudest teistest klasterdusalgoritmidest, ei nõua DBSCAN klastrite arvu sisendparameetrina (nagu nt k-keskmiste meetod).
 Kuna DBSCAN on tiheduspõhine, ei tee see klastrite kuju kohta mingeid eeldusi. DBSCAN-iga oleks võimalik eristada klastreid, kus üks on teise sees.
 Isoleeritud punktid saab märgendada müraks, et need ei mõjutaks klasterdamise kvaliteeti.
 Kaugusmõõdik ei pea olema ilmtingimata eukleidiline.

 Puudused 
 DBSCAN ei ole täiesti deterministlik klastri äärepunktide suhtes, mille märgend võib sõltuda punktide töötlusjärjekorrast. Tuumpuntkid ja mürapunktid on seevastu alati deterministlikult märgendatud.
 DBSCAN klasterdab andmeid tiheduse ( ja  kombinatsiooni) põhjal. Kui andmepunktide tihedused on märgatavalt erinevas suurusjärgus, langeb klasterdamise kvaliteet. Klasterduse kvaliteet langeb oluliselt andmetel, kus andmepunktide tihedused on märgatavalt erinevad.

 Viited 

Kategooria:Algoritmid