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.[1] A 2020[update], el document de seguiment "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN" [2] apareix a la llista dels 8 articles més descarregats de la prestigiosa revista ACM Transactions on Database Systems (TODS).[3]
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.[4] 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
[modifica]El 1972, Robert F. Ling va publicar un algorisme estretament relacionat a "The Theory and Construction of k-Clusters" [5] a The Computer Journal amb una complexitat d'execució estimada de O(n³).[5] 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
[modifica]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í p1,..., pn p1,..., pn amb p1 = p i pn = q, on cada pi+1 és directament accessible des de pi. 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
[modifica]Algorisme original basat en consultes
[modifica]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
[modifica]L'algorisme DBSCAN es pot resumir en els passos següents: [6]
- 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
[modifica]- ↑ «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.
- ↑ 5,0 5,1 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.