A Density-Based Algorithm for
Discovering Clusters in Large Spatial
Databases with Noise
M. Ester, H-P. Kriegel, J. Sander, X. Xu
Apresentação: Léia Michelle de Souza
Algoritmos Baseados em
Densidade


Esses algoritmos assumem que os clusters
são regiões de alta densidade de padrões
separadas por regiões com baixa densidade,
no espaço de padrões.
Um cluster é definido como um componente
denso conectado em qualquer direção dada
pela densidade.
Densidade – Características
Principais





Descoberta de grupos de forma arbitrária;
Tratamento de Ruído;
Apenas uma escaneada;
É necessário parâmetros de densidade como
condições.
Separar regiões de objetos de alta e baixa
densidade.
DBScan – Density Based Spatial Clustering
of Applications with Noise

É um algoritmo baseado em densidade para
agrupar os objetos ou pontos.
1. Parâmetros

Para se iniciar um algoritmo DBScan é
necessário definir dois parâmetros principais:

Raio - Distância entre um objeto (Ponto) e
seus vizinhos.

MinPts - Objetos(Pontos) Central.
2. Parâmetros
Eps
Valor que descreve a Medida de Proximidade, isto é,
quantos pontos vizinhos próximos, um par de pontos
necessita ter em comum para serem considerados
próximos.
Raio máximo da vizinhança
 MinPts
Valor relativo a densidade mínima, ou seja, número de
vizinhos próximos que um ponto precisa ter para ser
considerado “Core Point”.
Número de pontos mínimo em Eps desse ponto.

3. Parâmetros





Neps(p) : {q  D | dist(p,q) < = Eps}
Um ponto p é alcançável pela densidade de
um ponto q Eps, MinPts se:
1) p  Neps(q)
2)Condição de Ponto Núcleo:
|Neps(q)| >= MinPts
Exemplo 1
p : border point
q : core point
q
p
MinPts = 5
Eps = 1cm
1. Densidades

Alcançável pela Densidade

Um ponto p é alcançável pela densidade de um ponto q
Eps, MinPts se existe uma cadeia de pontos p1,...,pn,p1
= q,pn = p tal que pi+1 é diretamente alcançável pela
Densidade de pi.
p
q
p1
2. Densidades


Conectado pela Densidade
Um ponto p é conectado pela densidade a
um ponto q Eps, MinPts se existir um ponto
O para ambos, p e q são alcançáveis pela
densidade de O.
p
q
O
1. Regras para gerar Clusters




Um ponto pertence a um cluster K somente se estiver
localizado no raio de um ponto central do cluster;
Um ponto central p, no raio de um outro ponto central pi
qualquer, precisa pertencer ao mesmo cluster K;
Um ponto não central p, no raio de um ponto central
p1...pi, onde i>0 precisa pertencer ao mesmo cluster
cujo objeto central esteja entre p1...pi;
Um ponto não central p que não estiver no raio de
nenhum objeto central é considerado ruído.
2. Regras para gerar Clusters



Para a geração de Clusters é necessário que
se teste o raio de cada ponto da base de
dados. Se o raio de um objeto (ponto) p
contém mais de um ponto central (MinPts),
então criaremos um novo Clusters para o
objeto p.
Os objetos (pontos) no raio p são então
adicionados ao novo Cluster.
Pode-se ocorrer que um objeto central que já
pertença a um Cluster, seja encontrado
dentro de outro Cluster.
3. Regras para gerar Clusters

Os dois Clusters serão agrupados em um só
e o processo se encerra quando não existir
novos pontos a serem adicionados a
qualquer Cluster.
C2
C1
Algoritmo do DBScan
P
Escolha um Ponto arbitrariamente
Recupere todos os pontos alcançáveis
pela densidade de p,Eps,MinPts
Se p é um ponto core, forma-se um grupo
Se p é um ponto fronteira, não há pontos alcançáveis
pela densidade de p, visitar o próximo ponto
Continue o processo até que todos os pontos tenham sido processados
Distância entre dois pontos





Dist(S1,S2) = min{dist(p,q) | p  S1,q  S2}
DBScan (SetOfPoints, Eps,MinPts)
//SetOfPoints is UNCLASSIFIED
ClusterId : = nextId(NOISE);
FOR i FROM 1 TO SetOfPoints.size DO
 Point :=SetOfPoints.get(i);
 IF Point.ClId = UNCLASSIFIED THEN
IF
ExpandCluster(SetOfPoints,Point,ClusterId,E
ps,MinPts) THEN
 ClusterId := nextId(ClusterId)
 END IF

END IF
END FOR
END;//DBScan



Clusters



ExpandCluster(SetOfPoints,Point,ClId,Eps,Minpts):Boolean;
seeds:=SetOfPoints,regionQuery(Point,Eps);
IF seeds.size<MinPts THEN

SetOfPint.changeClId(Point,NOISE);

RETURN false;

ELSE

SetOfPoints.changeClIds(seeds,ClId);

Seeds.delete(Point);

While seeds <> Empty DO







END IF
END;
CurrentP:=seeds.firts();
Result:= SetOfPoints.regionQuery(currentP,Eps);
IF result.size > = MinPts THEN

FOR i FROM 1 TO result.size DO

resultP:=result.get(i);

IF resultP.ClId

IN {UNCLASSIFIED,NOISE} THEN

IF resultP.ClId = UNCLASSIFIED THEN

seeds.append(resultP);

END IF

SetOfPoints.changeClId(result,ClId);

END IF

END FOR
END IF
Seeds.delete(currentP);
END WHILE
RETURN True;
Parâmetros
Valor de Eps
Valor de 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
Agrupamentos descobertos por CLARANS
Avaliação de desempenho
Agrupamentos descobertos por DBSCAN
Run Time em segundos
Algoritmo DBScan

Vantagem


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

Desvantagem

Sensível aos parâmetros de entrada(Eps e MinPt)


Problemas do DBScan
Agrupamentos diferentes podem ter mesmo
densidades diferentes.
 Agrupamentos podem estar em hierarquias.

Referências Bibliográficas