K-Means
(Clustering)
Prof. Alexandre Monteiro
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
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
a8
a4
a11
Doença Y
5
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
Aprendizado Supervisionado


No caso da aprendizagem supervisionada, assume-se a
presença de um “professor”, onde são fornecidas as
respostas corretas para cada situação. A aprendizagem é
realizada a partir de exemplos (instâncias ou casos de
treino) compostos por um vetor de entradas e por um vetor
de saídas desejadas.
Existem dois tipos de aprendizagem supervisionada, por
Classificação, caracterizada por saídas com valores
discretos (classes) e Regressão, caracterizada por saídas
com valores contínuos, reais. Nesse caso, observa-se uma
convergência rápida no resultado. Esse tipo de
aprendizagem pode ser comparado à nota de um aluno em
uma prova.
Apredizado Não-Supervisionado



No caso da aprendizagem não-supervisionada, não é
fornecida nenhuma indicação externa, a aprendizagem é
realizada pela descoberta de regularidades (semelhanças)
nos dados de entrada, procurando agrupamentos
(clustering) dos exemplos de treino.
Nesse caso, observa-se uma convergência lenta no
resultado.
Esse tipo de aprendizagem pode ser comparado ao
desenvolvimento das células simples do córtex visual
estriado.
Tipos de Agrupamentos

Particionais versus Hierárquicos
• 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 versus Não-exclusivos versus Fuzzy
• 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.
- 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 conexo 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.
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).
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.
Os outliers seriam absorvidos nos clusters.
Baseados em Densidade
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: algoritmos 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
d(x,y) = |x1-y1|+ |x2-y2| + .... + |xp – yp|

Minkowski
d(x,y) =

Distância em geral
m
(x1-y1)m + (x2-y2)m+ .... + (xp – yp)m
Qualquer função d(x,y)  N que satisfaz as seguintes
propriedades:
• 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
= cos(d1,d2) = d1.d2
|d1| |d2|
d1
θ
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
1.
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.
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
i = 1 x ɛ Ci
SSE = Σ Σ d(x,ci)2
K
i = 1 x ɛ Ci
Coesão
= Σ Σ coseno(x,ci)2
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
5
6
7
8
9
12
13
11
14
15
16
10
17
Achar 3 clusters utilizando o k-means
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
Bibliografia





R. Turner. Logics for Artificial Intelligence. John
Wiley, 1985.
E. Rich e K. Knight. Inteligência Artificial. Makron
Books, 2a. Edição, 1994.
S. Haack. Filosofia das Lógicas. UNESP Editora, 1998.
P. Almeida e A. Evsukoff. Sistemas Fuzzy em Sistemas
Inteligentes. Manole, 2003
J. Jang, C. T. Sun e E. Mizutani. Neuro-Fuzzy and Soft
Computing. Prentice Hall, 1997.
30