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 clusterComo 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 tDado 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 3Considere as duas clusterizações do Exercicio 2. Calcule o coeficiente de silhueta do objeto tcom 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 clusteresTé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 antesda estabilização

Determinar o número ideal de clusteresTé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 HopkinsMedida 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 Hopkins2

2

1,5

1

1

0,5

1,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

0,5

Estatistica de Hopkins

Σi=1

p

ui

Σi=1

p

ui Σi=1

p

wi+

H =

Valores de distâncias minimas associados a objetos de G (artificialmente gerados)

Valores de distâncias minimas associados a objetos de A (“reais” do banco de dados)

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 4Considerar 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áveisNúmero de amostras = 20

Número de experimentos = 100

H = 0,95

Exercício 51

2

3

4 5

6

7

8

9

10

11

1213

14

1516

17

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

Calcule a estatística de Hopkins para estes dados para amostragens de 6 elementos, fazendo 10 experimentos . Conclua se os dadossão clusterizáveis, randômicos ou uniform. distribuídos.

Exercício 61 2

3

4 5

6

7

8

9

10

11

1213

14

15

16

17

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

Achar 3 clusters utilizando o k-means1ª escolha das sementes: pontos 3, 9, 142a 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 1988Livro disponível em http://

www.cse.msu.edu/~jain/Clustering_Jain_Dubes.pdfCapitulo 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