Agrupamento K-Means

Visão geral

O agrupamento k-means (k-means clustering) é um algoritmo de aprendizado não supervisionado (unsupervised learning) amplamente utilizado que particiona um conjunto de dados em k clusters. Cada cluster é representado por um centróide (centroid) (a média dos pontos atribuídos a esse cluster). O algoritmo busca encontrar atribuições de clusters que façam os pontos ficarem próximos do centróide do seu cluster, tipicamente usando distância euclidiana ao quadrado (squared Euclidean distance).

O k-means é popular porque é conceitualmente simples, computacionalmente eficiente em grandes conjuntos de dados e, com frequência, funciona bem quando os clusters são aproximadamente compactos e bem separados.

No kit de ferramentas mais amplo de clusterização, o k-means é mais apropriado quando você espera clusters “em forma de blob”, enquanto métodos baseados em densidade (density-based methods) como DBSCAN podem capturar formas irregulares, e abordagens probabilísticas (probabilistic approaches) como Modelos de Mistura Gaussiana modelam associações suaves a clusters.

Que problema o k-means resolve?

Dado:

  • Um conjunto de dados (X = {x_1, x_2, \dots, x_n}), em que cada (x_i \in \mathbb{R}^d)
  • Um número escolhido de clusters (k)

O k-means encontra:

  • Uma partição dos pontos em (k) clusters (C_1, \dots, C_k)
  • Centróides (\mu_1, \dots, \mu_k \in \mathbb{R}^d)

De modo que pontos dentro do mesmo cluster sejam tão semelhantes quanto possível sob a medida de distância escolhida (geralmente euclidiana).

Função objetivo (fundamentação teórica)

O k-means minimiza a soma intra-cluster de quadrados das distâncias (within-cluster sum of squared distances, WCSS), também conhecida como inércia (inertia):

[ \min_{C_1,\dots,C_k} \sum_{j=1}^{k}\sum_{x_i \in C_j} |x_i - \mu_j|^2 ]

Onde:

  • (C_j) é o conjunto de pontos atribuídos ao cluster (j)
  • (\mu_j = \frac{1}{|C_j|}\sum_{x_i \in C_j} x_i) é a média (centróide) desse cluster
  • (|\cdot|) geralmente é a norma euclidiana (Euclidean norm)

Por que a média?

Se as atribuições (C_j) são fixas, o valor de (\mu_j) que minimiza (\sum_{x_i \in C_j}|x_i-\mu_j|^2) é exatamente a média dos pontos. Essa é uma das razões pelas quais o k-means alterna entre atribuir pontos e recomputar médias.

Visão como descida coordenada

O k-means pode ser visto como otimizando o objetivo ao alternar entre duas etapas, cada uma das quais reduz (ou mantém inalterado) o objetivo:

  1. Etapa de atribuição (assignment step): fixa os centróides, escolhe o melhor cluster para cada ponto
  2. Etapa de atualização (update step): fixa as atribuições, recomputa os centróides como médias

Como o objetivo é não convexo (non-convex), o k-means pode convergir para um mínimo local (local minimum), não necessariamente para a melhor clusterização global.

O algoritmo k-means (etapas de atribuição/atualização)

Etapa 0: Escolher centróides iniciais

Selecione (k) centróides iniciais (\mu_1, \dots, \mu_k).

Etapa 1: Atribuição

Atribua cada ponto ao centróide mais próximo:

[ c(i) = \arg\min_{j \in {1,\dots,k}} |x_i - \mu_j|^2 ]

Etapa 2: Atualização

Recompute cada centróide como a média dos pontos atribuídos a ele:

[ \mu_j = \frac{1}{|C_j|}\sum_{x_i \in C_j} x_i ]

Etapa 3: Repetir até a convergência

Pare quando:

  • as atribuições pararem de mudar, ou
  • os centróides se moverem menos do que uma tolerância, ou
  • um número máximo de iterações for atingido

Pseudocódigo

initialize centroids μ1..μk
repeat
  for each point xi:
    assign xi to cluster with closest centroid
  for each cluster j:
    μj = mean of points assigned to cluster j
until convergence

Propriedades de convergência

  • Cada iteração não aumenta a WCSS; ela diminui monotonamente ou permanece a mesma.
  • Converge em um número finito de passos (há finitamente muitas partições possíveis), mas ainda pode ser lenta em construções de pior caso.
  • A resposta final depende fortemente da inicialização.

Estratégias de inicialização (por que o k-means++ importa)

Inicialização aleatória (abordagem básica)

Um baseline comum é selecionar (k) pontos aleatórios como centróides iniciais. Isso é rápido, mas pode ser instável:

  • sementes iniciais ruins podem produzir clusters ruins
  • clusters vazios podem ocorrer
  • os resultados variam entre execuções

k-means++ (padrão recomendado)

O k-means++ (k-means++) melhora a inicialização ao espalhar os centróides iniciais:

  1. Escolha o primeiro centróide uniformemente ao acaso a partir dos dados.
  2. Para cada ponto (x), calcule (D(x)^2), a distância ao quadrado até o centróide escolhido mais próximo.
  3. Escolha o próximo centróide com probabilidade proporcional a (D(x)^2).
  4. Repita até que (k) centróides sejam escolhidos.

Benefícios:

  • tipicamente menor WCSS
  • convergência mais rápida
  • estabilidade muito melhor do que a semeadura puramente aleatória

Na prática (por exemplo, no scikit-learn), o k-means++ frequentemente é o padrão por um bom motivo.

Múltiplas reinicializações

Como o k-means pode ficar preso em mínimos locais, é comum executá-lo múltiplas vezes com diferentes inicializações e manter a execução com a menor WCSS. No scikit-learn isso é controlado via n_init.

Escolhendo o número de clusters \(k\)

Selecionar (k) é uma decisão de modelagem; o k-means sempre produzirá exatamente k clusters, mesmo que os dados não tenham naturalmente essa quantidade.

Abordagens comuns:

Método do cotovelo

Calcule a WCSS para diferentes valores de (k) e procure um “cotovelo” em que clusters adicionais trazem retornos decrescentes.

Isso é frequentemente discutido como o Método do Cotovelo. É simples, porém subjetivo: o “cotovelo” nem sempre é claro.

Pontuação de silhueta

A pontuação de silhueta (silhouette score) compara o quão próximo um ponto está do seu próprio cluster vs. o cluster mais próximo alternativo. Valores próximos de 1 indicam clusters bem separados, próximos de 0 indicam sobreposição, e valores negativos sugerem atribuição incorreta.

Veja: Pontuação de Silhueta.

Seleção orientada pelo domínio

Em muitas aplicações reais, interpretabilidade e restrições operacionais importam:

  • Marketing pode querer 5–10 segmentos de clientes
  • Uma tarefa de compressão pode escolher k com base em trade-offs de armazenamento/qualidade
  • Um fluxo de trabalho pode exigir um pequeno número de grupos acionáveis

Análise de estabilidade

Execute o k-means em amostras bootstrap (bootstrap samples) ou com diferentes sementes aleatórias (random seeds) e meça se os clusters são estáveis. Alta instabilidade pode indicar:

  • k é grande demais
  • os dados não têm uma estrutura clara de clusters
  • os atributos são ruidosos ou mal escalonados

Considerações práticas (o que frequentemente determina o sucesso ou fracasso do k-means)

Escalonamento de atributos geralmente é essencial

O k-means é baseado em distância. Se um atributo tiver um intervalo numérico maior, ele pode dominar as distâncias.

Correção comum: padronizar atributos (média zero, variância unitária) ou normalizar adequadamente.

Isso se conecta de perto a Escalonamento de Atributos. Um fluxo de trabalho típico é:

  • imputar valores ausentes
  • escalar atributos numéricos
  • aplicar one-hot encoding a atributos categóricos (com cautela; veja abaixo)
  • executar k-means

Escolha da métrica de distância (e o que o k-means implica)

O k-means padrão corresponde a minimizar distâncias euclidianas (Euclidean) ao quadrado. Se a noção de similaridade dos seus dados não for euclidiana, o k-means padrão pode ser uma má escolha.

Existem variantes (por exemplo, k-means esférico com similaridade do cosseno (cosine similarity) para texto), mas o k-means clássico assume geometria euclidiana.

Sensibilidade a outliers

O k-means usa a média; médias não são robustas. Um único outlier extremo pode:

  • puxar um centróide para longe da região densa
  • distorcer atribuições
  • aumentar a WCSS e reduzir a qualidade dos clusters

Mitigações:

  • remover ou limitar outliers (winsorização (winsorization))
  • usar pré-processamento robusto (Detecção de Outliers)
  • considerar alternativas como k-medoides (k-medoids) (usa medoides, mais robusto) ou clusterização baseada em densidade como DBSCAN

Suposições sobre a forma dos clusters

O k-means tende a funcionar melhor quando os clusters são:

  • aproximadamente esféricos/convexos no espaço de atributos
  • semelhantes em tamanho e densidade

Ele tem dificuldade quando:

  • clusters são alongados, aninhados ou não convexos
  • densidades diferem fortemente (um cluster esparso vs. um cluster denso)
  • há muitos clusters sobrepostos

Nesses casos, Modelos de Mistura Gaussiana (atribuições suaves, elipsoides via covariâncias) ou DBSCAN podem ser melhores.

Problemas com dados de alta dimensionalidade

Em altas dimensões, distâncias tornam-se menos informativas (muitos pontos parecem estar a distâncias similares). Isso se relaciona à Maldição da Dimensionalidade.

Mitigações comuns:

Atributos categóricos e vetores esparsos

O k-means não é naturalmente adequado a variáveis categóricas porque “médias” de categorias não são significativas. Abordagens típicas:

  • aplicar one-hot encoding às categorias e, em seguida, escalar com cuidado (mas a distância euclidiana em one-hot pode ser questionável)
  • usar algoritmos projetados para dados mistos (por exemplo, k-prototypes), quando apropriado
  • para dados de texto, considerar variantes de clusterização baseadas em cosseno em vez de k-means euclidiano simples

Clusters vazios

Às vezes um centróide acaba sem pontos atribuídos. Implementações lidam com isso:

  • reinicializando esse centróide para um ponto aleatório
  • movendo-o para o ponto mais distante dos centróides existentes
  • usando semeadura k-means++ e múltiplas reinicializações para reduzir a chance

Complexidade e escalabilidade

Para (n) pontos em (d) dimensões e (k) clusters, cada iteração custa aproximadamente:

[ O(nkd) ]

Isso pode ser caro para grandes (n) e (k), mas o k-means ainda é frequentemente mais rápido do que métodos de clusterização mais complexos.

Para cenários em larga escala:

  • k-means por mini-batch (mini-batch k-means) atualiza centróides usando pequenos lotes aleatórios, melhorando significativamente a velocidade com pequena perda de qualidade.
  • Use estruturas de vizinho mais próximo aproximado (approximate nearest neighbor) ou bibliotecas aceleradas por GPU, quando disponíveis.

Exemplos práticos

Exemplo 1: Segmentação de clientes (dados tabulares)

Objetivo: agrupar clientes em (k) segmentos com base em atributos numéricos de comportamento, por exemplo:

  • gasto anual
  • número de compras
  • tamanho médio do carrinho
  • tempo desde a última compra

Etapas-chave:

  1. Tratar valores ausentes
  2. Escalar atributos (crítico)
  3. Executar k-means com múltiplas inicializações
  4. Interpretar centróides de clusters como “clientes típicos” em cada segmento

Exemplo em Python (scikit-learn):

import numpy as np
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline

X = np.array([
    [1200, 12, 100, 14],
    [3000, 30, 120, 2],
    [800,  10, 80,  40],
    [2500, 25, 110, 5],
])

model = make_pipeline(
    StandardScaler(),
    KMeans(n_clusters=2, init="k-means++", n_init=10, random_state=42)
)

labels = model.fit_predict(X)
print(labels)

Interpretando os resultados:

  • Após o ajuste, inspecione os centros dos clusters (em unidades originais revertendo o escalonamento) para entender o que diferencia os grupos.
  • Use esses segmentos para personalização, campanhas de retenção ou pipelines de análise de churn.

Exemplo 2: Quantização de cores de imagens (compressão)

O k-means pode reduzir o número de cores em uma imagem ao agrupar valores RGB dos pixels em (k) cores. Cada pixel é substituído pela cor do centróide do seu cluster.

Conceitualmente:

  • pontos de dados: pixels em (\mathbb{R}^3) (R,G,B)
  • clusters: cores representativas da paleta
  • k controla compressão vs. fidelidade visual

Esboço:

import numpy as np
from sklearn.cluster import KMeans

# pixels: shape (num_pixels, 3), values 0..255
pixels = ...  

k = 16
km = KMeans(n_clusters=k, init="k-means++", n_init=5, random_state=0)
labels = km.fit_predict(pixels)
palette = km.cluster_centers_.astype(np.uint8)

compressed = palette[labels]  # replace each pixel by palette color

Isso funciona bem porque o espaço RGB é semelhante ao euclidiano e os clusters frequentemente se formam em torno de cores dominantes.

Exemplo 3: Agrupamento de documentos (com ressalvas)

Com texto, você frequentemente representa documentos como vetores TF-IDF (alta dimensionalidade e esparsos). O k-means euclidiano simples pode ser menos apropriado do que variantes baseadas em cosseno, mas abordagens do tipo k-means ainda são comuns.

Pipeline típico:

  • vetorização TF-IDF
  • redução de dimensionalidade opcional (por exemplo, SVD truncada)
  • clusterização com uma métrica de similaridade adequada

Relação com outros métodos

K-means e EM / modelos de mistura gaussiana

O k-means se assemelha ao algoritmo de Maximização da Expectativa (EM):

  • etapa de atribuição ≈ etapa E (mas com atribuições rígidas)
  • etapa de atualização ≈ etapa M (atualiza parâmetros)

Uma abordagem de Modelos de Mistura Gaussiana generaliza o k-means ao:

  • usar probabilidades (atribuições suaves)
  • aprender covariância (clusters elípticos)
  • fornecer um objetivo baseado em verossimilhança

Quando preferir DBSCAN

Se seus dados têm:

  • ruído/outliers
  • formas de clusters irregulares
  • número desconhecido de clusters

então DBSCAN pode ser uma primeira escolha melhor do que o k-means.

Modos comuns de falha (e como diagnosticá-los)

  • Clusters diferem principalmente por atributos sensíveis à escala
    Sintoma: um atributo domina.
    Correção: escalonamento, transformações (log), escalonamento robusto.

  • Outliers criam clusters “quase singletons”
    Sintoma: o centróide é puxado em direção a um ponto extremo.
    Correção: tratamento de outliers, alternativas robustas.

  • Clusters não esféricos são divididos incorretamente
    Sintoma: o k-means divide um cluster longo em várias partes.
    Correção: tente GMMs, clusterização espectral, DBSCAN ou atributos engenheirados.

  • k escolhido grande demais
    Sintoma: clusters minúsculos, resultados instáveis entre execuções.
    Correção: reduzir k, validar com silhueta/estabilidade, considerar hierarquia.

Checklist de boas práticas

  • Use inicialização k-means++.
  • Faça múltiplas inicializações (n_init) e mantenha a melhor WCSS.
  • Escale atributos (frequentemente obrigatório).
  • Trate outliers antes da clusterização.
  • Escolha (k) com uma combinação de:
  • Considere Análise de Componentes Principais para dados de alta dimensionalidade.
  • Valide clusters usando utilidade a jusante (métricas de negócio, qualidade de recuperação, erro de compressão), não apenas WCSS.

Resumo

O agrupamento k-means particiona dados em k grupos ao minimizar a soma dos quadrados das distâncias entre pontos e seus centróides atribuídos. Seu laço central—atribuir ao centróide mais próximo e então recomputar centróides—é simples e rápido, mas o método é sensível à inicialização, ao escalonamento de atributos, a outliers e a suposições sobre a forma dos clusters.

Quando usado com bom pré-processamento (especialmente escalonamento), inicialização robusta (k-means++) e seleção criteriosa de (k), o k-means continua sendo um dos métodos de clusterização baseline mais eficazes e práticos em aprendizado de máquina.