A Density-Based Algorithm for
Discovering Clusters in Large Spatial
Databases with Noise
M. Ester, H-P. Kriegel, J. Sander, X. Xu
Apresentao: Lia Michelle de Souza
Algoritmos Baseados em
Densidade
Esses
algoritmos assumem que os clusters
so regies de alta densidade de padres
separadas por regies com baixa densidade,
no espao de padres.
Um cluster definido como um componente
denso conectado em qualquer direo dada
pela densidade.
Densidade Caractersticas
Principais
Descoberta
de grupos de forma arbitrria;
Tratamento de Rudo;
Apenas uma escaneada;
necessrio parmetros de densidade como
condies.
Separar regies 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. Parmetros
Para se iniciar um algoritmo DBScan
necessrio definir dois parmetros principais:
Raio - Distncia entre um objeto (Ponto) e
seus vizinhos.
MinPts - Objetos(Pontos) Central.
2. Parmetros
Eps
Valor que descreve a Medida de Proximidade, isto ,
quantos pontos vizinhos prximos, um par de pontos
necessita ter em comum para serem considerados
prximos.
Raio mximo da vizinhana
MinPts
Valor relativo a densidade mnima, ou seja, nmero de
vizinhos prximos que um ponto precisa ter para ser
considerado Core Point.
Nmero de pontos mnimo em Eps desse ponto.
3. Parmetros
: {q D | dist(p,q) < = Eps}
Um ponto p alcanvel pela densidade de
um ponto q Eps, MinPts se:
1) p Neps(q)
2)Condio de Ponto Ncleo:
|Neps(q)| >= MinPts
Neps(p)
Exemplo 1
p : border point
q : core point
p
MinPts = 5
Eps = 1cm
1. Densidades
Alcanvel pela Densidade
Um ponto p alcanvel 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 alcanvel pela
Densidade de pi.
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 so alcanveis pela
densidade de O.
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 no 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 no central p que no estiver no raio de
nenhum objeto central considerado rudo.
2. Regras para gerar Clusters
Para
a gerao de Clusters necessrio que
se teste o raio de cada ponto da base de
dados. Se o raio de um objeto (ponto) p contm
mais de um ponto central (MinPts), ento
criaremos um novo Clusters para o objeto p.
Os objetos (pontos) no raio p so ento
adicionados ao novo Cluster.
Pode-se ocorrer que um objeto central que j
pertena a um Cluster, seja encontrado dentro
de outro Cluster.
3. Regras para gerar Clusters
Os
dois Clusters sero agrupados em um s
e o processo se encerra quando no existir
novos pontos a serem adicionados a
qualquer Cluster.
C2
C1
Algoritmo do DBScan
P
Escolha um Ponto arbitrariamente
Recupere todos os pontos alcanveis
pela densidade de p,Eps,MinPts
Se p um ponto core, forma-se um grupo
Se p um ponto fronteira, no h pontos alcanveis
pela densidade de p, visitar o prximo ponto
Continue o processo at que todos os pontos tenham sido processados
Distncia 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 [Link] DO
Point :=[Link](i);
IF [Link] = UNCLASSIFIED THEN
IF
ExpandCluster(SetOfPoints,Point,ClusterId,Ep
s,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 [Link]<MinPts THEN
[Link](Point,NOISE);
RETURN false;
ELSE
[Link](seeds,ClId);
[Link](Point);
While seeds <> Empty DO
END IF
END;
CurrentP:=[Link]();
Result:= [Link](currentP,Eps);
IF [Link] > = MinPts THEN
FOR i FROM 1 TO [Link] DO
resultP:=[Link](i);
IF [Link]
IN {UNCLASSIFIED,NOISE} THEN
IF [Link] = UNCLASSIFIED THEN
[Link](resultP);
END IF
[Link](result,ClId);
END IF
END FOR
END IF
[Link](currentP);
END WHILE
RETURN True;
Parmetros
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
Avaliao de desempenho
Agrupamentos descobertos por CLARANS
Avaliao de desempenho
Agrupamentos descobertos por DBSCAN
Run Time em segundos
Algoritmo DBScan
Vantagem
Eficiente em tratar grandes bases de dados
Menos sensvel a rudos
Forma clusters de formato arbitrrio
Usurio no precisa especificar a quantidade de clusters
Desvantagem
Sensvel aos parmetros de entrada(Eps e MinPt)
Problemas do DBScan
Agrupamentos
diferentes podem ter mesmo
densidades diferentes.
Agrupamentos podem estar em hierarquias.
Referncias Bibliogrficas