Prof. José Francisco Moreira Pessanha [email protected] Análise de agrupamentos

Prof. José Francisco Moreira [email protected]

Análise de agrupamentosAnálise de agrupamentos

Análise de agrupamentosCluster 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).

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 agrupamentosCluster Analysis

Clusters

Algoritmo de análise de

agrupamentos

Cada ponto representa uma empresa

Identificação dos Identificação dos clustersclusters a partir dos dados a partir dos dados

O que é possível fazer com a 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

Clusters são grupos de objetos semelhantes.Clusters são grupos de objetos semelhantes.

Para formar clusters é necessário ter uma medida do grau de similaridade Para formar clusters é necessário ter uma medida do grau de similaridade entre os objetos ou de diferença (dissimilaridade) entre eles.entre os objetos ou de diferença (dissimilaridade) entre eles.

Vamos trabalhar com medidas de dissimilaridade (distâncias), por exemplo, o Vamos trabalhar com medidas de dissimilaridade (distâncias), por exemplo, o quadrado da distância euclidiana. quadrado da distância euclidiana.

Distâncias pequenas indicam objetos próximos, ou seja, semelhantes em um Distâncias pequenas indicam objetos próximos, ou seja, semelhantes em um conjunto de atributos.conjunto de atributos.

Sejam os objetos X e Y caracterizados por p atributos quantitativos: X = Sejam os objetos X e Y caracterizados por p atributos quantitativos: X = (x(x11,x,x22,...,x,...,xpp) e Y = (y) e Y = (y11,y,y22,...,y,...,ypp).).

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

||X-Y||||X-Y||22 = (x = (x11 – y – y11))22 + (x + (x22 – y – y22))22 +...+ (x +...+ (xpp - y - ypp))2 2 = =

p

iii yx

1

2

Centro de gravidade da nuvem de pontos

objetos atributo X atributo Y#1 1 1#2 1,5 1,5#3 5 5,5#4 6 7#5 1 3#6 1,5 3,5#7 5,5 1#8 6,5 2

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

Matriz de dadosMatriz de dados Nuvem de pontos com centro de gravidade CNuvem de pontos com centro de gravidade C

CC

As coordenadas do centro de gravidade C são as médias em cada atributo:As coordenadas do centro de gravidade C são as médias em cada atributo:

Abscissa de C = (1 + 1,5 + 5 + 6 + 1 + 1,5 + 5,5 + 6,5) / 8 = 3,5Abscissa de C = (1 + 1,5 + 5 + 6 + 1 + 1,5 + 5,5 + 6,5) / 8 = 3,5Ordenada de C = (1 + 1,5 + 5,5 + 7 + 3 + 3,5 + 1 + 2) / 8 = 3,06Ordenada de C = (1 + 1,5 + 5,5 + 7 + 3 + 3,5 + 1 + 2) / 8 = 3,06

Inércia total, medida de dispersão da nuvem de pontos ao redor do centro de gravidade da nuvem

8

1

2||||#i

Ci

Matriz de dadosMatriz de dadosNuvem de pontos com centro de gravidade CNuvem de pontos com centro de gravidade C

A inércia total é a soma dos quadrados das distâncias entre cada objeto e o A inércia total é a soma dos quadrados das distâncias entre cada objeto e o centro de gravidade da nuvem de pontos (ponto C):centro de gravidade da nuvem de pontos (ponto C):

Inércia total = ||#1 – C||Inércia total = ||#1 – C||2 2 + ||#2 – C||+ ||#2 – C||22 +...+ ||#8 – C|| +...+ ||#8 – C||22 = 75,72 = 75,72

Quadrado da distância entre o objeto #1 e o centro de gravidade C:Quadrado da distância entre o objeto #1 e o centro de gravidade C:||#1 – C||||#1 – C||22 = (1 – 3,5) = (1 – 3,5)22+ (1 - 3,06)+ (1 - 3,06)22 = 10,1 = 10,1

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

CC

#1#1


Centro de gravidade 3,50 3,06

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

Centros de gravidade dos clusters (centróides)


Matriz de dadosMatriz de dados Centros de gravidade dos clusters (centróides)Centros de gravidade dos clusters (centróides)

CC

Abscissa do centróide C1 = (1 + 1,5 + 1 + 1,5) / 4 = 1,25Abscissa do centróide C1 = (1 + 1,5 + 1 + 1,5) / 4 = 1,25Ordenada do centróide C1 = (1 + 1,5 + 3 + 3,5) / 4 = 2,25Ordenada do centróide C1 = (1 + 1,5 + 3 + 3,5) / 4 = 2,25

Abscissa do centróide C2 = (5 + 6 + 5,5 + 6,5) / 4 = 5,75Abscissa do centróide C2 = (5 + 6 + 5,5 + 6,5) / 4 = 5,75Ordenada do centróide C2 = (5,5 + 7 + 1 + 2) / 4 = 3,88Ordenada do centróide C2 = (5,5 + 7 + 1 + 2) / 4 = 3,88

O centro de gravidade de um cluster é a média dos seus objetos:O centro de gravidade de um cluster é a média dos seus objetos:

CC22CC11

Inércia inter-cluster medida de separação dos clusters

Contribuição do cluster 1 para a inércia inter-cluster = Contribuição do cluster 1 para a inércia inter-cluster = 4x||C4x||C11 – C|| – C||22

4x[(1,25 - 3,50)4x[(1,25 - 3,50)22 + (2,25 - 3,06) + (2,25 - 3,06)22] = 22,89] = 22,89Contribuição do cluster 2 para a inércia inter-cluster = Contribuição do cluster 2 para a inércia inter-cluster = 4x||C4x||C22 – C|| – C||22

4x[(5,75 - 3,50)4x[(5,75 - 3,50)22 + (3,88 - 3,06) + (3,88 - 3,06)22] = 22,89] = 22,89

Inércia inter-cluster = 22,89 + 22,89 = 45,78Inércia inter-cluster = 22,89 + 22,89 = 45,78

É a soma dos quadrados das É a soma dos quadrados das distâncias dos centróides dos distâncias dos centróides dos clusters ao centro de gravidade da clusters ao centro de gravidade da nuvem de pontos, ponderadas nuvem de pontos, ponderadas pelos respectivos tamanhos dos pelos respectivos tamanhos dos clusters.clusters.

4x||C4x||C11 – C|| – C||22 + 4x||C + 4x||C22 – C|| – C||220

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

CC CC22

CC11

Centro de gravidade abscissa (X) ordenada (Y)cluster 1 (C1) 1,25 2,25cluster 2 (C2) 5,75 3,88nuvem de pontos (C) 3,50 3,06

Inércia intra-clustermedida de heterogeneidade interna dos clusters

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

cluster 1 atributo X atributo Y#1 1 1#2 1,5 1,5#5 1 3#6 1,5 3,5

Centro de gravidade C1 1,25 2,25

CC

Inércia intra-cluster = 4,5 + 25,44 = 29,94Inércia intra-cluster = 4,5 + 25,44 = 29,94

É a soma dos quadrados das É a soma dos quadrados das distâncias dos objetos aos distâncias dos objetos aos centróides dos clusters onde estão centróides dos clusters onde estão alocados.alocados.

CC22

CC11

#1#1#2#2

#5#5#6#6

||#1 - C||#1 - C11||||22 + ||#2 - C + ||#2 - C11||||22+ ||#5 - C+ ||#5 - C11||||2 2 + ||#6 - C+ ||#6 - C11||||22 = 4,5 = 4,5

#3#3#4#4

#7#7 #8#8

||#3 - C||#3 - C22||||22+||#4 - C+||#4 - C22||||22+||#7 - C+||#7 - C22||||2 2 +||#8 - C+||#8 - C22||||22 = 25,44 = 25,44

Contribuição do cluster 1 para a inércia intra-clusterContribuição do cluster 1 para a inércia intra-cluster

Contribuição do cluster 2 para a inércia intra-clusterContribuição do cluster 2 para a inércia intra-clustercluster 2 atributo X atributo Y

#3 5 5,5#4 6 7#7 5,5 1#8 6,5 2

Cntro de gravidade C2 5,75 3,88

Decomposição da inércia

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

CC CC22

CC11

#1#1#2#2

#5#5#6#6

#3#3#4#4

#7#7 #8#8

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

CC CC22

CC11

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

CC

Inércia intra-clusterInércia intra-cluster

Inércia inter-clusterInércia inter-cluster

Inércia totalInércia total

29,9429,94

45,7845,78

75,7275,72

Inércia total =Inércia total =Inércia intra-cluster + Inércia inter-clusterInércia intra-cluster + Inércia inter-cluster

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

Há várias formas de dividir um conjunto em k clusters, a melhor é aquela que produz clusters mais homogêneos

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

Inércia Intra-cluster = 29,94Inércia Inter-cluster = 45,78Inércia Total = 75,72


Inércia Intra-cluster = 71,81Inércia Inter-cluster = 3,91Inérica Total = 75,72

Melhor solução Melhor solução com 2 clusterscom 2 clusters

2 clusters2 clusters


Quanto menor a Quanto menor a inércia intra-cluster, inércia intra-cluster, mais homogêneos mais homogêneos são os clusters são os clusters formadosformados

Quanto maior a Quanto maior a inércia inter-cluster, inércia inter-cluster, maior é a separação maior é a separação dos clustersdos clusters

A inércia total A inércia total permanece constante e permanece constante e independe da forma independe da forma como os objetos são como os objetos são agrupadosagrupados

Inércias intra e inter variam com o número de clusters (k), porém a soma é constante e independe de k

0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7


0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7


0

1

2

3

4

5

6

7

8

0 1 2 3 4 5 6 7

Inércia Intra-cluster = 3,13Inércia Inter-cluster = 72,59Inérica Total = 75,72




A inércia intra-cluster A inércia intra-cluster diminui a medida que diminui a medida que aumentamos o nº de aumentamos o nº de clustersclusters

A inércia inter-cluster A inércia inter-cluster aumenta a medida aumenta a medida que aumentamos o que aumentamos o nº de clustersnº de clusters

A inércia total A inércia total permanece constante permanece constante e independe do nº de e independe do nº de clustersclusters

Etapas da análise de agrupamentos

1) Seleção dos objetos a serem agrupados. (no caso da caracterização da carga são as curvas típicas dos dias úteis da amostra de clientes e redes)

2) Definição de um conjunto de variáveis que caracterizam os indivíduos.

(no caso da caracterização da carga são as demandas da curva de carga)

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

Procuram diretamente uma partição de N objetos em um número pré-definido de k clusters que satisfaçam duas premissas básicas: coesão interna e isolamento dos clusters.

O número de agrupamentos deve ser especificado a priori

Métodos não hierárquicos 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 (espécies, gêneros, famílias, ordem, etc.).

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

ji cx é o quadrado da distância do objeto xi ao centróide do cluster j

Demanda pontaDemanda pontaDe

ma

nd

a f

ora

de

po

nta

De

ma

nd

a f

ora

de

po

nta

xxi

ccj

2

ji cx Distância Distância entre os dois entre os dois pontospontos

Em cada cluster j, j=1,k, a heterogeneidade interna é avaliada pela seguinte soma de quadrados ou WSS(j):

j clusterx

2

ji

i

cxjWSS

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

k

1j j clusterx

2

ji

k

1j i

cxjWSSWSS

K-Means

Logo, para minimizar a heterogeneidade interna dos clusters devemos minimizar a inércia intra-cluster (WSS).

k

1j j clusterx

2

ji

i

cxWSS

Quanto menor WSS(j), menor é a heterogeneidade do j-ésimo cluster.

Dado que o objetivo é dividir o conjunto de n objetos em k clusters tal que a heterogeneidade interna dos clusters seja mínima, devemos identificar os k centróides cj , j=1,k , que minimizem a inércia intra-cluster (WSS).

Menor heterogeneidade Menor heterogeneidade interna dos clustersinterna dos clusters

Menor Inércia Intra-cluster (WSS)Menor Inércia Intra-cluster (WSS)

K-Means

Passo 1 Especifique um conjunto de k centróides iniciais cj , j=1,K (escolhidos ou gerados aleatoriamente com base na amostra).

Passo 2 Percorra a lista de objetos, calcule o quadrado da distância de cada objeto em relação ao centróide de cada cluster e aloque cada objeto ao cluster cujo centróide é o mais próximo.

Passo 3 Calcule o valor da inércia intra-cluster (WSS). Pare se o valor da função objetivo estiver abaixo de uma tolerância ou se a melhoria em relação a iteração anterior for desprezível.

Passo 4 Atualize os centróides calculando a média dos objetos em cada cluster e volte para o passo 2.

Algoritmo do Método K MeansAlgoritmo do Método K Means

jk todo para cxcx2

ki

2

ji objeto i classificado no cluster j se

O algoritmo deve continuar até o momento que não haja realocação de objetos de um cluster para outro

k

1j j clusterx

2

ji

i

cxWSS

K-Means

Lebart, L., Piron, M, Morineau, A. Statistique exploratoire multidimensionnelle, Dunod, 2000 Lebart, L., Piron, M, Morineau, A. Statistique exploratoire multidimensionnelle, Dunod, 2000

K-Means

Objetos Coordenadas

X1 X2

A 5 3

B -1 1

C 1 -2

D -3 -2

-3

-2

-1

0

1

2

3

4

-4 -3 -2 -1 0 1 2 3 4 5 6

X1

X2A

B

CD

ExemploExemplo

Dado o conjunto de 4 objetos (Dado o conjunto de 4 objetos (nn=4), use o algoritmo k-Means =4), use o algoritmo k-Means para identificar 2 clusters (para identificar 2 clusters (kk=2)=2)

K-Means

Centróides iniciais (seleção aleatória)Centróide Coordenadas dos centróides dos clusters

X1 X2

C1 2 2

C2 -1 -2

||A - C1||2 = (5-2)2 + (3-2)2 = 10

||A - C2||2 = (5+1)2 + (3+2)2 =61

||B - C1||2 =(-1-2)2 + (1-2)2 = 10||B - C2||2 =(-1+1)2 + (1+2)2 = 9

A Cluster com centróide C1

ExemploExemplo

Objetos Coordenadas

X1 X2

A 5 3

B -1 1

C 1 -2

D -3 -2

||C - C1||2 =(1-2)2 + (-2-2)2 = 5||C – C2||2 =(1+1)2 + (-2+2)2 = 4

||D - C1||2 =(-3-2)2 + (-2-2)2 = 39||D – C2||2 =(-3+1)2 + (-2+2)2 = 4

B Cluster com centróide C2

C Cluster com centróide C2

D Cluster com centróide C2

Lista de objetos

Alocação dos objetos aos clusters

K-Means

Clusters Coordenadas dos centros de gravidade

X1 X2

A 5 3

BCD -1 -1

-3

-2

-1

0

1

2

3

4

-4 -2 0 2 4 6

X1

X2A

B

CDcentro de gravidade

ExemploExemplo

Atualiza os Atualiza os centróidescentróides

K-Means

-3

-2

-1

0

1

2

3

4

-4 -2 0 2 4 6

X1

X2A

B

CD

ExemploExemplo

||A - C1||2 = (5-5)2 + (3-3)2 = 0

||A - C2||2 = (5+1)2 + (3+1)2 =61

||B - C1||2 =(-1-5)2 + (1-3)2 = 40||B - C2||2 =(-1+1)2 + (1+1)2 = 4

A Cluster com centróide C1

||C - C1||2 =(1-5)2 + (-2-3)2 = 39||C – C2||2 =(1+1)2 + (-2+1)2 = 5

||D - C1||2 =(-3-2)2 + (-2-2)2 = 41||D – C2||2 =(-3+1)2 + (-2+1)2 = 5

B Cluster com centróide C2

C Cluster com centróide C2

D Cluster com centróide C2

Alocação dos objetos aos clusters

C1C1

C2C2

Não houve realocação de objetos, Não houve realocação de objetos, portanto, o algoritmo convergiu e dois portanto, o algoritmo convergiu e dois clusters foram identificados: A e B,C,Dclusters foram identificados: A e B,C,D

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.

Exemplo: definição das metas de continuidade do fornecimento de energia elétrica com o K-Means

Formação dos clusters de conjuntos

semelhantespelo K-Means

Definição das metas de

DEC e FEC em cada cluster

Clusters Metas

Cerca de 6000 conjuntos de unidades consumidoras informados pelos sistema

GESTTOR/ANEEL

A Resolução ANEEL 024/2000: introduziu a análise comparativa (yardstick competition) dos desempenhos dos conjuntos de unidades consumidoras, como meio de definição das metas dos indicadores DEC e FEC.

A idéia é estabelecer metas diferenciadas que reconhecem a diversidade física e econômica das regiões atendidas pelas distribuidoras.

A análise comparativa e a definição das metas de continuidade está implementada no ANABENCH, um sistema computacional desenvolvido pelo CEPEL.

Atributos dos conjuntos: km de rede aérea primária – ERAP área do conjunto – AREA potência instalada – PNI número de consumidores - NUC consumo médio - CMM Isolado ou interligado

PESSANHA, J.F.M., CASTELLANI, V.L.O., HASSIN, E.S., CHEBERLE, LA.D. ANABENCH – Sistema Computacional para Estabelecimento de Metas de Continuidade, XVI Seminário Nacional de Distribuição de Energia Elétrica, Brasília, 2004.

85,8

90,0

91,091,7

92,292,7

93,1

79,5

88,2

75

77,5

80

82,5

85

87,5

90

92,5

95

10 20 30 40 50 60 70 80 90

Número de clusters

SQ

Inte

r %

Inércia Inter-cluster (SQInter) para diferentes níveis de agregaçãoInércia Inter-cluster (SQInter) para diferentes níveis de agregação

A inércia inter-cluster cresce com o nº de clusters.A inércia inter-cluster cresce com o nº de clusters.

Quantos clusters devem ser formados ?Quantos clusters devem ser formados ?

Uma partição em 30 cluster é razoável, pois:Uma partição em 30 cluster é razoável, pois:

• concentra mais de 80% da inércia inter-cluster (SQInter)concentra mais de 80% da inércia inter-cluster (SQInter)

• a partir deste ponto o ganho de SQInter com a adição de a partir deste ponto o ganho de SQInter com a adição de mais clusters torna-se muito pequenomais clusters torna-se muito pequeno

Exemplo: definição das metas de continuidade do fornecimento de energia elétrica com o K-Means

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 na forma de uma árvore de classificação conhecidapor dendrograma

Dois tipos de procedimentos hierárquicosde agrupamento: aglomerativo e divisivo

objetosobjetos

dendrogramadendrograma

distânciadistânciaO O

dendograma dendograma mostra a mostra a

sequência de sequência de agregação dos agregação dos

objetosobjetos


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.

Exemplo:Considere 5 veículos caracterizados pelos seguintes atributos: n° de portas, autonomia (km/l), preço, cilindrada, conforto, tamanho.

Métodos hierárquicos divisivos

Métodos hierárquicos aglomerativos

Métodos hierárquicos: matriz de distância

Os métodos hierárquicos dependem de uma matriz de distância entre

os objetos.

npnn

p

p

xxx

xxx

xxx

X

21

22221

11211Matriz de dados Objeto 1

Objeto n

Variável 1 Variável p

0

0

0

21

221

112

nn

n

n

dd

dd

dd

D

Matriz de distãncias

Métodos hierárquicos: matriz de distância (Reis, 2001)

Empresasnº de lojas

dimensão média das lojas m2

% da área alimentar no

total das vendas

montante da área almentar no total de

caixa ($ 1000)

Modelo 42 830 95 12.000

Pingo Doce 33 1215 92 11.500

Feira Nova 1 6000 70 18.500

Supa / Jumbo 6 5675 63 21.400

Minipreço 31 288 98 870

Continente 4 885 65 23.100

Com o objetivo de encontrar grupos estratégicos, pretende-se aplicar a análise de agrupamentos a uma amostra de seis grandes empresas comerciais portuguesas, para as quais foram medidas as seguintes dimensões estratégicas:

X1 = nº de lojasX2 = dimensão média das lojas (m)X3 = % da área alimentar no total das vendasX4 = montante da área alimentar no total de caixa ($ 1000)

Matriz de dados


j

jijij s

xxz

Valor padronizado da variável j na i-ésima empresa

Empresasnº de lojas



total das vendas

montante da área almentar no total de caixa ($ 1000)

Modelo 1,26 -0,63 0,90 -0,31

Pingo Doce 0,76 -0,48 0,71 -0,37

Feira Nova -1,04 1,34 -0,65 0,48

Supa / Jumbo -0,76 1,22 -1,08 0,83

Minipreço 0,65 -0,84 1,08 -1,66

Continente -0,87 -0,61 -0,96 1,04

Dados padronizados

Variáveis em escalas diferentes padronização


Empresasnº de lojas (X1)


(X2)


total das vendas (X3)

montante da área almentar no total

de caixa (1000 contos) (X4)

Modelo (1) 1,26 -0,63 0,90 -0,31

Pingo Doce (2) 0,76 -0,48 0,71 -0,37

Feira Nova (3) -1,04 1,34 -0,65 0,48

Supa / Jumbo (4) -0,76 1,22 -1,08 0,83

Minipreço (5) 0,65 -0,84 1,08 -1,66

Continente (6) -0,87 -0,61 -0,96 1,04

3,037,031,071,09,048,063,076,026,1 222212 d

Modelo (1)Pingo Doce

(2)Feira Nova

(3)Supa /

Jumbo (4)Minipreço (5) Continente (6)

0 Modelo (1)

0,3 0 Pingo Doce (2)

0 Feira Nova (3)

0 Supa / Jumbo (4)

0 Minipreço (5)

0 Continente (6)

D =




(X2)





Modelo (1) 1,26 -0,63 0,90 -0,31

Pingo Doce (2) 0,76 -0,48 0,71 -0,37

Feira Nova (3) -1,04 1,34 -0,65 0,48

Supa / Jumbo (4) -0,76 1,22 -1,08 0,83

Minipreço (5) 0,65 -0,84 1,08 -1,66

Continente (6) -0,87 -0,61 -0,96 1,04

2,1248,031,065.09,034,163,004,126,1 222213 d


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 0 Feira Nova (3)

0 Supa / Jumbo (4)

0 Minipreço (5)

0 Continente (6)

D =




(X2)





Modelo (1) 1,26 -0,63 0,90 -0,31

Pingo Doce (2) 0,76 -0,48 0,71 -0,37

Feira Nova (3) -1,04 1,34 -0,65 0,48

Supa/ Jumbo (4) -0,76 1,22 -1,08 0,83

Minipreço (5) 0,65 -0,84 1,08 -1,66

Continente (6) -0,87 -0,61 -0,96 1,04

7,1283,031,008.19,022,163,076,026,1 222214 d


(2)Feira Nova

(3)Supa /


0 Modelo (1)



12,7 0 Supa / Jumbo (4)

0 Minipreço (5)

0 Continente (6)

D =




(X2)



montante da área almentar no total de caixa (1000 contos)

(X4)

Modelo (1) 1,26 -0,63 0,90 -0,31

Pingo Doce (2) 0,76 -0,48 0,71 -0,37

Feira Nova (3) -1,04 1,34 -0,65 0,48

Supa/ Jumbo (4) -0,76 1,22 -1,08 0,83

Minipreço (5) 0,65 -0,84 1,08 -1,66

Continente (6) -0,87 -0,61 -0,96 1,04


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 9,2 0 Feira Nova (3)

12,7 9,9 0,4 0 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =


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.


ObjetosObjetos

Qual o par de objetos mais Qual o par de objetos mais próximos, ou seja, próximos, ou seja, parecidos?parecidos?

É o par E,F, logo estes É o par E,F, logo estes objetos são os primeiros a objetos são os primeiros a serem agrupadosserem agrupados

0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

AABB

CC

DD

EEFF

Matriz de distâncias entre os clustersMatriz de distâncias entre os clusters(matriz simétrica)(matriz simétrica)

Solução inicial Solução inicial com 6 clusters, com 6 clusters, cada um com 1 cada um com 1

objetoobjeto


Solução intermediária com 5 clusters.Solução intermediária com 5 clusters.

As distâncias passam a ser calculadas em As distâncias passam a ser calculadas em relação ao cluster e não mais em relação relação ao cluster e não mais em relação aos seus objetosaos seus objetos


0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

AABB

CC

DD

EEFF

Atualiza matriz de distânciasAtualiza matriz de distâncias

Qual o par de objetos mais Qual o par de objetos mais próximos?próximos?

É o par A,B, logo estes É o par A,B, logo estes objetos são os próximos a objetos são os próximos a serem agrupadosserem agrupados



0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

AABB

CC

DD

EEFF



É o par (E,F),D logo estes É o par (E,F),D logo estes objetos são os próximos a objetos são os próximos a serem agrupadosserem agrupados

Solução Solução intermediária com intermediária com




0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

AABB

CC

DD

EEFF



É o par (E,F,D),C logo estes É o par (E,F,D),C logo estes objetos são os próximos a objetos são os próximos a serem agrupadosserem agrupados





0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

AABB

CC

DD

EEFF


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

27,35 é a distância entre os dois 27,35 é a distância entre os dois clustersclusters




0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

6 objetos = 6 clusters 5 clusters 4 clusters

1 cluster

Matriz de distâncias 6x6Menor distância = 0,5

Matriz de distâncias 5x5Menor distância = 1


2 clusters


3 clusters


A cada iteração o número de clusters diminui de uma unidade e os novos agrupamentos tornam-se mais heterogêneos internamente.

0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

0

1

2

3

4

5

6

0 1 2 3 4 5 6 7

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 Melhor solução tem 2 clusters:tem 2 clusters:• Cluster ABCluster AB• Cluster CDEFCluster CDEF


1) Inicie com N clusters, cada um contendo apenas um objeto e construa a matriz de distâncias de ordem N.

2) Identifique o menor elemento da matriz de distâncias para encontrar o par de clusters mais similares.

3) Reúna os dois clusters identificados na etapa 2 em um único cluster e atualiza a matriz de distâncias, retirando as linhas e colunas relativas aos dois clusters identificados em 2 e incluindo a linha e coluna com as distâncias entre os demais clusters e o novo cluster formado. Note que a ordem da matriz de distâncias diminui de uma unidade a cada vez que a etapa 3 é executada

4) Repita os passos 2 e 3 até que reste apenas um cluster. A cada iteração guarde a identificação dos clusters que foram fundidos e também a distância entre eles, estas informações serão utilizadas na montagem do dendrograma.

AlgoritmoAlgoritmo

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).

AABB

Exemplo de como a ligação individual Exemplo de como a ligação individual pode agregar pontos distintos A e Bpode agregar pontos distintos A e B

Tende a concentrar a maior parte dos objetos em um pequeno número de clusters e formar muitos clusters com poucos objetos.

Métodos hierárquicos: encadeamento simples (single linkage)

Menor distância = d12 = 0,3 entre Modelo e Pingo Doce

5 clusters

ModeloPingo Doce

Feira Nova


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 9,2 0 Feira Nova (3)

12,7 9,9 0,4 0 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Continente

Supa/Jumbo

Minipreço

1ª iteração

Exemplo encadeamento simples (Reis, 2001)

ModeloPingo Doce

Feira Nova

Continente

Supa/Jumbo

Minipreço

Qual a distância entre Feira Nova e o cluster Modelo/Pingo Doce ?d12,3 = ?

d13 = 12,2

d23 = 9,2


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 9,2 0 Feira Nova (3)

12,7 9,9 0,4 0 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Pelo encademaneto simples = d12,3 = min(12,2 ; 9,2) = 9,2

Atualização da matriz de distâncias


Atualização

Modelo (1) Pingo Doce (2)Feira Nova

(3)Supa / Jumbo

(4)Minipreço (5) Continente (6)

0 0,3 12,2 12,7 2,3 9,8 Modelo (1)

0,3 0 9,2 9,9 1,9 7,4 Pingo Doce (2)

12,2 9,2 0 0,4 15,2 4,3 Feira Nova (3)

12,7 9,9 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 13,8 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Pingo Doce

Modelo (1,2) Feira Nova (3)Supa /


0 9,2 9.9 1,9 7,4 Modelo, Pingo Doce (1,2)

9,2 0 0,4 15,2 4,3 Feira Nova (3)

9.9 0,4 0 17,1 3,4 Supa / Jumbo (4)

1,9 15,2 17,1 0 13,8 Minipreço (5)

7,4 4,3 3,4 13,8 0 Continente (6)

D =



Pingo Doce

Modelo (1,2)Feira Nova

(3)Supa /

Jumbo (4)Minipreço

(5)Continente (6)

0 Modelo, Pingo Doce (1,2)


9.9 0,4 0 Supa / Jumbo (4)

1,9 15,2 17,1 0 Minipreço (5)

7,4 4,3 3,4 13,8 0 Continente (6)

D =

Menor distância = d34 = 0,4 entre Feira Nova e Supa/Jumbo

4 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

2ª iteração


ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

Pingo Doce


(3)Supa /

Jumbo (4)Minipreço

(5)Continente (6)



9.9 0,4 0 Supa / Jumbo (4)

1,9 15,2 17,1 0 Minipreço (5)

7,4 4,3 3,4 13,8 0 Continente (6)

D =

d12,3 = 9,2

d12,4=9,9

Qual a distância entre os clusters Feira Nova/Supa/Jumbo e Modelo/Pingo Doce ?d12,34 = ?

Pelo encademaneto simples = d12,34 = min(9,2 ; 9,9) = 9,2



Atualização

Pingo Doce



0 9,2 9.9 1,9 7,4 Modelo, Pingo Doce (1,2)

9,2 0 0,4 15,2 4,3 Feira Nova (3)

9.9 0,4 0 17,1 3,4 Supa / Jumbo (4)

1,9 15,2 17,1 0 13,8 Minipreço (5)

7,4 4,3 3,4 13,8 0 Continente (6)

D =

Pingo Doce Supa / Jumbo


(3,4)Minipreço

(5)Continente (6)

0 9,2 1,9 7,4 Modelo, Pingo Doce (1,2)

9,2 0 15,2 3,4 Feira Nova, Supa/Jumbo (3,4)

1,9 15,2 0 13,8 Minipreço (5)

7,4 3,4 13,8 0 Continente (6)

D =





(3,4)Minipreço

(5)Continente

(6)


9,2 0 Feira Nova, Supa/Jumbo (3,4)

1,9 15,2 0 Minipreço (5)

7,4 3,4 13,8 0 Continente (6)

D =

Menor distância = d12,5 = 1,9 entre Minipreço e o cluster Modelo/Pingo Doce

3 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

3ª iteração


Atualização



(3,4)Minipreço

(5)Continente (6)



1,9 15,2 0 13,8 Minipreço (5)

7,4 3,4 13,8 0 Continente (6)

D =

Minipreço

Pingo Doce Supa / JumboModelo (1,2,5)

Feira Nova (3,4)

Continente (6)

0 9,2 7,4 Modelo, Pingo Doce, Minipreço (1,2,5)

9,2 0 3,4 Feira Nova, Supa/Jumbo (3,4)

7,4 3,4 0 Continente (6)

D =



Minipreço


Feira Nova (3,4)

Continente (6)

0 Modelo, Pingo Doce, Minipreço (1,2,5)



D =

Menor distância = d34,6 = 3,4 entre Continente e o cluster Feira Nova/Supa/Jumbo

2 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

4ª iteração


Atualização

Minipreço


Feira Nova (3,4)

Continente (6)




D =

Minipreço Continente


Feira Nova (3,4,6)

0 7,4 Modelo, Pingo Doce, Minipreço (1,2,5)

7,4 0 Feira Nova, Supa/Jumbo, Continente (3,4,6)D =



Passo Distâncias Nº de clusters Clusters

1 d1.2 = 0,3 5 12 / 3 / 4 / 5 / 6

2 d3,4 = 0,4 4 12 / 34 / 5 / 6

3 d12,,5 = 1,9 3 125 / 34 / 6

4 d34,,6 = 3,4 2 125 / 346

5 d125,,346 = 7,4 1 123456

Processo de agrupamento das seis empresas segundo o critério do encadeamento simples


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.

MaisMais próximpróximoo Ligação Ligação

IndividualIndividualLigação Ligação CompletaCompleta

Mais Mais LongLongee

Métodos hierárquicos: encadeamento completo (complete linkage)


5 clusters

ModeloPingo Doce

Feira Nova


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 9,2 0 Feira Nova (3)

12,7 9,9 0,4 0 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Continente

Supa/Jumbo

Minipreço

1ª iteração

Exemplo encadeamento completo (Reis, 2001)

ModeloPingo Doce

Feira Nova

Continente

Supa/Jumbo

Minipreço


d13 = 12,2

d23 = 9,2


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 9,2 0 Feira Nova (3)

12,7 9,9 0,4 0 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Pelo encadeamento completo = d12,3 = max(12,2 ; 9,2) = 12,2



Atualização


(3)Supa / Jumbo


0 0,3 12,2 12,7 2,3 9,8 Modelo (1)

0,3 0 9,2 9,9 1,9 7,4 Pingo Doce (2)

12,2 9,2 0 0,4 15,2 4,3 Feira Nova (3)

12,7 9,9 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 13,8 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Pingo Doce



0 12,2 12,7 2,3 9,8 Modelo, Pingo Doce (1,2)

12,2 0 0,4 15,2 4,3 Feira Nova (3)

12,7 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,3 15,2 17,1 0 13,8 Minipreço (5)

9,8 4,3 3,4 13,8 0 Continente (6)

D =



Pingo Doce





12,7 0,4 0 Supa / Jumbo (4)

2,3 15,2 17,1 0 Minipreço (5)

9,8 4,3 3,4 13,8 0 Continente (6)

D =


4 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

2ª iteração


ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

d12,3 = 12,2

d12,4=12,7

Qual a distância entre os clusters Feira Nova/Supa/Jumbo e Modelo/Pingo Doce ?d12,34 = ?

Pelo encadeamento completo = d12,34 = max(12,2 ; 12,7) = 12,7

Pingo Doce





12,7 0,4 0 Supa / Jumbo (4)

2,3 15,2 17,1 0 Minipreço (5)

9,8 4,3 3,4 13,8 0 Continente (6)

D =



Atualização

Pingo Doce




12,2 0 0,4 15,2 4,3 Feira Nova (3)

12,7 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,3 15,2 17,1 0 13,8 Minipreço (5)

9,8 4,3 3,4 13,8 0 Continente (6)

D =



(3,4)Minipreço

(5)Continente (6)



2,3 17,1 0 13,8 Minipreço (5)

9,8 4,3 13,8 0 Continente (6)

D =





(3,4)Minipreço

(5)Continente (6)



2,3 17,1 0 Minipreço (5)

9,8 4,3 13,8 0 Continente (6)

D =


3 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

3ª iteração


AtualizaçãoMinipreço


Feira Nova (3,4)

Continente (6)




D =



(3,4)Minipreço

(5)Continente (6)



2,3 17,1 0 13,8 Minipreço (5)

9,8 4,3 13,8 0 Continente (6)

D =



Minipreço


Feira Nova (3,4)

Continente (6)




D =


2 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

4ª iteração


Minipreço


Feira Nova (3,4)

Continente (6)




D =



Feira Nova (3,4,6)

0 17,1 Modelo, Pingo Doce, Minipreço (1,2,5)

17,1 0 Feira Nova, Supa/Jumbo, Continente (3,4,6)D =

Atualização




1 d1.2 = 0,3 5 12 / 3 / 4 / 5 / 6

2 d3,4 = 0,4 4 12 / 34 / 5 / 6

3 d12,,5 = 2,3 3 125 / 34 / 6

4 d34,,6 = 4,3 2 125 / 346

5 d125,,346 =17,1 1 123456

Processo de agrupamento das seis empresas segundo o critério do encadeamento completo


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: encadeamento médio (average linkage)


5 clusters

ModeloPingo Doce

Feira Nova


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 9,2 0 Feira Nova (3)

12,7 9,9 0,4 0 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Continente

Supa/Jumbo

Minipreço

1ª iteração

Exemplo encadeamento médio (Reis, 2001)

ModeloPingo Doce

Feira Nova

Continente

Supa/Jumbo

Minipreço


d13 = 12,2

d23 = 9,2


(2)Feira Nova

(3)Supa /


0 Modelo (1)


12,2 9,2 0 Feira Nova (3)

12,7 9,9 0,4 0 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Pelo encadeamento médio = d12,3 = média(12,2 ; 9,2) = 10,7



Atualização


(3)Supa / Jumbo


0 0,3 12,2 12,7 2,3 9,8 Modelo (1)

0,3 0 9,2 9,9 1,9 7,4 Pingo Doce (2)

12,2 9,2 0 0,4 15,2 4,3 Feira Nova (3)

12,7 9,9 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,3 1,9 15,2 17,1 0 13,8 Minipreço (5)

9,8 7,4 4,3 3,4 13,8 0 Continente (6)

D =

Pingo Doce




10,7 0 0,4 15,2 4,3 Feira Nova (3)

11,3 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,1 15,2 17,1 0 13,8 Minipreço (5)

8,6 4,3 3,4 13,8 0 Continente (6)

D =




4 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

Pingo Doce




10,7 0 0,4 15,2 4,3 Feira Nova (3)

11,3 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,1 15,2 17,1 0 13,8 Minipreço (5)

8,6 4,3 3,4 13,8 0 Continente (6)

D =

2ª iteração


ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

d12,3 = 10,7

d12,4=11,3

Qual a distância entre os clusters Feira Nova/Supa/Jumbo e Modelo/Pingo Doce ?d12,34 = ? Pelo encadeamento médio = d12,34 = média(10,7 ; 11,3) = 11

Pingo Doce




10,7 0 0,4 15,2 4,3 Feira Nova (3)

11,3 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,1 15,2 17,1 0 13,8 Minipreço (5)

8,6 4,3 3,4 13,8 0 Continente (6)

D =



Atualização

Pingo Doce




10,7 0 0,4 15,2 4,3 Feira Nova (3)

11,3 0,4 0 17,1 3,4 Supa / Jumbo (4)

2,1 15,2 17,1 0 13,8 Minipreço (5)

8,6 4,3 3,4 13,8 0 Continente (6)

D =



(3,4)Minipreço

(5)Continente (6)

0 11 2,1 8,6 Modelo, Pingo Doce (1,2)

11 0 16,15 3,85 Feira Nova, Supa/Jumbo (3,4)

2,1 16,15 0 13,8 Minipreço (5)

8,6 3,85 13,8 0 Continente (6)

D =




3 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço



(3,4)Minipreço

(5)Continente (6)



2,1 16,15 0 13,8 Minipreço (5)

8,6 3,85 13,8 0 Continente (6)

D =

3ª iteração


AtualizaçãoMinipreço


Feira Nova (3,4)

Continente (6)



10,3 3,85 0 Continente (6)

D =



(3,4)Minipreço

(5)Continente (6)



2,1 16,15 0 13,8 Minipreço (5)

8,6 3,85 13,8 0 Continente (6)

D =




2 clusters

ModeloPingo Doce

Continente

Feira Nova

Supa/Jumbo

Minipreço

Minipreço


Feira Nova (3,4)

Continente (6)



10,3 3,85 0 Continente (6)

D =

4ª iteração


Atualização

Minipreço


Feira Nova (3,4)

Continente (6)



10,3 3,85 0 Continente (6)

D =



Feira Nova (3,4,6)

0 11.5 Modelo, Pingo Doce, Minipreço (1,2,5)

11.5 0 Feira Nova, Supa/Jumbo, Continente (3,4,6)D =




1 d1.2 = 0,3 5 12 / 3 / 4 / 5 / 6

2 d3,4 = 0,4 4 12 / 34 / 5 / 6

3 d12,,5 = 2,1 3 125 / 34 / 6

4 d34,,6 = 3,85 2 125 / 346

5 d125,,346 =11.5 1 123456

Processo de agrupamento das seis empresas segundo o critério do encadeamento médio


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.


Inicialmente, cada cluster é composto por apenas um objeto (N clusters).a inércia intra-cluster é nula e a inércia inter-cluster é igual a inércia total.

No final do processo de aglomeração, todos os objetos são agrupados em um único cluster. a inércia inter-cluster é nula e a inércia intra-cluster é igual a inércia total.

A cada iteração, a fusão de dois clusters transfere uma parcela da inércia inter-cluster para a inércia intra-cluster, aumentando a heterogeneidade interna dos agrupamentos, deteriorando a qualidade da partição:

O método de Ward agrupa os dois cluster que minimizam esta parcela .

2

,2

, jijjii GGjGGi dndn

Parcela resultante da agregação dos cluster i e jGij é o centro de gravidade da fusão dos clusters i e j

Inércia intra-cluster Inércia inter-clusterInércia intra-cluster Inércia inter-cluster


Para minimizar o incremento da inércia intra cluster a cada interação, o método de Ward trabalha com a seguinte métrica na matriz de distâncias.

ni = nº de elementos do cluster inj = nº de elementos do cluster jGi = centro de gravidade do cluster iGj = centro de gravidade do cluster jd2(Gi,Gj) = quadrado da distância euclidiana entre Gi e Gj

jiji

jiij GGd

nn

nnd ,2

DadosMatriz de distâncias

25,95,415,3111

11, 222

CACA

CAAC GGd

nn

nnd

Exemplo


Matriz de distâncias

167,241515,512

12, 222

,

AEFAEF

AEFAEF GGd

nn

nnd

Exemplo: 1ª iteração

Menor distância entre E e FForme cluster EFCentro de gravidade do cluster EF

Atualiza matriz

5;5,52

;2

FEFE

EF

yyxxG



250,285,155,15,522

22, 222

,

ABEFABEF

ABEFABEF GGd

nn

nnd


Menor distância entre A e BForme cluster ABCentro de gravidade do cluster AB

Atualiza matriz

5,1;5,12

;2

BABA

AB

yyxxG



02,35,433,45,35,513

13, 222

,

CEFDCEFD

CEFDCEFD GGd

nn

nnd


Menor distância entre EF e DForme cluster EFDCentro de gravidade do cluster EFD

Atualiza matriz

33,4;5,53

;3

DFEDFE

EFD

yyyxxxG



35,275,1375,45,1524

24, 222

,

ABEFDCABEFDC

ABEFDCABEFDC GGd

nn

nnd


Menor distância entre EFD e CForme cluster EFDCCentro de gravidade do cluster EFDC

Atualiza matriz

375,4;54

;4

CDFECDFE

EFDC

yyyyxxxxG


Vantagens:Vantagens: Rápidos e exigem menos tempo de processamento.

Apresentam resultados para diferentes níveis de agregação.

Desvantagens:Desvantagens: A alocação de um objeto em um cluster é irrevogável, ou seja, uma vez o objeto incluído em um cluster, ele nunca será removido e ligado a outro agrupamento. Combinações anteriores indesejáveis persistem no decorrer da análise e levam a resultados artificiais. Não existe a possibilidade de realocação de objetos que possam ter sido incorretamente agrupados nos estágios anteiores.

Impacto substancial dos outliers.

Não são apropriados para analisar uma amostra muita extensa, pois a medida que o tamanho da amostra aumenta, a necessidade de armazenamento da matris de distâncias cresce drasticamente.


Métodos Hierárquicos são preferidos quando: Serão analisadas varias alternativas de agrupamento. O tamanho da amostra é moderado ( de 300 a 1000 objetos )

Métodos não-hierárquicos são preferidos quando: O número de grupos é conhecido. Presença dos outliers, desde que os métodos não-hierárquicos são

menos influenciados por outliers. Há um grande nº de objetos a serem agrupados.

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

Método nãoHierárquico

dados

MétodoHierárquico

clusters

Perfis médios em cada clusters

MétodoHierárquico

dados

Método nãoHierárquico

clusters

Estabelece o nº de clusters e os centróides iniciais (perfis médios em cada cluster)

Aproveita as vantagens dos métodos hierárquicos e não hierárquicos.

Uso combinado de métodos hierárquico e não hierárquico

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. Por exemplo, o programa de revisão tarifária (PRT -1994) recomendava 8 tipologias

4) Escolher o menor número de clusters que satisfaça a desigualdade: inércia inter / inércia total 0,7

5) Escolher o número de cluster que minimize o coeficiente de compacidade e separação (CS)

BRASIL, Ministério das Minas e Energia, Secretaria de Energia, DNAEE; Programa de Revisão Tarifária - PRT, Projeto 1 - Caracterização da Carga, Dezembro de 1994.

2_2__min_º centróidesentredistânciaobjetosdenSQIntraCS

Análise de agrupamentos no SPSSAnálise de agrupamentos no SPSS

Exemplo: (Fávero et al, 2009)Exemplo: (Fávero et al, 2009)

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

Foram selecionadas 25 empresas que atuam nestes setores.Foram selecionadas 25 empresas que atuam nestes setores.

Os dados foram obtidos na revista exame – Melhores e Os dados foram obtidos na revista exame – Melhores e Maiores de 2005.Maiores de 2005.

Foram escolhidos quatro indicadores: Faturamento (US$ Foram escolhidos quatro indicadores: Faturamento (US$ milhões), Rentabilidade do patrimônio líquido (%), milhões), Rentabilidade do patrimônio líquido (%), Endividamento geral da empresa (%) e número de Endividamento geral da empresa (%) e número de empregados.empregados.

Base de dadosBase de dados

Métodos hierárquicosMétodos hierárquicos

Escolha a opção Analyze/Classify/Hierarchical clusterEscolha a opção Analyze/Classify/Hierarchical cluster

Selecione as variáveisSelecione as variáveis

Selecione as outras opçõesSelecione as outras opções

ResultadosResultados

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

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



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-MeansK-Means

Escolha a opção Analyze/Classify/K-Means Escolha a opção Analyze/Classify/K-Means





As variáveis faturamento e empregados foram as que mais As variáveis faturamento e empregados foram as que mais discriminaram os gruposdiscriminaram os grupos


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

Bibliografia

CORRAR, L.J.; PAULO, E.; DIAS FILHO, J.M. (coordenadores) Análise Multivariada para os cursos de administração, ciências contábeis e esconomia, Editora Atlas, São Paulo, 2007.

FÁVERO, L.P.; BELFIORE, P.; SILVA, F.L.; CHAN, B.L. Análise de dados: modelagem multivariada para tomada de decisões, Campus, Rio de Janeiro, 2009.

HAIR, J.F.; ANDERSON, R.E.; TATHAM R.L.; BLACK W.O. Análise Multivariada de Dados, Bookman, 2005.

JOHNSON, R.A. & WICHERN, D.W. Applied Multivariate Statistical Analysis, 5th edition, Prentice Hall, New Jersey, 2002.

LEBART, L.; MORINEAU, A.; PIRON, M. Statistique Exploratoira Multidimensionnelle, 3e édition, Dunod, Paris, 2004.

MINGOTI, S.A. Análise de dados através de métodos de estatística multivariada: uma abordagem aplicada, Editora UFMG, Belo Horizonte, 2005.

REIS, E. Estatística multivariada aplicada, 2ª edição, Edições Sílabo, Lisboa, 2001.

Documents

Prof. José Francisco Moreira Pessanha [email protected] Análise de agrupamentos