Agrupamento K-Means

O agrupamento K-means particiona observações em um número fixo de clusters, minimizando a soma total intra-cluster das distâncias quadradas aos centroides dos clusters.

Definition

O agrupamento K-means é um método de particionamento que posiciona um número prescrito de centros de cluster e atribui cada observação ao seu centro mais próximo, de modo a minimizar a distância euclidiana quadrada total das observações aos seus centros atribuídos.

Scope

Este tópico abrange o objetivo da soma dos quadrados intra-cluster, o algoritmo iterativo de atribuição e atualização que alterna entre atribuir pontos ao centroide mais próximo e recalcular os centroides, a dependência da inicialização e os ótimos locais resultantes, a escolha do número de clusters e as suposições e limitações do método.

Core questions

• Como as observações podem ser particionadas para minimizar a dispersão intra-cluster?
• Por que o algoritmo converge apenas para um ótimo local e como isso é mitigado?
• Como o número de clusters é escolhido?
• Quais formas e escalas de cluster o método implicitamente assume?

Key theories

Minimização da soma dos quadrados intra-cluster

O K-means busca a partição e o conjunto de centroides que minimizam a distância quadrada total dos pontos aos seus centros de cluster, um objetivo para o qual a iteração alternada de atribuição-atualização diminui monotonicamente o critério.

Sensibilidade ao ótimo local

Como o objetivo não é convexo, o algoritmo converge para um mínimo local que depende dos centros iniciais, o que motiva múltiplas reinicializações e uma semeadura cuidadosa.

Clinical relevance

O K-means é um método rápido e escalável para particionar grandes conjuntos de dados e é utilizado em quantização vetorial, redução de cores de imagens, segmentação de clientes e como inicialização para modelos mais complexos.

History

A ideia de particionamento baseada em centroides foi formalizada por MacQueen, que nomeou o k-means em 1967, baseando-se no algoritmo de quantização anterior de Lloyd. Tornou-se um dos métodos de agrupamento mais amplamente utilizados devido à sua simplicidade e velocidade.

Debates

Suposições implícitas do k-means

A minimização da distância euclidiana quadrada favorece clusters aproximadamente esféricos e de tamanho semelhante, portanto, o k-means pode ser enganoso quando os clusters são alongados, de tamanho desigual ou não convexos, o que motiva alternativas baseadas em modelos ou em densidade.

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

Por que o k-means oferece resultados diferentes em execuções distintas?

Seu objetivo não é convexo, então o algoritmo converge para um ótimo local que depende dos centros iniciais aleatórios; executá-lo várias vezes e manter o melhor resultado é uma prática padrão.

Como escolho o número de clusters k?

Heurísticas comuns incluem o 'cotovelo' na soma dos quadrados intra-cluster, a estatística de lacuna e a largura média da silhueta, embora nenhuma seja definitiva e o conhecimento do domínio muitas vezes guie a escolha.