Agrupación (k-medios, o de otra manera) con una restricción de tamaño de clúster mínimo

Question

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

Answer 1

Este problema se aborda en este documento:

Bradley, P. S., K. P. Bennett y Ayhan Demiriz. "Constrained k-means clustering." Microsoft Research, Redmond (2000): 1-8.

Tengo una implementación del algoritmo en Python.

Answer 2

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 python que utiliza las herramientas de investigación de operaciones de Google SimpleMinCostFlow, que es una implementación rápida de C++. Its tiene una API estándar de scikit-lean.