Agrupamento K-Means — Algoritmo e Como Funciona

O agrupamento k-means é uma forma de agrupar dados numéricos em $k$ clusters. Se você escolhe $k$ e usa a versão euclidiana padrão, o algoritmo repete um ciclo: atribui cada ponto ao centro mais próximo e depois move cada centro para a média dos pontos atribuídos a ele.

Em termos simples, ele tenta fazer com que os pontos do mesmo grupo fiquem próximos uns dos outros e que os pontos de grupos diferentes fiquem mais distantes. Ele é rápido e útil, mas só funciona bem quando esses "grupos" são razoavelmente compactos e a distância faz sentido.

O que o agrupamento k-means está otimizando

Na forma euclidiana padrão, o k-means tenta fazer com que os pontos dentro de cada cluster fiquem o mais próximos possível do centróide desse cluster. Um objetivo comum é

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Aqui, $C_j$ é o $j$-ésimo cluster e $\mu_j$ é seu centróide.

Essa é a soma dos quadrados dentro dos clusters. Valores menores significam que os pontos atribuídos estão mais concentrados ao redor de seus centróides.

Esse objetivo explica as duas partes do algoritmo:

• Se os centróides estão fixos, a melhor escolha é atribuir cada ponto ao centróide mais próximo.
• Se as atribuições estão fixas, o melhor centróide é a média dos pontos atribuídos.

É por isso que a regra de atualização não é arbitrária. As "means" em k-means são literalmente médias aritméticas.

Como o algoritmo k-means funciona

O ciclo usual é curto:

1. Escolha $k$ centróides iniciais.
2. Atribua cada ponto ao centróide mais próximo.
3. Recalcule cada centróide como a média dos pontos atribuídos a ele.
4. Repita até que as atribuições parem de mudar ou que a melhora seja muito pequena.

Esse processo geralmente converge rápido, mas não necessariamente para o melhor agrupamento possível. Centròides iniciais diferentes podem levar a respostas finais diferentes, então a inicialização importa.

Exemplo de agrupamento k-means passo a passo

Considere estes pontos de dados unidimensionais:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Suponha que queremos $k = 2$ clusters e começamos com centróides em $1$ e $10$. Este é um bom exemplo porque os centróides realmente se movem após a primeira atualização.

Etapa 1: atribuir os pontos ao centróide mais próximo

Os pontos $1, 2, 3$ estão mais próximos de $1$.

Os pontos $10, 11, 12$ estão mais próximos de $10$.

Então os clusters são

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Etapa 2: atualizar os centróides

O novo centróide do primeiro cluster é

$$\mu_1 = \frac{1+2+3}{3} = 2$$

O novo centróide do segundo cluster é

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Ambos os centróides se moveram, de $1$ para $2$ e de $10$ para $11$.

Etapa 3: atribuir novamente

Agora verifique outra vez o centróide mais próximo usando $2$ e $11$.

Os pontos $1, 2, 3$ ainda pertencem ao primeiro cluster, e os pontos $10, 11, 12$ ainda pertencem ao segundo cluster. Como as atribuições não mudam mais, o algoritmo convergiu.

Este é um exemplo limpo porque os dados se separam naturalmente em dois grupos compactos. Conjuntos de dados reais são mais bagunçados, e é aí que o k-means pode começar a induzir você ao erro.

Quando o k-means funciona bem

O k-means funciona melhor quando estas condições são aproximadamente verdadeiras:

• As variáveis são numéricas.
• A distância euclidiana é uma forma razoável de medir similaridade.
• Os clusters são relativamente compactos, não longos nem curvos.
• As variáveis foram escaladas para que uma não domine as outras.

Se essas condições falharem, a saída ainda pode parecer organizada, mas sem capturar a estrutura real dos dados.

Erros comuns com k-means

Tratar o k-means como um método universal de agrupamento

O k-means funciona melhor quando os clusters são razoavelmente compactos e a média é um resumo sensato. Ele não é uma boa escolha padrão para qualquer conjunto de dados.

Ignorar a escala das variáveis

Se uma variável é medida em uma escala muito maior do que outra, ela pode dominar o cálculo da distância. Padronizar ou normalizar as variáveis costuma ser importante antes de rodar o k-means.

Assumir que a resposta é única

O k-means pode convergir para diferentes mínimos locais a partir de diferentes pontos iniciais. É por isso que execuções repetidas ou métodos como a inicialização k-means++ são comumente usados.

Usar variáveis não numéricas ou mal codificadas

Como os centróides são médias, o k-means padrão foi feito para variáveis numéricas. Se uma variável é categórica, tirar uma média aritmética pode não fazer sentido.

Usá-lo em clusters fortemente não esféricos

Se os grupos reais forem longos, curvos ou muito desiguais em densidade, o k-means pode dividir um grupo natural ou juntar dois grupos diferentes. O método prefere clusters compactos baseados em centróides.

Esquecer que outliers podem puxar os centróides

Como os centróides são médias, valores extremos podem deslocá-los de forma perceptível. Se outliers são importantes nos seus dados, verifique isso antes de confiar no resultado.

Onde o agrupamento k-means é usado

O k-means é frequentemente usado para agrupamento exploratório, segmentação de clientes ou comportamentos, quantização de cores em imagens e como uma linha de base rápida em aprendizado não supervisionado.

Ele é mais útil quando você tem variáveis numéricas, quer um modelo simples e rápido e espera clusters aproximadamente compactos no espaço euclidiano.

Um modelo mental simples

Imagine colocar $k$ alfinetes móveis em um gráfico de dispersão. Cada ponto se conecta ao alfinete mais próximo. Depois, cada alfinete desliza para a posição média dos pontos conectados a ele. Repita isso até que os alfinetes quase parem de se mover.

Essa imagem não é só intuição. Ela é quase o algoritmo inteiro.

Tente um problema de agrupamento parecido

Pegue um pequeno conjunto de pontos em uma reta, escolha $k = 2$ e faça à mão um ciclo completo de atribuição e atualização. Depois mude os centróides iniciais ou adicione um outlier e veja como o resultado muda. Se quiser ir um passo além, teste sua própria versão em um pequeno conjunto de dados e compare o que acontece antes e depois do escalonamento das variáveis.