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.
Número de Grupos
Uma das maiores dificuldades da Análise de Agrupamentos é
a determinação do número de grupos.
Outra questão importante é a estabilidade dos objetos em
seus grupos.
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.
1. Procedimento para a determinação do número de grupos através do
DENDOGRAMA - técnicas hierárquicas
A estratégia é “cortar” o dendograma em alguns pontos observando
o número de grupos e o tamanho do intervalo do coeficiente de
similaridade/dissimilaridade. Deve-se escolher o intervalo de maior
tamanho, entre os diversos cortes (Romesburg, 1984).
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.
20
18
distância Euclideana
16
14
12
10
8
6
4
2
OBJ 9
nº de
OBJ 8
OBJ 7
OBJ 6
OBJ 5
OBJ 4
OBJ 3
OBJ 2
OBJ 1
objetos do(s) grupo(s)
Intervalo
tamanho int.
9
[ 1,2,3,4,5,6,7,8 e 9]
0.0  d ij  4.0
4.0
3
[ (1,2,3,4),(5,6,7,8) e 9]
6.5  d ij  110
.
4.5
2
[ (1,2,3,4) e (5,6,7,8,9)]
11.0  d ij  16.5
5.5
5
[ (1,2),(3,4),(5,6,7),8 e 9]
55
.  d ij  6.5
1.0
grupos
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.
2. Procedimento para a determinação do número de grupos através de
PARADA - técnicas hierárquicas
O procedimento chamado de “parada” (apresentado nos softwares
pelo indicativo de Amalgamation), consiste em examinar alguma
medida de similaridade ou distância entre os grupos a cada passo
sucessivo. A solução final é dada quando a medida escolhida
apresenta um salto abrupto entre algum passo.
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.
Animal
Medida 1
Medida 2
Medida 3
1
72
46
81
2
83
46
92
3
79
55
88
4
82
45
91
5
71
45
80
6
78
38
87
7
82
47
91
8
80
52
89
9
73
47
82
10
77
38
86
11
83
47
92
12
74
43
83
13
72
47
81
14
81
45
90
15
77
37
86
16
77
53
86
17
84
44
93
18
78
52
87
19
80
55
89
20
80
40
89
Number of
Similarity
Distance
Step
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Clusters
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
level
94,5926
94,5926
94,5926
92,3528
92,3528
91,4935
91,4935
91,4935
90,6341
86,3958
86,219
82,9218
81,3466
79,4686
75,9359
75,7274
level
1,0000
1,0000
1,0000
1,4142
1,4142
1,5731
1,5731
1,5731
1,7321
2,5159
2,5485
3,1583
3,4496
3,7969
4,4502
4,4888
17
18
19
3
2
1
48,241
40,3666
30,0285
9,5719
11,0282
12,9400
O cálculo para se obter, por exemplo, a coluna nível de distância,
nada mais é do o menor resultado da distância euclidiana para
compor cada uma das matrizes de distância do método escolhido,
neste caso a Distância Média
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.
Agglomeration Schedule
Cluster Combined
Stage
Resultado pata
SPSS v 19.0
Cluster 1
Stage Cluster First Appears
Cluster 2
Coefficients
Cluster 1
Next Stage
Cluster 2
1
10
15
1,000
0
0
7
2
1
13
1,000
0
0
8
3
2
11
1,000
0
0
9
4
3
19
2,000
0
0
10
5
4
14
2,000
0
0
12
6
16
18
3,000
0
0
14
7
6
10
3,000
0
1
16
8
1
9
3,000
2
0
11
9
2
7
3,000
3
0
12
10
3
8
11,000
4
0
14
11
1
5
12,000
8
0
15
12
2
4
12,000
9
5
13
13
2
17
19,000
12
0
17
14
3
16
22,000
10
6
18
15
1
12
24,000
11
0
18
16
6
20
27,000
7
0
17
17
2
6
172,000
13
16
19
18
1
3
262,000
15
14
19
19
1
2
342,000
18
17
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.
3. Procedimento para a determinação do número de grupos através da
Aplicação de vários Algoritmos - técnicas hierárquicas
A aplicação de vários métodos Hierárquicos Aglomerativos como
Vizinho mais Distante, Distância Média e Método de Ward, por
exemplo, pode gerar uma resolução satisfatória, baseada na estrutura
resultante da maior parte dos métodos (Bussab, et al., 1990).
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.
4. Procedimento para a determinação do número de grupos através da
Aplicação Índices Internos - técnicas hierárquicas
O índice de Calinski-Harabasz (CH) compara a homogeneidade interna
e o isolamento externo dos grupos. Também conhecido por Pseudo F,
faz a comparação entre a soma da distância quadrática dentro dos
grupos e compara com a soma da distância quadrática entre os grupos.
O índice de Calinski e Harabasz (CH) deve ser calculado para
diferentes números de grupos (k). O número de grupos mais indicado
será aquele que originar o maior valor de CH.
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.
Calinski-Harabasz (CH)
CH 
B  (n  K )
W  ( K  1)
Onde n é o número de objetos
e K é o número de grupos.
xi
k
B   k ( xi  x )
2
i 1
k
x
é o centro do grupo i (média dos
pontos do grupo)
é o centro de toda a base de dados
(média das médias)
ni
W   ( xij  xi ) 2
i 1 j 1
xij
é o j-ésimo ponto do grupo i.
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.
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 idéia básica é a mesma na ANOVA
Comparar a variabilidade
Entre os grupos com a variabilidade
Dentro dos grupos
Se a variabilidade for grande Entre Grupos e
pequena Dentro dos grupos, uma boa
estrutura foi obtida.
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.
O índice de Silhueta – S(i) define a qualidade dos agrupamentos
com base na proximidade entre os objetos de um determinado grupo
e na proximidade desses objetos ao grupo mais próximo
O resultado de s(i) varia entre -1 e 1. Quanto mais próximo de 1
melhor a alocação do objeto no grupo, porém quanto mais
próximo de -1, pior a alocação, dado que o objeto está, em
média, mais próximo dos elementos do grupo vizinho.
Para a obtenção do índice de Silhueta devem-se utilizar os grupos
obtidos mediante a aplicação de algum dos algoritmos de
agrupamento e da matriz de distância entre os objetos.
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.
O processo para obtenção de s(i) pode ser descrito da seguinte forma:
Considere os agrupamentos específicos A, B e C. Para qualquer objeto
i alocado ao grupo denotado por A (figura 1), teremos
Figura 1.
a(i) = média da distância de i para todos os demais objetos de A.
d(i,C) = Média da distância de i para todos os objetos de C.
Após computar todos os d(i,C) para AC selecionaremos o menor valor
e denotamos por: b(i) = mínimo d(i,C).
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.
Figura 1.
O grupo B, como na figura 1, para o qual
esse mínimo é atingido, isto é, d(i,B) =
b(i), denominamos de vizinho do objeto i.
Desta forma, pode-se observar que o
grupo B seria a melhor escolha, caso o
objeto i não fosse alocado no grupo A.
Desta forma teremos o grupo vizinho de cada um dos objetos, e o procedimento é
válido quando temos mais que um agrupamento.
O valor de S(i) é obtido
da seguinte forma:
 ai
1  b se ai  bi
i


s (i )  0
se ai  bi
b
 i  1 se ai  bi

 ai
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.
O valor do índice de Silhueta pode ser expresso
em termos de fórmula por:
s(i ) 
b(i )  a(i )
maxb(i ) , a(i ) 
O resultado de s(i) varia entre -1 e 1. Quanto mais próximo de 1
melhor a alocação do objeto no grupo, porém quanto mais
próximo de -1, pior a alocação, dado que o objeto está, em
média, mais próximo dos elementos do grupo vizinho.
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.
Para cada grupo pode-se obter o valor do índice de Silhueta
mediante o cálculo da média dos valores de silhueta para cada
objeto pertencente ao grupo.
sK
s


(i )
k
Onde k é o grupo especificado.
O valor de Sk é analisado da mesma maneira que cada um dos si.
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.
Amostras Grandes
Procedimento: Seleciona-se uma grande amostra, a maior possível, e
aplica-se a esta amostra a Análise de Agrupamentos, observando a
estrutura “natural” obtida. Os demais objetos serão alocados nos
grupos formados, através de uma outra técnica, como por exemplo a
Análise de Classificação. O problema deste procedimento surge
quando a amostra selecionada não representa bem a estrutura dos
dados, e assim, os demais objetos não se enquadram
convenientemente nos grupos (Romesburg, 1984).
Dr. Fernando Frei