Mineração de Dados: Agrupamento - Aula...

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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● Algoritmo K-Means● Atribuindo pontos ao centroide

mais próximo● Considere...

8

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

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

10

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

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

C 3 long=

∑x∈Ci

x

mi=

(0,56 )

1=0,56

C3 lat=∑x∈Ci

x

mi=

(0,04)

1=0,04

16

Mineração de dados: agrupamento

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

17

Mineração de dados: agrupamento

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

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

18

Mineração de dados: agrupamento

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

= 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

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

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

23

Mineração de dados: agrupamento

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

centroide mais próximo● c1 = (0,92; 0,49)● c2 = (0,04; 0,90)● c3 = (0,61; 0,04)

24

Mineração de dados: agrupamento

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

= 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

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

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

29

Mineração de dados: agrupamento

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

centroide mais próximo● c1 = (0,96; 0,54)● c2 = (0,04; 0,90)● c3 = (0,64; 0,09)

30

Mineração de dados: agrupamento

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

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

Mineração de dados: agrupamento

● 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

Mineração de dados: agrupamento

● 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