k-means vs k-means ++

Autant que je sache, k-means sélectionne les centres initiaux de manière aléatoire. Puisqu'ils sont basés sur la pure chance, ils peuvent être très mal sélectionnés. L'algorithme K-means ++ tente de résoudre ce problème en répartissant uniformément les centres initiaux.

• Les deux algorithmes garantissent-ils les mêmes résultats? Ou il est possible que les centroïdes initiaux mal choisis conduisent à un mauvais résultat, peu importe le nombre d'itérations.

• Disons qu'il existe un ensemble de données donné et un nombre donné de clusters souhaités. Nous exécutons un algorithme k-means tant qu'il converge (plus de mouvement central). Existe-t-il une solution exacte à ce problème de cluster (étant donné SSE), ou k-means produira parfois un résultat différent lors de la réexécution?

• S'il existe plus d'une solution à un problème de clustering (ensemble de données donné, nombre de clusters donné), K-means ++ garantit-il un meilleur résultat, ou juste un plus rapide? Par mieux, je veux dire un SSE inférieur.

La raison pour laquelle je pose ces questions est que je suis à la recherche d'un algorithme k-means pour regrouper un énorme ensemble de données. J'ai trouvé des k-means ++, mais il y a aussi des implémentations CUDA. Comme vous le savez déjà, CUDA utilise le GPU, et il peut exécuter plusieurs centaines de threads en parallèle. (Cela peut donc vraiment accélérer tout le processus). Mais aucune des implémentations CUDA - que j'ai trouvées jusqu'à présent - n'a d'initialisation k-means ++.

K-means commence par allouer des centres de grappes de manière aléatoire, puis recherche de «meilleures» solutions. K-means ++ commence par allouer un centre de cluster au hasard, puis recherche d'autres centres en fonction du premier. Ainsi, les deux algorithmes utilisent l'initialisation aléatoire comme point de départ, ils peuvent donc donner des résultats différents sur différentes exécutions. À titre d'exemple, vous pouvez vérifier cette conférence: Le clustering comme exemple de problème d'inférence , vers la 40e minute, il y a des exemples de k-means, mais la conférence entière est intéressante.

Donc, répondant à vos questions:

• Non, car il y a une initialisation aléatoire, différentes exécutions peuvent donner des résultats différents (voir les exemples dans la leçon). Ils devraient donner des résultats comparables mais cela n'est pas garanti. De plus, comme tous les centres sont initialisés de manière aléatoire dans k-means, cela peut donner des résultats différents de k-means ++.
• K-means peut donner des résultats différents sur différentes séries.
• Le papier k-means ++ fournit des résultats de simulation de monte-carlo qui montrent que k-means ++ est à la fois plus rapide et offre de meilleures performances, donc il n'y a aucune garantie, mais cela peut être mieux.

Quant à votre problème: quel est le k-means ++, il choisit les centres puis démarre un k-means "classique". Donc, ce que vous pouvez faire, c'est (1) utiliser la partie de l'algorithme qui choisit les centres puis (2) utiliser ces centres dans les implémentations GPU de k-means. De cette façon, au moins une partie d'un problème est résolu sur un logiciel basé sur GPU, devrait donc être plus rapide.

Affichage des centroïdes de départ de K-means et K-means ++

Pour ajouter une vue intuitive de la différence entre les centroïdes de départ des deux algorithmes, considérons le jeu de données de jouets suivant qui se compose de trois carrés générés uniformément

Voici des histogrammes 2D montrant où les algorithmes k-means et k-means ++ initialisent leurs centroïdes de départ (2000 simulations).

Clairement, le k-means standard initialise les points uniformément, tandis que k-means ++ a tendance à s'initialiser près du centre des carrés

Plusieurs fois, l'initialisation aléatoire de KMeans prend moins de temps que KMeans ++ mais donne un résultat médiocre. En raison de l'initialisation aléatoire, nous obtenons souvent un optimum local parce que notre ensemble initial de centres n'est pas distribué sur l'ensemble de données.

Donc, répondant à votre question:

1. Non, du fait que les centres KMeans ++ sont répartis sur les données, il est plus susceptible d'avoir un coût moindre (dans la somme des carrés du cluster) qu'une initialisation aléatoire.
2. comme il s'agit d'une initialisation aléatoire dans KMeans, elle donne un résultat différent selon votre ensemble initial de centres
3. tout d'abord il n'y a pas de solution définitive pour KMeans car c'est un apprentissage non supervisé, ce que nous pouvons faire est de réduire le coût des KMeans (SSE). KMeans choisit intelligemment le centre initial, il faut moins d'itération de llyodes pour converger et donne un meilleur résultat que Random