Análise de agrupamento

Disciplina: Métodos Multivariados

Professor: Jackson Conceição
 Análise de agrupamentos
Cluster Analysis

Abrange uma variedade de métodos que têm por

objetivo fracionar um conjunto de objetos em um
determinado nº de subconjuntos mutuamente
exclusivos (agrupamentos ou clusters), de tal forma
que os objetos em um mesmo cluster sejam
semelhantes entre si, porém diferentes dos objetos
dos outros clusters.

Os clusters devem exibir elevada homogeneidade

interna (pequena variabilidade dentro de cada
grupo) e elevada heterogeneidade externa (grande
separação entre os grupos).
 Análise de agrupamentos
Cluster Analysis

Os clusters não são conhecidos previamente, mas

são obtidos pela análise das semelhanças ou
diferenças entre os objetos do conjunto de dados.

Os métodos de análise de agrupamentos têm por

objetivo determinar uma estrutura de grupos que se
ajuste aos dados disponíveis, i.e., classificar os
objetos de acordo com o agrupamento natural dos
dados.
 Análise de agrupamentos
Cluster Analysis

Identificação dos clusters a partir dos dados

Cada ponto representa uma

empresa Clusters

Algoritmo de
análise de
agrupamentos
 O que é possível fazer com a análise de agrupamentos ?

 Formar uma taxonomia das observações

Identificar grupos naturais no interior dos dados, i.e., uma
classificação empírica dos objetos.

 Simplificar os dados (compressão de dados)

Descrever de forma compacta um razoável volume de
dados por meio dos elementos típicos dos clusters
(médias ou medianas).

 Identificar relações entre objetos

• Revelar similaridades e diferenças entre objetos não
reveladas de outra maneira.
• Identificar observações aberrantes.
 Características da análise de agrupamentos

 É descritiva, os métodos são exploratórios e a idéia é gerar

hipóteses.

 Cria grupos indiferentemente a existência de alguma

estrutura nos dados.

 Variedade de vias e critérios para definição dos grupos o

que implica na possibilidade de obter soluções diferentes
variando-se um ou mais critérios.

 A solução da análise de agrupamentos não é generalizável

por que ela é totalmente dependente tanto das variáveis
usadas como dos critérios em que ela se baseia.
 Medidas de similaridade e de dissimilaridade

Para formar clusters é necessário ter uma medida do grau de

similaridade entre os objetos ou de diferença (dissimilaridade)
entre eles.

Vamos trabalhar com medidas de dissimilaridade (distâncias),

por exemplo, o quadrado da distância euclidiana. Distâncias
pequenas indicam objetos próximos, ou seja, semelhantes em
um conjunto de atributos.

Sejam os objetos X e Y caracterizados por p atributos

quantitativos: X = (x1,x2,...,xp) e Y = (y1,y2,...,yp).

O quadrado da distância euclidiana entre X e Y é dado por:

p

||X-Y||2 = (x1 – y1)2 + (x2 – y2)2 +...+ (xp - yp)2 = 

 xi  yi 2

i 1
 Etapas da análise de agrupamentos

1) Seleção dos objetos a serem agrupados.

2) Definição de um conjunto de variáveis que caracterizam
os indivíduos.
3) Seleção de uma medida de similaridade ou
dissimilaridade entre objetos. (em geral é utilizada a
distância euclidiana ou o seu quadrado)
4) Seleção de um algoritmo de agregação dos indivíduos.
(há uma enorme variedade de métodos com esta
finalidade)
5) Definição do nº de clusters ou tipologias.
6) Interpretação e validação dos clusters obtidos.
 Métodos de análise de agrupamentos

Métodos não hierárquicos: k-Means , Nuvens dinâmicas

Métodos hierárquicos: métodos de encadeamento (linkage

methods) e Método de Ward

Métodos não hierárquicos Métodos hierárquicos

Procuram diretamente uma Particionam um conjunto com N

partição de N objetos em um objetos seqüencialmente em
número pré-definido de k clusters 1,2,3,4 até N clusters, obtendo no
que satisfaçam duas premissas final uma estrutura em árvore,
básicas: coesão interna e semelhante as classificações
isolamento dos clusters. zoológicas (espécies, gêneros,
famílias, ordem, etc.).
O número de agrupamentos deve
ser especificado a priori
 K-Means

Divide um conjunto de n objetos em k clusters (k é dado de entrada), de tal

forma que a heterogeneidade interna dos clusters seja minimizada.

Dado um conjunto de k centróides, cada objeto xi, i=1,n, é alocado ao cluster

com o centróide cj mais próximo.
2
xi  c j é o quadrado da distância do objeto xi ao centróide do cluster j

Em cada cluster j, j=1,k, a heterogeneidade interna é avaliada pela seguinte

soma de quadrados ou WSS(j):

WSS j    x c
2
i j
xi cluster j

Acumulando ao longo dos k clusters temos a inércia intra-cluster ou WSS:

k  k 
WSS  WSS j      xi  c j 
2

j 1  xi cluster j

j 1 
 K-Means

Vantagens

 Tendem a maximizar a dispersão entre os centros de

gravidade dos clusters (clusters bem separados).

 Simplicidade de cálculo, calcula somente as distâncias

entre os objetos e os centros de gravidade dos clusters.

Desvantagens

 A solução é dependente dos conjuntos de sementes

iniciais, principalmente se a seleção das sementes é
aleatória.

 Não há garantias de um agrupamento ótimo dos objetos.

 Métodos hierárquicos

Particionam um conjunto com N objetos seqüencialmente em 1,2,3,4 até N

clusters, obtendo no final uma estrutura em árvore, semelhante as classificações
zoológicas (reino, espécies, gêneros, famílias, ordem, etc.).

Produzem uma série de partições encaixadas: o grupo formado em um determinado

passo corresponde a união de grupos formados em passos anteriores.

O resultado é apresentado dendrograma

na forma de uma árvore
objetos
de classificação conhecida

distância
por dendrograma
O dendograma
mostra a
sequência de
agregação dos
objetos

Dois tipos de procedimentos hierárquicos

de agrupamento: aglomerativo e divisivo
 Métodos hierárquicos

Aglomerativo (método mais comum)

 No início cada objeto forma um cluster que
sucessivamente sofre uma série de fusões com outros
clusters até que no final todos os objetos estejam em um
único agrupamento.
 Um cluster formado em uma dada interação corresponde
a união de clusters formados em passos anteriores.

Divisivo
 No início há apenas um cluster formado pelo conjunto de
objetos que é dividido sucessivamente até que no final
cada cluster contenha apenas um objeto.
 Clusters formados em uma dada interação correspondem
a fragmentação de um cluster formado no passo anterior.
 Métodos hierárquicos: matriz de distância

Matriz de dados  x11 x12  x1 p  Objeto 1

x x 22  x 2 p 
X   21

    
 
 x n1 x n 2  x np  Objeto n

Variável 1 Variável p

 0 d12  d1n  Os métodos

d 0 
 d2n 
hierárquicos

D  21 dependem de
    
uma matriz de
distância entre
Matriz de distãncias   os objetos.
d n1 d n 2  0 
 Métodos hierárquicos aglomerativos

Vários métodos:

 Encadeamento Simples ou vizinho mais próximo

(Single linkage ou nearest neighbor)

 Encadeamento Completo ou vizinho mais longe

(Complete linkage ou furthest neighbor)

 Encadeamento Médio (Average linkage)

 Método de Ward (Ward´s method) MELHOR MÉTODO HIERÁRQUICO

 Método do Centróide (Centroid method)

Todos estes métodos partem de uma matriz de distâncias entre os objetos.

Os métodos diferem na maneira de como calculam

as distâncias entre os objetos e clusters.
 Métodos hierárquicos aglomerativos

Objetos
6

5 C F E
Solução inicial
4

3
D com 6 clusters,
B cada um com 1
2

1
A objeto
0
0 1 2 3 4 5 6 7

Matriz de distâncias entre os clusters Qual o par de objetos mais

(matriz simétrica) próximos, ou seja,
parecidos?

É o par E,F, logo estes

objetos são os primeiros a
serem agrupados
 Métodos hierárquicos aglomerativos

5 C F E Solução intermediária com 5 clusters.

4
D
3
B As distâncias passam a ser calculadas em
2
A relação ao cluster e não mais em relação
1
aos seus objetos
0
0 1 2 3 4 5 6 7

Atualiza matriz de distâncias

Matriz de distâncias entre os clusters Qual o par de objetos mais

(matriz simétrica) próximos?

É o par A,B, logo estes

objetos são os próximos a
serem agrupados
 Métodos hierárquicos aglomerativos

5 C F E
Solução
4

3
D intermediária com
B 4 clusters
2

1
A
0
0 1 2 3 4 5 6 7

Atualiza matriz de distâncias

Matriz de distâncias entre os clusters Qual o par de objetos mais

(matriz simétrica) próximos?

É o par (E,F),D logo estes

objetos são os próximos a
serem agrupados
 Métodos hierárquicos aglomerativos

5 C F E
Solução
4

3
D intermediária com
B 3 clusters
2

1
A
0
0 1 2 3 4 5 6 7

Atualiza matriz de distâncias

Matriz de distâncias entre os clusters Qual o par de objetos mais

(matriz simétrica) próximos?

É o par (E,F,D),C logo estes

objetos são os próximos a
serem agrupados
 Métodos hierárquicos aglomerativos

5 C F E
Solução
4

3
D intermediária com
B 2 clusters
2

1
A
0
0 1 2 3 4 5 6 7

Atualiza matriz de distâncias

Matriz de distâncias entre os clusters

(matriz simétrica)
O próximo passo seria agrupar
todos os objetos em um único
cluster (solução trivial).

27,35 é a distância entre os dois

clusters
 Métodos hierárquicos aglomerativos

6 objetos = 6 clusters 5 clusters 4 clusters

6 6 6

5 5 5

4 4 4

3 3 3

2 2 2

1 1 1

0 0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

Matriz de distâncias 6x6 Matriz de distâncias 5x5 Matriz de distâncias 4x4

Menor distância = 0,5 Menor distância = 1 Menor distância = 2,667

A cada iteração o número de clusters diminui de uma unidade e os

novos agrupamentos tornam-se mais heterogêneos internamente.
1 cluster 2 clusters 3 clusters
6 6 6

5 5 5

4 4 4

3 3 3

2 2 2

1 1 1

0 0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

Matriz de distâncias 2x2 Matriz de distâncias 3x3

Menor distância = 27,35 Menor distância = 3,02
 Métodos hierárquicos: dendrograma

A sequência das agregações e as distâncias em que elas ocorrem são

descritas no dendrograma, um gráfico útil na definição do número de
agrupamentos.

Melhor solução
tem 2 clusters:
• Cluster AB
• Cluster CDEF
Métodos hierárquicos: encadeamento simples (single linkage)

Em qualquer estágio, a fusão de dois clusters baseia-se na menor

distância individual entre os seus elementos.

Utiliza a distância mínima entre dois objetos para definir a distância entre
dois clusters.

Quando os objetos estão pobremente estruturados, o single linkage pode

reunir em um cluster elementos bastante diferentes, desde que haja entre
eles uma cadeia de outros elementos que sejam semelhantes entre si
(efeito de cadeia).

Tende a concentrar a maior parte dos

objetos em um pequeno número de
clusters e formar muitos clusters com
poucos objetos.
Exemplo de como a ligação individual A
pode agregar pontos distintos A e B
B
 Métodos hierárquicos: encadeamento completo (complete linkage)

A distância entre dois clusters é definida pela maior distância entre dois
objetos, um em cada cluster.

Elimina a possibilidade do efeito de encadeamento.

Mais
Mais próximo Longe
Ligação Completa
Ligação Individual

Métodos hierárquicos: encadeamento médio (average linkage)

A distância entre dois clusters é definida como a média das distância

entre os elementos dos dois grupos.

Tende a enviesar em direção à produção de grupos com

aproximadamente a mesma variância
 Métodos hierárquicos: Método de Ward

A cada iteração de um método hierárquico aglomerativo o número de

clusters diminui de uma unidade.

Os novos agrupamentos formados agregam mais elementos diferentes e

por isso tornam-se mais heterogêneos internamente

Durante a aglomeração dos clusters, a perda de qualidade da partição é

inexorável.

O método de Ward atenua este efeito do processo de aglomeração,

minimizando, a cada iteração, o incremento na heterogeneidade interna
dos clusters.
 Quantos clusters devem ser formados ?

Não há um procedimento padrão e objetivo para

determinar o “correto” número de agrupamentos.

1) O exame do dendrograma em busca de grandes

alterações dos níveis de similaridade para as sucessivas
fusões (só é possível nos métodos hierárquicos).

2) Análise gráfica das tipologias

3) Selecionar o número de clusters com base em um

critério “a priori”, avaliação prática, senso comum e
fundamentos teóricos.
Análise de agrupamentos no SPSS
Exemplo: (Fávero et al, 2009)

Imagine que um analista de mercado está interessado em

segmentar um conjunto de empresas que atuam no setor
de siderúrgia e metalurgia, com base em informações
financeiras publicadas.

Foram selecionadas 25 empresas que atuam nestes

setores.

Os dados foram obtidos na revista exame – Melhores e

Maiores de 2005.

Foram escolhidos quatro indicadores: Faturamento (US$

milhões), Rentabilidade do patrimônio líquido (%),
Endividamento geral da empresa (%) e número de
empregados.
Base de dados
Métodos hierárquicos
Escolha a opção Analyze/Classify/Hierarchical cluster
Selecione as variáveis
Selecione as outras opções
Resultados

Um critério para
identificação do número
de clusters:

Maior diferença (salto).

O estágio anterior ao
salto indica o ponto de
parada para novos
agrupamentos.
No caso a maior
diferença está entre 23 e
24, o que sugere a
escolha de dois clusters
Resultados
Resultados

cluster membership com

soluções de 3 clusters
salvos na planilha com
dados originais:
variáveis clu3_1

clu i_ j = cluster membership na solução com i

clusters na j-ésima execução de algum método
hierárquico
K-Means
Escolha a opção Analyze/Classify/K-Means
Selecione as variáveis
Selecione as variáveis
Resultados
Resultados

As variáveis faturamento e empregados foram as que mais

discriminaram os grupos
Resultados

cluster membership
com soluções de 3
clusters salvos na
planilha com dados
originais:
variáveis qcl_1

qcl i_ j = cluster membership na solução com i

clusters na j-ésima execução de algum método
hierárquico