Aprendizagem de Máquina
- Agrupamento
Ricardo Prudêncio
Clustering (Agrupamento)

Particionar objetos em clusters de forma que:
Objetos dentro de um cluster são similares
 Objetos de clusters diferentes são diferentes


Descobrir novas categorias de objetos de uma
maneira não-supervisionada

Rótulos de classes não são fornecidos a priori
Clustering - Etapas
Objetos
Representação
Redução da
dimensionalidade
Padrões (Vetores)
Seleção ou extração
de características
Cluster B
Objetos
Cluster A
Objetos
Clustering
Cluster C
Objetos
Partição
Similaridade
Tipos de Clustering

Algoritmos Flat (ou Particional)


Geram partição “plana”, i.e. não existe relação
hierárquica entre os clusters
Algoritmos Hierárquicos

Geram uma hierarquia de clusters, i.e. cada
cluster é associado a um cluster-pai mais genérico

Vantagem: diferentes visões dos dados
Tipos de Clustering

Hard


Cada objeto pertence exclusivamente a um único
grupo na partição
Fuzzy

Cada objeto está associado a um cluster com certo
grau de pertinência

Partição Fuzzy pode ser convertida facilmente para
uma partição hard
Tipos de Clustering

Incremental

Partição é atualizada a cada novo objeto
observado


Em geral, apenas um número pequeno de clusters é
modificado
Não-incremental

Partição é gerada de uma única vez usando todos
os objetos disponíveis
Algoritmo K-Means
Algoritmo k-Means

Algoritmo particional baseado em Otimização do
Erro Quadrado
K
e 2 ( D, C )  


j 1 d i C j

di  c j
2
centróide
do cluster j
Partição
Conjunto de
Objetos
i-ésimo objeto
do cluster j
Algoritmo k-Means

Encontra de forma interativa os centróides dos
clusters
d1
Centróide A
Centróide A
d2
Algoritmo k-Means

Clusters definidos com base nos centróides (centro
de gravidade, ou o ponto médio dos cluster:


1
c
d

i

| C | di C

Alocação dos objetos nos clusters feita com base na
similaridade com o centróide até critério de parada
Algoritmo k-Means




Passo 1: Defina k centróides iniciais, escolhendo k
objetos aleatórios;
Passo 2: Aloque cada objeto para o cluster
correspondente ao centróide mais similar;
Passo 3: Recalcule os centróides dos clusters.
Passo 4: Repita passo 2 e 3 até atingir um critério de
parada


e.g. até um número máximo de iterações ou;
até não ocorrer alterações nos centróides (i.e. convergência
para um mínimo local da função de erro quadrado)
k-Means (Exemplo com K=2)
Inicializar centróides
Alocar objetos
Computar centróides
Realocar objetos
x
x
x
x
Computar centróides
Realocar objetos
Convergiu!
Algoritmo k-Means

O k-Means tende a gerar clusters esféricos

Assim pode falhar para clusters naturais com formas
mais complexas

Exemplo -->
Algoritmo k-Means

O k-Means é popular pela facilidade de
implementação, e eficiência no tempo


O(nK), onde n é o número de objetos e K é o número de
clusters
Comentários:




Não adequado para atributos categóricos
Sensível a outliers e ruído
Converge para mínimos locais
Desempenho do algoritmo é dependente da escolha dos
centróides iniciais
Algoritmo k-Medoid

Similar ao k-Means mas cada cluster é representado
por um objeto que realmente existe (medoid)

Medoid é o objeto do grupo cuja similaridade média
com os outros objetos possui o valor máximo

Comentários:


Tolerante a outliers e adequado para atributos categóricos
Porém, custo mais alto
Algoritmos Hierárquicos
Algoritmos Hierárquicos

Geram uma partição onde os clusters são organizados
em uma hierarquia

Permite ao usuário ter diferentes visões dos objetos
sendo agrupados
Dendrograma
X2
F
G
D
E
B
A
C
X1
Tipos de Algoritmos Hierárquicos

Algoritmos Hierárquicos Divisivos ou Particionais



Assumem estratégia top-down
Iniciam com cluster mais geral que é progressivamente
dividido em sub-cluster
Algoritmos Hierárquicos Aglomerativos


Assumem estratégia bottom-up
Iniciam com clusters específicos que são progressivamente
unidos
Algoritmos Hierárquicos Divisivos


Passo 1: Inicie alocando todos os documentos em um
cluster;
Passo 2: A partir da estrutura existente de grupos,
selecione um cluster para particionar;



Em geral, o maior cluster, ou o cluster menos homogêneo
Passo 3: Particione o grupo em dois ou mais subgrupos;
Passo 4: Repita os passos 2 e 3 até que um critério de
parada seja verificado

e.g., até atingir um número desejado de grupos
Algoritmos Hierárquicos Divisivos

Bi-Secting k-Means



Uso do algoritmo k-Means na etapa de divisão dos
clusters
Clusters são sucessivamente particionados em 2 subclusters
Complexidade: O(n log(n))
Algoritmos Hierárquicos
Aglomerativos



Passo 1: Inicie alocando cada documento como um
cluster diferente;
Passo 2: Selecionar o par de clusters mais similares entre
si e os agrupe em um cluster mais geral;
Passo 3: Repita o passo 2 até a verificação de um critério
de parada

e.g., até que todos os documentos sejam agrupados em um
único cluster

Complexidade: O(n2 log(n))
Algoritmos Hierárquicos
Aglomerativos

Algoritmos variam conforme a maneira de medir
similaridade entre dois clusters

Single-Link: definida como a máxima similaridade entre os
membros dos clusters

Complete-Link: definida como a mínima similaridade entre os
membros dos clusters

Average-Link: definida como a média da similaridade entre os
membros dos clusters
Single Link

Similaridade entre clusters:
sim _ clusterSingleLink (C1 , C2 ) 

min sim(di , d j )
d i C1 , d j C2
Efeito:

Produz clusters mais alongados (efeito cadeia)
Single Link - Exemplo
Complete Link

Similaridade entre clusters:
sim _ clusterCompleteLink (C1 , C2 )  max sim(di , d j )
d i C1 , d j C2

Efeito:

Produz clusters mais coesos e compactos
Complete Link - Exemplo
Single Link X Complete Link
Single Link
Complete Link
Single-Link conecta pontos de classes diferentes através de uma cadeia
de pontos com ruído (*)
Single Link X Complete Link
1
1
1
1
2 2
2
2 2
2
1
1
1
1
1
1
1
1
Complete-Link não é capaz de identificar cluster de pontos (1)
Average-Link

Similaridade entre clusters:
1
sim _ clusterAverageLink (C1 , C2 ) 
sim(di , d j )

| C1 |  | C2 | di C1 ,d j C2

Efeito:


Equilíbrio entre clusters coesos e flexíveis
Em alguns contextos (e.g., clustering de texto)
tem se mostrado mais eficaz
Algoritmo Aglomerativo Baseado em
Centróides

Similaridade entre clusters é definido como a
similaridade entre seus centróides
2
2
2 2 2
2 2 x 2 2
2
2 2 2
2
3 3
3 3
3
1 1
1 1 1
1 1
1 1
1
1
1 1 1
1
Algoritmos Hierárquicos

Resumo:



Os algoritmos hierárquicos divisivos são menos custosos que
os aglomerativos
Dentre os aglomerativos, o Average-Link funciona melhor
em algumas aplicações
Desempenho pode ser melhorado através da combinação de
técnicas
Referências

Jain, A. K., Murty, M. N., and Flynn, P. (1999). Data
clustering: a review. ACM Computing Surveys, 3(31):264–
323.

Xu, R. and Wunsch II, D. (2005). Survey of Clustering
Algorithms, IEEE Trans. on Neural Networks, 16(3):645-677.

Jiang, D., T., Tang, and Zhang, A. (2004). Cluster Analysis
for Gene Expression Data: A Survey, IEEE Trans. on
Knowledge and Data Engineering, 16(11).