K-Means contraint

Les k-means construisent des clusters qui ne sont pas forcément équilibrés. Comment modifier l'algorithme original pour que ce soit le cas ?

Un échantillon aléatoire

k-means classique

Le modèles des k-means classique.

k-means contraint

Et maintenant la version où chaque cluster contient approximativement le même nombre de points.

not finished yet

L'algorithme essaye d'échanger des points entre deux classes balancées, l'échange est conservé si cela améliore l'inertie du nuage total, voir Same-size k-Means Variation.

k-means contraint - variantes

Une autre variante plus simple qui consiste à affecter d'abord les points proches du centre le plus proche, les points les plus éloignés sont traités en dernier et affectés à ce qui reste. Les clusters construits ne sont plus convexes.

On vérifie que la version distance ne paraît pas optimal à la périphérie des clusters. La version gain n'est pas encore parfaite. On regarde le résultat sans initialisation préalable de avec un k-means classique.