Validação de Agrupamentos
Marcílio Souto
DIMAp/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


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, 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
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


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 índice deve fazer sentido intuitivamente, deve ter uma base teórica e deve
ser prontamente computável
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:
E
E
i
j
R
S
i,j 
d
(m
i,m
j)

1
2
E

(
x

z
)

i
i
C
C
i x
i
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
Índice Davies-Bouldin (DB)

Com RSi,j, podemos calcular a similaridade relativa máxima
entre o grupo i e cada um dos outros (MRSi):
MRS i  max {RS i , j }
i j

O índice Davies-Bouldin (DB) para a partição {C1, C2 ... Ck} é a
média de MRSi (i = 1, 2 ... k):
1k
D
B
(
k
) 
M
R
S
i
k
i

1
Í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.
DBindex
Dataset I
2.5
Dataset II
2
1.5
DB(k)

1
0.5
0
2
4
6
8
Number of clusters(k)
10
12
Í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
CH =


 k
2 


N
z

z
 i i

i 1


k 1




 k n
2 
(
x

z
)
i
  j

i 1 j 1




nk




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
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


Seja B um outro grupo tal que diss(i,B) é a menor de todas


a(i) =
 diss(i,A) distância média de i para as outras instância do seu grupo
b(i) = min diss(i,B) (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 s (k )
 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 s (k )
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


Denote por N.j a soma de todas as linhas da coluna j


Número de instâncias no grupo i da partição A
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
I
n
s
t
â
n
c
i
a1
2
3
4
5
6
7
8
P
a
r
t
i
ç
ã
o
A
1
1
2
2
3
3
4
4
P
a
r
t
i
ç
ã
o
B
2
1
3
3
2
1
2
2
B
A
1
2
3
4
T
o
t
a
l
1
1
0
1
0
2
1
0
1
2
3
0
2
0
0
2
4
2
T
o
t
a
l
2
2
2
2
Medidas de Similaridade entre Partições:
Normalized Mutual Information
N

i
jN



2
N
o
g


i
jl


N
i
1j
1
i
.N
.j

N
M
I
(
A
,B
)
c
c
A
B
N

N


.j
i
.


N
o
g

N
o
g
 


il
.jl


N
 j
i
1
1
N

C
Ac
B
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
B
A
1
2
3
4
T
o
t
a
l
1
1
0
1
0
2
1
0
1
2
3
0
2
0
0
2
4
2

2
*
5
.
5
4
5
2
N
M
I
(
A
,
B
)


0
.
5
7
1
4

1
1
.
0
9
0
4

8
.
3
1
7
8
T
o
t
a
l
2
2
2
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.