Clustering: Conceitos e K-médias

Prévia do material em texto

Clustering
Conceitos básicos e Kmédias
Prof. Frederico Coelho. (Baseado no material de David Sontag)
2
Clustering
Aprendizagem não supervisionada
- Requer dados, mas nenhum rótulo
- Detectar padrões, por exemplo em
• Grupos de e-mails ou resultados de pesquisa
• padrões de compras do cliente
• Regiões de imagens
- Útil quando não sabe o que você está procurando
3
Clustering
Dado um conjunto de pontos, devemos agrupá-los de 
maneira que:
● Pontos dentro de um mesmo cluster sejam o mais similar 
possível;
● Pontos em clusters diferentes sejam o mais diferente 
possível.
4
Clustering – Ideia Básica
5
Clustering – Ideia Básica
6
Clustering – Ideia Básica
7
Clustering – Ideia Básica
O que significa "semelhante"?
- Uma opção: pequena distância euclidiana (ao quadrado)
Os resultados de agrupamento dependem crucialmente da medida de 
similaridade (ou distância) entre “pontos” a serem agrupados
8
Clustering – Algoritmos
Algoritmos de partição:
● K-means
● Mistura de Gaussianas
● Agrupamento Espectral
Algoritmoms Hierárquicos:
● Ward
9
Clustering – Exemplos
Segmentação de imagens
● Separar a imagem em regiões que tenham algum sentido
10
Clustering – Exemplos
Agrupamento de genes
11
Clustering – Exemplos
Agrupamento de genes
12
Clustering – K-médias
Algoritmo:
● Inicializa K centros
● Associa cada amostra ao centro mais próximo
● Calcula o novo centro do cluster
● Critério de parada: quando os pontos não se alterarem 
mais
13
Clustering – K-médias
14
Clustering – K-médias
15
Clustering – K-médias
16
Clustering – K-médias
17
Clustering – K-médias – 
Segmentação de imagens
18
Diferentes métrica
Fonte: Density-based geodesic distance for identifying the noisy and nonlinear clusters
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18