Agrupamento k-means: onde se começa decide o que se encontra

O k-means é o primeiro algoritmo de agrupamento que se aprende, e tem uma propriedade que raramente se menciona: encontra uma resposta diferente consoante o ponto onde calha começar. Rode o mostrador abaixo. Observe como os mesmos pontos, divididos no mesmo número de partes, se fixam num lugar diferente.

Exemplo resolvido — Agrupamento k-means: onde se começa decide o que se encontra

Soma dos quadrados intra-cluster	1,0989
Iterações até convergir	2
A distância entre elas	430,8%
Respostas diferentes	3 de 24
Logo, esta posição é	a melhor encontrada

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Agrupamento k-means: onde se começa decide o que se encontra

O k-means procura k grupos repetindo duas etapas até nada mais se mover: associa cada ponto ao centro mais próximo e, de seguida, desloca cada centro para a média daquilo que capturou. O que ele tenta minimizar é a soma dos quadrados intra-cluster, a distância total ao quadrado de cada ponto ao seu próprio centro. Como cada uma das duas etapas apenas consegue diminuir esse valor, eis a prova completa de que o algoritmo acaba por parar.

O que significa cada símbolo

k: a quantidade de clusters que solicitou, um valor que os próprios dados não revelam
WCSS: a distância total ao quadrado de cada ponto ao seu próprio centro

Pressupõe: Que um cluster é uma nuvem esférica de dimensão relativamente semelhante, dado que a distância euclidiana ao quadrado até uma média é incapaz de exprimir outra forma. Grupos alongados, aninhados ou muito desiguais não são mal identificados pelo k-means. Eles simplesmente não são o tipo de estrutura que o algoritmo procura.

Todas estas execuções convergiram 🖖

Mantenha os três aglomerados e k = 3. Percorra o mostrador de posição inicial de 1 a 24. Vinte e duas das posições estabilizam em 1,0989. Os números 17 e 21 ficam-se pelos 5,8172 e 5,8331, um resultado 5,3 vezes pior. Unem dois dos aglomerados e cortam o terceiro ao meio. Não houve qualquer erro nessas duas execuções. A convergência do algoritmo de Lloyd é garantida, pois a soma dos quadrados intra-cluster diminui a cada passo e não pode cair eternamente; logo, tem de parar. De facto, em 1536 execuções sobre todos os conjuntos, em todos os k e com ambas as inicializações, nenhuma falhou. O que não é garantido é que pare num sítio bom. Assim, afirmar que o algoritmo convergiu é fazer uma declaração mais sobre aritmética do que sobre os seus dados. Se executou o k-means apenas uma vez, não tem como saber qual destas duas respostas tem em mãos.

O k-means++ reduz o erro a metade e não promete nada 🖖

Altere Como começa para k-means++ e a dispersão neste conjunto desaparece por completo. Todas as vinte e quatro posições iniciais encontram 1,0989. Esta é a solução a que todos recorrem, e funciona porque espalha os centros iniciais em vez de os largar em pontos aleatórios. A melhoria, contudo, é estatística e não garantida, valendo a pena saber em que medida ocorre. Medido ao longo de 112 combinações de conjunto de pontos, tamanho da amostra e k: o k-means++ encontrou um ótimo estritamente melhor do que o arranque aleatório em 38 delas, o método aleatório foi melhor em 17, e os dois empataram em 57. A dispersão média nas vinte e quatro posições iniciais caiu de 55,5% para 31,7%. Assim, reduz quase a metade o erro de uma execução sem sorte, e num em cada seis casos teria sido melhor atirar dardos. Regule o anel para 90 pontos e k = 5 e verá um desses casos. O método aleatório alcança 0,9884 e o k-means++ fica-se por 1,0213.

Uma resposta estável, equilibrada e confiante para uma pergunta sem resposta 🖖

Carregue a última predefinição. Os pontos formam um reticulado regular, desprovido de qualquer cluster, mas o k-means divide-os em quatro grupos de exatamente 25. Agora, analise o que todos os seus diagnósticos dizem sobre esse resultado. Ele convergiu em onze iterações. É estável. Todas as vinte e quatro posições iniciais chegam à mesma conclusão, o que significa que recomeçar não revela que algo está errado. Os clusters estão perfeitamente equilibrados, o que é o aspeto típico de um bom agrupamento. Três sinais distintos apontam no mesmo sentido, e contudo não há ali nada. Esta é a faceta do agrupamento que não tem correção técnica. O k-means responde à questão "onde ficariam k centros" e tem sempre uma resposta, quer a questão "quantos grupos há nestes dados" tenha resposta ou não.

Problema resolvido na íntegra

Não sabe quantos clusters os dados contêm. Vai, portanto, tentar extrair essa resposta do cotovelo na curva de pontuações. Aplique a leitura aos quatro conjuntos de pontos e conte quantas vezes acerta. O painel inferior entrega-lhe a melhor pontuação para cada k de 1 a 8, desenhando em segundo plano a quebra em relação ao k anterior.

Abrir este problema na ferramenta
1. Primeiro, a razão para procurar um cotovelo e não um mínimo. Defina o conjunto para Três nuvens e observe a curva: 10,3978 em k = 1, seguindo-se 5,6145, 1,0989, 0,9241, 0,8052, 0,6875, 0,6077, 0,5366. A curva nunca sobe. Seria impossível. Qualquer agrupamento de k grupos converte-se num de k + 1 grupos ao separar um deles. Esta divisão empurra fatalmente os pontos para mais perto do seu próprio centro. Leve k até ao número total de pontos, e cada ponto passará a ser o seu próprio cluster com a pontuação de exatamente 0.
  
  $WCSS (k) = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}, WCSS (k + 1) \leq WCSS (k) three blobs : 10.3978, 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366$
2. Logo, a curva não esconde nenhum mínimo. A leitura terá, em vez disso, de se concentrar nas quedas. Nas nuvens, elas cifram-se em 46,0%, depois 80,4%, passando a 15,9%, 12,9%, 14,6%, 11,6% e 11,7%. A queda após k = 3 equivale à quinta parte da que a antecede (um colapso por um fator de 5,06), e k = 3 reflete exatamente a forma como os dados foram construídos. O método funciona com mestria aqui. Trata-se do caso clássico apresentado a todos os estudantes.
  
  $drop (k) = 1 - \frac{WCSS ( k + 1 )}{WCSS ( k )}, elbow = ar g max_{k} \frac{drop ( k - 1 )}{drop ( k )} three blobs : 46 . 0%, 80 . 4%, 15 . 9%, 12 . 9%, 14 . 6%, 11 . 6%, 11 . 7% \Rightarrow k = 3, \times 5.06$
3. Vejamos agora o Reticulado, que não possui quaisquer clusters. As suas quedas são de 41,6%, 34,1%, 36,8%, 16,4%, 16,9%, 12,8% e 15,7%. Dá-se um colapso por um fator de 2,25 depois de k = 4. É exatamente este o formato que lhe ensinaram a procurar. No entanto, a leitura do cotovelo devolve "quatro clusters" num conjunto sem nenhum.
  
  $lattice : 41 . 6%, 34 . 1%, 36 . 8%, 16 . 4%, 16 . 9%, 12 . 8%, 15 . 7% \Rightarrow k = 4, \times 2.25$
4. A seguir vem o Anel, um conjunto que tem genuinamente dois grupos. As quedas sucedem-se em 37,2%, 32,8%, 38,5%, 33,4%, 43,1%, 25,3% e 15,3%. Nenhuma tendência visível, ocorrendo apenas dois tombos no final. O colapso mais agudo surge depois de k = 6. A leitura sugere seis; a resposta é dois.
  
  $ring : 37 . 2%, 32 . 8%, 38 . 5%, 33 . 4%, 43 . 1%, 25 . 3%, 15 . 3% \Rightarrow k = 6, \times 1.70$
5. Por fim, o conjunto Desigual, composto por três clusters de tamanhos diferentes: 43,8%, 48,4%, 35,4%, 24,7%, 16,1%, 14,4% e 21,8%. Existe um declínio suave. Não há qualquer colapso à vista. O salto mais marcado limita-se a um fator de 1,53, valor insuficiente para formar uma quina. A leitura não devolve nada em dados que possuem, efetivamente, três clusters.
  
  $uneven : 43 . 8%, 48 . 4%, 35 . 4%, 24 . 7%, 16 . 1%, 14 . 4%, 21 . 8% \Rightarrow k = 5, \times 1.53$
Resposta

Um acerto em quatro: correto nas nuvens, quatro clusters inventados no reticulado, seis propostos para os dois do anel e silêncio no conjunto desigual. O padrão não é um acaso. O cotovelo revela-se acentuado apenas quando os clusters são arredondados, de dimensões semelhantes e bem separados. Nessas situações, a simples observação visual bastaria para os contar. A quina esbate-se em todos os conjuntos onde a ajuda faria realmente falta. Convém reter esta lição antes de utilizar a curva para justificar um número perante terceiros. É esta a razão pela qual o método do cotovelo figura ao lado da pontuação de silhueta, da estatística gap e dos critérios de informação, e não acima deles. Nenhum destes métodos consta desta página. Cada um deles representa uma forma diferente de colocar a mesma pergunta que a curva de pontuações é incapaz de responder: não "onde ficariam k centros", pergunta que tem sempre resposta, mas sim "existem, de facto, grupos aqui?".

$set three blobs lattice ring uneven elbow says 3465 truth 3023 sharpness \times 5.06 \times 2.25 \times 1.70 \times 1.53$

Percurso de aprendizagem

Ajustar uma reta a dados

Referências (3)

The algorithm itself. Written in 1957 for quantising a signal into levels, circulated as a Bell Labs memorandum, and not published for twenty-five years: S. P. Lloyd, “Least squares quantization in PCM.” IEEE Transactions on Information Theory 28(2), 129–137, 1982.
The initialisation the second insight block measures — and the source of the bound that makes it worth using, which is a guarantee about the EXPECTED score rather than about any single run: D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding.” In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’07), 1027–1035. SIAM, 2007.
Where the elbow reading comes from, and it was proposed with more caution than it is usually repeated with: R. L. Thorndike, “Who belongs in the family?” Psychometrika 18(4), 267–276, 1953.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.