Análise de Clusters – Introdução
Método K-means
AULA 14
DATA MINING
Agrupamento -Análise de Clusters
a1 a
F 1 0 1 1
a2 b M 0 0 1 1
. c F 1 1 1 0
.
d F 1 0 0 0
.
e M 1 1 0 1
Nome
Sexo
Doença X
a1
a2
a3
a7
a10 a a9
5
a8
a4
a11
Doença Y
a6
Doença Z
Sintomas
Número de Clusters = 3
Conceito = Doença
Análise de Clusters: Objetivos


Compreensão dos dados

Existe algum conceito inerente a cada grupo.

Que conceito é este ?
Utilidade em outras tarefas
Cada cluster pode ser representado por um objeto protótipo que
caracteriza o cluster

Sumarização : Algoritmos aplicados em grandes volumes de dados
podem ser aplicados apenas aos protótipos, reduzindo assim o tempo
de execução

Compressão : o objeto protótipo representa cada objeto dentro do
seu cluster

Otimização do cálculo dos vizinhos mais próximos:
Se dois protótipos estão distantes então os objetos nos respectivos
clusters também estão distantes.
Os objetos mais próximos do objeto X devem ser procurados no
cluster correspondente ao protótipo mais próximo de X.
Clusterização versus Classificação

Classificação

Aprendizado Supervisionado




Amostras de treinamento são classificadas
Número de Classes é conhecido
Aprendizado por Exemplo
Clusterização


Aprendizado Não Supervisionado
Aprendizado por Observação
Tipos de Agrupamentos

Particionais versus Hierárquicos



Exclusivos versus Não-exclusivos versus Fuzzy




Particionais: clusters são disjuntos
Hierárquicos:

Clusters possuem subclusters – organizados em árvore

Cada cluster (nó interno da árvore) é a união de seus filhos
Exclusivos: cada objeto pertence a um único cluster
Não exclusivos: existem objetos que são associados a diferentes clusters
Fuzzy : objetos são associados a um cluster com um certo grau de pertinência
Completos versus Parciais

Completos: cada objeto pertence a algum cluster

Parciais: existem objetos que não estão associados a nenhum cluster
(outliers, ruidos, sem interesse)
O que é um cluster ?
Como definir a noção de Cluster ?
Protótipos
Bem separados
Um cluster é um conjunto de objetos no
qual cada objeto está mais próximo (ou é
mais similar) a objetos dentro do cluster do
que qualquer objeto fora do cluster.
Baseados em Protótipos
Um cluster é um conjunto de objetos no
qual cada objeto está mais próximo ao
protótipo que define o cluster do que dos
protótipos de quaisquer outros clusters.
Em geral: Protótipo = centróide
Os clusters encontrados tendem a ser globulares.
O que é um cluster ?
Baseados em Grafos
Boa definição quando os clusters
são irregulares e entrelaçados.
Problema: quando os dados têm ruidos,
Pode haver distorções nos clusters
Exemplo: dois clusters distintos podem
se transformar num único cluster (os dois
clusters são ligados através de uns poucos
Outliers, como mostrado na figura).
- Os dados podem ser representados por um
grafo, onde os vértices são objetos e existe
aresta de a para b se a está mais perto de b do
que de outros objetos no conjunto.
- Estar perto significa estar diretamente
conectado.
- Um cluster é uma componente conexa do
grafo, isto é, um conjunto de objetos que
estão conectados um no outro, mas que não
estão conectados com nenhum outro objeto
de outro cluster.
a
b
a está perto de b
d(a,b) < α
O que é um cluster ?
Esta definição é utilizada quando
os clusters são irregulares ou entrelaçados
e quando ruido e outliers estão presentes.
Uma definição baseada em grafos não seria
adequada neste caso, pois os outliers
poderiam fazer uma ponte entre as regiões
transformando-as em um único cluster.
Baseados em Densidade
Os outliers seriam absorvidos nos clusters.
Um cluster é uma região densa rodeada
por uma região de baixa densidade.
No exemplo, temos 3 clusters = 3 regiões densas
A ‘’ponte’’ de outliers ligando as duas esferas
foi ‘’dissolvida’’ nos outros outliers.
O que é um cluster ?
Clusters Conceituais
Os objetos de um cluster possuem uma
propriedade que é derivada do conjunto
total de objetos. No exemplo, podemos distinguir
3 clusters: o triângulo, o retângulo e os dois anéis.
Um cluster representa um conceito.
Definição utilizada em Reconhecimento de Padrões.
Tipos de Técnicas de Clusterização

Particionamento


K-means:
K-medóides: PAM, CLARA, CLARANS
Particional e baseada em protótipos.
Encontra um número k de clusters (k é
fornecido pelo usuário) que são representados
por seus centróides.
Particionamento

BD com n amostras

K = número de clusters
desejado ( parâmetro )
K≤n
Tipos de Técnicas de Clusterização
Hierárquicas Aglomerativas
Produzem agrupamentos hierárquicos
começando com clusters unitários e
repetidamente aglutinando clusters próximos
dois a dois até chegar no número k de clusters
solicitado pelo usuário.
Exemplos: BIRCH, CURE, CHAMELEON,
ROCK...)

Hierárquicos Aglomerativos

BD com n amostras

K = número de clusters
desejado ( parâmetro )
K≤n
Tipos de Técnicas de Clusterização
Hierárquicas Divisórias
Produzem agrupamentos hierárquicos
começando com um cluster único contendo
todo o conjunto de objetos e repetidamente
dividindo os clusters em duas partes de
acordo com algum critério de similaridade até
chegar no número k de clusters solicitado pelo
usuário.
Exemplo: algoritmo DIANA

Tipos de Técnicas de Clusterização

Por densidade




Adequados para identificar clusters de formato arbitrário.
Robustos com respeito a ruídos e outliers.
Regiões densas = clusters
Regiões de baixa densidade = ruídos e outliers
Um ponto pertence a uma região densa se numa
vizinhança de raio α pequeno existem pelo menos M
objetos (M dado pelo usuário).
O número k de clusters não precisa ser dado pelo usuário.
É determinado pelo algoritmo.
Exemplos: DBSCAN, OPTICS, DENCLUE
Dados de Treinamento
Matriz de dados padronizados
Matriz de dissimilaridade
x11
x12
x13
...
x1n
0
0
...
0
x21
x22
x23
...
x2n
d(x1,x2)
0
...
0
x31
x32
x33
...
x3n
d(x1,x3) d(x2,x 3)
...
0
...
...
...
...
...
...
0
xp1
xp2
xp3
...
xpn
...
0
Distância Euclidiana
d(x,y) =
...
...
d(x1,xp) d(x2,x p)
(x1-y1)2 + (x2-y2)2 + .... + (xp – yp)2
Outras distâncias : Manhattan, Minkowski, Ponderada
Outras distâncias



Manhattan
Minkowski
d(x,y) =
m
(x1-y1)m + (x2-y2)m+ .... + (xp – yp)m
Distância em geral
Qualquer função d(x,y)  N que satisfaz as seguintes
propriedades:





d(x,y) = |x1-y1|+ |x2-y2| + .... + |xp – yp|
d(i,j) ≥ 0
d(i,i) = 0
d(i,j) = d(j,i)
d(i,k) ≤ d(i,j) + d(j,k) (desigualdade triangular)
Distância poderada
d(x,y) =
p1 (x1-y1)2 + p2 (x2-y2)2+ .... +pk (xk – yk)2
Outras medidas de similaridade

Para documentos




p1,p2, p3, ... : vocabulário (palavras)
Um documento = vetor (n1,n2,...,nk)
ni = número de vezes que a palavra i aparece no
documento
Medida de similaridade entre documentos d1,d2
d1
= cos(d1,d2) = d1.d2
θ
|d1| |d2|
d2
Exercicio


Sejam X1 = (1,2) e X2 = (4,6). Calcula as
distâncias euclidianas, Minkowski com m = 3
e Manhattan entre X1 e X2.
Ilustre no plano xy os segmentos
representando tais distâncias.
Algoritmo K-means
Exemplo K = 3
+
+
+
2ª
1ª Iteração
Algoritmo K-Means
Selecione k pontos como centróides iniciais
2.
Repeat
3.
Forme k clusters associando cada objeto a seu
centróide mais próximo
4.
Recompute o centróide de cada cluster
5.
Until Centróides não apresentam mudanças
Centróide = centro de gravidade do cluster
Coordenada i = média aritmética das coordenadas i de
seus objetos constituintes.
1.
Observações


Boa parte dos clusters já convergem nos
primeiros passos do algoritmo, ficando
somente uma quantidade pequena de clusters
que ainda modificam.
Assim, a condição 5 do algoritmo é
substituida por : “até que somente 1% dos
objetos mudam de clusters”.
Objetivo


Erro (x) = d(x,ci) = distância de x até o centróide ci de
seu cluster Ci
Objetivo do método K-means


Minimizar a soma dos erros (SSE = sum of square errors)
Maximizar a coesão (no caso de documentos)
K
SSE = Σ xΣɛ Cid(x,ci)2
i=1
Coesão
K
= Σ Σ coseno(x,ci)2
i = 1 x ɛ Ci
Observação


Nem sempre o K-means consegue minimizar
o SSE
Isto depende muito da escolha dos centróides
iniciais.
Técnicas para inicializar os centróides

Escolha aleatória – diversas rodadas do k-means até
encontrar a escolha que produz o menor SSE (ou
maior coesão).


Nem sempre funciona- depende dos dados e do número k
de clusters que se quer encontrar.
Utilizar uma amostra, aplicar um método de
clusterização hierárquica sobre a amostra. Centróides
iniciais = centróides dos clusters das amostras.

Funciona se a amostra é pequena (métodos hierárquicos
são computacionalmente caros !) e K é relativamente
pequeno com relação ao tamanho da amostra.
Exercício
1
2
1
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