DBSCAN

Allikas: Vikipeedia
Mine navigeerimisribale Mine otsikasti

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.[1]

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.[2]

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

Põhimõte[muuda | muuda lähteteksti]

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).[1]

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[muuda | muuda lähteteksti]

Järgnev pseudokood kirjeldab originaalset DBSCAN-i implementatsiooni.[4]

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[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

  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[muuda | muuda lähteteksti]

  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 ( 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[muuda | muuda lähteteksti]

  1. 1,0 1,1 Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M., toim. "A density-based algorithm for discovering clusters in large spatial databases with noise". Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. lk 226–231. ISBN 1-57735-004-9. 
  2. "Archived copy". Originaali arhiivikoopia seisuga 21.04.2010. Vaadatud 7.03.2018.  Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.
  3. "2014 SIGKDD Test of Time Award". ACM SIGKDD. 18.08.2014. Vaadatud 7.03.2018. 
  4. Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (juuli 2017). "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN". ACM Trans. Database Syst. 42 (3): 19:1–19:21. ISSN 0362-5915. doi:10.1145/3068335.