L'algorithme de Kmeans pour k = 2 qui donne des sorties de taille de cluster égales

Question

J'utilise un algorithme de Lloyd modifié pour obtenir des sorties de taille de cluster égales en kmeans avec k = 2. ci-après le pseudo-code:

- Randomly choose 2 points as initialization for the 2 clusters (denoted as c1, c2) 
- Repeat below steps until convergence 
    - Sort all points xi according to ascending values of ||xi-c1|| - ||xi-c2||, i.e. differences in distances to the first and the second cluster 
    - Put top 50% points in cluster 1 , others in cluster 2 
    - Recalculate centroids as average of the allocated points (as usual in Lloyd's) 

Maintenant, l'algorithme ci-dessus fonctionne bien pour moi de manière empirique:

1. Il donne des grappes équilibrées
2. Il diminue toujours l'objectif

a une telle un algorithme a été proposé ou analysé auparavant dans la littérature? Puis-je obtenir des références s'il vous plaît?

Answer 1

Une version plus générale pour plus de 2 groupes est expliqué ici:

https://elki-project.github.io/tutorial/same-size_k_means

j'ai vu k-means avec des contraintes différentes tailles à plusieurs reprises dans la littérature, mais je n'ai aucune référence à main. Je ne suis pas convaincu de cela: forcer les grappes à avoir la même taille contredit l'idée de k-means de trouver la meilleure approximation des moindres carrés à mon humble avis, car cela signifie délibérément choisir une approximation pire.