Agrupamento K-means
- Proposto por
- MacQueen, J. B.; Lloyd, S. P.
- Ano
- 1967 (formalized 1982)
- Tipo
- Partitional clustering
- Família
- Machine learning
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
K-means é um algoritmo clássico de agrupamento particional não supervisionado que divide um conjunto de dados em K grupos não sobrepostos, atribuindo iterativamente cada observação ao seu centroide mais próximo e atualizando os centroides como a média dos pontos atribuídos a eles.
É uma das ferramentas exploratórias mais amplamente utilizadas em aprendizado de máquina e análise de dados.
A intuição por trás do método
Imagine soltar K ímãs em um mapa de pontos de dados. Cada ponto é atraído para o seu ímã mais próximo, e então cada ímã se move para o centro de gravidade dos pontos que atraiu. Repita este ciclo de "puxar e mover" até que nada se mova: os ímãs encontraram K agrupamentos naturais. K-means formaliza exatamente essa ideia, minimizando a distância quadrada total de cada ponto ao centro de seu cluster, chamada de soma dos quadrados dentro do cluster (WCSS ou inércia).
História
A ideia do k-means foi introduzida independentemente por MacQueen em 1967, que cunhou o termo, e formalizada como um algoritmo iterativo eficiente por Stuart Lloyd no Bell Labs na década de 1950 (publicado em 1982). A melhoria da inicialização k-means++ por Arthur e Vassilvitskii em 2007 abordou o problema da sensibilidade ao mínimo local. Hoje, o k-means continua sendo um método de aprendizado não supervisionado fundamental ensinado em praticamente todos os currículos de ciência de dados.
Quando usar
K-means é adequado para agrupamento exploratório de grandes conjuntos de dados puramente numéricos quando você precisa de particionamento rápido e escalável e se sente confortável em especificar K antecipadamente ou procurá-lo com o método do cotovelo ou da silhueta. Funciona bem para segmentação de clientes, compressão de imagens, agrupamento de tópicos de documentos e pré-processamento antes do aprendizado supervisionado. Evite-o quando os clusters não são esféricos, têm tamanhos ou densidades muito variáveis, quando as características são categóricas ou ordinais (use k-modes ou k-prototypes em vez disso), quando o número de clusters é totalmente desconhecido e experimentos com K variável não são viáveis, ou quando os dados contêm muitos outliers (use DBSCAN ou variantes robustas em vez disso).
Limitações e considerações
- Requer que K seja especificado antecipadamente; escolher K de forma inadequada produz clusters sem sentido.
- Assume clusters esféricos e de tamanho semelhante; clusters alongados, irregulares ou com escalas diferentes são divididos ou mesclados incorretamente.
- Sensível a outliers: um único ponto extremo pode afastar um centroide do grosso do cluster.
- Funciona apenas com características numéricas contínuas; dados categóricos exigem um algoritmo diferente (k-modes).
- Converge para um mínimo local; os resultados podem variar entre execuções com diferentes sementes aleatórias, a menos que k-means++ ou múltiplas reinicializações sejam usadas.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Rápido e escalável: O(nKdi) por iteração, prático em milhões de observações com K e dimensões moderados.
- Simples de implementar, amplamente disponível em todas as principais estruturas de ML e fácil de explicar para públicos não técnicos.
- Funciona bem em clusters grandes, bem separados e aproximadamente esféricos de tamanho semelhante.
- A inicialização k-means++ reduz substancialmente a sensibilidade às condições iniciais em comparação com a inicialização aleatória.
- Determinístico dentro de uma semente aleatória fixa, tornando os resultados reproduzíveis.
Aplicações
- Segmentação de clientes para marketing e personalização com base em características comportamentais ou demográficas.
- Compressão de imagem quantificando as cores dos pixels para K valores representativos (quantização de cores).
- Agrupamento de documentos e textos como um passo em pipelines de modelagem de tópicos após a vetorização.
- Pré-processamento de detecção de anomalias: pontos distantes de qualquer centroide são candidatos a outliers.
- Etapa de inicialização para algoritmos mais complexos, como modelos de mistura gaussiana ou agrupamento hierárquico.
- Análise de expressão gênica para agrupar genes ou amostras com perfis de expressão semelhantes.
Como funciona
Como funciona
K centroides de cluster são posicionados no espaço de características, seja selecionando aleatoriamente K pontos de dados (Forgy) ou pela estratégia mais inteligente k-means++ que espalha os centroides iniciais para reduzir a chance de mínimos locais ruins. A escolha da inicialização é importante: k-means++ geralmente resulta em convergência mais rápida e melhores soluções finais.
Cada observação é atribuída ao cluster cujo centroide é o mais próximo de acordo com a distância euclidiana. Essa atribuição "rígida" cria K partições não sobrepostas dos dados. Formalmente, cada ponto x_i é atribuído ao cluster c_i = argmin_k ||x_i - mu_k||^2.
Fórmula
c_i = \arg\min_k \|x_i - \mu_k\|^2
Cada centroide é recalculado como a média aritmética de todos os pontos atualmente atribuídos a esse cluster: mu_k = (1/|C_k|) vezes a soma de todos os x_i em C_k. Este passo garante que o novo centroide minimize o WCSS dentro de cada cluster, dada a atribuição atual.
Fórmula
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_iOs passos de atribuição e atualização alternam até que as posições dos centroides parem de mudar (ou mudem por menos de um limiar de tolerância) ou um número máximo de iterações seja atingido. O algoritmo tem garantia de convergir para um mínimo local do WCSS, embora não necessariamente o mínimo global.
A qualidade da solução é avaliada com o WCSS total (inércia) J = soma sobre os clusters da soma sobre os pontos atribuídos de ||x_i - mu_k||^2. A escolha de K é uma preocupação separada abordada pelo método do cotovelo, pontuações de silhueta ou estatísticas de lacuna, pois o próprio algoritmo exige que K seja especificado antecipadamente.
Fórmula
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2Erros comuns
- Esquecer de padronizar as características antes do agrupamento — variáveis em grandes escalas dominarão os cálculos de distância.
- Selecionar K inspecionando apenas o WCSS dentro da amostra sem o gráfico do cotovelo ou a validação da silhueta, levando a K trivialmente pequeno ou grande.
- Executar apenas uma inicialização e aceitar o primeiro resultado sem múltiplas reinicializações para se proteger contra mínimos locais ruins.
- Incluir variáveis categóricas ou ordinais na matriz de características sem codificação apropriada ou mudar para k-modes.
- Tratar rótulos de cluster como identidades de grupo significativas sem validação externa, especialmente quando os clusters não estão bem separados.
Perguntas frequentes
Como escolho o número certo de clusters K?
Execute o k-means para uma faixa de valores de K, plote a soma dos quadrados dentro do cluster contra K e procure por um 'cotovelo' onde a taxa de diminuição diminui drasticamente. Complemente isso com pontuações de silhueta, que medem o quão semelhante cada ponto é ao seu próprio cluster versus clusters vizinhos; uma silhueta média mais alta indica clusters mais bem definidos.
Por que obtenho resultados diferentes a cada execução?
O K-means é sensível à inicialização e converge para um mínimo local, e não global, do WCSS. Use a inicialização k-means++ e defina uma semente aleatória fixa para reprodutibilidade. Executar o algoritmo várias vezes com diferentes sementes e manter a solução com a menor inércia é uma boa prática.
O k-means funciona com dados categóricos?
Não. O K-means depende da distância euclidiana e das médias dos centroides, que são indefinidas para variáveis categóricas. Para dados puramente categóricos, use k-modes; para dados mistos numéricos e categóricos, use k-prototypes.
Quando devo preferir DBSCAN ou GMM em vez de k-means?
Use DBSCAN quando os clusters têm formas irregulares ou você precisa de detecção automática de outliers sem especificar K. Use Modelos de Mistura Gaussiana (GMM) quando você deseja atribuições de cluster "suaves" (probabilísticas) ou clusters de diferentes tamanhos e orientações, ao custo de maior complexidade computacional.
Preciso escalar minhas características?
Sim, quase sempre. O K-means usa a distância euclidiana, então características com grandes intervalos numéricos dominarão o agrupamento. Aplique a padronização z-score ou o escalonamento min-max antes de ajustar o k-means, a menos que todas as características já estejam na mesma escala.
Métodos relacionados
Fontes
Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.
Abrir referência DOICopiado.MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
Abrir referência da publicaçãoCopiado.