Upload
ama
View
63
Download
0
Embed Size (px)
DESCRIPTION
Método de Clusterização baseado em Densidade Algoritmo DBSCAN. AULA 12 DATA MINING Sandra de Amo. Algoritmos Baseados em Densidade. Definição: Clusters são regiões de alta densidade de padrões separadas por regiões com baixa densidade, no espaço de padrões. - PowerPoint PPT Presentation
Citation preview
Método de Clusterização baseado em Densidade
Algoritmo DBSCAN
AULA 12
DATA MINING
Sandra de Amo
Algoritmos Baseados em Densidade Definição: Clusters são regiões de alta
densidade de padrões separadas por regiões com baixa densidade, no espaço de padrões.
Algoritmos baseados em densidade são projetados para encontrar clusters segundo esta definição.
O que são regiões densas ? Esparsas ? Definição baseada em centros:
Uma região densa é uma região onde cada ponto tem muitos pontos em sua vizinhança.
Muitos ??
Vizinhança ??
Parâmetros de Ajuste
Parâmetros de Ajuste Vizinhança: raio Eps Muitos : MinPts Assim, uma região densa é uma região em
que todos os pontos têm pelo menos MinPts pontos num raio de Eps ao seu redor
Eps
MinPts = 13
Observação A densidade de cada objeto depende dos
parâmetros Eps e MinPts Se Eps é muito grande, então é possivel que
todos os objetos tenham densidade grande (= m = número de objetos da base).
Se Eps é muito pequeno, então é possível que todos os objetos tenham baixa densidade.
Tipos de Objetos Objeto Core : está no interior de uma região densa.
Existem pelo menos MinPts objetos num raio Eps ao redor do objeto.
Objeto fronteiriço : está na fronteira de uma região densa. Está na vizinhança Eps de um objeto core, mas não é um
objeto core. Objetos outliers: está em uma região de baixa
densidade. Não é objeto core nem está numa vizinhança de um
objeto core.
Exemplo
p
q
p: objeto fronteiriço
q: objeto core
w: objeto outlier
MinPts = 5
Eps = 1cm
w
1 cm
Cadeia de objetos Um objeto p é diretamente alcançável pela
densidade a partir de um objeto q (com relação aos parâmetros Eps, MinPts) se: p Neps(q)
Neps(q) : {q’ BD | d(q,q’) ≤ Eps}
|Neps(q)| ≥ MinPts
Exemplo
p
q
p é diretamente alcançável a partir de q
MinPts = 5
Eps = 1cm
1 cm
Cadeia de objetos
Alcançável por Densidade Um objeto p é alcançável por densidade a partir de um
objeto q (com relação aos parâmetros Eps, MinPts) se existe uma cadeia de objetos q = p1, p2, p3,..., pn = p
tal que pi+1 é diretamente alcançável por densidade a partir de pi.
p3
pq
p2
Conexão por Densidade
Um objeto p é conectado por densidade a um objeto q (com respeito aos parâmetros Eps, MinPts) se existir um objeto O tal que p e q são alcançáveis por densidade a partir de O.
q
O
p
Exercicio 1 Se p é alcançável por densidade a partir de q,
isto não implica que q é alcançável por densidade a partir de p.
p
q
Exercicio 2 Se p é alcançável por densidade a partir de q,
e ambos são objetos core, é verdade que q também será alcançável por densidade a partir de p ?
Exercício 3 A relação “conectável por densidade” é
simétrica ?
Algoritmo DBSCAN Entrada
Eps, MinPts, um banco de dados BD Saída
Um conjunto de K clusteres tais que:
Objetos dentro de um mesmo cluster são conectados por densidade
Objetos em clusters distintos não são conectados por densidade.
Observação: Repare que o número K de clusteres é encontrado pelo algoritmo, não é dado como input.
Método : Etapa 1 Calcula a vizinhança Eps de cada objeto do
banco de dados Detecta os que são objetos core Cada objeto core q será o representante de um
cluster formado por sua vizinhança Neps(q) Enumera-se os clusteres assim obtidos
C1, C2, ... , Ck1
Seus representantes são p1, p2, ..., pk1
Etapa 2i = 1Procura o primeiro j tal que pj é diretamente alcançável a partir de p1
p1
pj
Une-se os clusteres C1 e Cj
Os novos representantes do novo cluster são p1 e pj
i = primeiro n ϵ {1,...,k1}, diferente de 1 e jRepete-se o processo para Ci e o primeiro Cj’ tais que pj’ seja diretamente alcançável a partir de pi
Final da Etapa 2
p1 p2
p5
p3
p6p4
p7
Etapa 3
p1
p2
p5
p4
• Para cada cluster Ci da etapa 2, procura-se um cluster Cki tal que um de seus representantes é diretamente alcançável a partir de um dos representantes do cluster Ci
• Junta-se os clusters Ci e CkiCluster C1
Cluster C2
Parada do algoritmo O algoritmo pára na etapa N quando não há
mais possibilidade de se juntar clusteres formados na etapa N-1.
ExercícioSejam C1,...,Ck os clusteres produzidos pelo
algoritmo DBSCAN Se p e q estão num mesmo cluster Ci então p
e q são conectados por densidade Se p e q estão em clusteres distintos então p e
que não são conectáveis por densidade O que se pode dizer de um objeto p que não
está em nenhum cluster Ci ?
Como selecionar os parâmetros ? Verificar a distância ao k-ésimo vizinho
mais próximo k-distAnálise1. Para objetos que estão dentro de um cluster:
se k ≤ tamanho do cluster então k-dist é pequeno.
2. Para objetos que não estão dentro de um cluster: k-dist é grande
Seleciona-se os k-dist para cada objeto, para um determinado valor de k.
Ordena-se os objetos pelos valores de k-dist No ponto onde houver uma grande variação do número k-
dist, significa que foi atingido um valor adequado para Eps. Só funciona se os clusteres não apresentarem grandes
variações de densidade. Valor de Eps depende do número k escolhido.
Na prática, o valor k = 4 é utilizado para a maioria dos banco de dados, com bons resultados
Como selecionar os parâmetros ?
Exemplo: BD com 3000 objetos
K-d
ist
Objetos 500 1000 1500 2000 2500 3000
10
20
30
40
50
Eps = 10
MinPts = 4
Crescimento muito grande de k-dist
10
Problema: Clusteres com diferentes densidades
A B C D
• Se Eps é alto suficiente para que C e D sejam detectados como clusteres então A e B e a região a sua volta se tornarão um unico cluster
• Se Eps é baixo suficiente para que A e B sejam detectados como clusteres separados então C e D (e os objetos a seu redor) serão considerados outliers !
Parâmetros versus Tipos de clusteres
Eps MinPt Resultado
Alto Alto Poucos clusters, grandes e densos
Baixo Baixo Muitos clusters, pequenos e menos densos
Alto Baixo Clusters grandes e menos densos
Baixo Alto Clusters pequenos e densos
Avaliação de desempenho: qualidade dos clusteres produzidos
Agrupamentos descobertos por CLARANS
Agrupamentos descobertos por DBSCAN
Avaliação de desempenho: qualidade dos clusteres produzidos
Tempo de execução em segundos
Vantagens e Desvantagens Vantagens Eficiente em tratar grandes bases de dados Menos sensível a ruídos Forma clusters de formato arbitrário Usuário não precisa especificar a quantidade de clusters Desvantagens Sensível aos parâmetros de entrada(Eps e MinPt) Produz resultados não confiáveis se os clusteres têm
densidades muito diferentes.
Referência M. Ester, H.-P Kriegel, J. Sander, X. Xu: A
Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, pp. 226-231, 1996.