Algoritmo_Exemplo-agrupamento

Prévia do material em texto

Exemplo de agrupamento 
 V1 V2 
A 1,0 1,0 
B 2,1 2,1 
C 2,8 2,8 
D 4,7 4,0 
E 6,0 6,0 
F 6,8 5,7 
G 6,5 6,6 
H 0,5 11,0 
 
 
distância euclidiana simples 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
E 7.071 5.515 4.525 2.385 0 
F 7.465 5.920 4.941 2.702 0.854 0 
G 7.849 6.294 5.304 3.162 0.781 0.949 0 
H 10.012 9.043 8.517 8.163 7.433 8.233 7.440 0 
 A B C D E F G H 
 
H
G
F
E
D
C
B
A
0,0
2,0
4,0
6,0
8,0
10,0
12,0
0,0 2,0 4,0 6,0 8,0
V1
V2
Ligação simples (Vizinho Mais Próximo) 
 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
E 7.071 5.515 4.525 2.385 0 
F 7.465 5.920 4.941 2.702 0.854 0 
G 7.849 6.294 5.304 3.162 0.781 0.949 0 
H 10.012 9.043 8.517 8.163 7.433 8.233 7.440 0 
 A B C D E F G H 
 
menor distância = 0,781 (EG) 1ª ligação E–G 
próxima matriz : 
 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
EG 7.071 5.515 4.525 2.385 0 
F 7.465 5.920 4.941 2.702 0.854 0 
H 10.012 9.043 8.517 8.163 7.433 8.233 0 
 A B C D EG F H 
 
menor distância = 0,854 (FEG) 2ª ligação EG–F 
próxima matriz : 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
EGF 7.071 5.515 4.525 2.385 0 
H 10.012 9.043 8.517 8.163 7.433 0 
 A B C D EGF H 
menor distância = 0,990 (BC) 3ª ligação B–C 
próxima matriz : 
A 0 
BC 1.556 0 
D 4.763 2,247 0 
EGF 7.071 4,525 2.385 0 
H 10.012 8,517 8.163 7.433 0 
 A BC D EGF H 
menor distância = 1,556 (ABC) 4ª ligação A–BC 
próxima matriz : 
ABC 0 
D 2,247 0 
EGF 4,525 2.385 0 
H 10.012 8.163 7.433 0 
 ABC D EGF H 
menor distância = 2,247 (ABCD) 5ª ligação ABC–D 
próxima matriz : 
ABCD 0 
EGF 2,385 0 
H 8,163 7.433 0 
 ABCD EGF H 
menor distância = 2,385 (ABCDEFG) 6ª ligação ABCD–EFG 
próxima matriz : 
ABCDEFG 0 
H 7,433 0 
 ABCDEFG H 
única distância sobrando = 7,433 última 
ligação ABCDEFG–H 
 
Ligação Completa (Vizinho Mais 
Distante) 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
E 7.071 5.515 4.525 2.385 0 
F 7.465 5.920 4.941 2.702 0.854 0 
G 7.849 6.294 5.304 3.162 0.781 0.949 0 
H 10.012 9.043 8.517 8.163 7.433 8.233 7.440 0 
 A B C D E F G H 
 
menor distância = 0,781 (EG) 1ª ligação E–G 
próxima matriz : 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
EG 7.849 6,294 5,304 3,162 0 
F 7.465 5.920 4.941 2.702 0.949 0 
H 10.012 9.043 8.517 8.163 7.440 8.233 0 
 A B C D EG F H 
menor distância = 0,949 (EGF) 2ª ligação EG–F 
próxima matriz : 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
EGF 7.849 6,294 5,304 3,162 0 
H 10.012 9.043 8.517 8.163 8,233 0 
 A B C D EGF H 
menor distância = 0,990 (BC) 3ª ligação B–C 
próxima matriz : 
A 0 
BC 1.556 0 
D 4.763 3.220 0 
EGF 7.849 6,294 3,162 0 
H 10.012 9.043 8.163 8,233 0 
 A BC D EGF H 
menor distância = 1,556 (ABC) 4ª ligação A–BC 
próxima matriz : 
ABC 0 
D 4.736 0 
EGF 7,849 3,162 0 
H 10,012 8.163 8,233 0 
 ABC D EGF H 
menor distância = 3,162 (DEFG) 5ª ligação D–EFG 
próxima matriz : 
ABC 0 
DEGF 7,849 0 
H 10,012 8,233 0 
 ABC DEGF H 
menor distância = 7,849 (ABCDEFG) 5ª 
ligação ABC–DEFG 
próxima matriz : 
ABCDEGF 0 
H 10,012 0 
 ABCDEGF H 
única distância sobrando =10,012 
última ligação ABCDEFG–H 
 
Média de grupo (UPGMA) 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
E 7.071 5.515 4.525 2.385 0 
F 7.465 5.920 4.941 2.702 0.854 0 
G 7.849 6.294 5.304 3.162 0.781 0.949 0 
H 10.012 9.043 8.517 8.163 7.433 8.233 7.440 0 
 A B C D E F G H 
 
menor distância = 0,781 (EG) 1ª ligação E–G 
próxima matriz : 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
EG 7,460 5,905 4,915 2,774 0 
F 7.465 5.920 4.941 2.702 0,902 0 
H 10.012 9.043 8.517 8.163 7,437 8.233 0 
 A B C D EG F H 
menor distância = 0,902 (EGF) 2ª ligação EG–F 
próxima matriz : 
A 0 
B 1.556 0 
C 2.546 0.990 0 
D 4.763 3.220 2.247 0 
EGF 7,462 5,910 4,923 2,750 0 
H 10.012 9.043 8.517 8.163 7,702 0 
 A B C D EGF H 
menor distância = 0,990 (BC) 3ª ligação B–C 
próxima matriz 
A 0 
BC 2,055 0 
D 4.763 2,734 0 
EGF 7,462 5,4165 2,750 0 
H 10.012 8,780 8.163 7,702 0 
 A BC D EGF H 
menor distância = 2,055 (ABC) 4ª ligação A–BC 
próxima matriz 
ABC 0 
D 3,410 0 
EGF 6,098 2,750 0 
H 9,191 8.163 7,702 0 
 ABC D EGF H 
menor distância = 2,750 (DEGF) 5ª ligação D–EGF 
próxima matriz : 
ABC 0 
DEGF 5,426 0 
H 9,191 7,817 0 
 ABC DEGF H 
menor distância = 5,426 (ABCDEFG) 6ª 
ligação ABC–DEFG 
próxima matriz : 
ABCDEGF 0 
H 8,406 0 
 ABCDEGF H 
única distância sobrando =8,406 última 
ligação ABCDEFG–H 
 
 
Ligação simples - algorítmo simplificado 
1. Procure o valor mais alto da coeficiente de similaridade na matriz. Os 2 objetos com 
a similaridade mais alta formam o primeiro grupo. 
2. Procure a próxima similaridade mais alta. Se os objetos já são membros do mesmo 
grupo vá até 3. Se os dois objetos não estão ligados com qualquer grupo, elas 
formam um novo grupo. Se um pertence a um grupo já existente, o objeto que 
não está ligado liga com este grupo. 
3. Se todas as espécies já estão ligadas, acabou. Se não, vá até 2. 
Algorítmo geral 
1. Procure o valor mais alto da coeficiente de similaridade ou menor distância na 
matriz. Os 2 objetos com a maior similaridade formam o primeiro grupo. 
2. Construa uma nova matriz, tratando o grupo recem-formado como um único objeto, 
calculando as novas similaridades/distâncias entre este grupo e os outros 
objetos. 
3. Procure a maior similaridade na nova matriz e ligue os objetos ou grupos 
correspondentes 
4. Se todas as objetos já estão agrupadas, termine. Se não volte a 2. 
 
ligação simples (vizinho mais próximo) - a maior similaridade (menor distância) entre 
os membros de um grupo e o outro. 
ligação completa (vizinho mais distante) - a menor similaridade (maior distância) entre 
os membros de um grupo e o outro 
média de grupo (UPGMA) - média aritmética das similaridades (distâncias) entre os 
membros de um grupo e o outro 
centróide (UPGMC) - similaridade ou distância entre os centróides dos grupos. 
método de Ward (variância mínima) - menor aumento em variância no novo grupo.