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

Saltar para a navegação Saltar para a pesquisa
[edição não verificada][edição não verificada]
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.
 
[[Ficheiro:Situacao.png|miniaturadaimagem|centro|''Figura 1: Situação em que os registros só podem ser agrupados corretamente utilizando-se um algoritmo baseado em densidade.'']]
 
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.
 
[[Ficheiro:Classificacao.png|700px|miniaturadaimagem|centro|''Figura 2: Classificação dos pontos de acordo com o DBScan sendo o valor do parâmetro N igual a 5.'']]

Menu de navegação