Mineração de Dados: Agrupamento - Aula 20professor.ufop.br/sites/default/files/janniele/files/...Algoritmo K-Means K-means(k centros) 1. Normalizar os registros do conjunto de treinamento

Mineração de Dados: Agrupamento - Aula 20

Profa Janniele Aparecida Soares Araujo

CSI462 – Sistemas de Apoio à Decisão

2

Mineração de dados: agrupamento

● Definição● Agrupamento é a tarefa de dividir os dados em grupos que tenham

significado e/ou sejam úteis● Exemplos de aplicações

● Encontrar grupos de genes com funções semelhantes● Encontrar uma alocação de antenas de telecomunicação● Segmentar clientes para atividades de marketing

3


● Definição● É uma técnica particional de agrupamento baseada em protótipos que

tenta encontrar um número especificado pelo usuário de grupos(k), que são representados pelos seus centroides

4


● Algoritmo K-Means● Encontrar K centroides que

melhor separam o conjunto de dados

● K é o número de grupos desejados

● K é um parâmetro especificado pelo usuário

5


● Algoritmo K-Means● Define-se K centroides iniciais

● De forma aleatória● Abordagens mais elaboradas

● Repita● Atribuir cada ponto a seu centroide mais próximo● Cada coleção de pontos atribuídos a um centroide é um grupo● Recalcular o centroide de cada grupo baseado nos pontos atribuídos

● Até que os centroide não mudem

6


● Algoritmo K-Means

K-means(k centros)

1. Normalizar os registros do conjunto de treinamento e selecionar k pontos como centroide iniciais

2. faça

1. Agrupar cada registro x(a) do conjunto de treinamento no grupamento, de acordo com a menor distância do registro ao centro de agrupamento da iteração corrente

2. Atualizar a matriz dos centros de agrupamentos pela média das coordenadas dos pontos em cada agrupamento

3. até que os centroides não mudem ou 1% de diferença

fimK-means

7


● Algoritmo K-Means● Atribuindo pontos ao centroide

mais próximo● Considere...

8


● Algoritmo K-Means● Como saber qual o centroide mais próximo?

● Distância euclidiana

● Como saber se um agrupamento está bom?● Soma do erro quadrado

● Como recalcular o centroide?● Média dos pontos que representa

d (x , y )=√∑k=1

n

(x k− y k)2

SSE=∑i=1

K

∑x∈Ci

d (ci , x )2

ci=∑x∈Ci

x

mi

9


● Algoritmo K-Means: exemplo● Agrupamento de correntes de ar, normalização

10


● Algoritmo K-Means: exemplo● Geração de K centroides aleatórios (K = 3)● c1 = (0,72; 0,31), c2 = (0,43; 0,81), c3 = (0,31; 0,17)

11


● Algoritmo K-Means: exemplo● It.1: Atribuir cada ponto ao

centroide mais próximo● c1 = (0,72; 0,31) ● c2 = (0,43; 0,81)● c3 = (0,31; 0,17)

12


● Algoritmo K-Means: exemplo● It.1: Calcular custo

= 0, 352 + 0, 352 + 0, 312 + 0, 352 + 0, 282 + 0, 332 + 0, 242 + 0, 052 + 0, 392 + 0, 402 + 0, 402 + 0, 442

= 1,38

SSE=∑i=1

K

∑x∈Ci

d (ci , x )2

13


● Algoritmo K-Means: exemplo● It.1: Recalcular os centroides

C 1 long=

∑x∈Ci

x

mi=

(1,00+0,97+0,93+0,95+0,61+0,66+0,74)

7=0,84

C1 lat=∑x∈Ci

x

mi=

(0,52+0,56+0,53+0,57+0,00+0,07+0,26)

7=0,36

14



C 2 long=

∑x∈Ci

x

mi=

(0,05+0,08+0,03+0,00)

4=0,04

C2 lat=∑x∈Ci

x

mi=

(0,89+1,00+0,81+0,89)

4=0,90

15



C 3 long=

∑x∈Ci

x

mi=

(0,56 )

1=0,56

C3 lat=∑x∈Ci

x

mi=

(0,04)

1=0,04

16


● Algoritmo K-Means: exemplo● It.1: Representação gráfica

17



centroide mais próximo● c1 = (0,84; 0,36)● c2 = (0,04; 0,90)● c3 = (0,56; 0,04)

18



= 0,232 + 0,232 + 0,202 + 0,242 + 0,002 + 0,062 + 0,102 + 0,142 + 0,012 + 0,112 + 0,092 + 0,042

= 0,26

SSE=∑i=1

K

∑x∈Ci

d (ci , x )2

19



C 1 long=

∑x∈Ci

x

mi=

(1,00+0,97+0,93+0,95+0,74)

5=0,92

C1 lat=∑x∈Ci

x

mi=

(0,52+0,56+0,53+0,57+0,26)

5=0,49

20



C 2 long=

∑x∈Ci

x

mi=

(0,05+0,08+0,03+0,00)

4=0,04

C2 lat=∑x∈Ci

x

mi=

(0,89+1,00+0,81+0,89)

4=0,90

21



C 3 long=

∑x∈Ci

x

mi=

(0,56+0,61+0,66)

3=0,61

C3 lat=∑x∈Ci

x

mi=

(0,04+0,00+0,07 )

3=0,04

22



23




24



= 0,092 + 0,082 + 0,052 + 0,092 + 0,052 + 0,042 + 0,062 + 0,262 + 0,012 + 0,112 + 0,082 + 0,042

= 0,11

SSE=∑i=1

K

∑x∈Ci

d (ci , x )2

25



C 1 long=

∑x∈Ci

x

mi=

(1,00+0,97+0,93+0,95)

4=0,96

C1 lat=∑x∈Ci

x

mi=

(0,52+0,56+0,53+0,57)

4=0,54

26



C2 lat=∑x∈Ci

x

mi=

(0,89+1,00+0,81+0,89)

4=0,90

C 2 long=∑x∈Ci

x

mi=

(0,05+0,08+0,03+0,00)

4=0,04

27



C 3 long=

∑x∈Ci

x

mi=

(0,56+0,61+0,66+0,74)

4=0,64

C3 lat=∑x∈Ci

x

mi=

(0,04+0,00+0,07+0,26)

4=0,09

28



29




30



C 2 lat=∑x∈Ci

x

mi=

(0,89+1,00+0,81+0,89)

4=0,90

C1 long=∑x∈Ci

x

mi=

(1,00+0,97+0,93+0,95)

4=0,96

C 1 lat=∑x∈Ci

x

mi=

(0,52+0,56+0,53+0,57)

4=0,54

C3 long=

∑x∈Ci

x

mi=

(0,56+0,61+0,66+0,74)

4=0,64

C 3 lat=∑x∈Ci

x

mi=

(0,04+0,00+0,07+0,26)

4=0,09

C 2 long=∑x∈Ci

x

mi=

(0,05+0,08+0,03+0,00)

4=0,04

31


● Algoritmo K-Means: exemplo● Centroides não mudaram!● Logo a solução final é:

● c1 = (0,96; 0,54)● c2 = (0,04; 0,90)● c3 = (0,64; 0,09)

● Custo = 0,11

32


● Exercício● Utilize o algoritmo K-Means

para encontrar as 3 classes existentes

● Calcule e mostre a posição dos centroides durante todas as iterações do algoritmo

33

Bibliografia

● Introdução ao Data Mining. Steinbach, Michael; Kumar, Vipin; Tan, Pang-ning, Rio de Janeiro: Ed. Ciência Moderna, 2009.

● Notas de Data Mining. Fonseca, G.H.G, Universidade Federal de Ouro Preto, 2013

Documents

Mineração de Dados: Agrupamento - Aula 20professor.ufop.br/sites/default/files/janniele/files/...Algoritmo K-Means K-means(k centros) 1. Normalizar os registros do conjunto de treinamento