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 $p$ on tuumpunkt, kui vähemalt $minPts$ punkti (sealhulgas punkt $p$ ise) on sellest kaugusel $\epsilon$ või lähemal, kus $\epsilon$ on punkti $p$ naabruspiirkonna raadius. Neid punkte loetakse otseselt kättesaadavaks punkti $p$ kaudu.
• Punkt $q$ on otseselt kättesaadav punkti $p$ kaudu, kui punkt $p$ asub punkti $q$ naabruspiirkonnas ja punkt $p$ on tuumpunkt.
• Punkt $q$ on kättesaadav punkti $p$ kaudu, kui leidub ahel $p_1,\dots ,p_n$, kus $p_1=p$ ja $p_n=q$ ning punkt $p_{i+1}$ on otseselt kättesaadav punkti $p_i$ kaudu. Seega kõik punktid ahelas (erandiks võib olla $q$) on tuumpunktid.
• Punktid, mis ei ole kättesaadavad ühegi teise punkti kaudu, loetakse müraks.

Kui $p$ on tuumpunkt, moodustab see klastri koos kõigi teiste punktidega, mis on $p$ kaudu kättesaadavad (olenemata sellest, kas need on tuumpunktid või mitte).

Sellel diagrammil on $minPts=4$. Punkt A ja teised punased punktid on tuumpunktid, kuna nende naabruspiirkonnas, raadiusega $\epsilon$, 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 $\epsilon$ 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 $O(\log n)$ ning kogu algoritmi keerukus $O(n\log n)$. Ilma mõne kiirendava indeksi struktuurita või muu optimeeritud päringuta oleks DBSCAN-i halvima juhu ajaline keerukus $O(n^2)$. Selle kiirendamiseks võib luua punktidevaheliste kauguste maatriksi suurusega $(n^2-n)/2$ (ruumilise keerukusega $O(n^2)$), et vähendada kauguste arvutusi, kuid maatriksita lahenduse ruumiline keerukus oleks $O(n)$.

Eelised

1. Erinevalt paljudest teistest klasterdusalgoritmidest, ei nõua DBSCAN klastrite arvu sisendparameetrina (nagu nt k-keskmiste meetod).
2. 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.
3. Isoleeritud punktid saab märgendada müraks, et need ei mõjutaks klasterdamise kvaliteeti.
4. Kaugusmõõdik ei pea olema ilmtingimata eukleidiline.

Puudused

1. 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.
2. DBSCAN klasterdab andmeid tiheduse ($minPts$ ja $\epsilon$ 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.