Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Agrupamento baseado em densidade: diferenças entre revisões

O ''DBScan'' é um algoritmo de agrupamento baseado em densidade de registros por região, o que permite a formação de grupos não-convexos e com formatos arbitrários. A figura 1 mostra um exemplo de registros que só podem ser agrupados corretamente utilizando-se esse algoritmo devido ao formato arbitrário dos grupos.

 

 

Essa técnica recebe dois valores como parâmetros: o valor de corte ''D'' que indica a distância máxima que dois pontos podem estar para eles serem considerados vizinhos e o número mínimo de vizinhos ''N'' que um ponto deve ter para ser considerado um ponto de centro, conforme será mostrado.

A principal limitação em termos de eficiência do DBScan é a sua primeira etapa que consiste em calcular a distância entre todos os pares possíveis de registros da base ''B'' para definir quantos vizinhos cada um possui e então classificá-los como ponto de centro, ponto de borda ou exceção. Os pontos de centro são aqueles que possuem ''N'' ou mais vizinhos. Os pontos de borda não possuem ''N'' ou mais vizinhos mas são vizinhos de um ponto de centro. Os registros considerados exceções possuem menos de ''N'' vizinhos e não são vizinhos de nenhum ponto de centro. A figura 2 ilustra as três classificações que um ponto pode receber nesse algoritmo.