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

Origem: Wikilivros, livros abertos por um mundo aberto.
[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Linha 31: Linha 31:
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.
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.'']]
[[Ficheiro:Classificacao.png|500px|miniaturadaimagem|centro|''Figura 2: Classificação dos pontos de acordo com o DBScan sendo o valor do parâmetro N igual a 5.'']]





Revisão das 12h16min de 15 de fevereiro de 2013

Descrição

Denominação

Agrupamento de dados massivos baseado em densidade.

Contexto

A mineração de dados é uma área da computação que visa a análise de dados para extração de informação e conhecimento. As tarefas de mineração podem ser divididas em supervisionadas, quando são usados registros conhecidos para o aprendizado de máquina, e não-supervisionada quando não há uso de registros para induzir os resultados.

O agrupamento é uma tarefa não-supervisionada de mineração de dados que consiste em dividir os registros da base de dados em grupos de forma a deixar os mais similares entre si em grupos iguais e os menos similares em grupos distintos. Essa tarefa possui inúmeras aplicações, dentre as quais pode-se destacar os sistemas de recomendação, predição de funções proteicas e resolução de entidades.

Três dos principais algoritmos de agrupamento são o K-means , o Expectation Maximization - EM e o DBScan . Ao contrário do DBScan, o K-Means e o EM são algoritmos que exigem como parâmetro o número de grupos a serem formados e não são capazes de formar grupos com formatos arbitrários, além de serem sensíveis à presença de exceções. Porém o DBScan é o algoritmo mais caro entre eles: apresenta custo quadrático em relação ao tamanho da base.

Considerando que essa abordagem baseada em densidade é fundamental para algumas aplicações, como por exemplo, quando o número de grupos não é conhecido ou quando há exceções na base, e se observado o crescente volume de dados disponíveis, torna-se desejável a utilização desse algoritmo para suportar dados massivos de forma que o agrupamento possa ser realizado com eficiência e escalabilidade.

Algoritmo

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.

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 definição de vizinhança V nesse contexto para um determinado ponto P é dada pelo conjunto de pontos que estão a uma distância d menor ou igual a D, ou seja,

V(P) = {Y | d(P,Y) <= D}.

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.

Figura 2: Classificação dos pontos de acordo com o DBScan sendo o valor do parâmetro N igual a 5.


Após essa etapa de classificação, os pontos de centro são percorridos e seus vizinhos são assimilados a seu grupo. Se um dos vizinhos do ponto de centro que está sendo percorrido for outro ponto de centro X, o algoritmo passa a percorrer os vizinhos de X. Observa-se que a ordem de percorrimento dos pontos de centro não alteram a disposição dos pontos de centro entre os grupos, porém pode influenciar na assimilação dos pontos de borda aos grupos. Os pontos exceções não são assimilados a nenhum grupo, independente da ordem de percorrimento. O algoritmo abaixo mostra os passos executados pelo DBScan conforme REFERÊNCIA.

 DBScan(B, D, N):

Para cada registro P em B {
Computa os vizinhos de P;
Classifica P;
}
grupoAtual = 0;
Para cada ponto de centro P não visitado {
grupoAtual++;
Assimila(P, grupoAtual);
}
Retorna resultado do agrupamento;

Assimila(P, grupoAtual):
Assimila P ao grupo grupoAtual;
Para cada vizinho Q de P {
Assimila Q ao grupo grupoAtual;
Se Q é ponto de centro {
Assimila(Q, grupoAtual);
} }

Quanto ao armazenamento, a implementação original do DBScan utiliza a estrutura R*-tree REFERÊNCIA para manter todos os registros em memória secundária.