O DBSCAN opera com base na ideia de alcance de densidade. Ele define clusters como regiões densas de pontos de dados separadas por áreas de menor densidade. Dois parâmetros principais determinam seu funcionamento:

• Épsilon (ε): o raio dentro do qual se busca por pontos vizinhos;

• Número mínimo de pontos (MinPts): o número mínimo de pontos exigido dentro do raio ε para formar uma região densa (incluindo o próprio ponto).

O DBSCAN classifica os pontos em três categorias:

• Pontos centrais: um ponto é considerado central se possui pelo menos MinPts dentro do seu raio ε;

• Pontos de fronteira: um ponto é de fronteira se possui menos que MinPts dentro do seu raio ε, mas é alcançável a partir de um ponto central (ou seja, está dentro do raio ε de um ponto central);

• Pontos de ruído: um ponto que não é nem central nem de fronteira é considerado um ponto de ruído.

Algoritmo

1. Começar com um ponto arbitrário não visitado;

2. Encontrar todos os pontos dentro do seu raio ε;

3. Se um ponto possui pelo menos MinPts vizinhos dentro do raio ε, ele é marcado como ponto central, iniciando um novo cluster que se expande recursivamente ao adicionar todos os pontos diretamente alcançáveis por densidade;

4. Se o número de pontos dentro do raio ε for menor que MinPts, marcar o ponto como ponto de fronteira (se estiver dentro do raio ε de um ponto central) ou como ponto de ruído (se não estiver);

5. Repetir os passos 1-4 até que todos os pontos sejam visitados.

Imagine um gráfico de dispersão de pontos de dados. O DBSCAN começaria escolhendo um ponto. Se encontrar vizinhos suficientes dentro do seu raio ε, ele o marca como ponto central e começa a formar um cluster. Em seguida, expande esse cluster verificando os vizinhos do ponto central e os vizinhos desses vizinhos, e assim por diante. Pontos que estão próximos de um ponto central, mas não possuem vizinhos suficientes, são marcados como pontos de fronteira. Pontos isolados são identificados como ruído.