DBSCAN

El agrupamiento espacial basat en densitat d'aplicacions en soroll o Density-based spatial clustering of applications with noise (DBSCAN) és un algoritme de agrupamiento de senyes (data clustering) propost per Martin Ester, Hans-Peter Kriegel, Jörg Sander i Xiaowei Xu en 1996. És un algoritme de agrupamiento basat en densitat (density-based clustering) perque troba un número de grups (clusters) començant per una estimació de la distribució de densitat dels nodos corresponents. DBSCAN és un dels algoritmes de agrupamiento més usats i citats en la lliteratura científica. OPTICS pot vore's com una generalisació de DBSCAN per a múltiples rancs, reemplaçant el paràmetro i pel radi màxim de busca.

En 2014, l'algoritme va ser mereixedor del premi a la prova del temps (un reconeiximent donat a algoritmes que han rebut una substancial atenció en la teoria i la pràctica) en la conferència líder de la mineria de senyes, KDD.

El paper "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN" apareix en la llista dels 8 artículs més descarregats en la revista ACM Transactions on Database Systems (TODS).

Preliminars

Archiu:DBSCAN-Illustration.svg

Els punts marcats com A són punts núcleu. Els punts B i C són densament alcanzables des d'i densament conectats en A, i pertanyen al mateix clúster. El punt N és un punt sorollós que no és núcleu ni densament alcanzable. (MinPts=3 o MinPts=4)

Considere un conjunt de punts a ser agrupats en un espai determinat. La tècnica d'agrupació DBSCAN classifica els punts com a punts núcleu, punts (densament-)alcanzables, o soroll de la següent forma:

• Un punt $p$ és un punt núcleu si a lo manco minPts punts estan a una distància ε d'ell. Es diu que estos punts són directament alcanzables des de $p$. No és possible tindre punts directament alcanzables des d'un punt que no siga un núcleu.
• Un punt $q$ és alcanzable des de $p$ si existix una seqüència de punts $p_1,\mathrm{...},p_n$ a on $p_1=p$ i $p_n=q$ tal que cada punt $p_{i+1}$ és directament alcanzable des de $p_i$; és dir, tots els punts de la seqüència deuen ser punts núcleus, en la possible excepció de $q$.
• Un punt que no siga alcanzable des de qualsevol atre punt és considerat soroll.

Si $p$ és un punt núcleu, este forma un cluster junt a atres punts (núcleu o no) que siguen alcanzables des d'ell. Cada cluster conté a lo manco un punt núcleu. Els punts no núcleus alcanzables poden pertànyer a un cluster pero actuen com una barrera posat que no és possible alcançar més punts des d'estos.

Note que la relació de ser alcanzable no és simètrica. Per definició, cap punt pot ser alcanzable des d'un punt que no siga núcleu, sense importar la distància a la que es trobe, és dir, un punt que no siga núcleu pot ser alcanzable pero res pot ser alcançat des d'est. Per lo tant la noció de connectividad és necessària per a definir formalment l'extensió d'un cluster donada per DBSCAN. Dos punts $p$ i $q$ estan conectats densament si existix un punt $o$ tal que abdós $p$ i $q$ siguen directament alcanzables des de $o$. La relació estar densament conectat és simètrica.

Un clúster, satisfà per lo tant dos propietats:

1. Tots els punts del clúster estan densament conectats entre sí.
2. Si un punt A és densament alcanzable des de qualsevol atre punt B del clúster, llavors A també forma part del clúster.

La variant DBSCAN* no distinguix entre nodos brode i nodos sorollosos. Els clusters consistixen solament en nodos que estan densament conectats entre sí, esta idea és més propenca a l'interpretació estadística de la densitat de components conexas (components conexas). El agrupamiento resultant, per lo general, conté més nodos sorollosos.

Algoritme

DBSCAN requerix dos paràmetros: $e$ (eps) i el número mínim de punts requerits per a que una regió es considere densa (minPts). L'algoritme comença per un punt arbitrari que no haja segut visitat. La $e$-veïnat d'este punt és visitada, i si conté suficients punts, s'inicia un clúster sobre el mateix. De lo contrari, el punt és etiquetat com a soroll. Notar que el punt en qüestió pot pertànyer a un atre veïnat que ho incloga en el clúster corresponent.

Si un punt s'inclou en la part densa d'un clúster, el seu $e$-veïnat també forma part del clúster. Aixina, tots els punts de dita veïnat s'afigen al clúster, de la mateixa manera que les $e$-veïnat d'estos punts que siguen lo suficientment denses. Este procés continua fins a construir completament un clúster densament conectat. Llavors, un nou punt no visitat es visita i processa en l'objectiu de descobrir un atre clúster o soroll.

En el següent Pseudocódigo es descriu este algoritme:

DBSCAN(D, eps, MinPts)
   C = 0
   for each unvisited point P in dataset D
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE
      else
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)

expandCluster(P, NeighborPts, C, eps, MinPts)
   add P to cluster C
   for each point P' in
      NeighborPts if P' is not visited
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      if P' is not yet member of any cluster
         add P' to cluster C

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

Referències

Bibliografia

• (2011).WIRÉs Data Mining and Knowledge Discovery.1(3)

231–240.doi:10.1002/widm.30.Consultat el 18 de decembre de 2014.