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

[edição não verificada][edição não verificada]
 
[[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 />