Lehekülje DBSCAN lähteteksti vaatamine

'''DBSCAN''' (ingliskeelsest '''''Density Based Spatial Clustering of Applications with Noise''''') on tiheduspõhine [[Klasteranalüüs|klasterdusalgoritm]], mille lõid Martin Ester, Hans-Peter Kriegel, Jörg Sander ja Xiaowei Xu aastal 1996.<ref name="dbscan">{{Cite conference
 | author1-first = Martin | author1-last = Ester | author2-link = Hans-Peter Kriegel | author2-first = Hans-Peter | author2-last =Kriegel | first3 = Jörg | last3 = Sander | first4 = Xiaowei | last4 = Xu
 | title = A density-based algorithm for discovering clusters in large spatial databases with noise
 |  pages = 226–231
 | editor1-first = Evangelos | editor1-last = Simoudis | editor2-first = Jiawei | editor2-last = Han | editor3-first = Usama M. | editor3-last = Fayyad
 | conference = Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96)
 | publisher = [[AAAI Press]]
 | year = 1996
 | isbn = 1-57735-004-9 
 | citeseerx = 10.1.1.121.9220
}}</ref>

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.<ref>{{cite web |url=http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm |title=Archived copy |accessdate=7.03.2018 |url-status=dead |archiveurl=https://web.archive.org/web/20100421170848/http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm |archivedate=21.04.2010 |df= }} Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.</ref>

2014. aastal sai algoritm KDD andmekaevekonverentsil SIGKDD auhinna "Test of Time".<ref>{{cite web|url=http://www.kdd.org/News/view/2014-sigkdd-test-of-time-award|date=18.08.2014|accessdate=7.03.2018|title=2014 SIGKDD Test of Time Award|publisher=[[Association for Computing Machinery|ACM]] SIGKDD}}</ref>

== Põhimõte ==
DBSCAN jagab andmepunktid kolme klassi: tuumpunktid (''core points''), kättesaadavad punktid (''reachable points'') ja müra (''noise'').
* Punkt <math>p</math> on tuumpunkt, kui vähemalt <math>minPts</math> punkti (sealhulgas punkt <math>p</math> ise) on sellest kaugusel <math>\varepsilon</math> või lähemal, kus <math>\varepsilon</math> on punkti <math>p</math> naabruspiirkonna raadius. Neid punkte loetakse otseselt kättesaadavaks punkti <math>p</math> kaudu.
* Punkt <math>q</math> on otseselt kättesaadav punkti <math>p</math> kaudu, kui punkt <math>p</math> asub punkti <math>q</math> naabruspiirkonnas ja punkt <math>p</math> on tuumpunkt.
* Punkt <math>q</math> on kättesaadav punkti <math>p</math> kaudu, kui leidub ahel <math>p_1, \ldots, p_n</math>, kus <math>p_1=p</math> ja <math>p_n=q</math> ning punkt <math>p_{i+1}</math> on otseselt kättesaadav punkti <math>p_i</math> kaudu. Seega kõik punktid ahelas (erandiks võib olla <math>q</math>) on tuumpunktid. 
* Punktid, mis ei ole kättesaadavad ühegi teise punkti kaudu, loetakse müraks.

Kui <math>p</math> on tuumpunkt, moodustab see klastri koos kõigi teiste punktidega, mis on <math>p</math> kaudu kättesaadavad (olenemata sellest, kas need on tuumpunktid või mitte).<ref name="dbscan" />
[[Pilt:DBSCAN-Illustration.svg|pisi|center|400px|Sellel diagrammil on <math>minPts = 4</math>. Punkt A ja teised punased punktid on tuumpunktid, kuna nende naabruspiirkonnas, raadiusega <math>\varepsilon</math>, 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.<ref name="tods">{{Cite journal|last=Schubert|first=Erich|last2=Sander|first2=Jörg|last3=Ester|first3=Martin|last4=Kriegel|first4=Hans Peter|author-link4=Hans-Peter Kriegel|last5=Xu|first5=Xiaowei|date=juuli 2017|title=DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN|url=https://www.vitavonni.de/research/acm.html#item3068335|journal=ACM Trans. Database Syst.|volume=42|issue=3|pages=19:1–19:21|doi=10.1145/3068335|issn=0362-5915}}</ref>
 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 <math>\varepsilon</math> 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 [[Algoritmiline keerukus|keerukus]] olla <math>O(\log n)</math> ning kogu algoritmi keerukus <math>O(n\log n)</math>. Ilma mõne kiirendava indeksi struktuurita või muu optimeeritud päringuta oleks DBSCAN-i halvima juhu ajaline keerukus <math>O(n^2)</math>. Selle kiirendamiseks võib luua punktidevaheliste kauguste [[maatriks]]i suurusega <math>(n^2-n)/2</math> (ruumilise keerukusega <math>O(n^2)</math>), et vähendada kauguste arvutusi, kuid maatriksita lahenduse ruumiline keerukus oleks <math>O(n)</math>.

== Eelised ==
# Erinevalt paljudest teistest klasterdusalgoritmidest, ei nõua DBSCAN klastrite arvu sisendparameetrina (nagu nt [[K-keskmiste meetod|''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 ruum|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 (<math>minPts</math> ja <math>\varepsilon</math> 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 ==
{{viited}}

[[Kategooria:Algoritmid]]