K-Means Clustering

O agrupamento k-means é um algoritmo de aprendizado não supervisionado que divide os dados em k grupos, cada um representado por seu centróide, a média dos pontos atribuídos a ele. O algoritmo busca a partição com a menor soma de distâncias quadráticas dentro dos agrupamentos, uma medida chamada inércia, para que os pontos de cada agrupamento fiquem próximos de seu centróide. O procedimento padrão é o algoritmo de Lloyd, que Stuart Lloyd desenvolveu nos Bell Labs em 1957 para quantizar sinais, e o nome "k-means" vem de um artigo de James MacQueen, de 1967. Por ser simples, rápido e capaz de escalar para milhões de pontos, o k-means é uma ferramenta padrão para mineração de dados, compressão e exploração da estrutura de dados sem rótulo.

Como o algoritmo funciona#

Depois de escolher os centróides iniciais, o algoritmo de Lloyd alterna entre uma etapa de atribuição e uma etapa de atualização até que os agrupamentos parem de mudar:

1. Inicialização: Escolha k centróides iniciais. O padrão do Scikit-learn, k-means++, escolhe o primeiro centróide aleatoriamente e cada um dos seguintes com uma probabilidade proporcional à distância quadrática até o centróide escolhido mais próximo, mantendo as sementes afastadas.
2. Atribuição: Atribua cada ponto ao centróide mais próximo, geralmente pela distância euclidiana.
3. Atualização: Mova cada centróide para a média dos pontos que agora estão atribuídos a ele.
4. Repetição: Volte à etapa de atribuição até que nenhum ponto mude de agrupamento ou os centróides se movam menos do que uma tolerância.

Nenhuma das etapas pode aumentar a inércia, então o ciclo sempre converge, mas apenas para um mínimo local que depende dos centroides iniciais. Encontrar o ótimo global é NP-difícil, por isso as implementações executam várias inicializações e mantêm aquela com a menor inércia. Em KMeans do scikit-learn, o padrão n_init="auto" executa uma vez ao inicializar com k-means++, e 10 vezes ao inicializar aleatoriamente.

Como escolher o número de agrupamentos#

O k-means exige que k seja definido de antemão. A inércia sempre diminui à medida que k aumenta, pois mais centróides ficam mais próximos dos pontos. Por isso, o método do cotovelo plota a inércia em relação a k e procura o ponto em que a queda começa a se estabilizar. A pontuação de silhueta compara, para cada ponto, a distância média ao próprio agrupamento com a distância média ao agrupamento mais próximo, e varia de -1 a 1; valores maiores indicam agrupamentos compactos e bem separados. Este exemplo calcula a pontuação para k de 2 a 6 em dados distribuídos ao redor de quatro centros:

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

A inércia cai de 18.363, com k=2, para 5.241, com k=3, e 1.127, com k=4; depois, cai apenas para 1.039, com k=5, e 922, com k=6, então o cotovelo fica em k=4. A pontuação de silhueta confirma esse resultado: ela atinge o pico de 0,811 com k=4 e cai para 0,687 com k=5, recuperando os quatro centros usados para gerar os dados.

Premissas e variantes#

O k-means funciona melhor quando os agrupamentos são aproximadamente esféricos, têm tamanhos semelhantes e estão separados no espaço euclidiano. Recursos em escalas maiores dominam a distância, então os dados geralmente são padronizados primeiro. Cada ponto é atribuído a algum agrupamento, e alguns valores discrepantes extremos podem afastar um centróide do grupo. Algumas variantes atenuam essas limitações:

• K-means em minilotes: Atualiza os centróides com pequenos lotes aleatórios, trocando um pouco de precisão por um treinamento muito mais rápido em conjuntos de dados grandes.
• K-medoids: Usa pontos reais dos dados como centros dos agrupamentos, o que o torna mais resistente a valores discrepantes e permite usar qualquer medida de distância.
• C-means fuzzy: Atribui a cada ponto um grau de pertinência a cada agrupamento, seguindo o princípio da lógica fuzzy, em vez de uma única atribuição rígida.
• Modelos de mistura gaussiana: Ajustam uma distribuição de probabilidade por agrupamento, o que permite agrupamentos elípticos de diferentes tamanhos e produz atribuições probabilísticas flexíveis.

Aplicações em IA e visão computacional#

• Quantização de cores: Agrupar as cores dos pixels de uma imagem e substituir cada pixel pelo centroide reduz uma foto com milhares de cores a uma paleta de k cores, o que comprime a imagem e também oferece uma forma rápida e aproximada de segmentação de imagens.
• Codebooks e quantização vetorial: Os centroides formam um codebook, e cada vetor é armazenado como o índice do centroide mais próximo. A recuperação de imagens clássica por saco de palavras visuais criou seus vocabulários dessa forma, a partir de descritores locais de imagens.
• Projeto de caixas-âncora: O YOLOv2 executou k-means nas larguras e alturas das caixas de treinamento, usando 1 menos IoU como distância, para escolher suas caixas-âncora.
• Paletização de pesos: Exportar YOLO26 para Core ML com quantize=8 agrupa os valores de cada tensor de pesos grande em 256 centroides usando k-means, de modo que o modelo exportado armazena um índice de 8 bits por peso, além de uma pequena tabela de consulta.
• Segmentação de clientes: varejistas agrupam clientes por frequência de compra, tamanho do carrinho e recência para adaptar as ofertas a cada segmento.

K-Means vs. algoritmos relacionados#

• K-vizinhos mais próximos (KNN): O "k" compartilhado causa confusão. O KNN é um algoritmo supervisionado que atribui um rótulo a um novo ponto com base nos k exemplos rotulados mais próximos, enquanto o k-means não é supervisionado e k representa o número de agrupamentos que ele cria.
• DBSCAN: Agrupa pontos por densidade, encontra sozinho o número de agrupamentos, acompanha agrupamentos de qualquer formato e rotula pontos esparsos como ruído, em vez de forçá-los a fazer parte de um agrupamento.
• Agrupamento hierárquico: Cria uma árvore de agrupamentos aninhados ao combinar repetidamente os grupos mais próximos, permitindo escolher k depois, cortando a árvore em qualquer nível, com um custo que cresce pelo menos quadraticamente com o número de pontos.