Definição Formal
Dado um conjunto de observações (x₁, x₂, ..., xₙ), onde cada observação é um vetor real d-dimensional, o agrupamento k-means tem como objetivo particionar as n observações em k (≤ n) conjuntos S = {S₁, S₂, ..., Sₖ} de forma a minimizar a soma dos quadrados dentro dos agrupamentos (WCSS), ou seja, a variância. Formalmente, o objetivo é encontrar:
argmin sobre S da soma de i=1 até k da soma de x em Sᵢ de ||x - μᵢ||²,
onde μᵢ é a média (também chamada de centroide) dos pontos em Sᵢ, e ||·|| é a norma L2 usual. Isso equivale a minimizar os desvios quadrados pareados de pontos no mesmo agrupamento, como mostrado pela identidade de que a soma das distâncias quadradas à média é igual à distância quadrada média pareada.
Algoritmo
O algoritmo mais comum, frequentemente chamado de algoritmo de Lloyd, usa uma abordagem de refinamento iterativo. Ele começa com um conjunto inicial de k centroides, depois alterna entre duas etapas: atribuição e atualização. Na etapa de atribuição, cada observação é designada ao agrupamento cujo centroide está mais próximo, tipicamente usando a distância euclidiana. Na etapa de atualização, o centroide de cada agrupamento é recalculado como a média dos pontos designados. Essas etapas se repetem até que as atribuições não mudem mais, indicando convergência para um ótimo local.
A inicialização é crucial; o método k-means++, que espalha os centroides iniciais, é uma heurística popular para melhorar o resultado final do agrupamento. O algoritmo é sensível à escolha de k, e métodos como o método do cotovelo ou a análise de silhueta são usados para estimar um número apropriado de agrupamentos.
Propriedades e Limitações
K-means assume que os agrupamentos são esférico e de tamanho semelhante, o que limita sua aplicabilidade a dados com formatos de agrupamentos complexos. Ele também é sensível a dados fora da curva (outliers), pois a média é influenciada por valores extremos. O algoritmo converge para um ótimo local, não necessariamente o global, e inicializações diferentes podem resultar em resultados diferentes. Apesar dessas limitações, sua simplicidade e escalabilidade o tornam uma escolha popular para grandes conjuntos de dados, especialmente em Data Augmentation e pipelines de pré-processamento.
Aplicações
O k-means é usado em vários domínios. Em inteligência artificial, ele serve como referência para tarefas de agrupamento. Em visão computacional, ele é usado para segmentação de imagens e quantização de cores. Em marketing, ele ajuda a segmentar clientes com base no comportamento de compra. Em linguística, ele pode agrupar documentos ou embeddings de palavras. O algoritmo também é um bloco de construção para técnicas mais avançadas, como aprendizado profundo e Generative AI em modelos de aprendizado de características.
Relação com Outros Métodos
O k-means está relacionado aos modelos de mistura gaussiana (GMM), pois ambos usam refinamento iterativo e centroides de agrupamento. No entanto, o GMM permite que os agrupamentos tenham formatos e covariâncias diferentes, enquanto o k-means assume agrupamentos isotrópicos. O classificador de centroides mais próximo, derivado do k-means, é um método simples de classificação supervisionada. O k-means é frequentemente confundido com k-nearest neighbors (k-NN), mas são distintos: o k-means é não supervisionado, enquanto o k-NN é supervisionado.
História e Desenvolvimento
O conceito de k-means foi proposto primeiro pelo matemático Hugo Steinhaus em 1956, e o termo "k-means" foi cunhado por James MacQueen em 1967. O algoritmo de Lloyd, publicado em 1957, mas não amplamente conhecido até 1982, é a implementação padrão. Ao longo dos anos, várias variantes foram desenvolvidas, como o mini-batch k-means para dados em grande escala e o fuzzy c-means para agrupamento suave.