Método K-medóides
Algoritmos PAM
e CLARA
AULA 11 – Parte I
DATA MINING
Sandra de Amo
Problema
Dados
Uma base de dados
um número k
Objetivo: particionar o conjunto de dados em k clusteres
Algoritmo PAM: (Partinioning Around Medoids)




encontra k clusters baseados em protótipos
Protótipos são objetos da base de dados, representativos dos
clusteres
Agrupamentos particionais (clusteres disjuntos)
Método de particionamento.
Idéia do Algoritmo PAM

Determinar os k objetos que melhor
representam os clusteres = medóides

Distribuir os objetos nos k clusteres.
Algoritmo
1. Seleciona k objetos aleatoriamente:


M1, M2, ..., Mk = medóides iniciais
O1, ..., Op = objetos não medóides
2. Para cada objeto Oi (Oi não medóide) e cada medóide
Mj, calcula-se

O custo de trocar Mj por Oi (Oi seria um novo medóide
no lugar de Mj)
p
CTij = Σ Cmij
m=1
Cmij = erro local provocado ao se trocar o medóide Mj por Oi
Como calcular o erro Cmij
Caso 1 : Om está no cluster de Mj
e com a substituição de Mj por Oi, Om ficar mais próximo
de um outro medóide Mj2
Om
Mj
Mj2
Cmij = d(Om,Mj2) – d(Om,Mj)
Oi
Número positivo
Como calcular o erro Cmij
Caso 2 : Om está no cluster de Mj
e com a substituição de Mj por Oi, Om ficar mais próximo
de Oi
Oi
Om
Mj
Mj2
Cmij = d(Om,Oi) – d(Om,Mj)
Número positivo ou negativo
Como calcular o erro Cmij
Caso 3 : Om não está no cluster de Mj –
(está no cluster de Mj2)
e com a substituição de Mj por Oi, Om continua no cluster
de Mj2 (não muda de cluster)
Oi
Mj
Om
Mj2
Cmij = d(Om,Mj2) – d(Om,Mj2) = 0
Como calcular o erro Cmij
Caso 4 : Om não está no cluster de Mj –
(está no cluster de Mj2)
e com a substituição de Mj por Oi, Om vai para o cluster
de Oi
Oi
Mj
Om Mj2
Cmij = d(Om,Oi) – d(Om,Mj2)
Número negativo
Algoritmo (continuação...)
3. Seleciona-se o par (Mj,Oi) que corresponde ao
minimo CTij.


Se este mínimo é negativo então substitui-se Mj
por Oi e volta ao passo 2.
Se este mínimo é positivo, vai para o passo 4.
4. Varre o banco de dados e distribui os objetos
entre os k clusteres cujos representantes são
os k medóides encontrados no passo 3.
Observação
No passo 3:
 se o custo mínimo é negativo, significa que
existe uma maneira de se substituir um
medóide por outro objeto de modo a diminuir
a soma dos erros SSE.
 se o custo mínimo é positivo, significa que
não há possibilidade de se modificar os
medóides atuais de modo a diminuir o SSE.
Logo, neste ponto, os medóides convergiram.
Complexidade


PAM funciona satisfatoriamente para
pequenos conjuntos de dados (em torno de
100 objetos e 5 clusters)
Ineficiente para grandes volumes de dados.



Número de pares MjOi = k(n-k)
Para cada par é preciso computar Cmij,
considerando todos os objetos não medóides Om
Complexidade de cada iteração = O(k(n-k)2)
Variante de PAM

CLARA (Clustering LARge Applications)



Considera uma amostragem do banco de dados
Aplica PAM na amostragem e encontra os k
medóides.
A idéia é encontrar uma amostragem tal que os kmedóides da amostragem estão próximos dos kmedóides da base de dados inteira.
Como encontrar a amostragem ideal ?



Considera diversas amostragens
Para cada amostragem, produz um particionamento da base
original em k clusteres = C1,…, Ck.
Considera o melhor particionamento, calculando a
dissimilaridade média de todos os objetos do banco de dados.
k

Dissimilaridade média = Σ Σ
d(x,Mi)
i = 1 x ɛ Ci
k
Quanto menor a dissimilaridade melhor o particionamento.
Observações

Número e tamanho das amostragens (obtidos
experimentalmente)



Número de amostragens = 5
Tamanho da amostragem = 40 + 2k
Performance satisfatória para bancos de dados
em torno de 1000 objetos e 10 clusteres.
Referência

R.T. Ng, J. Han: Efficient and Effective
Clustering Methods for Spatial Data Mining
VLDB 1994