---
  presentation
  theme: beige.css
  slideNumber: true
  width: 1024 height: 768
---

<!-- slide -->
## Aprendizado de Máquina

#### Aprendizado não-supervisionado (agrupamento)
#### Prof. Ronaldo Cristiano Prati
[ronaldo.prati@ufabc.edu.br](mailto:ronaldo.prati@ufabc.edu.br)  

Bloco A, sala 513-2

<!-- slide -->
## Tipos de Aprendizado

- **Supervisionado** os exemplos tem um atributo de interesse pré-determinado
- **Não supervisionado** não temos um atributo de interesse pré-determinado

<!-- slide -->
### Aprendizado não supervisionado

- **Agrupamento** identificar alguma estrutura nos dados
- **Redução de dimensionalidade** usar características estruturais para simplificar os dados

<!-- slide -->
## Agrupamento

- Organizar dados em grupos  de forma que exista
  - uma alta similaridade intra-classe
  - uma baixa similaridade inter-classes

- Mais informalmente, encontrar grupos que ocorrem naturalmente entre objetos.

<!-- slide -->
#### Qual é o agrupamento natural desses objetos?

![](simpsons.png)


<!-- slide -->
#### Agrupamento é subjetivo

![](simpsons-grupo.png)

<!-- slide -->
### Aprupamento particional

- **Algoritmos Particionais:** Construir diversas partições de acordo com algum critério

![](particional.png)

<!-- slide -->
### Aprupamento hierárquico

- **Algoritmos Hierárquicos:** Criar uma decomposição hierárquica de um conjunto de objetos utilizando algum critério

![](hierarquico.png)


<!-- slide -->
## K-médias

- Algoritmo particional: cada ponto é associado a um único grupo
- Precisamos decidir antecipadamente o número $k$ de grupos

<!-- slide -->
### K-médias - algoritmo

1. Decidir um valor para k.
2. Inicializar os centros dos k grupos (aleatoriamente, se necessário).
3. Decidir o grupo dos N objetos por meio da associação ao centro do grupo mais próximo.
4. Re-estimar os centros dos k grupos, assumindo que a associação com os grupos encontradas anteriormente está correta.
5. Se nenhum dos N objetos mudou de grupo na última iteração, pare. Caso contrário, volte para o passo 3.

<!-- slide -->
### K-médias - exemplo

![](km0.png)

queremos encontrar 2 grupos

<!-- slide -->
### K-médias - exemplo

![](km1.png)

inicalizamos aleatoriamente o centróide dos dois grupos

<!-- slide -->
### K-médias - exemplo

![](km2.png)

Cada exemplo é atribuído a um grupo, de acordo com o centróide mais próximo


<!-- slide -->
### K-médias - exemplo

![](km3.png)

O centróide do grupo é movido para o centro de cada grupo

<!-- slide -->
### K-médias - exemplo

![](km4.png)

Cada exemplo é (re)atribuído a um grupo, de acordo com o (novo) centróide mais próximo

<!-- slide -->
### K-médias - exemplo

![](km5.png)

O centróide do grupo é movido (novamente) para o (novo) centro de cada grupo

<!-- slide -->
### K-médias - exemplo

![](km6.png)

Cada exemplo é (re)atribuído a um grupo, de acordo com o (novo) centróide mais próximo

<!-- slide -->
### K-médias - exemplo

![](km7.png)

O centróide do grupo é movido (novamente) para o (novo) centro de cada grupo.

<!-- slide -->
### K-médias - exemplo

![](km7.png)

Cada exemplo é (re)atribuído a um grupo, de acordo com o (novo) centróide mais próximo. Como não houve alteração, convergiu.


<!-- slide -->
## K-médias

- O k-médias é dependente do número de cluster $k$

- O k-médias é sensível à inicialização dos clusters

<!-- slide -->
### K-médias - diferentes execuções

![](k3m.png)

<!-- slide -->

### Função objetivo

- Seja $c^i$ o cluster $i$, $\mu_{c^i}$ o centróide do cluster $i$ e $x^i$ um exemplo associado ao cluster $i$. Podemos definir a função objetivo como:

$$ J(c^1,\dots,c^k,\mu_{c^1},\dots,\mu_{c^k}) = \frac{1}{m} \sum_i^m \| x^i -  \mu_{c^i}\|^2$$

- Soma dos quadrados da distância de cada ponto ao seu respectivo cluster.
- Também chamado de inércia.

<!-- slide -->

### Função objetivo

![](inertia.png)

<!-- slide -->

### Escolha do valor de $k$

- Alguns problemas tem um valor de $k$ bem definido
  - Agrupar tarefas similares em 4 núcleos de CPU ($k=4$)
  - Agrupar roupas em 5 diferentes tamanhos para cobrir a maioris das pessoas ($k=5$)
  - Agrupar comentários similares em 10 grupos ($k=10$)

<!-- slide -->
### Escolha do valor de $k$

- Quando não temos conhecimento do domínio, escolher $k$
- Método do "cotovelo"
    - Executar k-médias para diferentes valores de $k$
    - Fazer um gráfico de $k$ por $J$
    - Escolher $k$ em que $J$ se "estabiliza"

<!-- slide -->
### Escolha do valor de $k$

- Chama-se método do "cotovelo" pois espera-se que o gráfico tenha o formato de um braço dobrado, e o $k$ adequado seria o "cotovelo"

![](joelho.png)

- Nem sempre tem esse formato

<!-- slide -->
### Suposições

<img src="assumptions.png" width=600>

<!-- slide -->

### Escolha da medida de distância

- A escolha da medida de distância é extremamente importante para o sucesso do agrupamento
- Cada métrica tem vantagens/desvantagens e casos de uso mais apropriado
- Muitas vezes é preciso realizar uma avaliação empírica

<!-- slide -->

### Distância Euclideana

![](euclidean.png)


<!-- slide -->

### Distância Manhattan

![](manhatan.png)

- Menos sensível a outliers

<!-- slide -->

### Distância de Cosenos

![](cosine.png)

- Menos sensível a escala e dimensionalidade


<!-- slide -->
### Agrupamento hierárquico

- Representa a similaridade entre os dados por meio de um dendograma

- A similaridade entre dois objetos em um dendograma é representada pela altura do nó interno mais baixo que eles compartilham.

![](dendograma.jpg)

<!-- slide -->
### Número de clusters

- O dendograma pode ajudar a determinar o número “correto” de agrupamentos. Nesse caso, a existência de duas árvores bem separadas é um forte indicativo de dois clusters.
- Infelizmente, raramente as coisas são assim tão claras.

<img src="nclus.png" width=400>


<!-- slide -->
### outliers
- Um possível uso de dendogramas é a detecção de outliers
- Um ramo único e isolado sugere um dado que é muito diferente de todos os demais

<img src="oulier.png" width=400>

<!-- slide -->

### Agrupamento hierárquico

- O número possível de dendogramas cresce exponencialmente com o tamanho do dataset
- Busca heurística:
  - **aglomerativo**: começa agrupando exemplos individualmente até construir um único cluster
  - **divisivo**: começa com um único cluster e vai dividindo recursivamente até chegar nos exemplos.

<!-- slide -->
### Matriz de Distância

- contém as distâncias entre cada par de objetos da base de dados

<img src="mdistancia.png" width=500>

<!-- slide -->
### Abordagem aglomerativa

1. Cada exemplo representa um grupo
2. Encontra o melhor par para (menor distância) para criar um novo grupo
3. Recalcula a distânci do grupo criado para os demais
4. Volta ao passo 2. até que um único grupo seja formado

<!-- slide -->
### Abordagem aglomerativa

<img src="hcust2.PNG" width=600>

<!-- slide -->
#### Distância entre clusters


- Ligação simples (vizinho mais próximo): distância entre os dois objetos mais próximos (vizinhos mais próximos) nos diferentes clusters.
- Ligação completa (vizinho mais distante): maior distância entre dois objetos nos diferentes clusters (“vizinhos mais distantes”).
- Ligação média de grupo: distância média entre todos os pares de objetos nos diferentes clusters.
- Ligação Wards: minimiza a variância entre os dois clusters aglomerados.

<!-- slide -->
#### Distância entre clusters

![](linkage.png)


<!-- slide -->
#### Distância entre clusters

![](difh.png)

<!-- slide -->
### Agrupamento hierárquico

- Não existe a necessidade de especificar o número de clusters a priori.
- A natureza hierárquica é facilmente mapeada pela intuição humana para alguns domínios.
- Eles não escalam bem: a complexidade de tempo é pelo menos $O(n^2)$, na qual $n$ é o número de objetos.
- Como qualquer algoritmo de busca heurística, mínimos locais são um problema.
- A interpretação dos resultados é (muito) subjetiva.