Análise de Agrupamento (estatísticas)

42     Análise de Agrupamento

Notação
x
=
valores das variáveis
h, i, j, l
=
subscritos dos objetos
f, g
=
subscritos das variáveis
p
=
número de variáveis
c
=
subscrito para o cluster
k
=
número de clusters
Nj
=
número de objetos no cluster j
N
=
número total de casos.

42.1  Estatísticas Univariadas

Se a antrada for um dataset do IDAMS, as seguintes estatísticas são calculadas para todas as variáveis utilizadas na análise:
a)   Média.

x
 

f 
= 1

N

å
i 
xif
b)   Desvio-médio absoluto.
sf   = 1

N

å
i 
| xif  -  

x
 

f 
|

42.2  Medidas Padronizadas

Na mesma situação, o programa pode computar medidas padronizadas, também chamadas z-scores, dadas por:
zif   =  ( xif  -  

x
 

f 
)  /  sf
para cada caso i e cada variável f usando o valor médio e o desvio-médio absoluto da variável f (ver seção 1 acima).

42.3  Matriz de Dissimilaridade Computada de um Dataset do IDAMS

Os elementos dij de uma matriz de dissimilaridade medem o grau de dissimilaridade entre casos i e j. Os dij são calculados diretamente dos dados originais, ou dos z-scores se as variáveis são requisitadas a serem padronizadas. Uma das duas distâncias pode ser escolhida: euclidiana ou city-block.
a)   Distância euclidiana.
dij =   æ
Ö

p
å
f=1 
(xif - xjf)2
 
b)   Distância city-block.
dij = p
å
f=1 
| xif - xjf |

42.4  Matriz de Dissimilaridade Computada de uma Matriz de Similaridade

Se a entrada consiste de uma matriz de similaridade com elementos sij, os elementos dij da matriz de dissimilaridade são calculados da seguinte maneira:
dij = 1  -  sij

42.5  Matriz de Dissimilaridade Computada de uma Matriz de Correlação

Se a entrada consiste de uma matriz de correlação com elementos rij, os elementos dij da matriz de dissimilaridade são calculados usando uma das duas fórmulas: SIGN ou ABSOLUTE.
Ao se usar a fórmula SIGN, variáveis com uma correlação positiva alta recebem um coeficiente de dissimilaridade próximo a zero, de outro modo, variáveis com uma correlação negativa forte serão consideradas muito dissimilares.
dij = (1  -  rij) / 2
Ao usar a fórmula ABSOLUTE, variáveis com uma correlação negativa ou positiva alta receberão uma pequena dissimilaridade.
dij = 1  -  |rij|

42.6  Partição ao Redor de Medoids (PAM)

O algoritmo busca k objetos representativos (medoides) que estão centralmente localizados nos clusters que eles definem. O objeto representativo de um cluster, o medoide, é o objeto para o qual a dissimilaridade média de todos os objetos no cluster é mínima. De fato, o algoritmo PAM minimiza a soma de dissimilaridades ao invés da dissimilaridade média.
A seleção de k medoides é executada em duas fases. Na primeira fase, um agrupamento inicial é obtido pela sucessiva seleção de objetos representativos até que k objetos tenham sido encontrados. O primeiro objeto é aquele para o qual a soma das dissimilaridades em relação a todos os outros objetos é a menor possível. (Isso é um tipo de "mediana multivariada" dos N objetos, por isso o termo "medoide".) Subseqüentemente, a cada passo, PAM seleciona o objeto que diminui a função objetivo (soma de dissimilaridades) tanto quanto possível. Na segunda fase, uma tentativa é feita para melhorar o conjunto de objetos representativos. Isso é feito considerando-se todos os pares de objetos (i,h) cujo objeto i foi selecionado e objeto h não, checando se selecionando h e deselecionando i reduz a função objetivo. Em cada passo, a troca mais econômica é mantida.
a)   Distância média final (dissimilaridade). Essa é a função objetivo do PAM, que pode ser visto como uma medida de ädequação" do agrupamento.
Distância média final = 1

N
N
å
i=1 
di, m(i)
onde m(i) é o objeto representativo (medoide) mais próximo do objeto i.
b)   Clusters isolados. Há dois tipos de clusters isolados: L-clusters e L*-clusters.
Cluster C é um L-cluster se para cada objeto i pertencendo a C

max
j Î C 
dij <
min
h Ï C 
dih
Cluster C é um L*-cluster se

max
i,j Î C 
dij <
min
l Î C, h Ï C 
dlh
c)   Diâmetro de um cluster. O diâmetro do cluster C é definido como a maior dissimilaridade entre objetos pertencentes a C:
DiâmetroC =
max
i,j Î C 
dij
d)   Separação de um cluster. A separação do cluster C é dfinida como a menor dissimilaridade entre dois objetos, um dos quais pertence ao cluster C e o outro não.
SeparaçãoC =
min
l Î C, h Ï C 
dlh
e)   Distância média a um medoide. Se j é o medoide do cluster C, a distância média de todos os objetos de C em relação a j é calculada da seguinte maneira:
Distância médiaj = 1

Nj

å
i Î C 
dij
f)   Distância máxima a um medoide. Se o objeto j é o medoide do cluster C, a distância máxima de todos os objetos de C em relação a j é calculada da seguinte maneira:
Distância máximaj =
max
i Î C 
 dij
g)   Silhuetas de cluster. Cada cluster é representado por uma silhueta (Rousseeuw 1987), mostrando que objetos se posicionam bem dentro do cluster e quais meramente ficam em uma posição intermediária. Para cada objeto, a seguinte informação é fornecida:
          - o número de clusters ao qual ele pertence (CLU),
          - o número do cluster vizinho (NEIG),
          - o valor si (denotado por S(I) no resultados),
          - o identificador de três-caracteres do objeto i,
          - uma linha, cujo comprimento é proporcional a si.
Para cada objeto i o valor si é calculado da seguinte maneira:
si = bi  -  ai

max
(ai,   bi)
onde ai é a dissimilaridade média do objeto i em relação a todos os outros objetos do cluster A, que contém i e onde bi é a dissimilaridade média do objeto i em relação a todos os outros objetos do cluster mais próximo B (vizinho do objeto i). Note que o cluster vizinho é um tipo de segundo-melhor para o objeto i. Quando o cluster A contém apenas um objeto i, o si é zero (si = 0).
h)   Largura média de silhueta de um cluster. É a média de si para todos os objetos i em um cluster.
i)   Largura média de silhueta. É a média de si para todos os objetos i nos dados, i.e. largura média de silhueta para k clusters. Isso pode ser utilizado para selecionar o "melhor" número de clusters, escolhendo aquele k dando a maior média de si.
Outro coeficiente, SC, chamado COEFICIENTE DE SILHUETA, pode ser calculado manualmente como a largura média máxima de silhueta ao longo de todo o k para o qual a silhueta pode ser construída. Esse coeficiente é uma medida adimensional da quantidade de estrutura de agrupamento que foi descoberta pelo algoritmo de classificação.
SC =
max
k 

s
 

k 
Rousseeuw (1987) propôs a seguinte interpretação do coeficiente SC:
0.71 - 1.00
Uma estrutura forte foi encontrada.
0.51 - 0.70
Uma estrutura razoável foi encontrada.
0.26 - 0.50
A estrutura é fraca e pode ser artificial;
por favor, tente métodos adicionais nesses dados.
£ 0.25
Nenhuma estrutura substancial foi encontrada.

42.7  Agrupamento Aplicado a Grandes Volumenes de Dados (CLARA)

Similarmente a PAM, o método CLARA é também baseado na busca por k objetos representativos. Mas o algoritmo CLARA é desenhado especialmente para analisar grandes conjuntos de dados. Conseqüentemente, a entrada de CLARA deve ser um dataset do IDAMS.
Internamente, CLARA conduz dois passos. Primeiro uma amostra é coletada do conjunto de objetos (casos), e dividida em k clusters usando o mesmo algoritmo de PAM. Então, cada objeto não pertecendo a amostra é designado para o mais próximo objeto representativo, em relação aos k objetos. A qualidade desse agrupamento é definida como a distância média entre cada objeto e seu objeto representativo. Cinco dessas amostras são coletadas e depois submetidas a um cluster e, então, aquela com a menor distância média obtida é selecionada.
O agrupamento retido do conjunto de dados inteiro é, então, analisado mais profundamente. A distância final média, as distâncias média e máxima em relação a cada medoide são calculadas do mesmo jeito como em PAM (para todos os objetos, e não apenas aqueles selecionados na amostra). Silhuetas de clusters e estatísticas relacionadas são também calculadas do mesmo jeito que em PAM, mas apenas para objetos na amostra selecionada (pois o gráfico da silhueta completa seria muito grade para imprimir).

42.8  Agrupamento Difuso (FANNY)

Agrupamento difuso é uma generalização do particionamento, que pode ser aplicada ao mesmo tipo de dado que o método PAM, mas o algoritmo é de natureza diferente. Ao invés de designar um objeto para um cluster particular, FANNY dá o seu grau de "belonging" (coeficiente de filiação) para cada cluster, e, portanto, propicia informação muito mais detalhada da estrutura dos dados.
a)   Função objetivo. A técnica de agrupamento difuso usada em FANNY pretende minimizar a função objetivo
Função objetivo = k
å
c=1 
  

å
i 

å
j 
 uic2  ujc2  dij

2  
å
j 
 ujc2
onde uic e ujc são funções de filiação que estão sujeitas às restrições
uic ³ 0
para  i = 1, 2, ..., N;c = 1, 2, ..., k

å
c 
uic = 1
para  i = 1, 2, ..., N
O algoritmo minimizando essa função objetivo é iterativo e pára quando a função converge.
b)   Agrupamento difuso (filiações). Esses são os valores de filiação (coeficiente de filiação uic) que fornecem o menor valor da função objetivo. Eles indicam, para cada objeto i, quão intensamente ele pertence ao cluster c. Note que a soma dos coeficientes de filiação é igual a 1 para cada objeto.
c)   Coeficiente de partição de Dunn. Esse coeficiente, Fk, mede quão "duro" um agrupamento difuso é. Ele varia de um mínimo de 1/k para um agrupamento completamente difuso (onde todos uic=1/k) até um valor de 1 para um agrupamento inteiramente "duro" (onde todos uic=0 ou 1).
Fk = N
å
i=1 
k
å
c=1 
 uic2  /  N
d)   Coeficiente de partição normalizado de Dunn. A versão normalizada do coeficiente de partição de Dunn sempre varia de 0 até 1, seja qual for o valor de k escolhido.
F¢k = Fk  -  (1/k)

1  -  (1/k)
= k Fk  -  1

k  -  1
e)   Agrupamento duro mais próximo. Essa partição (= agrupamento "duro") é obtida ao se designar cada objeto ao cluster no qual ele possui o maior coeficiente de filiação. Siluetas de clusters e estatísticas relacionadas são calculadas da mesma maneira que em PAM.

42.9  Agrupamento Hierárquico Aglomerativo (AGNES)

Esse método pode ser aplicado ao mesmo tipo de dados que os dos métodos PAN e FANNY. Contudo, não é mais preciso especificar o número de clusters requeridos. O algoritmo constrói uma hierarquia do tipo árvore que contém, implicitamente, todos os valores de k, iniciando com N clusters e procedendo por meio de fusões sucessivas até que um único cluster seja obtido com todos os objetos.
No primeiro passo, os dois objetos mais próximos (i.e. com a menor dissimilaridade inter-objeto) são juntos para constituir um cluster com dois objetos, enquanto os outros clusters mantêm apenas um membro. Em cada passo sucessivo, os clusters mais próximos (com a menor dissimilaridade inter-objeto) são fundidos.
a)   Dissimilaridade entre dois clusters. No algoritmo AGNES, o método de média de grupo de Sokal e Michener (às vezes chamado "método da média de grupo-emparelhado não-ponderado") é usado para medir dissimilaridades entre clusters.
Faça  e Q denotar dois clusters e |Â| e |Q| denotar seus números de objetos. A dissimilaridade d(Â, Q) entre clusters  and Q é definida como a média de todas as dissimilaridades dij, onde i é qualquer objeto de  e j é qualquer objeto de Q.
d(Â, Q) = 1

|Â|   |Q|

å
i Π 

å
j Î Q 
 dij
b)   Ordenamento final de objetos e dissimilaridades entre eles. Na primeira linha, os objetos são listados na ordem em que eles aparecem na representação gráfica dos resultados. Na segunda linha, as dissimilaridades entre clusters que se juntam são impressas. Note que o número de dissimilaridades impressas é um a menos que o número de objetos N, porque há N-1 fusões.
c)   Banner de dissimilaridades. É uma representação gráfica dos resultados. Um banner consiste de estrelas e listas. As estrelas indicam as ligações e as linhas são repetições de identificadores de objetos. Um banner é sempre lido da esquerda para a direita. Cada linha com estrelas se inicia na dissimilaridade entre os clusters sendo fundidos. Existem escalas fixas acima e abaixo do banner, indo de 0.00 (dissimilaridade 0) a 1.00 (maior dissimilaridade encontrada). A maior dissimilaridade de fato (correspondendo a 1.00 no banner) é fornecida logo abaixo do banner.
d)   Coeficiente aglomerativo. A largura média do banner é chamada de coeficiente aglomerativo (AC). Ele descreve a intensidade da estrututra de agrupamento que foi encontrada.
AC = 1

N

å
i 
li
onde li é o comprimento da linha contendo o identificador do objeto i.

42.10  Agrupamento Hierárquico Divisivo (DIANA)

O método DIANA pode ser usado para os mesmos tipos de dados como no método AGNES. Apesar de AGNES e DIANA produzirem um output similar, DIANA constói a sua hierarquia na direção oposta, começando com um grande cluster contendo todos os objetos. A cada passo, ele divide um cluster em dois clusters menores, até que todos os clusters contenham apenas um único elemento. Isso significa que para N objetos, a hierarquia é construída em N-1 passos.
No primeiro passo, os dados são separados em dois clusters fazendo-se uso das dissimilaridades. Em cada passo subseqüente, o cluster com o maior diâmetro (ver 6.c acima) é dividido da mesma maneira. Depois de N-1 passos divisivos, todos os objetos estarão separados.
a)   Dissimilaridade média em relação a todos os outros objetos. Faça A denotar um cluster e |A| denotar seu número de objetos. A dissimilaridade média entre o objeto i e todos os outros objetos no cluster A é definida como em 6.g acima.
di = 1

|A| - 1

å
j Î A, j ¹ i 
dij
b)   Ordenamento final de objetos e diâmetros dos clusters. Na primeira linha, os objetos são listados na ordem em que eles aparecem na representação gráfica. Os diâmetros dos clusteres são impresso logo em baixo. Essas duas seqüências de números juntas caracterizam a hierarquia completa. O maior diâmetro indica o nível no qual o conjunto de dados completos é dividido. Os objetos a esquerda desses valores constituem um cluster, e os objetos no lado direito constituem um outro cluster. O segundo maior diâmetro indica a segunda divisão, e assim sucessivamente.
c)   Banner de dissimilaridades. Em relação ao método AGNES, trata-se de uma representação gráfica dos resultados. Ele também consiste de linhas de estrelas, e das listras que repetem os identificadores dos objetos. O banner é lido da esquerda para direita mas as escalas fixas acima e abaixo do banner variam agora de 1.00 (correspondendo ao diâmetro do conjunto de dados completo) e 0.00 (correspondendo ao diâmetro dos singletons). Cada linha com estrelas termina no diâmetro onde o cluster é dividido. O diâmetro real do conjunto de dados (correspondendo a 1.00 no banner) é fornecido logo abaixo do banner.
d)   Coeficiente divisivo. A largura média do banner é chamada de coeficiente divisivo (DC). Ele descreve a intensidade da estrutura de cluster encontrada.
DC = 1

N

å
i 
li
onde li é o comprimento da linha contendo o identificador do objeto i.

42.11  Agrupamento Monotético (MONA)

O método MONA é destinado a dados que consistam exclusivamente de variáveis binárias (dicotômicas) (aquelas que podem assumir apenas dois valores, e portanto xif=0 ou xif=1). Apesar do algoritmo ser do tipo divisivo hierárquico, ele não usa dissimilaridades entre objetos, e portanto, a matriz de dissimilaridade não é computada. A divisão entre clusters usa as variáveis diretamente.
A cada passo, uma das variáveis (digamos, f) é utilizada para dividir os dados pela separação de objetos i, para os quais xif=1 daqueles onde xif=0. No próximo passo, cada cluster obtido no passo anterior é novamente dividido, usando valores (0 e 1) de uma das variáveis remanescentes (diferentes variáveis podem ser usadas em diferentes clusters). O processo é continuado até que cada cluster contenha apenas um objeto, ou até que as variáveis remanescentes não possam separá-lo.
Para cada divisão, a variável mais fortemente associada com as outras variáveis é escolhida.
a)   Associação entre duas variáveis. A medida de associação entre duas variáveis f e g é definida pelo seguinte:
Afg = |afg dfg  -  bfg cfg|
onde afg é o número de objetos i com xif=xig=0, dfg é o número de objetos com xif=xig=1, bfg é o número de objetos com xif=0 e xig=1, e cfg é o número de objetos com xif=1 e xig=0.
A medida Afg expressa se as variáveis f e g fornecem divisões similares do conjunto de objetos, e pode ser considerada como um tipo de similaridade entre variáveis.
Para selecionar a variável mais fortemente associada com outras variáveis, a medida total Af é calculada para cada variável f da seguinte maneira:
Af =
å
g ¹ f 
Afg
b)   Ordenamento final de objetos. Os objetos são listados na ordem em que eles aparecem no gráfico de separação (banner). Os passos de separação e as variáveis utilizadas para separação são impressas abaixo de identificadores de objetos.
c)   Gráfico de separação (banner). Essa representação gráfica é bastante similar ao banner impressa por DIANA. O comprimento de uma linha de estrelas é agora proporcional ao número do passo onde a separação foi conduzida. Linhas de identificadores de objetos correspondem a objetos. Uma linha de identificadores que não continue no lado direito do banner sinaliza um objeto que se tornou um cluster singleton naquele passo correspondente. Linhas de identificadores plotados entre duas linhas de estrelas indicam objetos que pertencem a um cluster que não pode ser separado.

42.12  Referências

Kaufman, L., and Rousseeuw, P.J., Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc., New York, 1990.
Rousseeuw, P.J., Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis, Journal of Computational and Applied Mathematics, 20, 1987.