Agrupamento (clustering)
Tarefa descritiva que agrupa exemplos
(objetos) de acordo com suas características

Objetivo: agrupar objetos em clusters (agrupamentos) de modo que
objetos pertencentes a um mesmo cluster são mais similares entre
si de acordo com alguma medida de similaridade pré-definida,
enquanto que objetos pertences a clusters diferentes têm uma
similaridade menor

Consumo de um carro em função de suas características

Valor de um imóvel em função das características dele e do bairro
1
HAC
MD - junho/2008
Tarefas de MD
Data
Mining
Atividade
Preditiva
Classifica
ção
Regressã
o
Atividade
Descritiva
Regras de
Associaçã
o
Clusterin
g
Sumariza
ção
2
HAC
MD - junho/2008
Agrupamento

Tarefa de aprendizado não-supervisionado:
Exemplos não estão rotulados – não existe uma
classe conhecida considerada o atributo meta
3
HAC
MD - junho/2008
Exemplo
k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Xk1 0 0 0 1 1 1 2 3 4 5 5 5 6 6 6
Xk2 0 2 4 1 2 3 2 2 2 1 2 3 0 2 4
xk2
4
3
2
1
1
HAC
2
3
4
5
6
xk1
4
MD - junho/2008
Examplo – conjunto de dados
1)
0.5
3
16)
6
8
31)
6.5
7.5
2)
1
3
17)
7
6
32)
4
2
3)
2
3
18)
10
4
33)
6
3
4)
1
1
19)
10.5
4
34)
6.5
3
5)
1
2
20)
10
3
35)
6
2
6)
1
2.5
21)
9.5
3
36)
8
2
7)
1.5
2
22)
9.5
4
37)
2
5
8)
2
1
23)
9.5
5
38)
1
6
9)
2
2
24)
7
7
39)
1.5
7
10)
3
2
25)
7
7.5
40)
2
6
11)
6
6
26)
9.5
3.5
41)
2
7
12)
9
3
27)
10
5
42)
2.5
6.5
13)
9
4
28)
7.5
7.5
43)
2.5
7.5
14)
6.5
6.5
29)
7
8
44)
4
6
15)
6
7
30)
9
5
45)
5
7
5
HAC
MD - junho/2008
6
HAC
MD - junho/2008
Processo de agrupamento


1. seleção de exemplos e seleção ou construção
de atributos

seleciona atributos relevantes ou

constroi atributos representativos
2. Similaridade entre exemplos


3. Agrupamento

HAC
seleciona a medida de similaridade a ser utilizada,
que deve ser adequada ao domínio
aplicação do algoritmo de agrupamento
7
MD - junho/2008
Medidas de similaridade

medidas de distância


medidas de correlação


(para dados contínuos)
(para dados contínuos)
medidas de associação

(para dados discretos)
8
HAC
MD - junho/2008
Medidas de distância



atributos dos exemplos são considerados
como dimensões de um espaço
multidimensional
cada exemplo corresponde a um ponto no
espaço
similaridade entre dois pontos é a distância
entre eles
9
HAC
MD - junho/2008
Medidas de distância

Manhattan/city-block

D(x,y) = ∑(abs(xi – yi))
formato do cluster encontrado:
0,0
10
HAC
MD - junho/2008
Medidas de distância

euclidiana

D(x,y) = SQRT(∑(xi – yi)2)
formato do cluster encontrado:
0,0
11
HAC
MD - junho/2008
Formatos de clusters
Manhattan
Euclidiana
Chebychev
Mahalanobis
12
HAC
MD - junho/2008
13
HAC
MD - junho/2008
Algoritmo k-means

usuário define previamente o número k de
partições

repetir até que os cluster se estabilizem:

Escolher aleatoriamente k pontos que serão os centros dos
clusters iniciais – centróides

determinar para cada exemplo do conjunto de dados, o
cluster ao qual ele pertence, calculando a distância entre o
exemplo e o centro do cluster

calcular um novo centróide para cada cluster, que passa a
ser o novo centro
(os pontos iniciais não são os centros definitivos dos
clusters, mas sim uma tentativa inicial)
HAC
14
MD - junho/2008