Validação de Agrupamentos
Marcílio SoutoDIMAp/UFRN
Validação de Agrupamentos
No contexto do Aprendizado Supervisionado, há uma variedade grande de medidas para avaliar a qualidade do modelo gerado
Acurácia, precisão, taxa de falso-positivo, recall, .... Para a análise de agrupamentos, a questão análoga é:
Como avaliar a “qualidade” dos grupos resultantes? Problema: “clusters are in the eye of the beholder”!
Mesmo assim, por que precisamos avaliá-los? Evitar a descoberta de padrões em ruído Comparar diferentes algoritmos de agrupamento Comparar duas partições Comparar dois grupos (clusters)
Validação de Agrupamentos: Diferentes Aspectos
Determinar a tendência de agrupamento (clustering tendency) de um conjunto de dados
Ou seja, identificar se uma estrutura não-aletatório de fato existe nos dados
A maioria dos algoritmos de agrupamento encontram grupos mesmo quando os dados são aleatórios
Comparar os resultados de uma análise de agrupamento com resultados externos conhecidos
Por exemplo, com os rótulos das classes de uma partição que se sabe previamente existir nos dados
Avaliar quão bem os resultados de uma análise de agrupamento se ajustam aos dados SEM usar informações externas
Ou seja, apenas com as próprias instâncias do conjunto de treinamento Comparar diversos algoritmos de agrupamento ou determinar o valor mais
apropriado de algum parâmetro do algoritmo (e.g., número de grupos)
Medidas para Validação de Agrupamentos
Medidas numéricas que são aplicadas para avaliar os vários aspectos da validação de agrupamentos são classificadas em três grupos:
Índices Externos Usados para avaliar o agrupamento gerado de acordo com uma
estrutura pré-especificada, imposta ao conjunto de dados Índice Rand ajustado (adjusted Rand) e índice de Jaccard
Índices Internos Usados para medir a qualidade de um agrupamento com base
apenas nos dados originais (instâncias ou matriz de similaridade) Índice Davies-Bouldin, Índice Dunn, Silhuetas, ...
Índices Relativos Usados para comparar diversos agrupamentos para decidir qual
deles é o melhor em algum aspecto Em geral, pode ser qualquer um dos índices acima definidos
Uso de Índices de Validação: Aspectos Importantes
Definição do índice O índice deve fazer sentido intuitivamente, deve ter uma base
teórica e deve ser prontamente computável Distribuição de probabilidade base
Uma distribuição base é uma distribuição derivada de uma população que não possui estrutura
Teste para verificar estrutura não-aleatória O valor de um índice é comparado com um threshold que
estabelece um certo nívell de significância. O threshold é definido a partir da distribuição base, que
raramente é conhecida na teoria Teste para verificar um tipo específico de estrutura
A habilidade do índice de validação de recuperar uma estrutura conhecida indica seu poder estatístico
Medidas para Validação de Agrupamentos: Estruturas
Os tipos de índices definidos anteriormente podem ser usados para avaliar os seguintes tipos de estrutura
Hierarquia Partição Grupo
O foco dessa aula será em índices (internos, externos e relativos) para partições
Índices Relativos
Com os íındices relativos objetiva-se determinar qual partição entre várias melhor se ajusta aos dados
Tanto os índices internos como os externos podem ser utilizados como índices relativos
Internos Estatística Hubert Γ modificada (Jain & Dubes 1988) Família de índices Dunn (Halkidi et al. 2002) Índice Davies-Bouldin (DB) (Jain & Dubes 1988) Silhouettes (Rousseeuw 1987) Índice de Calinski-Harabasz (CH) (Calinski & Harabasz 1974) Informação Mutual Normalizada (NMI) (Sterhl & Ghosh 2002)
Externos Rand Ajustado (AR) (Hubert & Arabie 1985)
Índices Relativos baseados em Índices Internos
A forma mais comum de utilização dos índices internos como índices relativos é na determinação do número de grupos mais adequado
Neste caso, o algoritmo de agrupamento é executado para vários valores diferentes para o parâmetro k representando o número de grupos
Em seguida, os valores do índice obtidos a partir das partições geradas são plotados em função de k
Nesse contexto, o melhor número de grupos é dado pelo mínimo ou o máximo dessa função, dependendo de como o índice foi definido
Índices Relativos baseados em Índices Externos
A forma mais comum de utilização dos índices externos como índices relativos é no cálculo de similaridade entre duas partições
Algoritmos de agrupamento são geralmente construídos para otimizar diferentes tipos de função objetivo
Essas funçõe são escolhidas de tal a modo a representarem o conceito de “bom agrupamento”
Por exemplo, um “bom grupo” pode ser definido como um que seja compacto (as distâncias entre a instâncias em um grupo para seu centróide são pequenas)
Uma outra definição intuitiva de “bom grupo” é que cada instância compartilhe o mesmo rótulo de grupo que seu vizinho mais próximo
Algoritmos que implementem estas duas definições podem levar a geração de partições complementamente diferentes para o mesmo conjunto de dados
Índices Relativos baseados em Índices Externos
Nesse conexto de análise comparativa, uma grande limitação no uso de índices internos é o fato de que eles em geral favorecem algum tipo de função objetivo
Portanto, comparação de algoritmos que otimizam critérios diferentes só faz sentido quando temos rótulos das classes de uma partição que se sabe previamente existir nos dados (padrão ouro ou partição a priori)
Índices Externos
Índices Relativos
Baseados em Índices Internos
Quantos grupos há nos meus dados?
Índice Davies-Bouldin (DB)
Dada uma partição {C1, C2 ... Ck}, definimos a similaridade relativa entre dois grupos, Ci e Cj, como:
em que d(mi, mj) é a distância entre as médias do grupo i e grupo j, mi e mj; Ei é a distância quadrada média dos pontos no i-ésimo grupo para o centroide (média) desse grupo
),(,ji
jiji mmd
EERS
iCx
ii
i zxC
E 2)(1
Índice Davies-Bouldin (DB)
Com RSi,j, podemos calcular a similaridade relativa máxima entre o grupo i e cada um dos outros (MRSi):
O índice Davies-Bouldin (DB) para a partição {C1, C2 ... Ck} é a média de MRSi (i = 1, 2 ... k):
k
iiMRS
kkD B
1
1)(
}{max , jiji
i RSMRS
Índice Davies-Bouldin (DB)
The DB index is plotted against the number of clusters
The partition that minimized DB is chosen as the best partition.
In the case of hierarchical clustering, the numbers {DB(k)} are obtained by cutting a dendrogram at levels that produce from 2 to kmax clusters.
Índice Davies-Bouldin (DB)
The smaller DB(k), the better the partition.
To find the optimal level of clustering, we can draw a diagram DB – k and search for a minimum.
DB index
0
0.5
1
1.5
2
2.5
2 4 6 8 10 12
Number of clusters (k)
DB
(k)
Dataset I
Dataset II
Índice Davies-Bouldin (DB)
Índice Davies-Bouldin (DB): Características
O valor desse índice é 0 para a partição trivial, em que cada instância pertence a um grupo individual Deve ser usado apenas quando cada grupo
contém um número razoável de instâncias O DB deve ser aplicado apenas quando os dados se
agrupam em aglomerados hiper-esféricos Não é apropriado para partições com grupos de
formas arbitrárias
Índice de Calinski-Harabasz (CH)
O índice CH é o com melhor desempenho no estudo de (Milligan & Cooper 1985) envolvendo 30 procedimentos de validação para determinar o melhor número de grupos
em que Ni é o número de instâncias no grupo i, e z é o centróide de todo o conjunto de dados
O melhor número de grupos é aquele que maximiza CH
11
2
k
Nk
ii zz i
kn
k
i
n
j1 1
2)( ij zx
CH =
Silhouettes
O índice Silhouette combina a idéia de coesão e separação Para cada instância i Seja diss(i,C) a dissimilaridade média entre i e cada elemento
no grupo C Seja A o grupo ao qual a instância i pertence
a(i) = diss(i,A) distância média de i para as outras instância do seu grupo
Seja B A um outro grupo tal que diss(i,B) é a menor de todas b(i) = diss(i,B) min (distância média de i para as instância de um
outro grupo) A silhouette para a instância i é dada por
s(i) = 1 - [a(i)/b(i)]; ou s(i)=[b(i)/a(i)] - 1, se a(i) >= b(i)
Silhouettes
O valor da silhoutte de uma instância está no intervalo [ - 1, 1] Se uma instância está bem situada dentro de sue grupo,
sua silhoutte apresentará um valor próximo de 1 Em contraste, um valor próximo de -1 indica que a instância
deveria ser associado a outro grupo Além da silhouette de cada objeto pode ser calculada:
A silhouette de cada grupo A largura média da silhouette
O valor médio da silhouette sobre todas as instâncias do conjunto de dados
Um modo de escolher o melhor valor de k (número de grupos) é selecionar aquele que resulta no maior valor de
)(ks
)(ks
Silhouettes
As silhouettes são apropriada nos casos em que:
A medidade proximidade está em uma escala de razão (e.g., distância euclidiana)
Identificação de grupos compactos e bem separados
os dados se agrupam em aglomerados hiper-esféricos
Índices Relativos
Medidas de Similaridade entre Partições
Introdução
Considere uma tabela de contingência para as partições A e B com as seguintes características
As linhas da tabela correspondem aos grupos em A e as colunas aos grupos em B
Denote por Nij a (i,j)-ésima célula da tabela, a qual contém o número de instâncias que estão tanto no grupo i da partição A quanto no grupo j da partição B
Denote por Ni. a soma de todas as colunas da linha i Número de instâncias no grupo i da partição A
Denote por N.j a soma de todas as linhas da coluna j O número de instâncias no grupo j da partição B
Seja cA e cB, respectivamente, o número de grupos na partição A e na partição B
Tabela de Contingência
Instância 1 2 3 4 5 6 7 8Partição A 1 1 2 2 3 3 4 4Partição B 2 1 3 3 2 1 2 2
BA 1 2 3 Total
1 1 1 0 22 0 0 2 23 1 1 0 24 0 2 0 2
Total 2 4 2
Medidas de Similaridade entre Partições: Normalized Mutual Information
A B
A B
c
i
c
j
jj
ii
C
i
c
j ji
ijij
N
NN
N
NN
NN
NNN
1 1
..
.
1 1 ..
loglog
log2
B)NMI(A,
Se A e B são idênticas, então NMI terá seu valor máximo de 1. Se A e B são independentes, então NMI tende a 0.
Medidas de Similaridade entre Partições: Normalized Mutual Information
5714.03178.80904.11
5452.5*2B)NMI(A,
BA 1 2 3 Total
1 1 1 0 22 0 0 2 23 1 1 0 24 0 2 0 2
Total 2 4 2
Medidas de Similaridade entre Partições: Índice Rand Ajustado
Medidas de Similaridade entre Partições: Índice Rand Ajustado
O índice externo Rand corrigido pode assumir valores entre -1 e 1, 1 indicando uma concordância perfeita entre partições, e valores próximos a 0 ou negativos correspondendo a concordâncias encontradas ao acaso
Bibliografia
Jain, A K. & Dubes, R. C. (1988). Algorithms for Clustering. Cap. IV - Cluster Validity, pp. 143-222. Prentice Hall.
Kuncheva, L. I. (2004). Combining Pattern Classifiers. Sec. 8.3 - Combing Clustering Results, pp. 251-264. Wiley.