Método de Clusterização baseado em Densidade

Algoritmo DBSCAN

Sandra de Amo

AULA 22

DATA MINING

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 core 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 é 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.