Formação de agrupamentos:
conceitos básicos e algoritmos (parte 2)
prof. Luis Otavio Alvares
INE/UFSC
Parte desta apresentação é baseada em material do livro
Introduction to Data Mining de Tan, Steinbach, Kumar
e de material do prof. José Leomar Todesco (UFSC)
Clustering hierárquico
Produz um conjunto de clusters aninhados,
organizados como uma árvore
 Pode ser visualizado como um dendrograma

– Um diagrama em forma de árvore que registra a
sequencia de uniões ou divisões
5
6
0.2
4
3
4
2
0.15
5
2
0.1
1
0.05
3
0
1
3
2
5
4
6
1
Pontos fortes do clustering hierárquico

Não precisa assumir nenhum número particular
de clusters
– Qualquer número desejado de clusters pode ser
obtido “cortando” o dendograma no nível adequado

Podem corresponder a taxonomias
– Exemplo em biologia: o reino animal
Clustering hierárquico

Dois tipos principais
– Aglomerativo:

Inicia com cada ponto como um cluster individual
A cada passo une o par de pontos mais próximos até que reste
somente um cluster (ou k clusters)

– Divisivo:

Inicia com um cluster contendo todos os pontos
A cada passo divide um cluster até que cada cluster contenha
apenas um ponto (ou até que haja k clusters)


Os algoritmos tradicionais usam uma matriz de
similaridade ou de proximidade (distância)
– Unem ou dividem um cluster de cada vez
Como definir a similaridade entre clusters
p1
p2
p3
p4 p5
...
p1
Similaridade?
p2
p3
p4





MIN
MAX
Média do grupo
Distância entre centróides
Outros métodos dirigidos por uma
função objetivo

método de Ward
p5
.
.
.
Matriz de proximidade
Como definir a similaridade entre clusters
p1
p2
p3
p4 p5
...
p1
p2
p3
p4





MIN
MAX
Média do grupo
Distância entre centróides
Outros métodos dirigidos por uma
função objetivo
 método de Ward
p5
.
.
.
Matriz de proximidade
Como definir a similaridade entre clusters
p1
p2
p3
p4 p5
...
p1
p2
p3
p4





MIN
MAX
Média do grupo
Distância entre centróides
Outros métodos dirigidos por uma
função objetivo

método de Ward
p5
.
.
.
Matriz de proximidade
Como definir a similaridade entre clusters
p1
p2
p3
p4 p5
...
p1
p2
p3
p4





MIN
MAX
Média do grupo
Distância entre centróides
Outros métodos dirigidos por uma
função objetivo

método de Ward
p5
.
.
.
Matriz de proximidade
Como definir a similaridade entre clusters
p1
p2
p3
p4 p5
...
p1


p2
p3
p4





MIN
MAX
Média do grupo
Distância entre centróides
Outros métodos dirigidos por uma
função objetivo

método de Ward
p5
.
.
.
Matriz de proximidade
Algoritmo Geral de Agrupamento Hierárquico Aglomerativo
Passo 1: Iniciar o agrupamento formado por grupos Unitários (cada
ponto é um cluster)
Passo 2: Encontre, no agrupamento corrente, o par de grupos de
dissimilaridade (distância) mínima (= similaridade máxima)
Passo 3: Construa um novo grupo pela fusão desse par de grupos
de dissimilaridade mínima
Passo 4: Atualize a matriz de dissimilaridades: suprima as linhas e
as colunas correspondentes aos grupos fusionados e adicione
uma linha e uma coluna correspondente as dissimilaridades
entre o novo grupo e os grupos antigos
Passo 5: Se todos os objetos estão grupados, pare; senão vá para
o passo 2
Prof. Luis Otavio Alvares
10
10
Similaridade MIN ou Single Link

A similaridade entre dois clusters é baseada nos
dois pontos mais similares (mais próximos) dos
dois clusters diferentes
– Determinada por um par de pontos, i.e., por um link
na matriz de proximidade.
I1
I2
I3
I4
I5
I1
1.00
0.90
0.10
0.65
0.20
I2
0.90
1.00
0.70
0.60
0.50
I3
0.10
0.70
1.00
0.40
0.30
I4
0.65
0.60
0.40
1.00
0.80
I5
0.20
0.50
0.30
0.80
1.00
1
2
3
4
5
Clustering Hierárquico: MIN
1
5
3
5
2
0.2
1
2
3
0.15
6
0.1
4
4
Clusters aninhados
0.05
0
3
6
2
5
Dendrograma
4
1
Métodos hierárquicos aglomerativos
Para ilustrar os procedimentos de diversos algoritmos
vamos usar o seguinte exemplo.
Exemplo: pretende-se investigar, de forma exploratória, o histórico de
crescimento corpóreo das pessoas. O pesquisador gostaria de escolher
representantes “típicos” da população para tentar traçar diferentes
históricos. O objetivo operacional passou a ser o de agrupar os
indivíduos da população alvo segundo as variáveis peso e altura.
Os dados de seis pessoas foram:
Indivíduo
A
B
C
D
E
F
Altura
180
175
170
167
180
165
Peso
79
75
70
63
71
60
Idade
30
28
20
25
18
28
Instrução
univ.
univ.
secund.
univ.
secund.
primário
Cor
Preta
Branca
Branca
Parda
Parda
branca
Sexo
M
M
F
F
M
F
13
Métodos hierárquicos aglomerativos
Como temos duas variáveis com unidades diferentes,
usar-se-á a normalização dos dados, onde cada valor será
subtraído da média de todas as observações e dividido
pelo desvio padrão de todas as observações. A nova
tabela fica:
Indivíduo
A
B
C
D
E
F
Altura
180
175
170
167
180
165
Peso
79
75
70
63
71
60
Zaltura
1,10
0,33
-0,44
-0,90
1,10
-1,21
Zpeso
1,31
0,75
0,05
-0,93
0,19
-1,35
14
Exemplo: Single Link (MIN)
1. Método do vizinho mais próximo (Método da ligação simplesSingle Link)
Para o nosso exemplo suponha a seguinte matriz de distâncias:
A
B
C
D
E
F
0 ,67*

 1,41
 2 ,12

 0 ,79
 2 ,49

B
C
D
E


0 ,74


1,47 0 ,77

0 ,67 1,09 1,62

1,84 1,13 0 ,37 1,96
Sempre é uma matriz
quadrada e simétrica
*
0,67 
1,10  0,33  1,31  0,75 
2
15
Exemplo: Single Link
 Passo 1: inicialmente, cada caso forma um grupo, isto é, temos 6 grupos
iniciais.
 Passo 2: olhando-se a matriz de distâncias, observa-se que as duas
observações mais próximas são D e F, corresponde a uma distância de 0,37,
assim, esta duas observações são agrupadas, formando o primeiro grupo.
Necessita-se, agora, das distâncias deste grupo aos demais. A partir da matriz
de distâncias iniciais têm-se:
d ( A, DF )  min{d ( A, D), d ( A, F )}  min{2,12 ; 2,49}  2,12
d ( B, DF )  min{d ( B, D), d ( B, F )}  min{1,47 ; 1,84}  1,47
d (C , DF )  min{d (C , D), d (C , F )}  min{0,77 ; 1,13}  0,77
d ( E , DF )  min{d ( E , D), d ( E , F )}  min{1,62 ; 1,96}  1,62
Com isso, temos a seguinte matriz de distâncias:
16
Exemplo: Single Link
A
B
C
E
DF
B
C
E
0,67

 1,41 0,74



0,79 0,67 1,09



 2,12 1,47 0,77 1,62
 Passo 3: Agrupar A e B ao nível de 0,67, e recalcular:
d ( C , AB )  m in{d ( C , A ),d ( C , B )}  m in{1,41;0,74 }  0,74
d ( E , AB )  m in{d ( E , A ),d ( E , B )}  m in{0,79;0,67 }  0,67
d ( DF , AB )  m in{d ( D , A ),d ( D , B ),d ( F , A ),d ( F , B )} 
m in{2,12;1,47;2,49;1,84 }  1,47
A matriz resultante será:
17
Exemplo: Single Link
C
E
DF
AB
 Passo
E
DF
1,09

0 ,77 1,62



0 ,74 0 ,67 1,47
4: Agrupar AB com E ao nível de 0,67, e recalcular:
d ( C , ABE )  m in{d ( C , A ),d ( C , B ),d ( C , E )}  m in{1,41;0,74;1,09 }  0,74
d ( DF , ABE )  m in{d ( D , A ),d ( D , B ),d ( D , E ),d ( F , A ),d ( F , B ),d ( F , E )} 
m in{2,12;1,47;1,62;2,49;1,84;1,96 }  1,47
Matriz resultante:
C
DF
ABE
DF
0,77

0,74 1,47


18
Exemplo: Single Link
 Passo
5: Agrupar C com ABE ao nível de 0,74, e recalcular:
d ( DF , ABCE ) 
m in{d ( D , A ),d ( D , B ),d ( D ,C ),d ( D , E ),d ( F , A ),d ( F , B ),d ( F ,C ),d ( F , E )} 
m in{2,12;1,47;0,77;1,62;2,49;1,84;1,13;1,96 }  0,77
Matriz resultante:
DF
ABCE
0,77
 Passo
6: O último passo cria um único agrupamento contendo os
6 objetos, que serão similares a um nível de 0,77.
19
Exemplo: Single Link
Resumindo-se, temos:
Nó
1
2
3
4
5
Fusão
DeF
AeB
AB e E
ABE e C
ABCE e DF
Nível
0,37
0,67
0,67
0,74
0,77
Dendograma:
1,0
0,9
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0,0
D
F
A
B
E
C
20
Pontos fortes da MIN
Pontos originais
• Pode tratar formas não-elípticas
Dois Clusters
Limitações da MIN
Pontos originais
• Sensível a ruído e outliers
Dois Clusters
Similaridade MAX ou Complete Linkage

A similaridade entre dois clusters é baseada nos pontos
menos similares (mais distantes) entre os dois clusters
(mas escolhe-se a menor distância máxima)
– Determinada por todos os pares de pontos dos dois clusters
I1 I2 I3 I4 I5
I1 1.00 0.90 0.10 0.65 0.20
I2 0.90 1.00 0.70 0.60 0.50
I3 0.10 0.70 1.00 0.40 0.30
I4 0.65 0.60 0.40 1.00 0.80
I5 0.20 0.50 0.30 0.80 1.00
1
2
3
4
5
Clustering hierárquico: MAX
4
1
2
5
5
0.4
0.35
2
0.3
0.25
3
3
6
1
4
0.2
0.15
0.1
0.05
0
Clusters aninhados
3
6
4
1
Dendrograma
2
5
Exemplo: Complete Linkage
2.
Método do vizinho mais longe (Método da ligação completa – Complete Linkage)
Define-se a distância entre os grupos X e Y como:
d ( X ,Y )  maxd i , j  : i  X e j Y 
Convém ressaltar que a fusão de dois grupos ainda é feita com os grupos mais parecidos
(menor distância).
 Passo 1: inicialmente, cada caso forma um grupo, isto é, temos 6 grupos iniciais.
 Passo 2: olhando-se a matriz de distâncias, abaixo, observa-se que as duas
observações mais próximas são D e F, corresponde a uma distância de 0,37, assim,
estas duas observações são agrupadas, formando o primeiro grupo. Necessita-se,
agora, das distâncias deste grupo aos demais. A partir da matriz de distâncias
iniciais tem-se:
A
B
C
D
E
B
C
D
E
F
0 ,67*

 1,41
 2 ,12

 0 ,79
 2 ,49



0 ,74


1,47 0 ,77

0 ,67 1,09 1,62

1,84 1,13 0 ,37 1,96
25
Exemplo: Complete Linkage
d ( A, DF )  max{d ( A, D ),d ( A, F )}  max{2,12;2,49}  2,49
d (B, DF )  max{d (B, D),d (B, F )}  max{1,47;1,84}  1,84
d (C, DF )  max{d (C, D ),d (C, F )}  max{0,77;1,13}  1,13
d (E, DF )  max{d (E, D ),d (E, F )}  max{1,62;1,96}  1,96
A
B
C
E
DF
 Passo
B
C
E
0,67

 1,41 0,74



0,79 0,67 1,09



2,49 1,84 1,13 1,96
3: Agrupar A e B ao nível de 0,67, e recalcular:
26
Exemplo: Complete Linkage
d ( C , AB )  m ax{d ( C , A ),d ( C , B )}  m ax{1,41;0,74 }  1,41
d ( E , AB )  m ax{d ( E , A ),d ( E , B )}  m ax{0,79;0,67 }  0,79
d ( DF , AB )  m ax{d ( D , A ),d ( D , B ),d ( F , A ),d ( F , B )} 
m ax{2,12;1,47;2,49;1,84 }  2,49
Temos:
C
E
DF
AB
E
DF
1,09

1,13 1,96



1,41 0 ,79 2 ,49
27
Exemplo: Complete Linkage
 Passo
4: Agrupar AB com E ao nível de 0,79, e recalcular:
d ( C , ABE )  m ax{d ( C , A ),d ( C , B ),d ( C , E )}  m ax{1,41;0,74;1,09 }  1,41
d ( DF , ABE )  m ax{d ( D , A ),d ( D , B ),d ( D , E ),d ( F , A ),d ( F , B ),d ( F , E )} 
m ax{2,12;1,47;1,62;2,49;1,84;1,96 }  2,49
Matriz resultante:
C
DF
ABE
DF
1,13

1,41 2,49


28
Exemplo: Complete Linkage
 Passo
5: Agrupar C com DF ao nível de 1,13, e recalcular:
d ( CDF , ABE ) 
m ax{d ( C , A ),d ( C , B ),d ( C , E ),d ( D , A ),d ( D , B ),d ( D , E ),d ( F , A ),d ( F , B ),d ( F , E )} 
m in{1,41;0,74;1,09;2,12;1,47;0,77;1,62;2,49;1,84;1,96 }  2,49
Matriz resultante:
CDF
ABE
2,49
 Passo 6: O último passo cria um único agrupamento contendo
os 6 objetos, que serão similares a um nível de 2,49.
29
Exemplo: Complete Linkage
Resumindo-se, temos:
Nó
1
2
3
4
5
Fusão
DeF
AeB
AB e E
DF e C
ABE e
CDF
Nível
0,37
0,67
0,79
1,13
2,49
Dendograma:
2,5
1,3
1,2
1,1
1,0
0,9
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0,0
D
F
C
A
B
E
Ponto forte da MAX
Pontos originais
• Menos suscetível a ruído e outliers
Dois Clusters
Limitações da MAX
Pontos originais
•Tendência a quebrar clusters grandes
• Tendência a formar clusters esféricos
Dois Clusters
Similaridade: Média do grupo

A proximidade de dois clusters é dada pela média da distância
entre pares de pontos dos dois clusters.
 proximidade(p , p )
proximidade(Clusteri , Clusterj ) 
I1
I2
I3
I4
I5
I1
1.00
0.90
0.10
0.65
0.20
I2
0.90
1.00
0.70
0.60
0.50
I3
0.10
0.70
1.00
0.40
0.30
I4
0.65
0.60
0.40
1.00
0.80
I5
0.20
0.50
0.30
0.80
1.00
i
pi Clusteri
p j Clusterj
j
|Clusteri ||Clusterj |
1
2
3
4
5
Clustering hierárquico: Média do grupo
5
4
1
0.25
2
5
0.2
2
0.15
3
6
1
4
3
Clusters aninhados
0.1
0.05
0
3
6
4
1
Dendrograma
2
5
Exemplo: Clustering hierárquico: Média do grupo
Dada a matriz de distâncias:
A
B
C
D
E
F
0 ,67
 1,41

 2 ,12

0 ,79
2 ,49
B
C
D
E


0 ,74


1,47 0 ,77

0 ,67 1,09 1,62

1,84 1,13 0 ,37 1,96
 Passo 1: inicialmente, cada caso forma um grupo, isto é, temos 6 grupos
iniciais.
 Passo 2: olhando-se a matriz de distâncias, observa-se que as duas
observações mais próximas são D e F, corresponde a uma distância de
0,37, assim, esta duas observações são agrupadas, formando o primeiro
grupo. Necessita-se, agora, das distâncias deste grupo aos demais. A
partir da matriz de distâncias iniciais tem-se:
35
Exemplo: Average Linkage
d ( A, DF )  { d ( A, D )  d ( A, F )} / 2  { 2,12  2,49 } / 2  2,30
d ( B , DF )  { d ( B , D )  d ( B , F )} / 2  { 1,47  1,84 } / 2  1,66
d ( C , DF )  { d ( C , D )  d ( C , F )} / 2  { 0,77  1,13} / 2  0,95
d ( E , DF )  { d ( E , D )  d ( E , F )} / 2  { 1,62  1,96 } / 2  1,79
A
B
C
E
DF
B
C
E
0,67

 1,41 0,74



0,79 0,67 1,09



2
,
30
1
,
66
0
,
95
1
,
79


Com a obtenção da matriz de distâncias conclui-se o passo 2, que
reuniu os pontos D e F, num nível igual à 0,37.
36
Exemplo: Average Linkage
 Passo
3: Analisando a nova matriz de similaridade, nota-se que existem
dois pares com a mesma proximidade: A com B e B com E. Recomenda-se
selecionar aleatoriamente um dos pares e criar o novo grupo. Então, neste
caso, agrupa-se A com B.
d (C , AB)  {d (C , A)  d (C , B)}/ 2  {1,41 0,74} / 2  1,08
d ( E, AB)  {d ( E, A)  d ( E , B)}/ 2  {0,79  0,67} / 2  0,73
d ( DF , AB)  {d ( D, A)  d ( D, B)  d ( F , A)  d ( F , B)}/ 4 
{2,12  1,47  2,49  1,84} / 4  1,98
Temos:
C
E
DF
AB
E
DF
1,09

0 ,95 1,79



1,08 0 ,73 1,98
37
Exemplo: Average Linkage
 Passo
4: Agrupar AB com E ao nível de 0,73, e recalcular:
d (C , ABE)  {d (C , A)  d (C , B)  d (C , E )}/ 3  {1,41 0,74  1,09} / 3  1,08
d ( DF , ABE)  {d ( D, A)  d ( D, B)  d ( D, E )  d ( F , A)  d ( F , B)  d ( F , E )}/ 6 
{2,12  1,47  1,62  2,49  1,84  1,96} / 6  1,92
Matriz resultante:
C
DF
ABE
DF
0,95

1,08 1,92


38
Exemplo: Average Linkage
 Passo
5: Agrupar C com DF ao nível de 0,95, obtendo-se a partição (ABE,
CDF) e recalcular:
d ( CDF , ABE ) 
{ d ( C , A )  d ( C , B )  d ( C , E )  d ( D , A )  d ( D , B )  d ( D , E )  d ( F , A )  d ( F , B )  d ( F , E )} / 9 
{ 1,41 0,74  1,09  2,12  1,47  1,62  2,49  1,84  1,96 } / 9  1,64
Matriz resultante:
CDF
ABE
1,64
 Passo 6: O processo encerra reunindo num único grupo os conjuntos
ABE e CDF, que são similares a um nível de 1,64 .
39
Exemplo: Average Linkage
Resumindo-se, temos:
Nó
1
2
3
4
5
Fusão
DeF
AeB
AB e E
DF e C
ABE e
CDF
Dendograma:
Nível
0,37
0,67
0,73
0,95
1,64
Observando o gráfico
em forma de árvore
(dendograma), notamos
que o maior salto é
observado na última
etapa, sugerindo a
existência de dois
grupos homogêneos
(A,B,E) e (C,D,F).
1,6
1,5
1,4
1,3
1,2
1,1
1,0
0,9
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0,0
D
F
C
A
B
E
40
Clustering hierárquico: Média do grupo

Compromisso entre MAX e MIN

Ponto forte
– Menos suscetível a ruído e outliers

Limitação
– Tendência de gerar clusters esféricos
Método de Ward (Ward’s method)

A similaridade de dois clusters é baseada no
aumento do erro quadrado quando dois clusters
são unidos
– Similar a média do grupo se a distância entre os
pontos é a distância ao quadrado

Menos suscetível a ruído e outliers

Tendência de gerar clusters esféricos

Clustering Hierárquico análogo ao K-médias
– Pode ser usado para inicializar o K-médias
Clustering Hierárquico: uma comparação
1
5
4
3
5
5
2
2
5
1
2
1
MIN
3
2
MAX
6
3
3
4
1
5
2
5
Método de Ward
2
3
3
4
4
1
2
5
2
3
6
1
4
1
4
4
5
6
Média do grupo
6
1
4
3
Clustering Hierárquico: necessidades de tempo e espaço

O(N2) para espaço usando matriz de
proximidade.
– N é o número de pontos.

O(N3) para o tempo em muitos casos
– Tem N passos e em cada passo a matriz de tamanho
N2 tem que ser atualizada e percorrida
– A complexidade pode ser reduzida para O(N2 log(N) )
em algumas abordagens
DBSCAN
Clustering baseado em densidade
DBSCAN (1996)

DBSCAN é um algoritmo baseado em
densidade
–
Densidade = número de pontos dentro de um raio
especificado (Eps)
–
Um ponto é um core point se ele tem mais de um número
especificado de pontos (MinPts) dentro do círculo de raio
Eps

Estes são pontos que pertencem a um cluster
–
Um border point tem menos do que MinPts dentro do
círculo de raio Eps, mas ele está na vizinhança (definida por
Eps) de um core point
–
Um noise point é todo ponto que não é nem core point nem
border point.
DBSCAN (Ester 1996)
Core and border points
r
Eps
q
Eps
p
Eps
minPts= 5
Eps= 1
Core point
Border point
noise
DBSCAN Algorithm
Eliminate noise points
 Perform clustering on the remaining points

DBSCAN example
Prof. Luis Otavio Alvares
49
Identifying core, border and noise points
Prof. Luis Otavio Alvares
50
Prof. Luis Otavio Alvares
51
Prof. Luis Otavio Alvares
52
DBSCAN: Core, Border and Noise Points
Pontos originais
Eps = 10, MinPts = 4
Point types: core,
border and noise
Quando o DBSCAN funciona bem
Pontos originais
Clusters
• Tolerante a ruído
• Pode tratar clusters de diferentes formas e tamanhos
Quando o DBSCAN não funciona bem
(MinPts=4, Eps=9.92).
Pontos originais
• Variação de densidades
• Dados com muitas dimensões
(MinPts=4, Eps=9.75)
OPTICS - Ordering Points to Identify the Clustering Structure
Utilizado para analisar a estrutura dos agrupamentos baseados em
densidade, através da variação do Eps para um mesmo número
mínimo de pontos (minPoints)
Eps
Referências

MacQueen, J. B. (1967). "Some Methods for classification and
Analysis of Multivariate Observations". Proceedings of 5th Berkeley
Symposium on Mathematical Statistics and Probability. University of
California Press. pp. 281–297

L. Kaufman and P.J. Rousueeuw. (1990) Finding Groups in Data: an
Introduction to Cluster Analysis, John Wiley & Sons
CLARANS

Raymond T. Ng, Jiawei Han(1994) Efficient and Effective Clustering
Methods for Spatial Data Mining. Proceedings of the 20th VLDB
Conference, Santiago, Chile. pp 144-155
DBSCAN

M. Ester, H-P. Kriegel, J. Sander, X. Xu. A Density-Based Algorithm for
Discovering Clusters in Large Spatial Databases with Noise. Proc. KDD
1996.
OPTICS

Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg
Sander (1999). "OPTICS: Ordering Points To Identify the Clustering
Structure". ACM SIGMOD international conference on Management
of data. ACM Press. pp. 49–60
K-means
PAM
Hierárquicos 
N. Jardine, R.Sibson. Mathematical Taxonomy.Wiley, New York,
1971.
Exercícios
Para o quadro abaixo, aplique o algoritmo aglomerativo MIN (single
link) e apresente o dendograma final com o passo a passo.
Prof. Luis Otavio Alvares
58
Passo 1: calcular a tabela de distâncias iniciais
A
B
C
D
d(A,B) = |3-4| + |2-5| = 4
d(A,C) = |3-4| + |2-7| = 6
….
B
4
C
6
2
D
6
4
2
E
7
3
3
5
Prof. Luis Otavio Alvares
59