Agrupamento com k-means

Encontrar grupos sem ninguém dizer quais são

Imagine espalhar moradores num mapa e querer abrir k lojas de forma que cada pessoa fique perto de uma. Você chuta k locais, manda cada pessoa à loja mais próxima, e então move cada loja para o centro dos seus clientes. Repetindo, as lojas migram até pousarem no coração dos aglomerados naturais de gente.

É exatamente o k-means. Não há rótulos "certos" — o algoritmo descobre os grupos a partir da geometria dos dados, alternando dois passos: atribuir cada ponto ao centroide mais próximo e mover cada centroide para a média dos seus pontos.

Atribuir e mover, até convergir

Os centroides (marcadores grandes) começam amontoados no centro. Cada passo reatribui os pontos por cor e desloca os centroides para o centro dos seus grupos. A inércia só cai — até estabilizar. Mude o k e veja como agrupamentos com k errado ficam estranhos.

O algoritmo de Lloyd

// k-means: agrupar sem rótulos (aprendizado não-supervisionado)

def kmeans(pontos, k, iteracoes=100):
    centroides = escolher_k_aleatorios(pontos, k)
    for _ in range(iteracoes):
        // PASSO 1 — atribuir: cada ponto vai ao centroide mais próximo
        grupos = [[] for _ in range(k)]
        for p in pontos:
            i = argmin(dist(p, c) for c in centroides)
            grupos[i].append(p)

        // PASSO 2 — atualizar: cada centroide vai ao centro do seu grupo
        novos = [media(grupo) for grupo in grupos]

        if novos == centroides: break   // convergiu
        centroides = novos
    return centroides, grupos

// Garante reduzir a INÉRCIA (soma das distâncias² ao centroide)
// a cada passo — até estabilizar num mínimo local.

Escolhendo k e evitando mínimos ruins

// Dois problemas práticos do k-means

// 1. Como escolher k? — Método do cotovelo (elbow)
// Rode k-means para k = 1,2,3,... e plote a inércia:
//   inércia
//    │\
//    │ \___        ← o "cotovelo" (aqui k=3) é o bom valor:
//    │     \____      depois dele, aumentar k quase não ajuda
//    └──────────── k

// 2. Inicialização ruim → mínimo local ruim
// Solução: k-means++ escolhe sementes iniciais bem espalhadas,
// e roda várias vezes guardando o melhor (menor inércia).

// Limitações: assume grupos esféricos e de tamanho parecido;
// sensível à escala das features (normalize antes!).

Agrupando dados de verdade

Mini projeto: implemente k-means do zero em Python/NumPy (atribuir + mover) e aplique a pontos 2D gerados em blobs (sklearn.datasets.make_blobs). Plote os grupos e os centroides a cada iteração e confirme que a inércia decresce monotonicamente.

Projeto principal: use k-means para compressão de imagem por quantização de cores: trate cada pixel como um ponto RGB (3D), agrupe em k=16 cores e substitua cada pixel pela cor do seu centroide. Compare a imagem com 16 cores vs. as originais 16 milhões — visualmente quase idêntica, com fração do tamanho. Plote a imagem reconstruída para k = 2, 4, 8, 16, 32.

Desafio extra: implemente o método do cotovelo automaticamente: rode k de 1 a 10, registre a inércia e detecte o "cotovelo" (maior variação de curvatura). Compare com o silhouette score, outra métrica de qualidade de cluster. Os dois concordam sobre o melhor k no seu dataset?

Teste sua intuição

Onde você encontra isso