Avaliação de Clusteres
Parte II
AULA 14
Data Mining
Sandra de Amo
Como utilizar coesão e separação para
“melhorar” a clusterização

Um cluster com baixo grau de coesão pode
ser dividido em 2 subclusteres.

Dois clusteres que têm boa coesão mas que
não tem bom grau de separação podem ser
juntados para formar um único cluster.
Como avaliar objetos dentro de um
cluster
Como objetos individualmente contribuem para a
coesão e separação globais de um conjunto de
clusteres ?

Objetos que contribuem mais para a coesão e
separação estão mais no “interior” de seu cluster.

Objetos que contribuem pouco estão mais na
“fronteira” de seu cluster.
Coeficiente de Silhueta
Medida que combina coesão e separação
 Coeficiente de Silhueta de um cluster C
= média do coef. Silhueta dos objetos de C
 Coeficiente de Silhueta da clusterização =
média do coef. Silhueta de todos os objetos
 Coeficiente de Silhueta de um objeto –
depende da clusterização.

Coeficiente de Silhueta de um Objeto t
Dado um conjunto de Clusteres C = {C1,...,Ck} e um
objeto t do banco de dados
 Calcule at = distância média de t a todos os objetos
de seu cluster.
 Calcule bt



Para cada cluster C’ não contendo t, calcule t(C’) a
distância média entre t e todos os objetos de C’
bt = min {t(C’) | C’ não contém t }
Coef. Silhueta (t) = (bt – at ) / max(at , bt )
Coeficiente de Silhueta de objetos


Coeficiente de Silhueta varia de -1 a 1.
Valores negativos: at > bt (não desejados)


Distância média de t a objetos de seu cluster é
maior que distância média de t a objetos de outros
clusteres
Valores Ideais



Valores positivos
at bem próximo de zero
Coeficiente de silhueta bem próximo de 1
Dados agrupados em 10 clusters e os
coeficientes de silhueta dos pontos
Exercício 3
Considere as duas clusterizações do Exercicio 2.
Calcule o coeficiente de silhueta do objeto t
com relação a cada uma destas clusterizações.
t
t
Para casa: calcular o coeficiente de Silhueta global de cada uma das duas clusterizações e
decida qual a melhor.
Determinar o número ideal de clusteres
Técnica 1
 Executa-se o algoritmo K-means diversas vezes com
diferentes números de clusteres.
 Calcula-se o SSE global de cada clusterização obtida
 Plota-se os valores de SSE (eixo y) por número de
clusteres (eixo x)
 O número ideal de clusteres corresponde a um
momento onde se atinge um mínimo no gráfico e
logo em seguida há uma estabilização.
Exemplo : número de clusters = 10
Ponto minimo antes
da estabilização
Determinar o número ideal de clusteres
Técnica 2
 Executa-se o algoritmo K-means diversas vezes com
diferentes números de clusteres.
 Calcula-se o coeficiente de silhueta global de cada
clusterização obtida.
 Plota-se os valores dos coeficientes de silhueta (eixo
y) por número de clusteres (eixo x)
 O número ideal de clusteres corresponde a um
momento onde se atinge um pico no gráfico.
Exemplo: Número de Clusters = 10
Ponto de Pico
Determinar a tendência de clusteres
nos dados

Técnica óbvia de se testar a tendência dos dados



Aplique um algoritmo de clusterização
Avalie cada um dos clusteres obtidos
Caso pelo menos um dos clusteres é de boa qualidade

boa coesão e boa separação dos demais
Conclua que os dados apresentam alguma tendência de
clusteres.

Problema: os dados podem apresentar clusteres de
um tipo não detectável pelo algoritmo aplicado.
Determinar a tendência de clusteres
nos dados

Outra técnica


Aplicar diversos algoritmos de clusterização que
buscam clusteres de naturezas distintas: baseados
em protótipos, em densidade, em grafos
Se nenhum algoritmo apresenta clusteres com boa
coesão e boa separação pode-se concluir que os
dados não apresentam tendência de clusteres.
Estatística de Hopkins
Medida que permite verificar se um conjunto de dados tem
tendência de clusteres sem efetuar nenhuma clusterização

G = p objetos randomicamente distribuídos no espaço dos
dados (não necessariamente são objetos do BD !)


G = {g1, g2, ... , gp}
A = uma amostragem de p objetos pertencentes ao
banco de dados.

A = {a1, a2, ..., ap}
Estatistica de Hopkins
2
2
1
1
0,5
1,5
1,5
0,5
Para cada objeto (tanto de G quanto de A)
calcula-se a distância a seu vizinho mais próximo da base de
dados original
Estatistica de Hopkins
p
Σ ui
H=
Valores de distâncias minimas associados
a objetos de A (“reais” do banco de dados)
i=1
p
Σ ui
i=1
p
+
Σ wi
i=1
Valores de distâncias minimas associados
a objetos de G (artificialmente gerados)
Estatistica de Hopkins


0≤H≤ 1
H próximo de 1 : dados clusterizáveis
wi são pequenos, ui não necessariamente pequenos

H próximo de 0 : uniformemente distribuídos
Se os dados são regularmente espaçados, os wi tendem a ser
grandes.

H em torno de 0,5 : randomicamente distribuídos

Indica que a distribuição dos ui e dos wis são similares,
Exercício 4
Considerar o conjunto de dados do Ex. 2
Calcule a estatística de Hopkins destes dados
e conclua se estes dados apresentam alguma
estrutura de clusteres ou são aleatórios
Exemplo: dados não clusterizáveis
Número de amostras = 20
Número de experimentos = 100
H = 0,56
Dados são randômicos
Clusterização utilizando DBSCAN
Outlier !!
Outlier !!
Outlier !!
Clusterização utilizando K-Means
Exemplo de dados clusterizáveis
Número de amostras = 20
Número de experimentos = 100
H = 0,95
Exercício 5
1
2
3
4
5
6
7
8
9
12
13
11
14
15
16
10
17
Calcule a estatística de Hopkins para estes
dados para amostragens de 6 elementos,
fazendo 10 experimentos . Conclua se os dados
são clusterizáveis, randômicos ou uniform. distribuídos.
1
1,9
7,3
2
3,4
7,5
3
2.5
6,8
4
1,5
6,5
5
3,5
6,4
6
2,2
5,8
7
3,4
5,2
8
3,6
4
9
5
3,2
10
4,5
2,4
11
6
2,6
12
1.9
3
13
1
2,7
14
1.9
2,4
15
0,8
2
16
1,6
1,8
17
1
1
Exercício 6
1
2
3
4
1
1,9
7,3
2
3,4
7,5
3
2.5
6,8
4
1,5
6,5
5
3,5
6,4
6
2,2
5,8
7
3,4
5,2
8
3,6
4
9
5
3,2
10
4,5
2,4
11
6
2,6
12
1.9
3
13
1
2,7
14
1.9
2,4
15
0,8
2
16
1,6
1,8
17
1
1
5
6
7
8
9
12
13
11
14
15
16
10
17
Achar 3 clusters utilizando o k-means
1ª escolha das sementes: pontos 3, 9, 14
2a escolha das semestes: pontos 6,10,15
Exercício 7

Calcular o coeficiente de silhueta global de
cada uma das clusterizações. Analise os
resultados.
Exercícios 8 e 9

Exercicio 8: Aplique o algoritmo CURE nos dados do exercício 5 para
encontrar 3 clusters.
a) Faça 2 escolhas distintas para cada um dos parâmetros α e N (= número
de representantes de cada cluster).
b) Calcule o coeficiente de silhueta global de cada uma das clusterizações
e analise o resultado.

Exercício 9: Aplique o algoritmo DBSCAN nos dados do exercício 5.
a) Faça 2 escolhas distintas para cada um dos 2 parâmetros do algoritmo:
Eps, MinPts
b) Calcule o coeficiente de silhueta global de cada uma das clusterizações
e analise o resultado.
Referências
P-N Tan, M. Steinbach, V. Kumar:
Introduction to Data Mining, 2006.
 A. K. Jain and R. C. Dubes
Algorithms for Clustering Data. Prentice Hall
Advanced Reference Series. March 1988
Livro disponível em

http://www.cse.msu.edu/~jain/Clustering_Jain_Dubes.pdf
Capitulo 5:
Aplicações de Clusterização em Processamento de Imagens
Data Clustering: A Review
Jain et al. 1999 –
ACM Computing Surveys, Vol. 31, n. 3, Sep. 1999
Aplicações – Survey Jain et al. 1999