1.

Construção da Matriz de Similaridades com Dados Binários

Num estudo com cinco alunos da disciplina Técnicas Multivariadas, foram avaliadas
as seguintes características:
Indivíduo Altura Peso Cor Cor Uso das
(polegadas) (libras) Olhos Cabelos mãos Sexo
Fernanda 68 140 verdes loiro destro fem.
Adão 73 185 castanhos castanhos canhoto masc.
Francisco 67 165 azuis loiro destro masc.
Vera 64 120 castanhos castanhos destro fem.
Cleide 76 210 castanhos castanhos canhoto fem.

Sejam seis variáveis binárias definidas por:

1 Altura  72pol. 1 cabelos loiros

X1   X4  
0 Altura  72pol. 0 cabelos não lo iros

1 peso  150 lib. 1 destro

X2   X5  
0 peso  150 lib. 0 canhoto

1 Olhos castanhos 1 Sexo feminino

X3   X6  
0 Olhos não cast anhos 0 Sexo masculino

Escores para alunos Cleide e Vera:

X1 X2 X3 X4 X5 X6
Cleide 1 1 1 0 0 1
Vera 0 0 1 0 1 1

Vera
1 0 totais
Cleide 1 2 2 4
0 1 1 2
totais 3 3 6
 ad 3
a) Indíce de similaridade: sVC  
p 6

Fe A Fr V C
Fe  1 
A  0 1 
Matriz de similaridades:  
Fr 4 6 2 6 1 
 
V 4 6 2 6 2 6 1 
C 1 6 5 6 1 6 3 6 1

Maior similadirade: Adão e Cleide (5/6) Menor similaridade: Fernanda e Adão (0)

Matriz de similaridades reorganizada

Fr Fe V C A
Fr 1
Fe 4/6 1
V 2/6 4/6 1
C 1/6 1/6 3/6 1
A 2/6 0 2/6 5/6 1

2 Grupos: ( I ) alunos Francisco, Fernanda e Vera

( II ) alunos Cleide e Adão.
b) Indíce de similaridade com peso duplo para os pares 1-1 e 0-0:
2( a  d ) 2 3 2
sVC   
2( a  d )  b  c 2  3  3 3

Fe A Fr V C
Fe  1 
A  0 1 
Matriz de similaridades:  
Fr  4 5 1 2 1 
 
V 4 5 1 2 1 2 1 
C 2 7 10 11 2 7 2 3 1

Maior similadirade: Adão e Cleide (10/11) Menor similaridade: Fernanda e Adão (0)

Matriz de similaridades reorganizada

Fr Fe V C A
Fr 1
Fe 4/5 1
V 1/2 4/5 1
C 2/7 2/7 2/3 1
A 1/2 0 1/2 10/1 1
1
2 Grupos (mais evidentes): ( I ) alunos Francisco, Fernanda e Vera
( II ) alunos Cleide e Adão.
c) Indíce de similaridade com peso duplo para os pares 1-0 e 0-1:
ad 3 1
sVC   
a  d  2(b  c ) 3  2  3 3

Fe A Fr V C
Fe  1 
A  0 1 
Matriz de similaridades:  
Fr  1 2 1 5 1 
 
V 1 2 1 5 1 5 1 
C 1 11 5 7 1 11 1 3 1

Maior similadirade: Adão e Cleide (5/7) Menor similaridade: Fernanda e Adão (0)

Matriz de similaridades reorganizada

Fr Fe V C A
Fr 1
Fe 1/2 1
V 1/5 1/2 1
C 1/1 1/1 1/3 1
A 1
1/5 1
0 1/5 5/7 1

4 Grupos (bem evidentes): ( I ) Fernanda

( II ) Vera
( III ) Francisco
( IV ) Cleide e Adão.
2. Medidas de distância e de similaridades

A) Medidas de similaridades

Coeficiente Descrição

ad
Pesos iguais para combinações 1-1 e 0-0.
p

2( a  d )
Pesos duplos para combinações 1-1 e 0-0.
2( a  d )  b  c

ad
Pesos duplos para combinações 0-1 e 1-0.
a  d  2(b  c)

a
Considera apenas combinações 1-1.
p

a Desconsidera as combinações 0-0.

abc (que são consideradas irrelevantes)

2a Pesos duplos para as combinações 1-1 e

2a  b  c desconsiderando as combinações 0-0

a Pesos duplos para as combinações 0-1 e 1-0,

a  2(b  c ) desconsiderando as combinações 0-0

a Razão entre as combinações 1-1 com as

combinações 0-1 e 1-0, desconsiderando as
bc
combinações 0-0
B) Medidas de dist€ncia

Coeficiente Nome
p
d 2 (v, w)   (vi  wi ) 2 Quadrado da dist€ncia Euclidiana entre
i 1 os itens v e w para dados bin•rios.
(retorna o n‚mero de combinaƒ„es 0-1 e
d 2 (v, w)  b  c 1-0)

bc Dist€ncia bin•ria de Sokal.

d 2 (v, w) 
p (dist€ncia Euclidiana quadr•tica m…dia).

p
 (vi  wi ) 2 
i 1 Dist€ncia Euclidiana entre os itens v e w.
(dados quantitativos)
 ( v  w)t ( v  w)
p
 (vi  wi ) 2 Dist€ncia Euclidiana e ao quadrado.
i 1

Dist€ncia Estat†stica ou
t 1
( v  w) S (v  w)
dist€ncia de Mahalanobis.
1/ m Dist€ncia de Minkowski (ou power):
 p 
  | vi  wi |m   para m = 1 … a dist€ncia “city block”;
 
 i 1   para m = 2 … a dist€ncia Euclidiana.

max | vi  wi |, i  1,, p. Dist€ncia de Chebychev.

i
3. Métodos Hierárquicos

Formado por técnicas que procedem por uma série de uniões (ou
divisões) sucessivas sendo que, em cada etapa, os objetos são agrupados
conforme suas similaridades. Podem ser aglomerativos ou divisivos:
 Aglomerativos = agrupamento por uniões;
 Divisivos = agrupamento por divisões

3.1. Métodos Hierárquicos Aglomerativos

I) Linkagem Simples: mínima distância ou vizinho mais próximo.

A distância entre dois grupos G1 e G2 é dada pela menor distância

entre seus objetos.

Agrupar n objetos, itens ou indivíduos.

a) O processo inicia com n clusters, ou grupos, cada um com um objeto,

e a respectiva matriz de distâncias ou simiatridades;
b) Identifica-se na matriz o par u e v com a menor distância (maior
similaridade, sendo a distância entre u e v dada por duv ;
c) Os objetos u e v são agrupados em um cluster que passa a ser
denominado uv e a matriz de distâncias é atualizada:
i) elinando-se a linha e a coluna referenteas aos objetos u e v ;
ii) calculando-se as distâncias entre os demais objetos e o grupo uv, tal
que

d (uv) w  min(duw , d vw ) ;
d) Repetir os itens (b) a (c) até que todos os objetos formem um único
cluster.

Exemplo 1: Considere a matriz de distâncias entre cinco objetos

1 2 3 4 5
1 0 
2 9 0 
a)  
3 3 7 0 
 
4 6 5 9 0 
5 11 10 ( 2) 8 0

Menor distância: d35  2 , novo cluster: (35)

b) Novas distâncias:

d (35)1  min(d31 , d 51 )  min(3,11)  3

d (35) 2  min(d32 , d 52 )  min(7,10)  7
d (35) 4  min(d 34 , d54 )  min(9,8)  8

(35) 1 2 4
(35) 0 
a') nova matriz: (3) 0 
1  
2 7 9 0 
 
4  8 6 5 0

Menor distância: d (35)1  3 , novo cluster: (351)

b') Novas distâncias:

 
d (351) 2  min d (35) 2 , d12  min(7,9)  7
 
d (351) 4  min d (35) 4 , d14  min(8,6)  6
 (351) 2 4
(351) 0 
a'') nova matriz: 7 0 
2  
4 6 (5) 0

Menor distância: d 24  5 , novo cluster: (24)

b'') Novas distâncias:

 
d ( 24)(351)  min d 2(351) , d 4(351)  min(7,6)  6

(351) ( 24)
a''') situação final: (351) 0 
6 0
( 24)  

Assim, os grupos (351) e (24), com distância mínima entre seus

objetos de 6 unidades, são agrupados num único cluster (12345).
II) Linkagem Completa: máxima distância ou vizinho mais distante.

A distância entre dois grupos G1 e G2 é dada pela maior distância

entre seus objetos.

O método da linkagem completa é semelhante ao anterior (linkagem

simples) com a diferença de que, neste caso, as distâncias são atualizadas
conforme a seguinte relação:

d (uv ) w  max(d uw , d vw ) .

Exemplo 2: Considere a mesma matriz de distâncias do caso anterior

1 2 3 4 5
1 0 
2 9 0 
a)  
3 3 7 0 
 
4  6 5 9 0 
5 11 10 ( 2) 8 0

Menor distância: d35  2 , novo cluster: (35)

b) Novas distâncias:

d (35)1  max(d31 , d 51 )  max(3,11)  11

d (35) 2  max(d 32 , d 52 )  max(7,10)  10
d (35) 4  max(d 34 , d54 )  max(9,8)  9
 (35) 1 2 4
(35) 0 
a') nova matriz: 11 0 
1  
2 10 9 0 
 
4  9 6 (5) 0

Menor distância: d 24  5 , novo cluster: (24)

b') Novas distâncias:

 
d ( 24)(35)  max d 2(35) , d 4 (35)  max(10,9)  10
d ( 24)1  maxd 21 , d 41   max(9,6)  9

(35) ( 24) 1
(35) 0 
a'') nova matriz: 10 0 
( 24)  
1 11 (9) 0

Menor distância: d ( 24)  9 , novo cluster: (241)

b'') Novas distâncias:

 
d ( 241)(35)  max d( 24)(35) , d1(35)  max(10,11)  11

(35) ( 241)
a''') situação final: (35) 0 
11 0
( 241)  

Assim, os grupos (35) e (241), com distância máxima entre seus

menbros de 11 unidades, são agrupados num único cluster (12345).

Observe que na linkagem completa, o objeto 1 foi agrupado ao

cluster (24).
III) Linkagem Média: distância média.

A distância entre dois grupos G1 e G2 é dada pela média das

distâncias entre seus objetos.

O método da linkagem média é semelhante aos anteriores com a

diferença de que, neste caso, as distâncias são atualizadas conforme a
seguinte relação:

 dij
i j
d (uv) w  ,
n(uv) nw

em que: dij = distância entre o objeto i, do cluster (uv) e o objeto j, do

cluster w ;
n(uv) = número de objetos do cluster (uv);

nw = número de objetos do cluster w.

Exemplo 3: Considere a mesma matriz de distâncias dos casos anteriores

1 2 3 4 5
1 0 
2 9 0 
a)  
3 3 7 0 
 
4  6 5 9 0 
5 11 10 ( 2) 8 0

Menor distância: d35  2 , novo cluster: (35)

b) Novas distâncias:

d31  d51 3  11
d (35)1   7
2 2
 d32  d52 7  10
d (35) 2    8.5
2 2
d34  d54 9  8
d (35) 4    8.5
2 2

(35) 1 2 4
(35) 0 
a') nova matriz: 7 0 
1  
2 8.5 9 0 
 
4 8.5 6 (5) 0

Menor distância: d 24  5 , novo cluster: (24)

b') Novas distâncias:

( d32  d34 )  (d 52  d 54 ) (7  9)  (10  8) 34

d (35)( 24)     8.5
2 2 2 2 4
d 21  d 41 96
d ( 24)1    7.5
2 2

(35) ( 24) 1
(35) 0 
a'') nova matriz: 8.5 0 
( 24)  
1 (7) 7.5 0

Menor distância: d (35)1  7 , novo cluster: (351)

b'') Novas distâncias:

(d 32  d 34 )  ( d52  d54 )  ( d12  d14 )

d (351)( 24) 
3 2
(7  9)  (10  8)  (9  6) 49
d (351)(24)    8.167
3 2 6
 (351) ( 24)
a''') situação final: (351)  0 
8.167 0
( 24)  

Assim, os grupos (35) e (241), com distância média entre seus

menbros de 8.167 unidades, são agrupados num único cluster (12345).
Exemplo 3 (agrupamento de variáveis): Dados da taxa de retorno semanal
ma bolsa de valores das empresas Allied Chemical (AC), DuPont (DP),
Union Carbide (UC), Exxon (E), Texaco (T).
menor distância  maior correlação
DP UC AC E T
DP  1 
 
Matriz de correlações: UC 0.58 1

AC 0.51 (0.60) 1 
 
E 0.39 0.39 0.44 1 
T 0.46 0.32 0.43 0.52 1

a) Linkagem Simples:
DP_UC AC E T
DP_UC 1
AC (0.58) 1
E 0.44 0.39 1
T 0.43 0.46 0.52 1

DP_UC_AC E T
DP_UC_AC 1
E 0.44 1
T 0.46 (0.52) 1

DP_UC_AC E_T
DP_UC_AC 1
E_T 0.46 1
b) Linkagem Completa:
DP_UC AC E T
DP_UC 0
AC 0.51 0
E 0.39 0.39 0
(0.52
T 0.32 0.46 0
)

DP_UC E_T AC
DP_UC 0
E_T 0.32 0
AC (0.51) 0.39 0

DP_UC_AC E_T
DP_UC_AC 0
E_T 0.32 0
3.1.1. Outros Métodos Hierárquicos:

I) Método Hirárquico do Centróide: a distância entre dois clusters á

dada pela distância entre os seus vetores de médias, ou centróides.

Sejam, por exemplos, dois grupos C1 e C2 formados pelos itens (X1,

X3, X7) e (X2, X6), respectivamente, então
X1  X3  X 7
X1  e X2  X 2  X6 ,
3 2

e, a distância Euclidiana entre C1 e C2 será dada por

d (C1 , C 2 )  ( X1  X 2 ) t ( X1  X 2 ) .

Podemos, ainda considerar o seu qyadrado, ou seja,

d 2 (C1 , C 2 )  ( X1  X 2 ) t (X1  X 2 )

Nesse caso, o centróide de um novo cluster (uv)w será atualizado

segunda a relação:

xuv  x w
x (uv ) w 
nuv  nw

Nota: o método do centróide pode gerar distorção nos resultados quando

o número de elementos dos grupos for muito discrepantes, situação na
qual o grupo maior domina a nova média.
Exemplo 4: Considere os dados na tabela

Item Renda Idade

A 9.6 28
B 8.4 31
C 2.4 42
D 18.2 38
E 3.9 25
F 6.4 41
x 8.15 34.2
s 5.61 7.14

Matriz de distâncias:
A B C D E F
A 0
B 3.23 0
C 15.74 12.53 0
D 13.19 12.04 16.29 0
E 6.44 7.50 17.06 19.33 0
F 13.39 10.19 4.12 12.18 16.19 0

 9.0 
Menor distância: d ( AB )  3.23 , X AB   
29.5

Novas distâncias:
i) d ( AB)C  (9.0  2.4) 2  (29.5  42) 2  199.81  14.14
ii) d ( AB) D  (9.0  18.2) 2  (29.5  38) 2  156.89  12.53
iii) d ( AB) E  (9.0  3.9) 2  (29.5  25) 2  46.26  6.80
iv) d ( AB) F  (9.0  6.4) 2  (29.5  41) 2  139.01  11.79
Matriz atualizada:
(AB) C D E F
(AB 0
)
C 14.14 0
D 12.53 16.29 0
E 6.80 17.06 19.33 0
F 11.79 4.12 12.18 16.19 0

 4.4 
Menor distância: d (CF )  4.12 , XCF   
41.5

Novas distâncias:
i) d (CF )( AB)  (4.4  9.0) 2  (41.5  29.5) 2  165.16  12.85
ii) d (CF ) D  (4.4  18.2) 2  (41.5  38) 2  202.69  14.24
iii) d (CF ) E  (4.4  3.9) 2  (41.5  25) 2  272.5  16.51

Matriz atualizada:
(AB) (CF) D E
(AB) 0
(CF) 12.85 0
D 12.53 14.24 0
E 6.80 16.51 19.33 0

7.3
Menor distância: d ( AB ) E  6.80 , X ABE   

28.0

Novas distâncias:
i) d ( ABE )(CF )  (7.3  4.4) 2  (28.0  41.5) 2  190.66  13.81
ii) d ( ABE ) D  (7.3  18.2) 2  (28.0  38.0) 2  218.81  14.79
Matriz atualizada:
(ABE) (CF) D
(ABE) 0
(CF) 13.81 0
D 14.79 14.24 0

6.14
Menor distância: d ( ABE )(CF )  13.81 , X ABCEF   

33.4

i) d ( ABCEF ) D  (6.14  18.2) 2  (33.4  38.0) 2  166.60  12.91 < 13.81 !

II) Método Hirárquico da Mediana: semelhante ao caso anterior, porém,
a atualização dos centróides é feita pela média aritmética sem a
ponderação pelo tamanho dos grupos, ou seja, um novo cluster (uv)w
será atualizado por

x uv  x w
x (uv) w 
2

III) Método Hirárquico de Ward: método baseado na análise de

variância, utiliza as somas de quadrados (SQ) dentre e entre grupos.
Os grupos são formados tal que a SQDentro seja minimizada.

IV) Método Hirárquico Flexível Beta: utiliza uma ponderação na

atualização das distâncias com pesos que variam de acordo com o
método (Ferreira, DF, pag 382).

d (uv ) w   u d uw   v d vw   d uv   d uw  d vw ,

com as restrições:  u   v    1 ,  u   v ,   0 ,   1.

Notas:
i) segundo as restrições acima, o único parâmetro a ser especificado
seria , pois teríamos  u  (1  ) / 2 ;
ii) os demais métodos hierárquicos podem ser especificados pelo método
flexível beta ecolhendo-se valores adequados para os parâmetros  u ,
 v ,  e  (ver tabela).
 Método u v  
Linkagem 1 1 1
0 
simples 2 2 2
Linkagem 1 1 1
0
completa 2 2 2
nu nv
Linkagem média 0 0
nu  nv nu  nv
nu nv  nu nv
Centróide 0
nu  nv nu  nv (nu  nv ) 2
nu  nw nv  nw  nw
Ward 0
nu  nv  nw nu  nv  nw nu  nv  nw
(1  ) (1  )
Flexível beta <1 0
2 2

3.1.2. Implementação nos Softwares

Na tabela abaixo, temos os diferentes métodos implementados nos

softwares SAS, Statistica e Minitab.

Método SAS Statistica Minitab

Linkagem Simples * * *
Linkagem Completa * * *
Linkagem Média * * *
Média ponderada *
Mediana * * *
Centróide * * *
Ward * * *
McQuitty * *
Flexível Beta *
Density *
Density 2-estágios *
EML *
3.2. Propriedades dos métodos hierárquicos

I) Monotonicidade: segundo a propriedade de monotonicidade, dois

grupos serão sempre aglomerados numa junção que é maior do que a
anterior.
Os métodos que atendem a essa propriedade são classificados como
monotônicos.

i) Os métodos de linkagem simples, linkagem completa, linkagem média

e de Ward são todos monotônicos;
ii) O método flexível beta requer que os pesos atendam à condição
 u   v    1 para que seja monotônico;
iii) Os métodos do centróide e da mediana não são monotônicos.

O Exemplo 4, com o agrupamento das variáeis referentes às taxas de

retorno das Cias AC, DP, UC, E e T, apresenta uma situação na qual a
monotonicidade não foi atendida.

II) Alteração das características do espaço das distâncias: segundo essa

propriedade o método de agrupamento pode causar uma contração ou
uma dilatação no espaço das distâncias.
i) Nos métodos onde ocorre a contração, os grupos tendem a se juntar
com objetos simples.
O método da linkagem simples é um método que causa a contração do
espaço. Exemplo, Car data ([Link] - Statistica):
ii) Nos m…todos onde ocorre a dilatadores, objetos simples tendem a
formar grupos com outros objetos simples e n‰o com grupos pr…
existentes.
O m…todo da linkagem completa … um m…todo dilatador do espaƒo.
Exemplo, Car data ([Link] - Statistica):

Obs: os demais m…todos se situam em posiƒ„es intermedi•rias a esses.

a) os m…todos do centrŠide e linkagem m…dia s‰o, conservativos, n‰o
alterandom esta propriedade;
b) Ferreira, DF, classifica o m…todo de Ward como um m…todo de
contraƒ‰o do espaƒo;
c) o m…todo flex†vel beta depende do balor do par€metro : se  < 0, …
de contraƒ‰o;  = 0 … conservativo e, para  > 1 … dilatador.
Ferreira, DF, indica  = −0.25 como um bom valor para a qualidade
final do agrupamento.

Na pr•tica, recomenda-se a utilizaƒ‰o de diversos m…todos,

comparando os resultados e, escolher aquele que reflete algum
agrupamento natural.
III) Sensibilidade à outliers: é uma propriedade desejada

a) Linkagem simples, linkagem média e Ward são bastante sensíveis;

b) Linkagem completa é sensível;

c) Método do Centróide é robusto à presença de outliers.

Nota: Estudos indicam que, de maneira geral, os métodos da linkagem

média e de Ward apresentam os melhores resultados, porém, os
resultados dependem muito do comportamento dos dados.
Como determinar o número de grupos

I) Altura entre as junções dos grupos/objetos: a partir do dendrograma,

fazer um corte na junção onde se tem um salto ''significativo'' (maior
salto).
Esse procedimento pode ser problemático, pois depende da qualidade
do agrupamento.

Daniel F. Ferreira introduz o procedimento definido por Mozena

(1977), o qual escolhe o maior salto no dendrograma como ponto de
corte.
Desta forma, o número de linhas verticais intercepadas definirá o
número de grupos.

Exemplo 5: Considerando o dendrograma do agrupamento dos veículos

(car data), pela linkagem completa, observamos que o ''maior salto'' se
dá entre o nível 4.19 e 2.83, sendo igual a 4.19  2.83  1.36 ( Figura)
 O software STATISTICA fornece um gráfico onde as distâncias são
apresentadas num gráfico em função do passo do algoritmo, no qual
pode-se observar a junção com o maior salto.

Para formalizar a idéia, Mojena (1977) indica a escolha do número

de grupos dado pela junção na qual

h j  h   sh ,

em que: h j é a altura da junção correspondente a n  j  1 grupos,

j  1, 2,, n , h e sh são a média e o desvio padrão das alturas e  é
uma constante.

Mojena (1977) sugere que 2 .75    3.50 e Milligan & Cooper

(1985) sugerem   1.25 .
Exemplo 6: Considerando ainda, o exemplo agrupamento dos veículos
Junção Grupos hj
1 15 0.00
2 14 0.46
3 13 0.62
4 12 0.67
5 11 0.98
6 10 1.14
7 9 1.20
8 8 1.28
9 7 1.83
10 6 2.29
11 5 2.48
12 4 2.80
13 3 2.83
14 2 4.19
15 1 4.42
soma 27.19

27.19 e
h  1.813 sh  1.3305
15
Considerando   1 .25 , temos: h   sh  1.813  1.25 1.3305  3.48.

Logo, o corte deve ser realizado na primeira junção cuja altura h

ultrapassar o valor 3.48, ou seja, entre a junção 13 e 14. Desta forma,
teremos um número de grupos igual a 3 (ver Figura).
II) Somas de quadrados e o coeficiente R2:

Devem ser calculados a cada passo do algoritmo, sendo definidos

como:

Soma de quadrados total:

g * ni
SQT    (xij  x) t (xij  x) ;
i 1 j 1

Soma de quadrados residual (dentro):

g * ni
SQRes    (xij  xi ) t (xij  xi ) ;
i 1 j 1

Soma de quadrado entre grupos

g*
SQB   ni (xi  x)t (xi  x) ,
i 1

em que g* é o número de grupos em cada passo do algoritmo.

O coeficiente R2 é, então, calculado por:

SQB
R2 
SQT

Quanto mais homogêneos foram os grupos, maior a SQB e nomor a

SQRes e, consequentemente, maior será o R2.
Desta forma, devemos procurar um passo do algoritmo com um
grande (ou o maior) salto de R2 em relação aos demais.

Obs: a análise pode ser feita por meio de um gráfico passo  R2.
III) Pseudo-F:

Estatística introduzida por Calinski & Harabasz (1974), deve ser

calculada passo-a-passo.

SQB /( g * 1) n g*  R2 
F    
SQT /(n  g*) g * 1 1 R2 
 

Se F é monotonicamente crescente com g*, então, os dados sugerem

que não existe uma partição natural;
Se F apresentar um valor máximo, então, o número de clusters e a
partição correspondente no respectivo passo indicam a parti€•o ideal.

Pode-se mostrar que, se os dados forem normais p-variados, então:

F ~ Fp ( g *1), p ( n  g *) .

A idéia do pseudo-F é a de que testes de igualdade entre os vetores

de médias dos grupos formados estariam sendo realizados em cada passo
do processo. Assim, busca-se o passo com o maior valor do pseudo-F,
ou seja, aquele que estaria relacionado com a menor probabilidade de
significância do teste, “rejeitando” a igualdade entre os vetores de
médias. Nessa situação, os dois conglomerados não deveriam ser unidos,
indicando a interrupção do processo.
IV) Estatística CCC - Cubic Clustering Criterium:

Estatística propsta por Sarle (1983) obtrida comparando-se o valor

observado do coeficiente R 2 com o RE2 , coeficiente esperado sob a
suposição de que os grupos são gerados de acordo com uma distribuição
uniforme p-dimensional.

CCC > 0  R 2  RE2 , indicando uma estrutura de grupos

diferentes da partição uniforme

O número de grupos finais estaria relacionado com CCC > 3.

Obs: a estatística CCC está implementada no SAS.

V) Pseudo-T 2:

De interpretação semelhante ao pseudo-F, o número de grupos

corresponde à junção na qual o pseudo-T 2 alcança o seu valor máximo,
ou àquele imediatemente anterior.
Sob as suposições de normalidade, na junção dos clusters u e v, o
pseudo-T 2 tem distribuição F com p e (nu  nv  2) graus de liberdade,
podendo ser interpretado como testes de hipóteses entre vetores de
médias.
Desta forma, busca-se o maior valor do pseudo-T 2 e, com a
igualdade entre os vetores de médias sendo rejeitada, os dois clusters não
devem ser unidos.
VI) Correlação semiparcial:

Considere que num determinado passo ocorra a junção dos clusters

Cu e Cv, então, a correlação semiparcial da partição nesse passo é dada
por:

2  n n  ( xu   x v ) t ( xu   xv )
SPR   u v 
 nu  nv  SQT

Obs: a SPR2 é uma função não decrescente.

A SPR2 é calculada em cada passo do algoritmo sendo que, deve-se

buscar o ponto em que ocorre um salto significativo (maior do que os
restantes). Esse ponto indica o número de grupos a ser considerado. A
idéia é semelhante ao indicado no item (I), no qual busca-se o passo com
a maior altura entre as junções.

Nota: os pontos de corte obtido pelas medidas pseudo-F, pseudo-T2 e

SPR2 podem ser encontrados por meio de um gráfico no qual plotamos oi
valor da medida versus o passo do algoritmo. Daí, procuramos o pontto
de máximo ou o maior salto, conforme o caso.
Exemplo 7: Dados das características de 15 marcas de carros (Statistica,
[Link]).
Variáveis observadas:
Preco: preço aproximado;
Aceler: tempo de acelaração (s) de 0 a 60mph;
Freio: distância de frenagem a uma velocidade de 80mph;
Manuseio: índice de capacidade de aderência na estrada;
Autonom: autonomia em milhas por galão.

Método hierárquico da linkagem completa

Nível de
Grupos Junção SP R2 R2 CCC PS-F PS-T2
junção
1 14 Chrysler Dodge 0.46 0.0026 0.997 . 29.1 .
2 13 Audi Mercedes 0.62 0.0049 0.992 . 22.0 .
3 12 Honda Pontiac 0.67 0.0056 0.987 . 20.5 .
4 11 G1 G3 0.98 0.0158 0.971 . 13.4 3.8
5 10 Mitsub. Nissan 1.14 0.0163 0.955 . 11.7 .
6 9 G2 BMW 1.20 0.0186 0.936 . 11.0 3.8
7 8 Acura Olds 1.28 0.0208 0.915 . 10.8 .
8 7 G4 G5 1.83 0.0444 0.871 . 9.0 4.4
9 6 G6 Mazda 2.29 0.0687 0.802 . 7.3 5.8
10 5 G7 G8 2.48 0.1213 0.681 . 5.3 6.9
11 4 Corvette Ford 2.80 0.0983 0.583 . 5.1 .
12 3 G9 Buick 2.83 0.1074 0.475 -2.7 5.4 3.5
13 2 G10 G12 4.19 0.2242 0.251 -2.2 4.4 5.8
14 1 G11 G13 4.43 0.2510 0 0 . 4.4
Medidas para escolha do número de grupos
Exemplo 8: Indicadores de desenvolvimento de 21 paises (ONU, 2002),
obtidos de Sueli A. Mingotti, (2005).
Variáveis observadas:
exp_vida: expectativa de vida;
educ: indicador de educação;
pib: pib ;
estab: indicador de estabilidade política.

Método hierárquico de Ward

Nível de
Grupos Junção SP R2 R2 CCC PS-F PS-T2
junção
1 20 Autrália Canadá 0.001 0 1.000 . 4520.0 .
2 19 R_Unido França 0.004 0.0001 1.000 . 1193.0 .
3 18 EUA Japão 0.008 0.0002 1.000 . 705.0 .
4 17 G1 G3 0.009 0.0002 1.000 . 576.0 2.2
5 16 Brasil China 0.022 0.0004 0.999 . 388.0 .
6 15 G2 Uruguai 0.047 0.0009 0.998 . 241.0 11.3
7 14 Senegal Etiópia 0.060 0.0012 0.997 . 183.0 .
8 13 Argentina G5 0.066 0.0013 0.996 . 158.0 3.0
9 12 G4 Cingapura 0.076 0.0015 0.994 . 143.0 12.6
10 11 Cuba Egito 0.122 0.0024 0.992 . 123.0 .
11 10 Nigéria Ser_Leoa 0.127 0.0025 0.989 . 115.0 .
12 9 G6 G9 0.168 0.0033 0.986 . 107.0 6.9
13 8 Colombia Paraguai 0.245 0.0047 0.981 . 98.4 .
14 7 G8 G10 0.301 0.0058 0.976 . 93.5 4.3
15 6 G11 Angola 0.659 0.0128 0.963 . 77.8 5.2
16 5 G7 Mocambique 0.917 0.0178 0.945 . 68.8 15.3
17 4 G13 G15 1.450 0.0281 0.917 -0.12 62.5 4.2
18 3 G14 G16 3.514 0.0682 0.849 -0.65 50.5 14.2
19 2 G12 G18 12.055 0.2339 0.615 -1.80 30.3 31.8
20 1 G19 G17 31.680 0.6148 0 0 . 30.3
Medidas para escolha do número de grupos
4. Métodos não hierárquicos:

O método das k-médias (k-means) é um método aglomerativo não

hierárquico (MNH). Os métodos não hierárquicos podem, ainda, serem
baseados em estimações de densidades ou misturas de distribuições,
porém o método das k-médias é o mais popular de todos.

Os métodos não hierárquicos são caracterizados por:

 o número de grupos deve ser estabelecido (conhecido) a priori;
 utilizam diretamente a matriz de dados, não sendo necessário o
cálculo da matriz de distâncias (vantajoso quando se tem muitos
dados);
 diferentemente dos métodos hierárquicos, os objetos podem ser
realocados diversas vezes durante o processo;
 o agrupamento final é obtido ao se atingir um critério de parada que
é determinado segundo uma função objetivo (que deve ser
otimizada);
 devem ser utilizados para agrupamento de objetos (ou itens) e não de
variáveis.

Os métodos não hierárquicos podem começar com uma partição

inicial dos objetos ou com um grupos de pontos, ou sementes, que serão
os núcleos dos clusters. Essa configuração deve ser livre de viés,
portanto, é adequado que seja obtida através de escolhas aleatórias das
sementes ou partições iniciais.

4.1. Método das k-médias:

O método das k-médias pode utilizar diferentes medidas como

função objetivo, como por exemplo, a distância Euclidiana, distância
Euclidiana ao quadrado, somas de quadrados dentro e entre grupos.
 Algoritmo:

a) Dividir arbitrariamente os n objetos iniciais em g grupos e calcular os

seus centróides (vetores de médias);
Ou, determinar g sementes arbitrárias como centróides, que podem ser
escolhidas dentre os n objetos ou mesmo geradas aleatoriamente;

b) Calcular as distâncias dos n objetos com todos os centróides e:

 manter o objeto no seu grupo se a sua distância em relação ao
centróide de seu grupo for a menor ou,
 realocar o objeto para o grupo cuja distância em relação ao
centróide for a menor;

c) Recalcular os centróides para aqueles grupos que sofreram alteração;

d) Repetir os passos (b) e (c) até que não ocorram mais realocações.

Exemplo 9: Sejam as variáveis X1 e X2 medidas para os objetos A, B, C, D

e E. Dividir os objetos em 2 grupos pelo método das k-médias.

Situação inicial.
objeto grupo x1 x2
A G1 5 3
B G1 -2 2
C G2 -1 -2
D G2 -3 -2
E G2 1 1

Centróides iniciais:

Grupo 1: x1   1.5 , 2.5 

Grupo 2: x2    1.0 ,  1.0 

 Primeira atualização:
quadrado da distância ao centróide realocado
objeto x1 x2
grupo
ao grupo
A 12.5 52.0 1 1
B 12.5 10.0 1 2
C 26.5 1.0 2 2
D 40.5 5.0 2 2
E 2.5 8.0 2 1

Novos centróides:
Grupo 1: x1   3 , 2 

Grupo 2: x2    2 ,  2 / 3 
 Segunda atualização:
quadrado da distância ao centróide realocado
objeto x1 x2 grupo
ao grupo
A 5.0 62.4 1 1
E 5.0 11.8 1 1
B 32.0 2.8 2 2
C 52.0 2.8 2 2
D 25.0 7.1 2 2

Como não há mais realocações, a tabela acima representa a

composição final dos grupos, ou seja:

Grupo Componentes Centróides

A x1   3 , 2 
1
E
B
2 C x2    2 ,  2 / 3 
D
Exemplo 10: O m…todo das k-m…dias baseiado na partiƒ‰o da soma de
quadrados total de uma análise de variância, tal como a alocaƒ‰o de
Ward, (extra†do do livro de minicurso de L‚cia P. Barroso, 2003,
Lavras).

O procedimento tem como objetivo a minimizaƒ‰o da soma de

quadrados da partiƒ‰o SQDP (Soma de Quadrados Dentro dos clusters),
que … dada por

k nj
SQDv    ( xi j v  x j v ) 2 ,
j 1 i 1

em que: SQD(v) … a soma de quadrados “dentro” dos grupos para a

vari•vel v, v = 1,..., p;
x j v … a m…dia amostral da vari•vel v, no grupo j-ésimo grupo,
xi j v … a i-ésima observaƒ‰o da vari•vel v, no j-ésimo grupo.

Assim, a soma de quadrados total da partiƒ‰o SQDP … dada por:

p
SQDP   SQDv .
v 1

Dados de Indicadores de violŒncia de cinco regi„es administrativas

do Estado de S‰o Paulo considerando duas vari•veis apenas.
Tabela 1: Dados parciais de indicadores de violŒncia (SSP/SP).
Dados Brutos Dados Padronizados
Regi„es
Hom. Doloso Furto Hom. Doloso Furto
SJRPreto 10.85 1500.80 -0.6638 0.8475
RibPreto 14.13 1496.07 -0.0731 0.8128
Bauru 8.62 1448.79 -1.0654 0.4655
Campinas 23.04 1277.33 1.5315 -0.7937
Sorocaba 16.04 1204.02 0.2709 -1.3321
M…dia 14.54 1385.40 0.00 0.00
D.P. 5.55 136.16 1.00 1.00
Procedimento passo-a-passo
1) Definiƒ‰o da semente (centrŠides) da partiƒ‰o inicial.
No caso ser‰o consideradas os dois primeiros pontos, referentes •s
regi„es de SJRPreto e RibPreto.

2) Formar grupos com as regi„es com menores dist€ncias em relaƒ‰o •s

sementes (alocaƒ‰o inicial).

Dist€ncia Euclidiana em rel. a Grupo mais

Regi„es
SJRPreto RibPreto prŠximo
Bauru 0.55 1.05 SJRPreto
Campinas 2.74 2.27 RibPreto
Sorocaba 2.37 2.17 RibPreto

Grupos iniciais: Grupo 1 – Bauru, SJRPreto

Grupo 2 – Campinas, Sorocaba e RibPreto

C•lculo da SQDP (com as vari•veis padronizadas):

Grupos HDolo Furto
Regi„es ( xi j1  x j1 ) 2 ( xi j 2  x j 2 ) 2
Iniciais (v = 1) (v = 2)
1 SJRPreto -0.664 0.848 0.04032 0.03648
1 Bauru -1.065 0.466 0.04032 0.03648
m…dias x1 -0.865 0.657
SQD(v) 0.0806 0.0730
SQDP1 0.1536
2 RibPreto -0.073 0.813 0.42189 1.56360
2 Campinas 1.532 -0.794 0.91219 0.12675
2 Sorocaba 0.271 -1.332 0.09337 0.79999
m…dias x2 0.577 -0.438
SQD(v) 1.4275 2.4903
SQDP2 3.9178

SQDP = SQDP1 + SQDP2 = 4.0714

3) Reavaliar as dist€ncias das regi„es com relaƒ‰o •s m…dias dos
grupos.

Dist€ncia em rel. •s m…dias Grupo

Regi„es
Grupo 1 Grupo 2 atual mais prŠximo
SJRPreto 0.28 1.63 1 1
RibPreto* 0.81 1.14 2 1
Bauru 0.28 1.85 1 1
Campinas 2.80 1.14 2 2
Sorocaba 2.29 1.42 2 2

Grupos apŠs ajuste: Grupo 1 – Bauru, RibPreto e SJRPreto

Grupo 2 – Campinas e Sorocaba
C•lculo da SQDP:
SQD(1) SQD(2) SQDPi
Grupo 1 0.4983 0.0892 0.5875
Grupo 2 0.7946 0.1449 0.9395
SQDP = 1.5271

Ao realocar RibPreto para o grupo 1, a SQDP sofreu uma grande

diminuiƒ‰o, passando de 4.07 para 1.53, o que indica que a nova partiƒ‰o
… melhor do que a primeira.

4) O passo seguinte … procurar por nova configuraƒ‰o que leve a uma

partiƒ‰o ainda melhor.
Dist€ncia em rel. •s m…dias Grupo
Cidade
Grupo 1 Grupo2 atual mais prŠximo
SJRPreto 0.15 2.47 1 1
RibPreto 0.54 2.11 1 1
Bauru 0.52 2.49 1 1
Campinas 2.61 0.69 2 2
Sorocaba 2.22 0.69 2 2

Como n‰o h• mais modificaƒ„es, a alocaƒ‰o acima representa a

composiƒ‰o final dos grupos, com uma soma de quadrados da partiƒ‰o
igual a SQDP = 1.5271 ( seria a menor SQDP ? )
4.1.1. M…todo das k-m…dias no SAS – Procedure FASTCLUS

O m…todo das k-m…dias est• implementado no SAS pelo Procedure

FASTCLUS.
Na sequŒncia s‰o apresentadas algumas opƒ„es do FASTCLUS:
- maxcluster = n : define o n‚mero de clusters para o agrupamento;
- converge = c : define valor de referŒncia para a convergŒncia;
- distance: calcula e mostra as dist€ncias entre as m…dias dos clusters;
- least = p : 1 < p < ∞, define a m…trica
▪ se p = 1, o procedimento minimiza a diferenƒa absoluta m…dia
entre os dados e a mediana do seu grupo;
▪ se p = 2, o procedimento minimiza a raiz quadrada da diferenƒa
quadr•tica m…dia entre os dados e a m…dia do seu grupo;
▪ se p = max, o procedimento minimiza a m•xima diferenƒa
absoluta entre os dados e a m…dia do seu grupo;
▪ para 1 < p < ∞, o procedimento minimiza a p-ésima raiz da m…dia
das diferenƒas absolutas na potŒncia p.
- maxiter = n : especifica o n‚mero m•ximo de iteraƒ„es (o default varia
com o valor de p);
Valores default:
▪ se p = 1, n = 20;
▪ se 1 < p < 1.5, n = 50;
▪ se 1.5 < p < 2, n = 50;
▪ se p = 2, n = 10;
▪ se p > 2, n = 20;
▪ se p n‰o … especificado, n = 1;
- out = sas-data-name: gera arquivo com as sa†das (ver tamb…m outstat);
- replace : especifica a partiƒ‰o inicial (ver help do SAS).