Cluster (k-mean ou outro) com uma restrição de tamanho mínimo de cluster

14

Preciso agrupar unidades em clusters para minimizar a soma de quadrados dentro do grupo (WSS), mas preciso garantir que cada um dos clusters contenha pelo menos m unidades. Alguma idéia se alguma das funções de cluster de R permitir agrupar em k clusters sujeitos a uma restrição mínima de tamanho de cluster? O kmeans () parece não oferecer uma opção de restrição de tamanho.kmk

r clustering Cyrus S
fonte

Respostas:

5

Use o clustering EM

No clustering EM, o algoritmo refina iterativamente um modelo de cluster inicial para ajustar os dados e determina a probabilidade de que exista um ponto de dados em um cluster. O algoritmo termina o processo quando o modelo probabilístico se ajusta aos dados. A função usada para determinar o ajuste é a probabilidade de log dos dados, conforme o modelo.

Se clusters vazios forem gerados durante o processo, ou se a associação de um ou mais clusters cair abaixo de um determinado limite, os clusters com populações baixas serão novamente gerados em novos pontos e o algoritmo EM será executado novamente.

mariana soffer
fonte
Obrigado, Marianna. Eu preferiria uma solução que se baseie menos nos modelos paramétricos (normalmente injustificáveis), mas que definitivamente analisará.
Cyrus S
4

Este problema é tratado neste documento:

Bradley, PS, KP Bennett e Ayhan Demiriz. "K-significa restrito agrupamento." Pesquisa Microsoft, Redmond (2000) : 1-8.

Eu tenho uma implementação do algoritmo em python.

Behrouz Babaki
fonte
Isso é perfeito, obrigado! Usei o rPythonpacote no R para criar uma interface para esta implementação que eu acessei do meu script R.
Michael Ohlrogge 27/02
@MichaelOhlrogge você tem um exemplo em algum lugar (github?) Na interface que você escreveu para chamar esse pacote python de formulário R? Obrigado!
Matifou 8/02
Desculpe, olhei em volta do meu código antigo, mas não consegui mais encontrá-lo.
Michael Ohlrogge
3

Eu acho que seria apenas uma questão de executar os meios k como parte de um loop if com um teste para tamanhos de cluster, ou seja, Contar n no cluster k - lembre-se também de que os meios k fornecerão resultados diferentes para cada execução nos mesmos dados. você provavelmente deve executá-lo como parte de um loop de qualquer maneira para extrair o "melhor" resultado


fonte
1
Obrigado Alex. No entanto, vejo um problema com isso: e se, ao longo dos loops, as soluções geradas nunca satisfizerem a restrição? Isso poderia acontecer se os meios k estivessem configurados para serem executados sem restrição de tamanho de cluster. Eu adoraria uma solução que evite isso. (A natureza da aplicação é tal que eu realmente preciso para garantir clusters são de um tamanho mínimo.)
Cyrus S
1

Qual é o tamanho do seu conjunto de dados? Talvez você possa tentar executar um cluster hierárquico e decidir quais clusters serão retidos com base no seu dendrograma.

Se o seu conjunto de dados for grande, você também poderá combinar os dois métodos de cluster: um cluster não hierárquico inicial e, em seguida, um cluster hierárquico usando os grupos da análise não hierárquica. Você pode encontrar um exemplo dessa abordagem em Martínez-Pastor et al (2005)

Manuel Ramón
fonte
Obrigado Manuel. Isso realmente soa como uma possibilidade muito intrigante. Preciso pensar se o particionamento hierárquico imporia certas restrições que impediriam o algoritmo de atingir o particionamento ideal de cluster diretamente sob a restrição de tamanho. Mas intuitivamente, posso ver que isso pode funcionar.
Cyrus S
0

Isso pode ser alcançado modificando a etapa de atribuição de cluster (E em EM), formulando-a como um problema de otimização de rede linear de fluxo de custo mínimo (MCF).

Eu escrevi um pacote python que usa o SimpleMinCostFlow das ferramentas de Pesquisa Operacional do Google, que é uma implementação rápida de C ++. Tem uma API padrão do scikit-lean.

joshlk
fonte