Avaliação de
Clusteres – Parte I
AULA 13
DATA MINING
Sandra de Amo
O que avaliar ?




Os dados são “clusterizáveis” ? Isto é, existem
estruturas não-randômicas nos dados ?
Qual o número ideal de clusteres ?
Os clusteres encontrados realmente correspondem a
clusteres “reais” ?
Dados dois conjuntos de clusteres para os mesmos
dados, qual é o melhor ?
Como avaliar ?

Como medir a



“tendência de clusteres”,
o número ideal de clusteres,
a qualidade da clusterização,
sem a “visualização gráfica” dos dados (só factível até
3 dimensões) ?
Medidas de Avaliação

Não-supervisionadas




Medem a qualidade de uma clusterização sem utilizar
medidas externas aos dados
Medidas de Coesão
Medidas de Separação
Supervisionadas

Medem a qualidade de uma clusterização utilizando
medidas externas aos dados, por exemplo, dados de testes
etiquetados com um atributo classe.
Fórmula geral de avaliação
Seja C = {C1, ...., Ck} um conjunto de clusteres
k
Avaliação(C) =i Σ
w
Avaliação(Ci)
i
=1
Avaliação global de C
pesos
Avaliação individual do
cluster Ci
Clusteres baseados em Protótipos

Medidas de Avaliação = coesão e separação
Coesão
(individual)
Mede o quanto os objetos
dentro de um cluster se aglomeram
perto do centro do cluster
Separação
(inter clusteres)
Mede o quanto os centros dos clusteres
estão bem separados entre si
Clusteres baseados em Protótipos

Coesão(Ci) = Σ proximidade(x,ci)
x ɛ Ci
ci = centroide (centro de gravidade) de Ci


Separação(Ci,Cj) = proximidade(ci,cj)
Separação (Ci) = proximidade(ci,c)
c = centro de gravidade do conjunto total de dados
Proximidade : noção que pode variar dependendo da aplicação
Exemplo:
SSE mede coesão quando a função de proximidade é o quadrado da distância.
Clusteres baseados em Grafos

Medidas de Avaliação = coesão e separação
Coesão
(individual)
Mede o quanto os objetos
dentro de um cluster estão juntos
Separação
(inter clusteres)
Mede o quanto cada elemento de
um cluster está afastado dos
elementos de outros clusteres.
Clusteres baseados em grafos

Coesão(Ci) = Σ proximidade(x,y)
x,y ɛ Ci

Separação(Ci,Cj) = Σ proximidade(x,y)
x ɛ Ci, y ɛ Cj
Proximidade: noção que pode variar dependendo da
aplicação
Coesão e Separação globais
Medida
I1
Fórmula para os clusters
individuais (Ci)
Σ
proximidade(x,y)
x,y ɛ Ci
I2
Σ
proximidade(x,ci)
x ɛ Ci
E1
proximidade(ci,c)
c = centro de gravidade do
conjunto total de dados
G1
k
Σ
i=1
i≠j
k
Σ prox.(x,y)
j=1
x ɛ Ci , y ɛ Cj
Peso
1/mi
mi=tamanho de Ci
1
Tipo
Coesão baseada
em grafo
Coesão baseada
em protótipo
mi
Separação
baseada em
protótipo
1
Separação
baseada grafo
Σ prox.(x,y)
x,y ɛ Ci
Exemplos de Medidas de Coesão

Baseada em protótipo

SSE : noção de proximidade é dada pelo quadrado da distância
euclidiana dist

SSE(Ci) = Σ dist(x,ci)2
x ɛ Ci

SSE = Σ SSE(Ci)
i = 1,...,k


Baseada em grafos

Σ dist(x,y)2
x,y ɛ Ci
Relação entre as duas medidas
SSE(Ci) = 1 Σ dist(x,y)2
2mi x,y ɛ Ci
Exemplo de Medidas de Separação

Baseada em Protótipos
 SSB =
Σ mi dist(ci,c)2
onde mi = tamanho de Ci
i = 1,...,k

Se os clusters têm mesmo tamanho mi = m/k
 SSB =
1/2k Σ m/k dist(ci,cj)2
i,j = 1,...,k

Relação entre coesão e separação
(baseada em protótipos)
SSE + SSB = TSS = Σ
Σ
i = 1,...,k x ɛ Ci
Número constante
Independe dos clusteres
Só depende dos dados iniciais
dist(x,c)2
Exercício 1

Considere o seguinte conjunto de objetos
D = {(1,2), (1.3, 2.5), (2,2.2), (5,1), (5.5, 1.3), (5.3,2.4)}
Considere C = {C1, C2} onde
C1 = {(1,2), (1.3, 2.5), (2,2.2)}
C2 = {(5,1), (5,5, 1,3), (5,3.2,4)}
Calcule a coesão e separação do conjunto de clusteres C,
utilizando as medidas SSE e SSB respectivamente.
Calcule TSS para o conjunto de dados D (não depende de C).
Mostre que SSE + SSB = TSS
Exercício 2 : Comparação de medidas de agrupamentos
(baseados em protótipos e baseados em grafos)
Clusterização 2
obtida utilizando um método
baseado em grafos
Clusterização 1
obtida utilizando um método
baseado em grafos
Qual a que tem a melhor coesão segundo I1 ? E a melhor separação segundo G1?
Proximidade = quadrado da distância.
Dados para Exercício 2
X
Y
1,5
1,4
1,5
2,5
2,5
1,3
4
1,3
3,5
2,1
3,8
3,3
5,2
3