# DBSCAN

La agrupació espacial d'aplicacions amb soroll basada en densitat (DBSCAN) és un algorisme de agrupació de dades proposat per Martin Ester, Hans-Peter Kriegel, Jörg Sander i Xiaowei Xu el 1996. És un algorisme no paramètric d'agrupament basat en la densitat: donat un conjunt de punts en algun espai, agrupa els punts que estan estretament empaquetats (punts amb molts veïns propers), marcant com a punts atípics que es troben sols en regions de baixa densitat. (els veïns més propers estan massa lluny). DBSCAN és un dels algorismes d'agrupació més comuns i més citats.
El 2014, l'algoritme va rebre el premi de prova del temps (un premi atorgat a algorismes que han rebut una atenció substancial en teoria i pràctica) a la conferència de mineria de dades líder, ACM SIGKDD. A 2020, el document de seguiment "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN" apareix a la llista dels 8 articles més descarregats de la prestigiosa revista ACM Transactions on Database Systems (TODS).
El popular seguiment HDBSCAN* va ser publicat inicialment per Ricardo JG Campello, David Moulavi i Jörg Sander el 2013, després es va ampliar amb Arthur Zimek el 2015. Revisa algunes de les decisions originals, com ara els punts de frontera, i produeix un resultat jeràrquic en lloc d'un resultat pla.

## Història

El 1972, Robert F. Ling va publicar un algorisme estretament relacionat a "The Theory and Construction of k-Clusters" a The Computer Journal amb una complexitat d'execució estimada de O(n³). DBSCAN té el pitjor cas d'O(n²) i la formulació de consulta de rang orientada a la base de dades de DBSCAN permet accelerar l'índex. Els algorismes difereixen lleugerament pel que fa al maneig dels punts de frontera.

## Preliminar

Considereu un conjunt de punts en algun espai per agrupar-los. Sigui ε un paràmetre que especifica el radi d'un veïnat respecte a algun punt. Amb el propòsit de l'agrupació DBSCAN, els punts es classifiquen com a punts bàsics, (directament -) punts accessibles i punts atípics, de la manera següent:
* Un punt p és un punt central si almenys minPts punts es troben a la distància ε d'aquest (incloent p).
* Un punt q és directament accessible des de p si el punt q es troba a la distància ε del punt central p. Només es diu que els punts són directament accessibles des dels punts centrals.
* Un punt q és accessible des de p si hi ha un camí p$_1$,..., p$_n$ p$_1$,..., p$_n$ amb p$_1$ = p i p$_n$ = q, on cada p$_i$$_{+1}$ és directament accessible des de p$_i$. Tingueu en compte que això implica que el punt inicial i tots els punts del camí han de ser punts centrals, amb la possible excepció de q.
* Tots els punts als quals no es pot arribar des de cap altre punt són atípics o punts de soroll.
Ara, si p és un punt central, llavors forma un clúster juntament amb tots els punts (nuclis o no centrals) als quals es pot accedir des d'ell. Cada clúster conté almenys un punt central; els punts no centrals poden formar part d'un clúster, però en formen la "vora", ja que no es poden utilitzar per arribar a més punts.
L'accessibilitat no és una relació simètrica: per definició, només els punts centrals poden arribar a punts no centrals. El contrari no és cert, de manera que es pot arribar a un punt no central, però no es pot arribar a res des d'ell. Per tant, cal una altra noció de connexió per definir formalment l'extensió dels clústers trobats per DBSCAN. Dos punts p i q estan connectats per densitat si hi ha un punt o tal que tant p com q són accessibles des de o. La connexió densitat és simètrica.
Aleshores, un clúster compleix dues propietats:
* Tots els punts del clúster estan mútuament connectats per densitat.
* Si un punt és accessible per densitat des d'algun punt del clúster, també forma part del clúster.

## Algoritme
### Algorisme original basat en consultes

DBSCAN requereix dos paràmetres: ε (eps) i el nombre mínim de punts necessaris per formar una regió densa (minPts). Comença amb un punt de partida arbitrari que no ha estat visitat. Es recupera el veïnat ε d'aquest punt i, si conté prou punts, s'inicia un clúster. En cas contrari, el punt s'etiqueta com a soroll. Tingueu en compte que aquest punt es podria trobar més tard en un entorn ε de mida suficient d'un punt diferent i, per tant, formar part d'un clúster.

### Algorisme abstracte

L'algorisme DBSCAN es pot resumir en els passos següents:
* Trobeu els punts del barri ε (eps) de cada punt i identifiqueu els punts centrals amb més de minPts veïns.
* Trobeu els components connectats dels punts centrals al gràfic veí, ignorant tots els punts no centrals.
* Assigneu cada punt no central a un clúster proper si el clúster és un veí ε (eps), en cas contrari assigneu-lo al soroll.
Una implementació ingènua d'això requereix emmagatzemar els barris al pas 1 i, per tant, requereix una memòria substancial. L'algorisme DBSCAN original no ho requereix fent aquests passos per un punt a la vegada.

## Referències

* ↑ «2014 SIGKDD Test of Time Award» (en anglès). ACM SIGKDD, 18-08-2014. [Consulta: 27 juliol 2016].
* ↑ Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei ACM Trans. Database Syst., 42, 3, 7-2017, pàg. 19:1–19:21. DOI: 10.1145/3068335. ISSN: 0362-5915.
* ↑ «TODS Home» (en anglès). tods.acm.org. Association for Computing Machinery. [Consulta: 16 juliol 2020].
* ↑ Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg ACM Transactions on Knowledge Discovery from Data, 10, 1, 2015, pàg. 1–51. DOI: 10.1145/2733381. ISSN: 1556-4681.
* 1 2 Ling, R. F. (en anglès) The Computer Journal, 15, 4, 01-01-1972, pàg. 326–332. DOI: 10.1093/comjnl/15.4.326. ISSN: 0010-4620.
* ↑ Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei ACM Trans. Database Syst., 42, 3, 7-2017, pàg. 19:1–19:21. DOI: 10.1145/3068335. ISSN: 0362-5915.