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.


Objeto fronteiriço : está na fronteira de uma região
densa.


Existem pelo menos MinPts objetos num raio Eps ao
redor do objeto.
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: objeto fronteiriço
w
q: objeto core
1 cm
w: objeto outlier
p
q
MinPts = 5
Eps = 1cm
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 é diretamente alcançável
a partir de q
MinPts = 5
Eps = 1cm
p
q
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.
q
p
p2
p3
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.
p
q
O
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 2
i=1
Procura 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 j
Repete-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
p4
p7
p2
p5
p3
p6
Etapa 3
Cluster C2
p5
p2
p1
• 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
p4
Cluster C1
• Junta-se os clusters Ci e Cki
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ício
Sejam 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-dist
Análise
1. 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
Como selecionar os parâmetros ?





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 kdist, 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
K-dist
Exemplo: BD com 3000 objetos
50
40
30
Eps = 10
20
MinPts = 4
10
500
1000
1500
2000
2500
3000
Objetos
Crescimento muito grande de k-dist
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
Avaliação de desempenho: qualidade
dos clusteres produzidos
Agrupamentos descobertos por DBSCAN
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.