Parte desta apresentação é baseada em material do livro

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

1 3 2 5 4 60

0.05

0.1

0.15

0.2

1

2

3

4

5

6

1

23 4

5

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

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

Similaridade?

MIN MAX Média do grupo Distância entre centróides Outros métodos dirigidos por uma

função objetivo método de Ward

Matriz de proximidade

Como definir a similaridade entre clusters

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

MIN MAX Média do grupo Distância entre centróides Outros métodos dirigidos por uma

função objetivo método de Ward

Matriz de proximidade

Como definir a similaridade entre clusters

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

MIN MAX Média do grupo Distância entre centróides Outros métodos dirigidos por uma

função objetivo método de Ward

Matriz de proximidade

Como definir a similaridade entre clusters

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

MIN MAX Média do grupo Distância entre centróides Outros métodos dirigidos por uma

função objetivo método de Ward

Matriz de proximidade

Como definir a similaridade entre clusters

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

MIN MAX Média do grupo Distância entre centróides Outros métodos dirigidos por uma

função objetivo método de Ward

Matriz de proximidade

Prof. Luis Otavio Alvares 10

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

Algoritmo Geral de Agrupamento Hierárquico Aglomerativo

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 I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.00 1 2 3 4 5

Clustering Hierárquico: MIN

Clusters aninhados Dendrograma

1

2

3

4

5

6

1

2

3

4

5

3 6 2 5 4 10

0.05

0.1

0.15

0.2

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 Altura Peso Idade Instrução Cor Sexo A 180 79 30 univ. Preta M B 175 75 28 univ. Branca M C 170 70 20 secund. Branca F D 167 63 25 univ. Parda F E 180 71 18 secund. Parda M F 165 60 28 primário branca F

13

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 Altura Peso Zaltura Zpeso A 180 79 1,10 1,31 B 175 75 0,33 0,75 C 170 70 -0,44 0,05 D 167 63 -0,90 -0,93 E 180 71 1,10 0,19 F 165 60 -1,21 -1,35

Métodos hierárquicos aglomerativos

14

1. Método do vizinho mais próximo (Método da ligação simples- Single Link)

Para o nosso exemplo suponha a seguinte matriz de distâncias:

961370131841492

621091670790

770471122

740411

670

,,,,,

,,,,

,,,

,,

, *B

C

D

E

F

A B C D E

Sempre é uma matriz quadrada e simétrica

*

2

75,031,133,010,167,0

Exemplo: Single Link (MIN)

15

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:

62,1}96,1;62,1min{)},(),,(min{),(

77,0}13,1;77,0min{)},(),,(min{),(

47,1}84,1;47,1min{)},(),,(min{),(

12,2}49,2;12,2min{)},(),,(min{),(

FEdDEdDFEd

FCdDCdDFCd

FBdDBdDFBd

FAdDAdDFAd

Com isso, temos a seguinte matriz de distâncias:

Exemplo: Single Link

16

621770471122

091670790

740411

670

,,,,

,,,

,,

,B

C

E

DF

A B C E

Passo 3: Agrupar A e B ao nível de 0,67, e recalcular:

471841492471122

670670790

740740411

,},;,;,;,min{

)}B,F(d),A,F(d),B,D(d),A,D(dmin{)AB,DF(d

,},;,min{)}B,E(d),A,E(dmin{)AB,E(d

,},;,min{)}B,C(d),A,C(dmin{)AB,C(d

A matriz resultante será:

Exemplo: Single Link

17

471670740

621770

091

,,,

,,

,E

DF

AB

C E DF

Passo 4: Agrupar AB com E ao nível de 0,67, e recalcular:

471961841492621471122

740091740411

,},;,;,;,;,;,min{

)}E,F(d),B,F(d),A,F(d),E,D(d),B,D(d),A,D(dmin{)ABE,DF(d

,},;,;,min{)}E,C(d),B,C(d),A,C(dmin{)ABE,C(d

Matriz resultante:

471740

770

,,

,DF

ABE

C DF

Exemplo: Single Link

18

Passo 5: Agrupar C com ABE ao nível de 0,74, e recalcular:

770961131841492621770471122 ,},;,;,;,;,;,;,;,min{

)}E,F(d),C,F(d),B,F(d),A,F(d),E,D(d),C,D(d),B,D(d),A,D(dmin{

)ABCE,DF(d

Matriz resultante:

770,ABCE

DF

Passo 6: O último passo cria um único agrupamento contendo os 6 objetos, que serão similares a um nível de 0,77.

Exemplo: Single Link

19

Resumindo-se, temos:

Nó Fusão Nível 1 D e F 0,37 2 A e B 0,67 3 AB e E 0,67 4 ABE e C 0,74 5 ABCE e DF 0,77

Dendograma:

0,00,10,20,30,40,50,60,70,80,91,0

D F A B E

Dis

tân

cia

C

Exemplo: Single Link

20

Pontos fortes da MIN

Pontos originais Dois Clusters

• Pode tratar formas não-elípticas

Limitações da MIN

Pontos originais Dois Clusters

• Sensível a ruído e outliers

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 I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.00 1 2 3 4 5

Clustering hierárquico: MAX

Clusters aninhados Dendrograma

3 6 4 1 2 50

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

1

2

3

4

5

6

1

2 5

3

4

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:

YjeXi:j,idmax)Y,X(d 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:

Exemplo: Complete Linkage

25

961370131841492

621091670790

770471122

740411

670

,,,,,

,,,,

,,,

,,

, *B

C

D

E

F

A B C D E

96,1}96,1;62,1max{)},(),,(max{),(

13,1}13,1;77,0max{)},(),,(max{),(

84,1}84,1;47,1max{)},(),,(max{),(

49,2}49,2;12,2max{)},(),,(max{),(

FEdDEdDFEd

FCdDCdDFCd

FBdDBdDFBd

FAdDAdDFAd

961131841492

091670790

740411

670

,,,,

,,,

,,

,B

C

E

DF

A B C E

Passo 3: Agrupar A e B ao nível de 0,67, e recalcular:

Exemplo: Complete Linkage

26

492841492471122

790670790

411740411

,},;,;,;,max{

)}B,F(d),A,F(d),B,D(d),A,D(dmax{)AB,DF(d

,},;,max{)}B,E(d),A,E(dmax{)AB,E(d

,},;,max{)}B,C(d),A,C(dmax{)AB,C(d

Temos:

492790411

961131

091

,,,

,,

,E

DF

AB

C E DF

Exemplo: Complete Linkage

27

Passo 4: Agrupar AB com E ao nível de 0,79, e recalcular:

492961841492621471122

411091740411

,},;,;,;,;,;,max{

)}E,F(d),B,F(d),A,F(d),E,D(d),B,D(d),A,D(dmax{)ABE,DF(d

,},;,;,max{)}E,C(d),B,C(d),A,C(dmax{)ABE,C(d

Matriz resultante:

492411

131

,,

,DF

ABE

C DF

Exemplo: Complete Linkage

28

Passo 5: Agrupar C com DF ao nível de 1,13, e recalcular:

492961841492621770471122091740411 ,},;,;,;,;,;,;,;,;,;,min{

)}E,F(d),B,F(d),A,F(d),E,D(d),B,D(d),A,D(d),E,C(d),B,C(d),A,C(dmax{

)ABE,CDF(d

Matriz resultante:

492,ABE

CDF

Passo 6: O último passo cria um único agrupamento contendo os 6 objetos, que serão similares a um nível de 2,49.

Exemplo: Complete Linkage

29

Resumindo-se, temos:

Nó Fusão Nível 1 D e F 0,37 2 A e B 0,67 3 AB e E 0,79 4 DF e C 1,13 5 ABE e

CDF 2,49

Dendograma:

0,0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0

D F A B E

Dis

tân

cia

C

1,3

1,2

1,1

2,5

Exemplo: Complete Linkage

Ponto forte da MAX

Pontos originais Dois Clusters

• Menos suscetível a ruído e outliers

Limitações da MAX

Pontos originais Dois Clusters

•Tendência a quebrar clusters grandes

• Tendência a formar clusters esféricos

Similaridade: Média do grupo

A proximidade de dois clusters é dada pela média da distância entre pares de pontos dos dois clusters.

||Cluster||Cluster

)p,e(pproximidad

)Cluster,e(Clusterproximidadji

ClusterpClusterp

ji

jijjii

I1 I2 I3 I4 I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.00 1 2 3 4 5

Clustering hierárquico: Média do grupo

Clusters aninhados Dendrograma

3 6 4 1 2 50

0.05

0.1

0.15

0.2

0.25

1

2

3

4

5

6

1

2

5

3

4

961370131841492

621091670790

770471122

740411

670

,,,,,

,,,,

,,,

,,

,B

C

D

E

F

A B C D E

Dada a matriz de distâncias:

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: Clustering hierárquico: Média do

grupo

79129616212

95021317702

66128414712

30224921222

,/},,{/)}F,E(d)D,E(d{)DF,E(d

,/},,{/)}F,C(d)D,C(d{)DF,C(d

,/},,{/)}F,B(d)D,B(d{)DF,B(d

,/},,{/)}F,A(d)D,A(d{)DF,A(d

791950661302

091670790

740411

670

,,,,

,,,

,,

,B

C

E

DF

A B C E

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.

Exemplo: Average Linkage

36

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.

98,14/}84,149,247,112,2{

4/)},(),(),(),({),(

73,02/}67,079,0{2/)},(),({),(

08,12/}74,041,1{2/)},(),({),(

BFdAFdBDdADdABDFd

BEdAEdABEd

BCdACdABCd

Temos:

981730081

791950

091

,,,

,,

,E

DF

AB

C E DF

Exemplo: Average Linkage

37

Passo 4: Agrupar AB com E ao nível de 0,73, e recalcular:

92,16/}96,184,149,262,147,112,2{

6/)},(),(),(),(),(),({),(

08,13/}09,174,041,1{3/)},(),(),({),(

EFdBFdAFdEDdBDdADdABEDFd

ECdBCdACdABECd

Matriz resultante:

921081

950

,,

,DF

ABE

C DF

Exemplo: Average Linkage

38

Passo 5: Agrupar C com DF ao nível de 0,95, obtendo-se a partição (ABE, CDF) e recalcular:

6419961841492621471122091740411

9

,/},,,,,,,,,{

/)}E,F(d)B,F(d)A,F(d)E,D(d)B,D(d)A,D(d)E,C(d)B,C(d)A,C(d{

)ABE,CDF(d

Matriz resultante:

641,ABE

CDF

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 .

Exemplo: Average Linkage

39

Resumindo-se, temos:

Nó Fusão Nível 1 D e F 0,37 2 A e B 0,67 3 AB e E 0,73 4 DF e C 0,95 5 ABE e

CDF 1,64

Dendograma:

0,00,10,20,30,40,50,60,70,80,91,0

D F A B E

Dis

tân

cia

C

1,31,21,1

1,6

1,41,5

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).

Exemplo: Average Linkage

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

Média do grupo

Método de Ward

1

2

3

4

5

61

2

5

3

4

MIN MAX

1

2

3

4

5

61

2

5

34

1

2

3

4

5

61

2 5

3

41

2

3

4

5

6

12

3

4

5

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.

Core and border points

pEps

qEps

DBSCAN (Ester 1996)

rEps

minPts= 5Eps= 1

Core pointBorder pointnoise

DBSCAN Algorithm

Eliminate noise points Perform clustering on the remaining points

Prof. Luis Otavio Alvares 49

DBSCAN example

Prof. Luis Otavio Alvares 50

Identifying core, border and noise points

Prof. Luis Otavio Alvares 51

Prof. Luis Otavio Alvares 52

DBSCAN: Core, Border and Noise Points

Pontos originais Point types: core, border and noise

Eps = 10, MinPts = 4

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

Pontos originais

(MinPts=4, Eps=9.92).

(MinPts=4, Eps=9.75)

• Variação de densidades

• Dados com muitas dimensões

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

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

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

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.

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

N. Jardine, R.Sibson. Mathematical Taxonomy.Wiley, New York, 1971.

Referências

K-means

PAM

CLARANS

DBSCAN

OPTICS

Hierárquicos

Prof. Luis Otavio Alvares 58

Para o quadro abaixo, aplique o algoritmo aglomerativo MIN (single link) e apresente o dendograma final com o passo a passo.

Exercícios

Itens/Variáveis V1 V2A 3 2B 4 5C 4 7D 2 7E 6 6F 7 7G 6 4

Prof. Luis Otavio Alvares 59

A B C D

B 4

C 6 2

D 6 4 2

E 7 3 3 5

d(A,B) = |3-4| + |2-5| = 4d(A,C) = |3-4| + |2-7| = 6….

Passo 1: calcular a tabela de distâncias iniciais