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 \varepsilon või lähemal, kus \varepsilon 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, \ldots, 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).

## 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| \varepsilon 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
# 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 (minPts ja \varepsilon 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