Vous serez probablement souvent déçu par la solution que n'importe quelle exécution particulière de "l'algorithme de k-means" (c'est-à-dire l'algorithme de Lloyd) arrive avec. C'est parce que l'algorithme de Lloyd est souvent bloqué dans les mauvais minima locaux.
Heureusement, Lloyd's est juste une façon de résoudre les k-means. Et il y a une approche qui trouve presque toujours de meilleurs minima locaux.
L'astuce consiste à mettre à jour les affectations de cluster des points de données un à la fois. Vous pouvez le faire efficacement en comptant le nombre de points n affectés à chaque moyenne. Alors que vous pouvez recalculer le cluster signifie m après le retrait du point x comme suit:
m_new = (n * m - x)/(n - 1)
Et ajouter x à grappe moyenne m utilisant:
m_new = (n * m + x)/(n + 1)
Bien sûr parce qu'il ne peut pas être vectorisé, c'est un peu pénible de fonctionner dans MATLAB mais pas trop mal dans d'autres langues.
Si vous voulez vraiment obtenir les meilleurs minima locaux, et que cela ne vous dérange pas d'utiliser un clustering basé sur l'exemple, vous devriez regarder affinity propagation. Les implémentations de MATLAB sont disponibles sur le Frey lab affinity propagation page.
Je suppose que vous avez raison. Pour obtenir une meilleure convergence, j'ai plutôt modifié mon algoritme pour faire plusieurs tentatives avec différents centres de masse initiaux, puis déterminer le meilleur en mesurant la variance des groupes. Une faible variance moyenne dans une tentative est égale à des groupes compacts. Comment ça sonne? – Theodor
@Theodor: C'est un critère possible en effet. –