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] |
Linha 170: | Linha 170: | ||
<td align="center">-</td> |
<td align="center">-</td> |
||
<td align="center">0</td> |
<td align="center">0</td> |
||
</tr> |
|||
</tbody> |
|||
</table> |
|||
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 <math>\sqrt{10}</math>. O resultado da classificação está mostrado abaixo. |
|||
[!h] |
|||
<table> |
|||
<thead> |
|||
<tr class="header"> |
|||
<th align="center">'''Pontos de centro'''</th> |
|||
<th align="center">3,5,6,8</th> |
|||
</tr> |
|||
</thead> |
|||
<tbody> |
|||
<tr class="odd"> |
|||
<td align="center">'''Pontos de borda'''</td> |
|||
<td align="center">1,4</td> |
|||
</tr> |
|||
<tr class="even"> |
|||
<td align="center">'''Exceções'''</td> |
|||
<td align="center">2,7</td> |
|||
</tr> |
</tr> |
||
</tbody> |
</tbody> |
Revisão das 12h23min 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.
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.
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.
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.
[!h]
<thead> </thead> <tbody> </tbody>Pontos de centro | 3,5,6,8 |
---|---|
Pontos de borda | 1,4 |
Exceções | 2,7 |