Análise de Agrupamentos (Clusters) Marcílio C. P. de Souto DIMAp/UFRN

Análise de Agrupamentos Análise de Agrupamentos ((ClustersClusters))

Marcílio C. P. de Souto

DIMAp/UFRN

O que é análise de agrupamentos? (1/4)

Dado um conjunto de objetos, colocar os objetos em grupos (clusters) baseados na similaridade entre eles

Utilizado para encontrar padrões inesperados nos dados

Inerentemente é um problema não definido claramente

Como agrupar os animais seguintes?


Dado um conjunto de objetos, colocar os objetos em grupos baseados na similaridade entre eles




Com bicoCom bico

Sem bicoSem bico






TerraTerraÁguaÁgua






OvíparoOvíparo

MamíferoMamífero

Análise de Agrupamentos

Aprendizado não-Supervisionado Dado um conjunto de objetos descritos por múltiplos valores

(atributos) (1) atribuir grupos (clusters) aos objetos particionando-os

objetivamente em grupos homogêneos de maneira a: Maximizar a similaridade de objetos dentro de um mesmo

grupo Minimizar a similaridade de objetos entre grupos distintos

(2) atribuir uma descrição para cada grupor formadoCluster 1

Cluster 2

Cluster K

.

.

.

DadosAlgoritmo

deAgrupamento

(1)

cor=azul

cor=laranja

cor=amarelo

(2)

Representação dos Grupos

ad

kj

h

g if

ec

b

(a)

(c) 1 2 3

abc

0.4 0.1 0.50.1 0.8 0.10.3 0.3 0.4

...

(b)

ad

kj

h

gif

ec

b

(d)

g a c i e d k b j f h

Formalmente, ...

Dado um conjunto de instâncias X={x1, x2,..., xN} (meus dados), em que xj={xj1, xj2,..., xjd}T d e cada xji é um atributo:

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D

Agrupamento Particional Um algoritmo de agrupamento particional (hard)

gera uma K-partição de X, C={C1, C2, ..., CK} (K N), tal que:

Ci (i=1,...,K) i=1 Ci = X Ci Cj = (i,j=1,...,K e i j)

Exemplo: Agrupamento Particional

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D C2C1

C3

Agrupamento Hierárquico

Um algoritmo de agrupamento hierárquico gera uma estrutura aninhada (árvore) de X, H={H1, H2, ..., HQ} (K N), tal que:

Ci Hm e Cj Hl (m > l), implica que

Ci Cj ou Ci Cj = (i,j,m,l=1,...,Q e i j)

Agrupamento Hierárquico: Exemplo

0

G

F

C

A

B

D

E

1 2 3 4

12

3

4

5

6

Agrupamento Fuzzy

Para algoritmos de agrupamentos particional hard, cada instância (objeto) pertence a apenas um grupo (cluster)

No entanto, pode ser permitido a uma instância pertencer a todos os grupos com um grau de pertinência, ui,j [0,1], que representa o coeficiente de pertinência da j-ésima instância ao i-ésimo grupo (cluster)

j i

k

=1 ui,j =1 e i j

N

=1 ui,j < N

Como funciona a análise de agrupamentos? (1/2)

Suponha que um biólogo queira identificar subtipos de um determinado câncer(tumor) com base na expressão gênica do tecido extraído do tumor

Uma pequena amostra de sete pacientes é selecionada A expressão gênica de dois genes - V1 e V2 - foi medida

para o tumor de cada paciente

Paciente V1 V2A 3 2B 4 5C 4 7D 2 7E 6 6F 7 7G 6 4

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D

Como funciona a análise de agrupamentos? (2/2)

O objetivo principal da análise de agrupamentos é definir a estrutura dos dados colocando observações (instâncias ou objetos) mais parecidas em grupos

Mas para conseguir isso, devemos abordar três questões básicas

Como medir a similaridade? Correlação, Distância, Medida de Associação, ...

Como formamos os grupos (clusters)? Não importa apenas medir a similaridade, deve haver um

procedimento para agregar as observações mais similares em grupos

Quantos grupos formamos? Compromisso entre menos grupos e mais homogeneidade

Medida de Similaridade: Distância Euclidiana

A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

Paciente V1 V2A 3 2B 4 5C 4 7D 2 7E 6 6F 7 7G 6 4

d(A,B)=Sqrt[(3-4)2+(2-5)2]

d(C,F)=Sqrt[(4-7)2+(7-7)2]

........

Formação de Grupos

Como já temos a medida de similaridade, devemos desenvolver um procedimento para formar grupos

Para nosso propósito, usaremos uma regra simples:

Identifique as duas observações mais semelhantes (mais próximas) que ainda não estão no mesmo grupo e combine seus grupos

Aplicamos essa regra repetidamente, começando com cada observação em seu próprio grupo e combinando dois grupos por vez, até que todas as observações estejam em um único grupo

Procedimento Hierárquico e Aglomerativo

Formação de Grupos: Passo 1

A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D


A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D


A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D


A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D


A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D


A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

0

2

4

6

8

10

0 1 2 3 4 5 6 7 8 9 10

V1

V2

FE

G

C

B

A

D

Dendograma

0

G

F

C

A

B

D

E

1 2 3 4

12

3

4

5

6

Solução Inicial

0

G

F

C

A

B

D

E

1 2 3 4

Passo 1

0

G

F

C

A

B

D

E

1 2 3 4

1

Passo 2

0

G

F

C

A

B

D

E

1 2 3 4

12

Passo 3

0

G

F

C

A

B

D

E

1 2 3 4

12

3

Passo 4

0

G

F

C

A

B

D

E

1 2 3 4

12

3

4

Passo 5

0

G

F

C

A

B

D

E

1 2 3 4

12

3

4

5

Passo 6

0

G

F

C

A

B

D

E

1 2 3 4

12

3

4

5

6

Quantos grupos a solução final deve ter?

Um método hierárquico resulta em diversas soluções de agrupamentos (partições)

No caso do exemplo anterior, elas variam de um a seis grupos Qual devemos escolher?

Sabemos que quando nos afastamos de grupos unitários, a homogeneidade diminui

Então, por que não ficamos com sete grupos, a opção mais homogênea possível?

O problema é que não definimos qualquer estrutura com sete grupos

Assim, devemos devemos verificar cada solução para a sua descrição de estrutura versus a homogeneidade dos grupos

Quantos grupos a solução final deve ter?

Para fins de ilustração, no nosso exemplo foi usada uma medida muito simples homogeneidade:

As distâncias médias de todas as observações dentro dos grupos

A B C D E F GA 0,000B 3,162 0,000C 5,099 2,000 0,000D 5,099 2,828 2,000 0,000E 5,000 2,236 2,236 4,123 0,000F 6,403 3,606 3,000 5,000 1,414 0,000G 3,606 2,236 3,606 5,000 2,000 3,162 0,000

Solução Inicial

Na solução inicial com sete grupos, essa medida de similaridade geral é 0 (nenhum observação faz par com alguma outra)

Passo Par-Instância Pertinência #Grupos Distância(A)(B)(C)(D)(E)(F)(G) 7 0

Distância MínimaProcesso de Aglomeração Solução

Solução Incial

Passo 1

Nesse passo, a similaridade média (1,414) é a distância entre as duas observações reunidas (E-F)


1 E-F (A)(B)(C)(D)(EF)(G) 6 1,414


1,414Solução Incial

Passo 2

Um agrupamento de três elementos (E, F e G) é formado A medida de similaridade geral é a média das distâncias entre

E e F (1,414), e E e G (2,000), e F e G (3,162), que nos dá 2,192


1 E-F (A)(B)(C)(D)(EF)(G) 6 1,4142 E-G (A)(B)(C)(D)(EFG) 5 2,192



2,000

Aumento do valor da similaridade geral, em relação ao passo anterior

Passo 3

No Passo 3, um novo grupo de dois membros é formado com a distância 2,000

Ligeira diminuição do valor da similaridade geral, em relação ao passo anterior


1 E-F (A)(B)(C)(D)(EF)(G) 6 1,4142 E-G (A)(B)(C)(D)(EFG) 5 2,1923 C-D (A)(B)(CD)(EFG) 4 2,144



2,0002,000

Passo 4

Ligeira alteração do valor da similaridade geral, em relação ao passo anterior

Isto significa que estamos gerando outros grupos essencialmente com a homogeneidade dos grupos existentes


1 E-F (A)(B)(C)(D)(EF)(G) 6 1,4142 E-G (A)(B)(C)(D)(EFG) 5 2,1923 C-D (A)(B)(CD)(EFG) 4 2,1444 B-C (A)(BCD)(EFG) 3 2,234


1,414

2,000

Solução Incial

2,0002,000

Passo 5

Combinação de dois grupos com três observações. Grande aumento no valor da similaridade geral, em relação ao passo anterior

Isso é indicativo de que reunir esses dois grupos resultou em um agregado que é bem menos homogêneo

Segundo a nossa medida, poderíamos considerar a solução do Passo 4 muito melhor do que esta


1 E-F (A)(B)(C)(D)(EF)(G) 6 1,4142 E-G (A)(B)(C)(D)(EFG) 5 2,1923 C-D (A)(B)(CD)(EFG) 4 2,1444 B-C (A)(BCD)(EFG) 3 2,2345 B-E (A)(BCDEFG) 2 2,896


1,414

2,0002,236

Solução Incial

2,0002,000

Passo 6

Nesse passo, a medida geral novamente aumenta consideravelmente

Ou seja, a observação “A” mesmo sozinha ainda foi capaz de mudar a homogeneidade do agrupamento. Observação atípica?

Portanto, segundo a nossa medida, ainda consideraríamos a solução do Passo 4 muito melhor do que esta


1 E-F (A)(B)(C)(D)(EF)(G) 6 1,4142 E-G (A)(B)(C)(D)(EFG) 5 2,1923 C-D (A)(B)(CD)(EFG) 4 2,1444 B-C (A)(BCD)(EFG) 3 2,2345 B-E (A)(BCDEFG) 2 2,8966 A-B (ABCDEFG) 1 3,42


1,414

2,0002,2363,162

Solução Incial

2,0002,000

Pré-Proc Alg. Clustering

Interpretação Validação

Conhecimento

Dados

Partição

Passos na Análise de Agrupamentos

Medidas de Similaridade

Marcilio SoutoDIMAp/UFRN

Medidas de Similaridade

A similaridade entre objetos (instâncias) é uma medida de correspondência ou semelhança entre objetos a serem agrupados

Ela pode ser medida de diversas formas Medidas Correlacionais (e.g., correlação de Pearson) Medidas de Distância (e.g., distância euclidiana) Medidas de Associação (e.g., índice de Jaccard)

Cada uma dessas formas representa uma perspectiva particular da similaridade, dependendo de seus objetivos e do tipo de dados

Tanto as medidas correlacionais quanto as medidas de distância requerem dados métricos, ao passo que as medidas de associação são para dados não-métricos

Medidas de Similaridade: Fórmulas

Medidas Correlacionais Medidas correlacionais representam similaridades pela

correspondência de padrões ao longo dos atributos Ela não olha a magnitude do valores dos atributos, apenas

o padrão global de valores

X1 X2 X3 X4 X5Cliente_1 7,000 10,000 9,000 7,000 10,000Cliente_2 9,000 9,000 8,000 9,000 9,000Cliente_3 5,000 5,000 6,000 7,000 7,000Cliente_4 6,000 6,000 3,000 3,000 4,000Cliente_5 1,000 2,000 2,000 1,000 2,000Cliente_6 4,000 3,000 2,000 3,000 3,000Cliente_7 2,000 4,000 5,000 2,000 5,000

0

2

4

6

8

10

12

X1 X2 X3 X4 X5

Cliente_1

Cliente_2

Cliente_3

Cliente_4

Cliente_5

Cliente_6

Cliente_7

Exemplo

0

2

4

6

8

10

12

X1 X2 X3 X4 X5

Cliente_1

Cliente_2

Cliente_3

Cliente_4

Cliente_5

Cliente_6

Cliente_7

Medidas Correlacionais

Cliente_1 Cliente_2 Cliente_3 Cliente_4 Cliente_5 Cliente_6 Cliente_7Cliente_1 1,000Cliente_2 -0,147 1,000Cliente_3 0,000 0,000 1,000Cliente_4 0,087 0,516 -0,824 1,000Cliente_5 0,963 -0,408 0,000 -0,060 1,000Cliente_6 -0,466 0,791 -0,354 0,699 -0,645 1,000Cliente_7 0,891 -0,516 0,165 -0,239 0,963 -0,699 1,000


X1 X2 X3 X4 X5 MédiaCliente_1 7,000 10,000 9,000 7,000 10,000 8,600Cliente_2 9,000 9,000 8,000 9,000 9,000 8,800Cliente_3 5,000 5,000 6,000 7,000 7,000 6,000Cliente_4 6,000 6,000 3,000 3,000 4,000 4,400Cliente_5 1,000 2,000 2,000 1,000 2,000 1,600Cliente_6 4,000 3,000 2,000 3,000 3,000 3,000Cliente_7 2,000 4,000 5,000 2,000 5,000 3,600

Cliente_1 7,000 10,000 9,000 7,000 10,000Media 8,6 8,6 8,6 8,6 8,6X-Media -1,600 1,400 0,400 -1,600 1,400(X-Media)^2 2,56 1,96 0,16 2,56 1,96 9,2

Cliente_5 1,000 2,000 2,000 1,000 2,000Media 1,6 1,6 1,6 1,6 1,6Y-Media -0,600 0,400 0,400 -0,600 0,400(Y-Media)^2 0,36 0,16 0,16 0,36 0,16 1,2

0,96 0,56 0,16 0,96 0,56 3,23,32265

0,963087


Cliente_1 Cliente_2 Cliente_3 Cliente_4 Cliente_5 Cliente_6 Cliente_7Cliente_1 1,000Cliente_2 -0,147 1,000Cliente_3 0,000 0,000 1,000Cliente_4 0,087 0,516 -0,824 1,000Cliente_5 0,963 -0,408 0,000 -0,060 1,000Cliente_6 -0,466 0,791 -0,354 0,699 -0,645 1,000Cliente_7 0,891 -0,516 0,165 -0,239 0,963 -0,699 1,000

As instâncias 1, 5 e 7 têm padrões semelhantes e correlação (positiva) altaDa mesma forma instâncias 2, 4 e 6A instância 3 tem correlação baixa ou negativas com todas as demais, de modo que talvez forme um grupo por si mesmaPortanto, as correlações representam padrões ao longo dos atributos, muito mais do que as magnitudes

Medidas de Distância

Representam a similaridade como a proximidade entre observações (instâncias) ao longo dos atributos

As medidas de distância são, na verdade, uma medida de dissimilaridade, em que os valores maiores denotam menor similaridade

A distância é convertida em similaridade pelo uso da relação inversa (1 - distância)

Medidas de Distância: Exemplo

Distância Euclidiana

Cliente_1 Cliente_2 Cliente_3 Cliente_4 Cliente_5 Cliente_6 Cliente_7Cliente_1 0,00Cliente_2 3,32 0,00Cliente_3 6,86 6,63 0,00Cliente_4 10,24 10,20 6,00 0,00Cliente_5 15,78 16,19 10,10 7,07 0,00Cliente_6 13,11 13,00 7,28 3,87 3,87 0,00Cliente_7 11,27 12,16 6,32 5,10 4,90 4,36 0,00

Distância versus Correlação

As medidas de distância se concentram na magnitude dos valores e representam casos similares que estão próximos, mas podem ter padrões muito diferentes ao longo dos atributos

No caso do exemplo anterior, vemos emergir grupos muitos diferentes quando a distância é considerada em lugar da correlação

Como as distâncias menores representam maior similaridade, percebemos que as instâncias 1 e 2 formam um grupo e as instâncias 4, 5, 6 e 7 formam outro

Um terceiro grupo, que consiste apenas do caso 3, difere dos outros dois porque possui valores que são tantos altos quanto baixos

Distância versus Correlação

Agrupamentos baseados em medidas correlacionais podem não ter valores similares, mas sim padrões similares

Agrupamentos baseados em distância têm valores mais similares no conjunto de atributos, mas os padrões podem ser bem diferentes

Medidas para Atributos Binários

Considere dos vetores binários xi e xk

n11 - quantidade de vezes que xil e xkl são ambos 1 n00 - quantidade de vezes que xil e xkl são ambos 0 n01 - quantidade de vezes que xil=0 e xkl=1 n10 - quantidade de vezes que xil=1 e xkl=0

1 0

1 n11 n10

0 n01 n00

Medidas para Atributos Binários1 0

1 n11 n10

0 n01 n00

Coeficiente de matching simples Índice (coeficiente) de Jaccard

n11

n01 + n10 + n11

n11 + n00

n00 + n01 + n10 + n11

Medidas para Atributos Categóricos

Pode-se transformar esses atributos em binários e, depois, aplicar uma medida binária

Outra possibilidade

Sij = d Sijl

0, se i<>jSijl =

1, se i=j

Medidas para Strings

Programação Dinâmica

Sejam s e t duas seqüências, com |s|=m e |t|=n,

construir uma matriz (m+1) x (n+1), em que M(i, j) contém

a similaridade entre s[1..i] e t[1..j]. M (i, j) = max M (i, j-1) - 2 (último passo = Inserção) M (i-1, j-1) + p(i,j) (último passo =

Substituição/Match) M (i-1, j) - 2 (último passo = Remoção)

Bibliografia

Hair-Jr., J. F. et al (2005). Análise multivariada de dados. Capítulo 9 - Análise de Agrupamentos. pp. 381-419. Bookman.

Xu, R. and Wunsch II, D. (2005). Survey of Clustering Algorithms. IEEE Trans. on Neural Networks, v. 16, pp. 645-678.

Documents

Análise de Agrupamentos (Clusters) Marcílio C. P. de Souto DIMAp/UFRN