Clustering (k-means ou autre) avec une contrainte de taille de cluster minimum

J'ai besoin de regrouper les unités en grappes pour minimiser la somme des carrés au sein du groupe (WSS), mais je dois m'assurer que les grappes contiennent chacune au moins unités. Une idée si l'une des fonctions de clustering de R permet le clustering en clusters soumis à une contrainte de taille de cluster minimum? kmeans () ne semble pas offrir une option de contrainte de taille.m $k$$m$$k$

Utiliser le clustering EM

Dans le clustering EM, l'algorithme affine de manière itérative un modèle de cluster initial pour ajuster les données et détermine la probabilité qu'un point de données existe dans un cluster. L'algorithme met fin au processus lorsque le modèle probabiliste correspond aux données. La fonction utilisée pour déterminer l'ajustement est la log-vraisemblance des données compte tenu du modèle.

Si des clusters vides sont générés au cours du processus, ou si l'appartenance à un ou plusieurs des clusters tombe en dessous d'un seuil donné, les clusters avec de faibles populations sont réensemencés à de nouveaux points et l'algorithme EM est réexécuté.

Ce problème est traité dans cet article:

Bradley, PS, KP Bennett et Ayhan Demiriz. "Cluster k-means contraint." Microsoft Research, Redmond (2000) : 1-8.

J'ai une implémentation de l'algorithme en python.

Je pense qu'il s'agirait simplement d'exécuter les k moyennes dans le cadre d'une boucle if avec un test pour les tailles de cluster, c'est-à-dire le nombre n dans le cluster k - rappelez-vous également que k moyennes donnera des résultats différents pour chaque exécution sur les mêmes données afin vous devriez probablement l'exécuter dans le cadre d'une boucle pour extraire le "meilleur" résultat

Quelle est la taille de votre ensemble de données? Vous pouvez peut-être essayer d'exécuter un clustering hiérarchique, puis décider quels clusters conserver en fonction de votre dendrogramme.

Si votre ensemble de données est énorme, vous pouvez également combiner les deux méthodes de clustering: un clustering non hiérarchique initial puis un clustering hiérarchique utilisant les groupes de l'analyse non hiérarchique. Vous pouvez trouver un exemple de cette approche dans Martínez-Pastor et al (2005)

Cela peut être réalisé en modifiant l'étape d'affectation de cluster (E dans EM) en la formulant comme un problème d'optimisation de réseau linéaire à coût minimal (MCF).

J'ai écrit un package python qui utilise SimpleMinCostFlow des outils de recherche opérationnelle de Google, qui est une implémentation C ++ rapide. Il possède une API standard adaptée à scikit.