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 governam 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 de seu raio ε;

• Pontos de borda: um ponto é considerado de borda se possui menos que MinPts dentro de 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 borda é considerado um ponto de ruído.

Algoritmo

1. Iniciar com um ponto arbitrário não visitado;

2. Encontrar todos os pontos dentro de 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 borda (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 de 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 borda. Pontos isolados são identificados como ruído.