DBSCAN funciona basándose en la idea de la alcanzabilidad por densidad. Define los clústeres como regiones densas de puntos de datos separadas por áreas de menor densidad. Dos parámetros clave rigen su comportamiento:

• Épsilon (ε): el radio dentro del cual se buscan los puntos vecinos;

• Número mínimo de puntos (MinPts): el número mínimo de puntos requeridos dentro del radio ε para formar una región densa (incluyendo el propio punto).

DBSCAN clasifica los puntos en tres categorías:

• Puntos núcleo: un punto es núcleo si tiene al menos MinPts dentro de su radio ε;

• Puntos frontera: un punto es frontera si tiene menos de MinPts dentro de su radio ε pero es alcanzable desde un punto núcleo (es decir, está dentro del radio ε de un punto núcleo);

• Puntos ruido: un punto que no es ni núcleo ni frontera se considera un punto de ruido.

Algoritmo

1. Comenzar con un punto arbitrario no visitado;

2. Encontrar todos los puntos dentro de su radio ε;

3. Si un punto tiene al menos MinPts vecinos dentro de un radio ε, se marca como punto núcleo, iniciando un nuevo clúster que se expande recursivamente añadiendo todos los puntos directamente alcanzables por densidad;

4. Si el número de puntos dentro del radio ε es menor que MinPts, marcar el punto como punto frontera (si está dentro del radio ε de un punto núcleo) o como punto de ruido (si no lo está);

5. Repetir los pasos 1-4 hasta que todos los puntos hayan sido visitados.

Imaginar un diagrama de dispersión de puntos de datos. DBSCAN comenzaría seleccionando un punto. Si encuentra suficientes vecinos dentro de su radio ε, lo marca como punto núcleo y empieza a formar un clúster. Luego expande este clúster revisando los vecinos del punto núcleo y los vecinos de estos, y así sucesivamente. Los puntos que están cerca de un punto núcleo pero no tienen suficientes vecinos se marcan como puntos frontera. Los puntos que están aislados se identifican como ruido.