Como decidir o número correto de clusters?

54

Encontramos os centros de cluster e atribuímos pontos a k diferentes compartimentos de cluster no cluster k-means, que é um algoritmo muito conhecido e é encontrado quase em todos os pacotes de aprendizado de máquina da rede. Mas a parte que falta e mais importante na minha opinião é a escolha de um k correto. Qual é o melhor valor para isso? E, o que se entende por melhor ?

Eu uso o MATLAB para computação científica, onde analisar gráficos de silhueta é uma forma de decidir sobre o k discutido aqui . No entanto, eu estaria mais interessado em abordagens bayesianas. Todas as sugestões são apreciadas.

petrichor
fonte
2
Boa pergunta ...
Na visualização para cluster, existe (ahem) uma maneira de visualizar os clusters k e ver o efeito de vários k de uma só vez, usando MSTs.
Denis #
Eu respondi a essa pergunta com uma meia dúzia de métodos em Rcima aqui
Ben
11
Decidir sobre o "melhor" número k de clusters implica comparar soluções de cluster com k diferentes - qual solução é "melhor". Nesse aspecto, a tarefa parece semelhante à comparação de métodos de cluster - o que é "melhor" para seus dados. As diretrizes gerais estão aqui .
ttnphns

Respostas:

28

Isso já foi solicitado algumas vezes no stackoverflow: aqui , aqui e aqui . Você pode dar uma olhada no que a multidão ali pensa sobre essa questão (ou uma pequena variante dela).

Deixe-me também copiar minha própria resposta para esta pergunta, no stackoverflow.com:

Infelizmente, não há como definir automaticamente o K "certo" nem definir o que é "certo". Não existe um método estatístico baseado em princípios, simples ou complexo que possa definir o "K certo". Existem heurísticas, regras práticas que às vezes funcionam, às vezes não.

A situação é mais geral, já que muitos métodos de agrupamento têm esse tipo de parâmetro, e acho que esse é um grande problema em aberto na comunidade de pesquisa de agrupamento / aprendizado não supervisionado.

carlosdc
fonte
Depois de ler isso - me parece tão intuitivo .... mas devo dizer que nunca pensei nisso antes. que realmente o problema de escolher o número de PCs em PCA é equivalente ao problema de escolher o número de clusters no K-média ...
Dov
2
@ Dov essas duas coisas não são exatamente equivalentes. Existem medidas específicas que podem ser usadas para examinar a qualidade de uma solução de PCA (principalmente erro de reconstrução, mas também% de variância capturada etc.), e essas tendem a ser (principalmente) consistentes. No entanto, no cluster, geralmente não existe uma "resposta correta" - um cluster pode ser melhor que outro em uma métrica e o inverso pode ser verdadeiro usando outra métrica. E, em algumas situações, dois agrupamentos diferentes podem ser igualmente prováveis ​​sob a mesma métrica.
tdc
@tdc, mas não fazer isso en.wikipedia.org/wiki/... é mais ou menos assim improvedoutcomes.com/docs/WebSiteDocs/PCA/... ?
Dov
2
@Dov Sim, eles são "mais ou menos" um do outro, mas eu estava simplesmente dizendo que o problema de escolher o número de clusters é muito mais complicado do que escolher o número de PCs - ou seja, eles não são "equivalentes".
tdc
11
+1 Você está certo. Nós tipo de introduzir algum outro modelo ou pressuposto para decidir sobre o melhor k mas então a questão torna-se por isso é que o modelo ou hipótese a melhor ...
Petrichor
19

Em primeiro lugar uma ressalva. No cluster, geralmente não existe uma "resposta correta" - um cluster pode ser melhor que outro em uma métrica e o inverso pode ser verdadeiro usando outra métrica. E, em algumas situações, dois agrupamentos diferentes podem ser igualmente prováveis ​​sob a mesma métrica.

Dito isto, você pode querer dar uma olhada nos Processos Dirichlet . Veja também este tutorial .

Se você começar com um modelo de Mistura Gaussiana, terá o mesmo problema que os meios-k - precisará escolher o número de clusters. Você pode usar evidência de modelo, mas não será robusta neste caso. Portanto, o truque é usar um processo de Dirichlet antes dos componentes da mistura, o que permite que você tenha um número potencialmente infinito de componentes da mistura, mas o modelo (normalmente) encontrará automaticamente o número "correto" de componentes (sob as premissas de o modelo).

αα

tdc
fonte
11
Um processo de Dirichlet sob qual parâmetro de concentração? É equivalente à mesma pergunta original, k-significa sob o que k? Embora eu concorde que entendemos melhor a distribuição Direchlet que o comportamento de algum algoritmo complexo em alguns dados do mundo real.
Carlosdc
@carlosdc bom ponto, eu atualizei a resposta para incluir um pouco de discussão sobre o parâmetro de concentração
tdc
11
Na minha experiência, é muito mais fácil aprender um parâmetro de concentração com valor contínuo como alfa do que determinar o número de clusters em um modelo de mistura finita. Se você quiser ficar com o modelo de mistura finita, e tomar um rumo Bayesian, existe salto reversível MCMC ( onlinelibrary.wiley.com/doi/10.1111/1467-9868.00095/abstract )
11
Ótima resposta. Eu acrescentaria o artigo Revisitando K-Means: Novos Algoritmos via Não Paramétricos Bayesianos . O que fornece uma abordagem "contínua" simples ao K-Means. Então é fácil, usando a otimização, encontrar o valor ideal.
Royi 30/12/19
9

Eu uso o método Elbow :

  • Comece com K = 2 e continue aumentando a cada etapa em 1, calculando seus clusters e o custo que acompanha o treinamento. Em algum valor para K, o custo cai drasticamente e, depois disso, atinge um platô quando você aumenta ainda mais. Este é o valor K que você deseja.

A lógica é que, depois disso, você aumenta o número de clusters, mas o novo cluster fica muito próximo de alguns dos existentes.

vonPetrushev
fonte
Parece que é o princípio que o método L (veja minha resposta) avalia.
winwaed
6

Os tamanhos de cluster dependem muito dos seus dados e para o que você usará os resultados. Se você estiver usando seus dados para dividir as coisas em categorias, tente imaginar quantas categorias você deseja primeiro. Se for para visualização de dados, torne-o configurável, para que as pessoas possam ver os clusters grandes e os menores.

Se você precisar automatizá-lo, poderá adicionar uma penalidade ao aumento de k e calcular o cluster ideal dessa maneira. E então você pesa k, dependendo se você quer uma tonelada de clusters ou se deseja muito poucos.

neurônio
fonte
5

Consegui usar o "Método L" para determinar o número de clusters em um aplicativo geográfico (isto é, essencialmente um problema 2d, embora tecnicamente não-euclidiano).

O Método L é descrito aqui: Determinando o Número de Clusters / Segmentos em Algoritmos Hierárquicos de Cluster / Segmentação Stan Salvador e Philip Chan

Essencialmente, isso avalia o ajuste para vários valores de k. Um gráfico em forma de "L" é visto com o valor ótimo de k representado pelo joelho no gráfico. Um cálculo simples de ajuste de mínimos quadrados de linha dupla é usado para encontrar o ponto do joelho.

Achei o método muito lento porque o k-means iterativo deve ser calculado para cada valor de k. Também achei que o k-means funcionou melhor com várias execuções e escolhendo a melhor no final. Embora cada ponto de dados possua apenas duas dimensões, uma simples distância pitagórica não pôde ser usada. Então isso é muito calculista.

Um pensamento é pular todos os outros valores de k (digamos) para metade dos cálculos e / ou reduzir o número de iterações de meios k e, em seguida, suavizar levemente a curva resultante para produzir um ajuste mais preciso. Perguntei sobre isso no StackOverflow - IMHO, a questão da suavização continua sendo uma questão de pesquisa aberta.

winwaed
fonte
4

k

Mas e se o seu conjunto de dados não se encaixar no esquema Voronoi?

kk

k

Anony-Mousse
fonte
3
Embora a descrição dos meios K no primeiro parágrafo não esteja errada, isso pode levar algumas pessoas a equacionar esse método com o particionamento Voronoi com base nos dados originais. Não é assim: a partição é baseada nos locais dos meios do cluster, que podem não (e geralmente não irão) coincidir com nenhum dos dados originais.
whuber
3

No geral, você pode escolher o número de clusters em dois caminhos diferentes.

  1. orientado pelo conhecimento: você deve ter algumas idéias de quantos clusters você precisa do ponto de vista comercial. Por exemplo, você está agrupando clientes, deve perguntar a si mesmo, depois de obter esses clientes, o que devo fazer em seguida? Pode ser que você tenha tratamento diferente para diferentes grupos? (por exemplo, publicidade por email ou telefone). Então, quantos tratamentos possíveis você está planejando? Neste exemplo, você seleciona, digamos, 100 clusters não fará muito sentido.

  2. Acionado por dados: maior número de clusters está em excesso e menos número de clusters está em mau ajuste. Você sempre pode dividir os dados ao meio e executar a validação cruzada para ver quantos números de clusters são bons. Observe que, no cluster, você ainda tem a função de perda, semelhante à configuração supervisionada.

Por fim, você deve sempre combinar conhecimento e dados, no mundo real.

Haitao Du
fonte
2

Como ninguém apontou ainda, pensei em compartilhar isso. Existe um método chamado X-means, ( veja este link ) que estima o número adequado de clusters usando o critério de informação bayesiano (BIC). Essencialmente, isso seria como tentar K significa com Ks diferentes, calculando o BIC para cada K e escolhendo o melhor K. Esse algoritmo faz isso com eficiência.

Há também uma implementação weka , cujos detalhes podem ser encontrados aqui .

Rivu
fonte
0

Outra abordagem é usar um algoritmo evolutivo cujos indivíduos tenham cromossomos de diferentes comprimentos. Cada indivíduo é uma solução candidata: cada um carrega as coordenadas dos centróides. O número de centróides e suas coordenadas são evoluídos para alcançar uma solução que produza a melhor pontuação de avaliação de cluster.

Este artigo explica o algoritmo.

felipeduque
fonte