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.

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).

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 

Algoritmid