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

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

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₁,..., p_n p₁,..., p_n amb p₁ = 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:

1. Tots els punts del clúster estan mútuament connectats per densitat.
2. 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: ^[6]

1. Trobeu els punts del barri ε (eps) de cada punt i identifiqueu els punts centrals amb més de minPts veïns.
2. Trobeu els components connectats dels punts centrals al gràfic veí, ignorant tots els punts no centrals.
3. 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