Aula 13: k-means

Question 1

Motivos para o uso do aprendizado não-supervisionado

Answer 1

Rotular padrões em grande conjunto de dados pode ser custoso

Padrões podem mudar durante o processo de classificação

O aprendizado não supervisionado pode ser usado na etapa de pré-processamento para o aprendizado supervisionado (ex.: redução da dimensionalidade e avaliação de regularidades nas features)

Question 2

O problema do aprendizado não supervisionado…

Answer 2

O problema envolve estimar a distribuição de probabilidade p(x | θ) de um vetor aleatório x de um dataset X.

Se for possível assumir a forma da distribuição de cada elemento de θ, então pode-se usar métodos paramétricos, isto é, elementos que seguem uma distribuição normal. Isso na prática não é a realidade de muitos casos.

Question 3

Clusterização

Answer 3

Procedimento que agrupa elementos de acordo com as similaridades internas entre os grupos. Para medir similaridade ou dissimilaridade entre os pontos é calculado suas distâncias (distância euclidiana entre dois pontos).

Question 4

Algoritmo k-means

Answer 4

Um algoritmo de clusterização que agrupa elementos de um dataset em k clusters disjuntos.

Question 5

Centróide de um cluster

Answer 5

É a média de todos os valores daquele cluster. Todos os centróides são inicializados antes da primeira iteração: Uma possibilidade é uma inicialização randômica através dos elementos.

Question 6

c^i
µ_j
u_(c^(i))

Answer 6

c^i: Índice do centróide do cluster de x^i
µ_j: Centróide do cluster
u_(c^(i)): centróide do cluster em que o exemplo x^i foi alocado

Question 7

Consequência de minimizar J (função objetiva) sem ajustar as variáveis…

Answer 7

Minimizar J (função objetiva) sem ajustar as variáveis leva a clusters que minimizam internamente a distância entre os pontos e ao mesmo tempo maximiza a distância entre os clusters. Essa minimização é um problema NP-hard. K-means é um procedimento subótimo e pode ficar preso a um mínimo local. Pode-se contornar isso executando k-means várias vezes e usando a função objetiva para escolher a melhor configuração dos clusters.

Question 8

Consequência de ajustar as variáveis

Answer 8

Ajustar as variáveis significa fazer premissas e restrições sobre as variáveis. Isso pode ser feito através da extração de features por meio de técnicas de redução da dimensionalidade como o PCA e o t-SNE.

Question 9

Consequência de não ajustar as variáveis

Answer 9

Ao não ajustar as variáveis isso leva o algoritmo a não fazer premissas ou restrições sobre as variáveis e suas features, isso permite que o algoritmo descubra os padrões e faça o agrupamento baseado somente na distância entre o centróide e um dado elemento.

Question 10

Por quê o k-means é um procedimento subótimo?

Answer 10

Os clusters obtidos pelo k-means podem não representar a melhor ou mais precisa clusterização para um dado dataset. Isso implica que o k-means é um procedimento subótimo e que pode ficar preso à um mínimo local.
Uma alternativa pode ser rodar o k-means várias vezes e usar J (função objetiva) para escolher os melhores conjuntos possíveis.

Question 11

Como escolher um bom valor para k

Answer 11

Existe o método do cotovelo e da silhueta, porém ajuda também ter conhecimento sobre o problema em questão.

Question 12

Método da silhueta

Answer 12

Verifica a consistência do cluster. Para um dado ponto é medido a similaridade desse ponto em relação à outros do mesmo cluster (coesão) e ao mesmo tempo o quão dissimilar é esse ponto em relação à outros clusters (separação). Varia de -1 à +1. Se a maioria dos clusters possuem valores altos, então a configuração é considerada correta.

Question 13

Como é calculado a silhueta para um ponto x

Answer 13

Primeiro é calculado a distância (euclidiana) média dentro do cluster a(x^i), após isso é calculado a distância média para clusters próximos b(x^i).

Idealmente se quer que a(x^i) < b(x^i), caso contrário é considerado que foi classificado erroneamente o ponto.

Question 14

Exemplos de aplicações para o uso de aprendizado não-supervisionado

Answer 14

Segmentação em marketing

Análise de expressão genética

Question 15

A cada iteração do k-means ocorre duas etapas…

Answer 15

Etapa 1: Atualização do centróide;

Etapa 2: Atribuição de clusters.

Question 16

PCA

Answer 16

Principal Component Analysis

Question 17

t-SNE

Answer 17

t-Distributed Stochastic Neighbor Embedding

Question 18

“Os padrões podem mudar ao longo do processo de classificação: o agrupamento de dados não rotulados lida melhor com essa situação”.

Qual o significado disso?

Answer 18

Os padrões nem sempre podem ser estáticos ou facilmente discerníveis. A natureza dos dados pode mudar com o tempo, dificultando a classificação precisa de novos pontos de dados inéditos.

Question 19

Atualização do cluster

Answer 19

O centróide de um cluster (µ_j) j ∈ {1, …, k} é a média de todos os valores daquele cluster;

Antes da 1ª iteração, todos os k centróides devem ser inicializados (inicialização randomica com os pontos do dataset);

Os valores de c¹, …, c^N são fixados.

Question 20

Atribuição do cluster

Answer 20

A cada iteração, rotula-se um ponto x^i com o índice do centróide mais próximo (ou mais similar);

Para isso é medido a distância euclidiana entre x^i (elemento em questão) e cada um dos centróides (µ_1, …, µ_k);

Então rotula-se x^i com o índice j do centróide µ_j que é o mais próximo de x^i;

Os valores de µ_1, …, µ_k são fixos.