Agrupamentos / Clustering
•
Filipe Wanderley Lima ([email protected])
Roteiro
→ Motivação;
→ Conceitos básicos;
→ Modelos de clusters;
→ K-means;
→ Aplicações.
2
Motivação
→ Encontrar conjuntos de dados pode ser fácil, mas
classificá-los é custoso;
→ No estágios iniciais de uma investigação, uma análise
exploratória dos dados pode ser útil para extrair
informações sobre a natureza ou estrutura dos
mesmos:
↳ Quais sub-populações existem nos dados?
•
•
•
•
Quantas são? Quais seus tamanhos?
O que elementos de uma sub-população tem em comum?
Eles são homogênios, ou eles podem ser partidos ainda mais?
Existem outliers?
3
Conceitos básicos
→ Clustering é a tarefa de atribuir um conjunto de
objetos em grupos (chamados clusters) de maneira
que os objetos em um mesmo cluster são mais
similares entre si do que aqueles em outros clusters.
Conjunto de objetos
Clusters
4
5
Conceitos básicos
→ É considerado um método para aprendizagem não
supervisionada:
↳ Não se sabe de antemão qual a classificação de cada dado.
Altura
85
1,87
92
1,88
112
2,05
105
1,93
68
1,65
56
1,58
48
1,69
67
1,62
100
1,80
Classe
2.1
2
1.9
?
Peso
Peso
1.8
1.7
1.6
1.5
40
60
80
Altura
100
120
Conceitos básicos
→ Clusters:
↳ Varia entre algoritmos;
↳ É uma das muitas decisões a serem tomadas na hora de escolher o
algoritmo adequado;
↳ Entender os modelos de clusters é a chave para entender as
diferenças entre os vários tipos de algoritmos.
6
7
Modelos de clusters
Hierárquicos
→ Constroem modelos baseados na distância de
conectividade:
↳ Objetos são mais similares a objetos próximos do que a objetos que
estão longe.
→ Um cluster pode ser definido pela distância máxima
necessária para conectar as partes do cluster:
↳ Difentes distâncias formam diferentes clusters.
→ Os clusters podem ser representados por
dendrogramas:
A
AB
B
C
ABCDE
CD
D
E
CDE
Modelos de clusters
Hierárquicos
→ Não fornecem uma partição única do conjunto de
dados, mas sim uma hierarquia extensiva de clusters
que se juntam uns com os outros a certas distâncias;
→ Não são robustos para tratar de outliers.
8
Modelos de clusters
Centróides
→ Representa cada cluster como um simples vetor de
média.
9
Modelos de clusters
10
Distribuições
→ Os clusters são modelados usando distribuições
estatísticas:
↳ Os clusters são definidos como objetos pertencentes
provavelmente a uma mesma distribuição.
→ É um método forte, pois não somente fornece clusters,
mas também produz modelos complexos de clusters
que podem também capturar atributos de correlação e
dependência.
Modelos de clusters
11
Densidade
→ Definem clusters como regiões de mais alta densidade
do que o restante do conjunto de dados;
→ Objetos nas áreas esparças são normalmente
considerados como ruídos e pontos de fronteira;
→ Esperam por uma baixa de densidade para detectar as
fronteiras dos clusters;
K-Means
→ Escolha inicial dos centros:
↳ Aleatória.
→ Cálculo da Distância:
↳ Distância Euclidiana.
→ Critérios de Parada:
↳ Não modificação dos clusters em duas iterações sucessivas.
K-Means
→Exemplo K = 3
c2
1. Escolher os centros iniciais.
2. Associar cada vetor ao cluster mais
próximo.
3. Determinar os novos centros.
4. Associar cada vetor ao cluster mais
próximo.
5. Determinar os novos centros.
6. Associar cada vetor ao cluster mais
próximo.
7. Não houve alterações.
c1
K-Means
→ Applet intereativo:
↳ http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/Appl
etKM.html
Aplicações
→ Agrupar tags por sua relevância:
↳ https://addons.mozilla.org/en-US/firefox/addon/search-cloudletfor-google-yah/
Aplicações
→ Clustering resultados de busca.
Aplicações
Ciência da computação
→ Quantização de vetores para comprimir imagens.
Imagem
KK==original
10
3
2
[Bishop, PR ML]
Aplicações
Ciência da computação
→ Segmentação de imagens:
↳ Usado para dividir uma imagem digital em regiões distintas para
detecção de fronteiras ou reconhecimento de objetos.
[http://www.cs.brown.edu/~pff/segment/]
Aplicações
Ciência da computação
→ Sistemas de recomendação:
↳ Prever as preferências dos usuários baseado nas preferências de
outros usuários pertencentes ao mesmo cluster.
Aplicações
→ Clustering de expressões de dados de genes.
[Eisen et al, PNAS 1998]
Aplicações
Internet
→ Agrupamento de resultados de busca:
↳ Pode ser usado para criar conjuntos de resultados de busca mais
relevantes.
[Yippy]
Aplicações
Internet
→ Análise de redes sociais:
↳ Usado para identificar comunidades entre grandes grupos de
pessoas.
Referências
→ Seminário sobre Categorização/Classificação &
Agrupamento da disciplina de Mineração da Web
2011.1
→ Aula sobre Agrupamentos da disciplina de
Aprendizagem de Máquina
→ Introductory Applied Machine Learning por Chris
Williams and Victor Lavrenko
→ Clustering por Sriram Sankararaman
23
Dúvidas?