Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Programa de Pós-graduação em Biociências
Área de Concentração
“Caracterização e Aplicação da Diversidade Biológica”
Análise de Agrupamentos para Reconhecimento de
Padrões em Saúde e Ecologia.
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Método Hierárquicos Aglomerativos
Iniciam operando a matriz de similaridade, considerando cada
objeto como sendo o grupo inicial (cluster).
1. Na matriz de similaridade procuram-se os dois objetos mais similares
2. Retiram-se os objetos i e j , os quais formam um grupo;
eliminando-se a linha e a coluna correspondentes de i e j;
3. Definem-se uma linha e uma coluna obtidas pelas distâncias
entre o grupo (ij) e os objetos restantes, de acordo com o
procedimento do algoritmo adotado;
4. Repetem-se os passos anteriores n-1 vezes, de maneira que todos
os n objetos pertençam a um grupo ao fim do algoritmo
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Métodos Abordados
•Single Linkage
•Complete Linkage
•Average Linkage
•Método de Ward
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Vizinho mais Próximo (Single Linkage) - Este método,
também conhecido por “nearest neighbor”, inicia seu
procedimento pela procura dos dois objetos mais similares
na matriz de similaridade D1.
A 4
16
B 16 14
D  C 10 14
D 14 10
E 8
16
A 0


B 12,2 0



D  C  6,3 6,0 0
1


D 11,7 4,5 5,6 0

E  4,0 8,2 2,8 8,5 0
O primeiro passo é verificar a
distância mínima entre dois
objetos, na matriz D, a qual é
dada por:
min
(d ij )  d CE  2,8
(intersecção entre a coluna 3 e a linha 5);
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
A
B
C D A
A 0


B 12,2 0



D  C  6,3 6,0 0
1


D 11,7 4,5 5,6 0

E  4,0 8,2 2,8 8,5 0
Necessitamos obter a distâncias entre
os objetos do grupo (CE) e os objetos
restantes.
Neste ponto o método Single Linkage fica
caracterizado, as distâncias entre o
grupo (CE) e os demais devem ser
as menores; assim teríamos :
d (CE)A 
min d CA , d EA  = min 6,3;4,0= 4,0
d (CE)B 
min d CB , d EB  = min 6,0;8,2= 6,0
d (CE)D 
min d CD , d ED  = min 5,6;8,5= 5,6
(CE)
A
B
D
(CE)  0


0
A 4,0


D2 =

B 6,0 12,2 0


D 5,6 11,7 4,5 0
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
(CE)
A
B
D
(CE)  0


0
A 4,0


D2 =

B 6,0 12,2 0


D 5,6 11,7 4,5 0
d (CEA)B 
min
d(CE)B, dAB  min6,0;12,2  6
d (CEA)D 
min
d (CE)D, dAD  min5,6;11,7  5,6
(CEA) (BD)
D3
D
(CEA)  0


=
B  6,0 0


D  5,6 4,5 0 
D4
(CEA)  0

=
(BD)  5,6 0 
SINGLE LINKAGE
6,0
5,5
Distância Euclideana
(CEA) B
5,0
4,5
4,0
3,5
3,0
2,5
D
B
E
C
A
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Características do Single Linkage
•Em geral, grupos muito próximos podem não ser identificados;
• Permite detectar grupos de formas não-elipticas;
• Apresenta pouca tolerância a ruído, pois tem tendência a incorporar
os ruídos em um grupo já existente;
• Apresenta bons resultados tanto para distância Mahalanobis
quanto para outras distâncias;
• Tendência a formar longas cadeias (encadeamento).
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Vizinho mais Distante (Complete Linkage)
Este método, após agrupar os dois indivíduos mais semelhantes,
de menor distância, verifica a distância máxima deste primeiro
grupo para os objetos restantes.
Desta forma procura garantir que os objetos de um grupo guardem
a máxima distância de outros grupos.
Utilizaremos a mesma matriz de distância do exemplo anterior
para ilustrar os passos deste método.
A 4
16
B 16 14
D  C 10 14
D 14 10
E 8
16
A
B
C
D
E
A 0


B 12,2 0



D1  C 6,3 6,0 0


D 11,7 4,5 5,6 0


E  4,0 8,2 2,8 8,5 0
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
A
B
C D A
A 0


B 12,2 0



D  C  6,3 6,0 0
1


D 11,7 4,5 5,6 0

E  4,0 8,2 2,8 8,5 0
Necessitamos obter a distâncias entre
os objetos do grupo (CE) e os objetos
restantes.
Neste ponto o método Complete Linkage fica
caracterizado, as distâncias entre o
grupo (CE) e os demais devem ser
as maiores; assim teríamos :
d (CE)A  max d CA , d EA  = max 6,3;4,0= 6,3
d (CE)B  max d CB , d EB  = max 6,0;8,2= 8,2
d (CE)D  max d CD , d ED  = max 5,6;8,5= 8,5
(CE)
A
B
D
(CE) 0


A 6,3 0

D2 =

B 8,2 12,2 0


D 8,5 11,7 4,5 0
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Complete Linkage
(CE)
A
D2 =
B
D
(CE) A
B D
0

6,3 0



8,2 12,2 0



8,5 11,7 4,5 0
Single Linkage
(CE)
A
B
D
(CE)  0


0
A 4,0


D2 =

B 6,0 12,2 0


D 5,6 11,7 4,5 0
O próximo passo é, novamente, obter a menor distância.
O valor é obtido pela intersecção da coluna representada pelo
objeto B e da linha representada pelo objeto D, esta distância é
igual a 4,5, o que indica a formação de um novo grupo,
objetos B e D (BD).
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.

(CE) (BD) A

d (CE)(BD)  max d (CE)B , d (CE)D = max 8,2;8,5= 8,5
(CE)  0



0
D 3 = (BD) 8,5

A 6,3 12,2 0
d (BD)A  max d BA , d DA  = max 12,2;11,7= 12,2
(CEA) (BD)
(CEA)  0

D4 =

(BD)  12,2 0 
COMPLETE LINKAGE
14
12
Distância Euclideana
10
8
6
4
2
0
D
B
E
C
A
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Características do Complete Linkage
•Apresenta bons resultados tanto para a distâncias Mahalanobis
quanto para outras distancias;
• Tendência a formar grupos compactos;
• Os ruídos demoram para serem incorporados ao grupo.
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Distância Média (Average Linkage)
O método da Distância Média procede, inicialmente, da mesma
maneira que os métodos anteriores, ou seja, principia por agrupar
os dois objetos mais semelhantes. A seguir utiliza a média aritmética
das distâncias dos objetos de cada grupo para confeccionar a nova
matriz de distâncias
A
A 4
16
B 16 14
D  C 10 14
D 14 10
E 8
16
B
C
D
E
A 0


B 12,2 0


D1  C  6,3 6,0 0


D 11,7 4,5 5,6 0

E  4,0 8,2 2,8 8,5 0
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Novamente temos como passo inicial a obtenção do grupo (CE),
o qual apresenta a distância mínima igual a 2,8.
Utilizando a média aritmética, obteremos as novas distâncias
que irão compor a nova matriz de distância D2:
A
B
C
D
E
A 0



B 12,2 0


D1  C  6,3 6,0 0


D 11,7 4,5 5,6 0


E  4,0 8,2 2,8 8,5 0
1
d (C, A)  d (E, A)  1 6,3  4,0  5,2
2
2
1
1
d (CE)B  d (C, B)  d (E, B)   6  8,2  7,1
2
2
1
1
d (CE)D  d (C, D)  d (E, D)   5,6  8,5  7,1
2
2
d (CE)A 
(CE) A
B D
(CE) 0



A 5,2 0

D2 =

B  7,1 12,2 0


D  7,1 11,7 4,5 0
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
(CE) A
B D
(CE) 0


A 5,2 0

D2 =

B  7,1 12,2 0


D  7,1 11,7 4,5 0
d (BD)A 
1
d (B, A)  d (D, A)  1 12,2  11,7  11,9
2
2
d (BD), (CE) 
1
d (B, (CE))  d (D, (CE))   1 7,1  7,1  7,1
2
2
(CEA) (BD)
(CE) (BD) A
0

 7,1 0



5,2 11,9 0
=
(CEA)  0

(BD)  9,5 0 
A V E R A GE L IN K A GE
10
9
8
distância Euclideana
(CE)
D 3 = (BD)
A
D4
7
6
5
4
3
2
1
D
B
E
C
A
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Características do Avarege Linkage
• Menor sensibilidade a ruídos que os métodos de ligação simples
e completa;
• Apresenta bons resultados tanto para a distância Mahalanobis
quanto para outras distâncias;
• Tendência a formar grupos com número de elementos similares.
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Diferentes Resultados!
Pode parecer que, qualquer uma das três metodologias descrita,
forneça o mesmo resultado. No exemplo utilizado isto é verdade,
pois temos, como resultado dois grupos, o primeiro formado pelos
objetos (ECA) e o segundo por (BD), entretanto, em outras situações,
onde a estrutura de dados analisada não é tão bem definida,
resultados diferentes podem surgir para diferentes algoritmos.
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Exemplo
v1 v2 v3 v4
A  2 5 11
B  3 7 11

C  1 9 12

D  5 11 15
E 11 5 6

F2 8 9
G4 9 6

H5 4 7
I  6 2 11
D=
2
3

2

4
1

4
6

7
3
D1 =
 0
 2 ,4

 4 ,2

 8,1
10,3

 4 ,1
 7 ,8

 7 ,1
 5,1

0
3,2
6,1
9 ,9
2 ,7
6, 2
6, 7
5,8




0

5,7
0


12 ,4 12 ,7
0

3,9 7 ,3 10,4 0


7 ,8 9 ,5 9 ,5 4 ,2 0

9 ,5
11
8,6 6,2 5,3 0

8,7 9 ,9 7 ,9 7 ,5 9 ,3 6,1 0
Complete Linkage
Single Linkage
14
14
13
12
12
11
10
Linkage Distance
Linkage Distance
10
9
8
7
6
8
6
4
5
4
2
3
2
0
1
E
D
H
I
G
C
F
B
A
H
G
I
E
D
F
C
B
A
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Método de Ward
Este método, diferente dos anteriores, tem como característica,
a obtenção da soma dos quadrados, a qual chamaremos de SQ,
para todos os possíveis grupos. A reunião definitiva dos objetos irá
contemplar os menores valores de SQ. Este método pode ser usado
diretamente na matriz de dados iniciais .
P
n
E (G1G 2)    ( xiv  xv ) 2
V i 1
i G1
onde xV é a média do grupo para cada variável V.
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Exemplo
V1 V2
A 4
16
B 16 14
O primeiro passo é calcular o valor de SQ para cada um
dos possíveis pares de objetos:
D  C 10 14
D 14
E 8
10
16
SQ(AB)  (4  10) 2  (16  10) 2  (16  15) 2  (14  15) 2  74
onde
xv1 
4  16
 10
2
e
xv2 
16  14
 15
2
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Passo
Possíveis Grupos
1
(AB)
(AC)
(AD)
(AE)
(BC)
(BD)
(BE)
(CD)
(CE)
(DE)
C
B
B
B
A
A
A
A
A
A
D
D
C
C
D
C
C
B
B
B
2
(CE)
(CE)
(CE)
(CEA)
(CEB)
(CED)
(AB)
(AD)
(BD)
B
A
A
D
B
A
D
D
B
3
(CEA)
(CEBD)
(CE)
(BD)
A
(BDA)
4
(ABCDE)
E
E
E
E
B
E
E
B
E
B
C
74
20
68
08
18
10
34
16
04*
36
78
72
14*
21.3
37.5
37.5
31*
59
105
O primeiro grupo é formado
pelos objetos C e E, valor de
SQ é o menor (SQ =4).
Desta forma, podemos iniciar
o segundo passo (passo 2),
que consiste na
combinação do grupo
(CE) com todas as
demais possibilidades
de agrupamento.
Para ilustrar este passo
calcularemos:
115
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
V1 V2
Continuação...
A 4
P
B 16 14
n
E (G1G 2)    ( xiv  xv )
2
16
D  C 10 14
V i 1
i G1
D 14
E 8
10
16
WARD
2
2
2
2
SQ(CE)(AB)  (
10  9)  (8  9)  (14  15)  (16  15) 




grupo(AB)
14
12
distância euclideana
grupo(CE)
2
2
2
2
 ( 4  10)  (16  10)  (16  15)  (14  15)  78
16
10
8
6
4
2
0
D
B
E
C
A
SQ (CEA)  (4  7,3) 2  (10  7,3) 2  (8  7,3) 2  (16  15,3) 2 
 (14  15,3) 2  (16  15,3) 2  21,3
Dr. Fernando Frei
Universidade Estadual Paulista “Júlio de Mesquita Filho”
FCLassis – Depto de Ciências Biológicas
Análise de Agrupamentos para Reconhecimento de Padrões em Saúde e Ecologia.
Características do Método de Ward
• Apresenta bons resultados tanto para distâncias Mahalanobis
quanto para outras distâncias;
• Pode apresentar resultados insatisfatórios quando o número
de elementos em cada grupo é praticamente igual;
• Tem tendência a combinar grupos com poucos elementos;
• Sensível à presença de outliers.
Dr. Fernando Frei