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 111: Linha 111:


[[Ficheiro:AgrupamentoFinal.png|500px|miniaturadaimagem|centro|Resultado final do agrupamento.]]
[[Ficheiro:AgrupamentoFinal.png|500px|miniaturadaimagem|centro|Resultado final do agrupamento.]]

== Requisitos ==

== Paralelizações existentes ==

Esta seção descreve como o a implementação do ''DBScan'' já foi realizada para suportar grandes volumes de dados.

Em é apresentado uma implementação paralela do ''DBScan'' com uma abordagem mestre-escravo: enquanto o núcleo mestre realiza a etapa de assimilação de grupos, os escravos respondem a consultas de vizinhança usando a estrutura ''R*-Tree'' para armazenamento.

Em ''P-DBSCAN'' , a base é particionada e o agrupamento é feito de forma independente entre os nós de forma distribuída. Ao final, há uma agregação dos resultados de cada nó para formar o resultado final. Quanto ao armazenamento, a estrutura utilizada é a ''Priority R-Tree'' que é uma variação eficiente da ''R-Tree''. Nessa implementação há a limitação de haver um único nó para juntar os resultados do agrupamento feito por todos os nós. Além disso, os pontos considerados exceções por um nó não são tratados posteriormente na junção dos grupos, portanto grupos densos podem ser perdidos se seus registros estiverem divididos entre os nós.

De forma similar ao ''P-DBSCAN'', o ''MR-DBSCAN'', proposto em , é uma implementação distribuída do ''DBScan'' com quatro estágios e que utiliza o paradigma ''Map-reduce'' . A primeira etapa consiste em dividir a base entre os nós de forma balanceada e de forma a deixar os registros mais próximos no mesmo nó. Em seguida, na fase ''map'', o ''DBScan'' é executado de forma independente dentro de cada nó. A terceira etapa é a fase ''reduce'': todos os nós são analisados para descobrir em quais situações o mesmo nó foi agrupado para diferentes grupos, ou seja, é feito um mapeamento da junção e remarcação dos grupos que é realizada na quarta e última etapa. Os resultados mostraram que a escalabilidade e a eficiência dessa abordagem são bastante satisfatórias.

Em ''SDBDC''<ref>''Scalable Density-Based Distributed Clustering''
</ref> , que é uma melhora de , também é realizada a tarefa de agrupamento baseada em densidade de forma distribuída. Nessa abordagem, os pontos centrais de cada nó são determinados e a partir deles, os pontos representativos globais são identificados. A partir dessa informação sobre os pontos representativos globais, os pontos de cada nó são rotulados para os grupos. Portanto essa técnica parte de uma informação local para gerar uma análise global e novamente gerar uma informação local. Há a possibilidade do usuário balancear a quantidade de pontos considerados representativos em cada nó, o que pode aumentar o tempo de execução e a qualidade ou realizar uma execução mais rápida com menos qualidade.

Considerando os trabalhos existentes de paralelização do ''DBScan'', conclui-se que o agrupamento distribuído baseado em densidade não é uma tarefa trivial e há vários fatores a serem balanceados já que é inviável atender a todos. Alguns desses fatores são a comunicação, a descentralização de tarefas, a completude e a qualidade da solução.

Se há muita centralização das tarefas, perde-se em escalabilidade porém há ganhos quanto à completude e à qualidade do agrupamento. Por exemplo, se o agrupamento é feito de forma independente entre os nós para que depois haja uma união centralizada dos grupos, quanto mais informações for considerada de cada nó, maior será a qualidade, porém menor será a eficiência. Por exemplo, se os pontos considerados exceções não forem considerados nessa etapa de união dos grupos, pode-se perder informações sobre os grupos que poderiam ser formados se esses pontos estivessem juntos. Por outro lado, a escalabilidade da aplicação seria comprometida se esses pontos fossem considerados.

A comunicação é outro fator que se comporta de forma similar à centralização: quanto mais comunicação, maior será o ''overhead'' da aplicação, porém melhor a qualidade dos resultados. Em nenhum dos trabalhos vistos houve uso de comunicação durante o processo de execução do algoritmo nos nós.

Portanto, como o agrupamento baseado em densidade depende de informações globais sobre vizinhança entre os pontos e a implementação paralela ou distribuída deve ser capaz de encontrar um balanceamento entre agregação dos dados globais (centralização ou comunicação), eficiência e qualidade.

<references />

Revisão das 12h51min 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.


Exemplo de funcionamento

Essa seção mostra passo-a-passo como o DBScan realiza o agrupamento para os dados mostrados na figura 3 com parâmetros de distância e número mínimo de vizinhos iguais a e , respectivamente.

Distribuição dos pontos a serem agrupados.


Inicialmente, a distância entre os pares de registros são calculados. Os valores estão mostrados na tabela abaixo.

Ponto 1 2 3 4 5 6 7 8
1 0
2 - 0
3 - - 0
4 - - - 0
5 - - - - 0
6 - - - - - 0
7 - - - - - - 0
8 - - - - - - - 0


A medida que os pares de pontos têm suas distâncias calculas, os pontos são classificados como ponto de centro, de borda, ou exceção. Observa-se que nesse exemplo para dois pontos serem considerados vizinhos eles devem estar a uma distância menor ou igual a . O resultado da classificação está mostrado abaixo.

Classificação Pontos
Pontos de centro 3,5,6,8
Pontos de borda 1,4
Exceções 2,7


Na segunda fase do DBScan, os pontos de centro são percorridos. O primeiro grupo criado possui o ponto de centro 3 e durante o percorrimento de seus vizinhos, os pontos 5 e 6 são assimilados a esse grupo. O segundo grupo criado possui inicialmente o ponto de centro 8 e a medida que seus vizinhos são perridos, os pontos 1 e 4 também são assimilados a ele. Os pontos 2 e 7 não são vizinhos de nenhum ponto de centro e por isso não são assimilados a nenhum grupo. A figura 4 mostra o resultado do agrupamento para esse exemplo.

Resultado final do agrupamento.

Requisitos

Paralelizações existentes

Esta seção descreve como o a implementação do DBScan já foi realizada para suportar grandes volumes de dados.

Em é apresentado uma implementação paralela do DBScan com uma abordagem mestre-escravo: enquanto o núcleo mestre realiza a etapa de assimilação de grupos, os escravos respondem a consultas de vizinhança usando a estrutura R*-Tree para armazenamento.

Em P-DBSCAN , a base é particionada e o agrupamento é feito de forma independente entre os nós de forma distribuída. Ao final, há uma agregação dos resultados de cada nó para formar o resultado final. Quanto ao armazenamento, a estrutura utilizada é a Priority R-Tree que é uma variação eficiente da R-Tree. Nessa implementação há a limitação de haver um único nó para juntar os resultados do agrupamento feito por todos os nós. Além disso, os pontos considerados exceções por um nó não são tratados posteriormente na junção dos grupos, portanto grupos densos podem ser perdidos se seus registros estiverem divididos entre os nós.

De forma similar ao P-DBSCAN, o MR-DBSCAN, proposto em , é uma implementação distribuída do DBScan com quatro estágios e que utiliza o paradigma Map-reduce . A primeira etapa consiste em dividir a base entre os nós de forma balanceada e de forma a deixar os registros mais próximos no mesmo nó. Em seguida, na fase map, o DBScan é executado de forma independente dentro de cada nó. A terceira etapa é a fase reduce: todos os nós são analisados para descobrir em quais situações o mesmo nó foi agrupado para diferentes grupos, ou seja, é feito um mapeamento da junção e remarcação dos grupos que é realizada na quarta e última etapa. Os resultados mostraram que a escalabilidade e a eficiência dessa abordagem são bastante satisfatórias.

Em SDBDC[1] , que é uma melhora de , também é realizada a tarefa de agrupamento baseada em densidade de forma distribuída. Nessa abordagem, os pontos centrais de cada nó são determinados e a partir deles, os pontos representativos globais são identificados. A partir dessa informação sobre os pontos representativos globais, os pontos de cada nó são rotulados para os grupos. Portanto essa técnica parte de uma informação local para gerar uma análise global e novamente gerar uma informação local. Há a possibilidade do usuário balancear a quantidade de pontos considerados representativos em cada nó, o que pode aumentar o tempo de execução e a qualidade ou realizar uma execução mais rápida com menos qualidade.

Considerando os trabalhos existentes de paralelização do DBScan, conclui-se que o agrupamento distribuído baseado em densidade não é uma tarefa trivial e há vários fatores a serem balanceados já que é inviável atender a todos. Alguns desses fatores são a comunicação, a descentralização de tarefas, a completude e a qualidade da solução.

Se há muita centralização das tarefas, perde-se em escalabilidade porém há ganhos quanto à completude e à qualidade do agrupamento. Por exemplo, se o agrupamento é feito de forma independente entre os nós para que depois haja uma união centralizada dos grupos, quanto mais informações for considerada de cada nó, maior será a qualidade, porém menor será a eficiência. Por exemplo, se os pontos considerados exceções não forem considerados nessa etapa de união dos grupos, pode-se perder informações sobre os grupos que poderiam ser formados se esses pontos estivessem juntos. Por outro lado, a escalabilidade da aplicação seria comprometida se esses pontos fossem considerados.

A comunicação é outro fator que se comporta de forma similar à centralização: quanto mais comunicação, maior será o overhead da aplicação, porém melhor a qualidade dos resultados. Em nenhum dos trabalhos vistos houve uso de comunicação durante o processo de execução do algoritmo nos nós.

Portanto, como o agrupamento baseado em densidade depende de informações globais sobre vizinhança entre os pontos e a implementação paralela ou distribuída deve ser capaz de encontrar um balanceamento entre agregação dos dados globais (centralização ou comunicação), eficiência e qualidade.

  1. Scalable Density-Based Distributed Clustering