Initialisation des centres K-means au moyen de sous-échantillons aléatoires de l'ensemble de données?

Si j'ai un certain ensemble de données, comment serait-il intelligent d'initialiser des centres de cluster à l'aide d'échantillons aléatoires de cet ensemble de données?

Par exemple, supposons que je veuille 5 clusters. Je prends la 5 random samplesparole size=20%de l'ensemble de données d'origine. Puis-je alors prendre la moyenne de chacun de ces 5 échantillons aléatoires et utiliser ces moyennes comme mes 5 centres de cluster initial? Je ne sais pas où j'ai lu ceci mais je voulais savoir ce que vous en pensez.

MISE À JOUR: Veuillez consulter ce fil Initialisation du clustering K-means: quelles sont les méthodes existantes? pour la discussion générale sur les différentes méthodes d'initialisation.

Si vous divisez l'échantillon au hasard en 5 sous-échantillons, vos 5 moyennes coïncideront presque. Quel est le sens de faire de ces points proches les centres de cluster initiaux?

Dans de nombreuses implémentations de K-means, la sélection par défaut des centres de grappes initiaux est basée sur l'idée opposée: trouver les 5 points les plus éloignés et en faire les centres initiaux. Vous vous demandez peut-être comment trouver ces points éloignés? Voici ce que fait K-means de SPSS pour cela:

Prenez tout k cas (points) de l'ensemble de données comme centres initiaux. Tous les cas restants sont en cours de vérification pour la capacité de les remplacer comme centres initiaux, par les conditions suivantes:

• a) Si le boîtier est plus éloigné du centre le plus proche de lui que la distance entre deux centres les plus proches les uns des autres, le boîtier se substitue au centre des deux derniers dont il est le plus proche.
• b) Si le boîtier est plus éloigné du deuxième centre le plus proche de lui que la distance entre le centre le plus proche et le centre le plus proche de celui-ci, le boîtier se substitue au centre le plus proche.

Si la condition (a) n'est pas satisfaite, la condition (b) est vérifiée; s'il n'est pas satisfait, le cas ne devient pas un centre. À la suite de tels cas traversés, nous obtenons k cas extrêmes dans le nuage qui deviennent les centres initiaux. Le résultat de cet algo, bien que suffisamment robuste, n'est pas totalement insensible au choix de départ de k cas" et à l'ordre de tri des cas dans l'ensemble de données; ainsi, plusieurs tentatives de démarrage aléatoires sont toujours les bienvenues, comme c'est toujours le cas avec K-means.

Voir ma réponse avec une liste de méthodes d'initialisation populaires pour k-means. La méthode de division en sous-échantillons aléatoires (critiquée ici par moi et d'autres) ainsi que la méthode décrite utilisée par SPSS - sont également sur la liste.

Les moyens seront beaucoup trop similaires. Vous pourriez tout aussi bien trouver la moyenne de l'ensemble de données, puis placer les centroïdes initiaux dans un petit cercle / sphère autour de cette moyenne.

Si vous voulez voir un schéma d'initialisation plus solide pour k-means, jetez un œil à k-means ++. Ils ont mis au point une méthode assez intelligente pour semer les k-means.

• Arthur, D. et Vassilvitskii, S. (2007).
  k-means ++: les avantages d'un ensemencement soigné ".
  Actes du dix-huitième symposium annuel ACM-SIAM sur les algorithmes discrets

Diapositives de l'auteur: http://www.ima.umn.edu/~iwen/REU/BATS-Means.pdf

L'utilisation des moyens d'échantillons aléatoires vous donnera l'opposé de ce dont vous avez besoin, comme l'a souligné ttnphns dans son commentaire. Il nous faudrait un moyen de trouver des points de données assez éloignés les uns des autres.

Idéalement, vous pouvez parcourir tous les points, trouver les distances entre eux, déterminer où les distances sont les plus grandes ...

Pas pour contourner l'intention de l'OP, mais je pense que la "solution" est intégrée dans l'algorithme k-means. Nous effectuons plusieurs itérations et recalculons les centroïdes de cluster en fonction des itérations précédentes. Nous exécutons également généralement l'algorithme kmeans plusieurs fois (avec des valeurs initiales aléatoires) et comparons les résultats.

Si l'on a des connaissances a priori, des connaissances de domaine, cela pourrait conduire à une méthode supérieure pour identifier où les centres de cluster initiaux devraient être. Sinon, il s'agit probablement de sélectionner des points de données aléatoires comme valeurs initiales, puis d'utiliser plusieurs exécutions et plusieurs itérations par exécution.

Les réponses proposées sont toutes efficaces, mais sont beaucoup plus difficiles à opérationnaliser que votre proposition d'origine. Un moyen très simple d'initialiser est de prendre$k$observations aléatoires comme points d'origine. La probabilité de rapprochement de deux points initiaux est assez faible et l'algorithme s'exécute rapidement pour tous les cas sauf les plus extrêmes.