Agrupación (k-means, o de otro modo) con una restricción mínima de tamaño de agrupación

14

Necesito agrupar unidades en grupos para minimizar la suma de cuadrados dentro del grupo (WSS), pero necesito asegurarme de que cada grupo contenga al menos unidades. ¿Alguna idea de si alguna de las funciones de agrupación de R permite la agrupación en agrupaciones sujetas a una restricción de tamaño de agrupación mínima? kmeans () no parece ofrecer una opción de restricción de tamaño.kmk

r clustering Cyrus S
fuente

Respuestas:

5

Use EM Clustering

En la agrupación EM, el algoritmo refina iterativamente un modelo de agrupación inicial para que se ajuste a los datos y determina la probabilidad de que exista un punto de datos en una agrupación. El algoritmo finaliza el proceso cuando el modelo probabilístico se ajusta a los datos. La función utilizada para determinar el ajuste es la probabilidad logarítmica de los datos dados el modelo.

Si se generan grupos vacíos durante el proceso, o si la membresía de uno o más de los grupos cae por debajo de un umbral dado, los grupos con poblaciones bajas se vuelven a sembrar en nuevos puntos y el algoritmo EM se vuelve a ejecutar.

mariana más suave
fuente
Gracias Marianna Preferiría una solución que se base menos en modelos paramétricos (típicamente injustificables), pero que definitivamente lo investigará.
Cyrus S
4

Este problema se aborda en este documento:

Bradley, PS, KP Bennett y Ayhan Demiriz. "Restringido k-significa agrupamiento". Microsoft Research, Redmond (2000) : 1-8.

Tengo una implementación del algoritmo en python.

Behrouz Babaki
fuente
Esto es perfecto, gracias! Usé el rPythonpaquete en R para crear una interfaz para esta implementación a la que accedí desde mi script R.
Michael Ohlrogge
@MichaelOhlrogge ¿tiene un ejemplo en algún lugar (github?) En la interfaz que escribió para llamar a ese paquete de python forma R? ¡Gracias!
Matifou
Lo siento, busqué mi antiguo código pero no pude encontrarlo más.
Michael Ohlrogge
3

Creo que sería solo una cuestión de ejecutar k significa como parte de un bucle if con una prueba para los tamaños de clúster, es decir, contar n en el clúster k; también recuerde que k significa dará resultados diferentes para cada ejecución en los mismos datos, por lo que probablemente deberías ejecutarlo como parte de un ciclo de todos modos para extraer el "mejor" resultado


fuente
1
Gracias Alex. Sin embargo, veo un problema con esto: ¿qué pasa si sobre los bucles las soluciones generadas nunca satisfacen la restricción? Eso podría suceder si k medios se configuraron para ejecutarse sin restricción de tamaño de clúster. Me encantaría una solución que evite esto. (La naturaleza de la aplicación es tal que realmente necesito asegurarme de que los grupos sean de un tamaño mínimo).
Cyrus S
1

¿Qué tan grande es su conjunto de datos? Tal vez podría intentar ejecutar un clúster jerárquico y luego decidir qué clústeres retienen según su dendrograma.

Si su conjunto de datos es enorme, también podría combinar ambos métodos de agrupación: una agrupación no jerárquica inicial y luego una agrupación jerárquica utilizando los grupos del análisis no jerárquico. Puede encontrar un ejemplo de este enfoque en Martínez-Pastor et al (2005)

Manuel Ramón
fuente
Gracias manuel. Esto en realidad suena como una posibilidad muy intrigante. Necesito pensar si la partición jerárquica impondría ciertas restricciones que evitarían que el algoritmo logre la partición óptima del clúster directamente bajo la restricción de tamaño. Pero intuitivamente, puedo ver que esto podría funcionar.
Cyrus S
0

Esto se puede lograr modificando el paso de asignación de clúster (E en EM) formulándolo como un problema de optimización de red lineal de Flujo de costo mínimo (MCF).

He escrito un paquete de Python que usa SimpleMinCostFlow de las herramientas de Investigación de Operaciones de Google, que es una implementación rápida de C ++. Tiene una API scikit-lean estándar.

joshlk
fuente