Prévia do material em texto
Análise de Agrupamentos Análises de Agrupamento Análises de Agrupamento Grupo ou Cluster Grupo ou Cluster Algoritmos de Agrupamento O que são algoritmos? • Correspondem a uma sequência de instruções utilizadas para resolver problemas bem formulados • Problemas são especificados em entradas (inputs) • O algoritmo corresponde ao método em que as entradas serão analisadas e traduzidas em resultados (outputs) • Os algoritmos então nos auxiliam a organizar a sequência com que determinados eventos devem ocorrer para se chegar a “determinada” resposta!!!! O BATMAN SAI DO BANHO E TEM UMA CHAMADA URGENTE PARA IMPEDIR UMA AÇÃO DO CORINGA!!!! QUAL A MELHOR SEQUÊNCIA DE ROUPAS ELE DEVE VESTIR, MINIZANDO O TEMPO E ACERTANDO A SEQUÊNCIA DE PEÇAS???? Ele pode colocar: (1) blusa (2) depois a calça, (3) short.... ou (1) calça (2) short (3) blusa (4), etc... Mas ele não deve colocar, primeiro a bota, depois a capa, o short, a calça!..... Existem algumas sequências possíveis, e outras que devem, no mínimo, ser evitas!!!! Agrupamentos Hierárquicos Aglomerativos Dendrogramas Dendrograma Lembre-se: Similaridade – 0 a 1 – menor = maior similaridade Distância – 0 a ~ - menor = menor similaridade Distância corda – 0 a √2 = menor = maior Complementos.... Dendrograma Dendrograma Como medir distâncias entre grupos? Como medir a distância até um grupo? Ligação simples ou vizinho mais próximo Ligação simples (viz. + próx.) Ligação Simples Ligação completa (vizinho mais distante) Ligação simples (viz. + próx.) Ligação completa (viz. + dist.) Ligação Completa 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 A B C D E F G H 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 V 2 Ligação 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 A B C D E F G H 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 V 2 Ligação simples 2 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 A B C D E F G H 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 V 2 Ligação simples 3 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 A B C D E F G H 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 V 2 Ligação simples 4 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 A B C D E F G H 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 V 2 Ligação simples 5 ABC 0 D 2,247 0 EGF 4,525 2.385 0 H 10.012 8.163 7.433 0 ABC D EGF H A B C D E F G H 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 V 2 Ligação simples 6 ABCD 0 EGF 2,385 0 H 8,163 7.433 0 ABCD EGF H A B C D E F G H 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 V 2 Ligação simples 7 A B C D E F G H 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 V 2 ABCDEFG 0 H 7,433 0 ABCDEFG H Ligação simples 8 A B C D E F G H 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 V 2 Média de Grupo (UPGMA) Centróide Centróide Centroide d is tâ n c ia e u c lid ia n a s im p le s 2,9 2,8 2,7 2,6 2,5 2,4 2,3 2,2 2,1 2 1,9 1,8 1,7 1,6 1,5 1,4 1,3 1,2 1,1 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 123 45 67 891 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 5 Page 1 of 1 Centróide – inversões 1 3.15 A B C 3 .1 8 2 .7 7 Centróide – inversões 2 3.15 A B C 3 .1 8 2 .7 7 A B C A B C 3,18 3,18 3,15 A B C A BC 2,77 2,77 3,15 B C A Métodos Ponderados - WPGMA WPGMA 3x Métodos Ponderados - WPGMC WPGMC Centróide – inversões 2 3.15 A B C 3 .1 8 2 .7 7 A B C A B C 3,18 3,18 3,15 A B C A BC 2,77 2,77 3,15 B C A Método de Ward Soma de quadrados progressiva (Ward 1963, Orlóci 1967) O critério de agrupamento minimiza o aumento na soma de quadrados dentro do grupo formado a cada passo de agrupamento, i.e. QPQ = QP+Q - QP - QQ Onde QP+Q é a soma de quadrados total no grupo P+Q e QP e QQ são as somas de quadrados dentro dos grupos P e Q. QP+Q = 1 n p + nq h d hi 2 i para h=1, ..., n-1 e i=h+1, ..., n objetos, desde que h e i pertençam ao grupo P ou Q QP = 1 n p h d hi 2 i para h=1, ..., n-1 and i=h+1, ..., n objetos , desde que h e i pertençam ao grupo P QQ = 1 nq h d hi 2 i para h=1, ..., n-1 and i=h+1, ..., n objetos , desde que h e i pertençam ao grupo Q Soma de quadrados progressiva . 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 . Método de Ward Soma de quadrados progressiva (Ward 1963, Orlóci 1967) Algoritmo geral para agrupamento aglomerativo • Lance & Williams • se dois grupos i e j se unem, então a distância entre este novo grupo e qualquer outro grupo k é dado por :- ( )k i j i ki j kj ij ki kjd d d d d d, = + + + − Algoritmo geral tipo i ligação simples ½ 0 -½ ligação completa ½ 0 ½ média de grupo (UPGMA) ( ) i i j n n n+ 0 0 McQuitty (WPGMA) ½ 0 0 Centróide (UPGMC) ( ) i i j n n n+ ( ) i j i j n n n n − + 2 0 Mediano (WPGMC) ½ -0,25 0 mét. de Ward ( ) ( ) i k i j k n n n n n + + + ( ) − + + k i j k n n n n 0 flexível ( )1 2 − − +1 1 0 ( )k i j i ki j kj ij ki kjd d d d d d, = + + + − Método flexível Metodo flexivel d is tâ n c ia e u c lid ia n a s im p le s 2,2 2,1 2 1,9 1,8 1,7 1,6 1,5 1,4 1,3 1,2 1,1 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 123 4 567 891 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 5 Page 1 of 1 Metodo flexivel d is tâ n c ia e u c lid ia n a s im p le s 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0 123 45 67 8 91 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 5 Page 1 of 1 = − 0,7 = + 0,8 Method Alternative name Usually used with: Distance between cluster defined as: Remarks Single linkage Nearest neighbour Similarity or Distance Mininum distance between pair of objects, one in one cluster, one in the other Tends to produce unbalanced and straggly clusters (‘chaining’) especially in large data sets. Does not take account of cluster structure Complete linkage Furthest neighbour Similarity or Distance Maximum distance between pair of objects, one in one cluster, one in the other Tends to find compact clusters with equal diameters (maximum distance between objects). Does not take account of cluster structure. (Group) Average linkage UPGMA Similarity or Distance Average distance between pair of objects, one in one cluster, one in the other Tends to join cluster with small variances. Intermediate between single and complete linkage. Takes account of cluster structure. Relativaly robust. Centroid linkage UPGMC Distance (raw data) Squared Euclidean distance between mean vectors (centroids) Assumes points can be represented in Euclidean space (for geometrical interpretation). The more numerous of two groups clustered dominates the merged clusters, subjectto reversals. Median linkage WPGMC Distance (raw data) Squared Euclidean distance between weihgted centroids Assumes points can be represented in Euclidean space for geometrical interpretation. New group intermediate in position between merged groups, subject to reversals. Ward’s method Minimum sum of squares Distance (raw data) Increase in sum of squares within cluster, after fusionn, summed over all variables Assumes points can be represented in Euclidean space for geometrical interpretation. Tends to find same size, spherical clusters, sensitive to outliers. Media de grupo (UPGMA) d is tâ n c ia e u c lid ia n a s im p le s 8,5 8 7,5 7 6,5 6 5,5 5 4,5 4 3,5 3 2,5 2 1,5 1 0,5 0 AB CDE FG H Page 1 of 1 Correlação Cofenética 1 A 0 B 2,05 0 C 2,05 0,99 0 D 5,43 5,43 5,43 0 E 5,43 5,43 5,43 2,75 0 F 5,43 5,43 5,43 2,75 0,90 0 G 5,43 5,43 5,43 2,75 0,78 0,90 0 H 8,41 8,41 8,41 8,41 8,41 8,41 8,41 0 A B C D E F G H Correlação Cofenética 2 Matriz cofenética e matriz original A B C D E F G H A 0,00 1,56 2,55 4,76 7,07 7,47 7,85 10,01 B 2,05 0,00 0,99 3,22 5,52 5,92 6,29 9,04 C 2,05 0,99 0,00 2,25 4,53 4,94 5,30 8,52 D 5,43 5,43 5,43 0,00 2,39 2,70 3,16 8,16 E 5,43 5,43 5,43 2,75 0,00 0,85 0,78 7,43 F 5,43 5,43 5,43 2,75 0,90 0,00 0,95 8,23 G 5,43 5,43 5,43 2,75 0,78 0,90 0,00 7,44 H 8,41 8,41 8,41 8,41 8,41 8,41 8,41 0,00 Correlação Cofenética 3 Media de grupo (UPGMA) / distância euclidiana simples : Correlação Cofenética = 0,899117 Valor Cofenético 8,587,576,565,554,543,532,521,51 d is tâ n c ia e u c lid ia n a s im p le s 10,5 10 9,5 9 8,5 8 7,5 7 6,5 6 5,5 5 4,5 4 3,5 3 2,5 2 1,5 1 0,5 0,781 8,406 Pág. 1 de 1 Slide 1: Análise de Agrupamentos Slide 2: Análises de Agrupamento Slide 3 Slide 4 Slide 5: Análises de Agrupamento Slide 6: Grupo ou Cluster Slide 7: Grupo ou Cluster Slide 8: Algoritmos de Agrupamento Slide 9: O que são algoritmos? Slide 10 Slide 11: Agrupamentos Hierárquicos Aglomerativos Slide 12: Dendrogramas Slide 13: Dendrograma Slide 14: Dendrograma Slide 15: Dendrograma Slide 16: Como medir distâncias entre grupos? Slide 17: Como medir a distância até um grupo? Ligação simples ou vizinho mais próximo Slide 18: Ligação Simples Slide 19 Slide 20: Ligação completa (vizinho mais distante) Slide 21: Ligação Completa Slide 22 Slide 23: Agrupamento Slide 24: Ligação simples Slide 25: Ligação simples 2 Slide 26: Ligação simples 3 Slide 27: Ligação simples 4 Slide 28: Ligação simples 5 Slide 29: Ligação simples 6 Slide 30: Ligação simples 7 Slide 31: Ligação simples 8 Slide 32 Slide 33 Slide 34 Slide 35: Média de Grupo (UPGMA) Slide 36 Slide 37 Slide 38 Slide 39: Centróide Slide 40: Centróide Slide 41: Centróide – inversões 1 Slide 42: Centróide – inversões 2 Slide 43: Métodos Ponderados - WPGMA Slide 44: Métodos Ponderados - WPGMC Slide 45: Centróide – inversões 2 Slide 46: Método de Ward Soma de quadrados progressiva (Ward 1963, Orlóci 1967) Slide 47 Slide 48 Slide 49: Algoritmo geral para agrupamento aglomerativo Slide 50: Algoritmo geral Slide 51: Método flexível Slide 52 Slide 53 Slide 54: Correlação Cofenética 1 Slide 55: Correlação Cofenética 2 Slide 56: Correlação Cofenética 3
