Método Hierárquico Aglomerativo
de Clusterização
Algoritmo CURE
AULA 11 – Parte II
DATA MINING
Sandra de Amo
Clustering Using REpresentatives (CURE)





No início, cada amostra é um cluster.
número de clusters = número de amostras
Calcula-se distância entre os clusters.
Clusters próximos são reunidos num único cluster.
Repete-se o processo de cálculo da distância entre
clusters e reunião de clusters próximos.
O processo termina quando se atinge o número préfixado de clusters.
Como medir a distância entre clusteres

Enfoque baseado em centróide

Distância entre clusteres C1 e C2 =
dmean(C1,C2) = d(m1,m2)
mi = centróide de Ci

Enfoque MST (Minimum Spanning Tree)

dmin(C1,C2) = min d(p,q)
p ɛ C1, q ɛ C2
Como medir a distância entre clusteres

Média
dmedia(C1,C2) = 1
Σ
Σ d(p,q)
p ɛ C1 q ɛ C2
ni nj
ni = tamanho do cluster Ci


Max

d(C1,C2) = max d(p,q)
p ɛ C1, q ɛ C2
Distância entre Clusters
Centróides
Média
MST
MAX
Cálculo da Distância em CURE

Política mista: centróides e MST

Determina um número N de objetos em cada
cluster que são mais representativos do cluster.



Elementos bem distribuídos
Representam zonas distintas do cluster
Calcula a mínima distância entre estes elementos
mais representativos.
Distância entre Clusters
CURE
Elementos representativos do
Cluster C1
Elementos representativos do
Cluster C2
Representantes de um cluster


Quando um cluster é unitário, seu
representante é seu único elemento
Quando um cluster é obtido juntando-se 2
clusters, cada um com seus representantes, os
representantes do novo cluster não são
necessariamente amostras originais do BD.
Representantes de um novo cluster
Novo Cluster
+
Parâmetros
de
Entrada
Coeficiente de Retração
Número de representantes escolhidos em cada
cluster
Parâmetros de Ajuste


Representantes : capturam o formato do cluster
Retração em direção do centro de gravidade:


Diminuir a influência de ruídos
Coeficientes de retração :


Valores pequenos : favorecem clusters de formato não
convexo, menos compacto
Valores grandes : aproximam os representantes do centro
do cluster, favorecem clusters convexos, de forma
esférica.
Algoritmo CURE

Entrada





Banco de Dados BD
K = número de clusters
α = fator de retração ( 0 ≤ α < 1)
N = número de representantes em cada cluster
Saída

K clusters disjuntos
Algoritmo CURE

Duas estruturas de dados


Uma para armazenar os clusters a cada iteração
(heap sequencial)
Uma para armazenar os representantes dos
clusters a cada iteração (kd-tree – estrutura de
dados utilizada para armazenamento e consulta
eficientes de dados multidimensionais)
Apresentação simplificada

Q = arquivo para armazenar os clusters
id1
id2
id3
id4
u2 = u1.mp

u1
u2
u3
2
2
3
u = cluster = {a1, a2, ..., an}
u4
4
u.mp = cluster mais próximo
de u
clusters
d(u, u.mp) Arquivo Q ordenado pela terceira coluna
T = arquivo para armazenar os representantes de cada cluster
id1 {p1,p2,p3}
id2 {q1,q2,q3}
id3 {w1,w2,w3}
id4 {v1,v2,v3}
u1. rep
u2. rep
u3. rep
u4. rep
Exercício 4 (para entregar)

Mostre que u2 = u1.mp
Criação dos Clusteres
ui = {pi}, onde BD = {p1,...,pm}



Inicialmente cada objeto é um cluster
Clusteres são ordenados em Q segundo a menor distância a seus clusteres
mais próximos.
Arquivo T contém m registros, cada registro é um conjunto unitário {pi}.
Repeat
1.
2.
3.
4.
5.
6.
7.
Considera-se o primeiro cluster u em Q e v = u. mp
Retira u e v de Q
w = u U v ; w.rep = representantes de w
Remove de T os registros u.rep e v.rep
Calcula w.mp
Atualiza a terceira coluna do arquivo Q
Insere em Q o cluster w na posição adequada e w.rep em T
Until Q contém k clusteres
Exemplo: cálculo de w.rep
Cluster v
Cluster u
N=3
α = 0.5
p1
p2
q1
q2
p3
Centro de gravidade de w = u U v
w = {p1, p2, p3, q1, q2}
Repr. 1 = o que está mais afastado do centro = q1
Repr. 2 = o que está mais afastado de q1 = p2
Repr. 3 = o que está mais afastado de {q1, p2}
d(p1,{q1,p2}) = min {d(p1,q1), d(p1,p2)} = d(p1,p2)
d(p2,{q1,p2}) = 0
d(p3,{q1,p2}) = d(p3,p2)
d(q1,{q1,p2}) = 0
d(q2,{q1,p2}) = d(q1,q2)
Exemplo: cálculo de w.rep
Cluster v
Cluster u
N=3
α = 0.5
p1
p2
p3
q1
q2
Centro de gravidade de w = u U v
w = {p1, p2, p3, q1, q2}
w.rep = representantes do cluster w
Cálculo de w.mp (mais próximo de w)
1.
2.
3.
Considera-se x = o primeiro cluster de Q – {u,v}
Fazemos w.mp = x
Para cada y em Q – {u,v}
3.1 Se d(y,w) < d(w,w.mp) então w.mp:= y
3.2 Se y.mp = u ou v
3.2.1 Se d(y,y.mp) < d(y,w)
y.mp:= Cluster_mp(T,y,d(y,w))
3.2.2 Se d(y,y.mp) ≥ d(y,w)
y.mp:= w
3.3 Se y.mp é diferente de u e v
3.3.1 Se d(y,y.mp) > d(y, w)
y.mp:= w
Para cada cluster y
atualiza seu cluster mais próximo
Exercício 5 (para entregar)

A rotina Cluster_mp(T,y,d(y,w)) faz o seguinte:






Procura em T os representantes de y = {p1,...,pN}
Para cada representante pi, considera a vizinhança de raio d(y,w)
É claro que, para algum pi, sua vizinhança de raio d(y,w) contém um
representante de outro cluster z.
Considero um destes representantes z que está mais próximo do centro pi da
vizinhança.
Retorna y.mp = z
Pede-se: explique por que o cluster retornado por esta rotina
realmente é o cluster mais próximo de y.
Vantagens e Desvantagens

CURE detecta clusters de formato arbitrário
K-means detecta clusters de formato esférico

CURE é robusto quanto a outliers

Desvantagem de CURE : complexidade
O(n2), n = tamanho do banco de dados
Referência

S. Guha, R. Rastogi, K. Shim: CURE – An
Efficient Clustering Algorithm for Large
Databases. ACM/SIGMOD 1998.