Je cherche à regrouper k-means sur un ensemble de points à 10 dimensions. Le hic: il y a 10 ^ 10 points .
Je recherche juste le centre et la taille des plus grands clusters (disons 10 à 100 clusters); Je me fiche du cluster dans lequel se trouve chaque point. L'utilisation de k-means en particulier n'est pas importante; Je cherche juste un effet similaire, tout k-means approximatif ou algorithme associé serait génial (minibatch-SGD signifie, ...). Puisque GMM est en quelque sorte le même problème que k-means, faire GMM sur les mêmes données de taille est également intéressant.
À cette échelle, le sous-échantillonnage des données ne modifie probablement pas le résultat de manière significative: les chances de trouver les mêmes 10 principaux clusters à l'aide d'un échantillon au 1/10000e des données sont très bonnes. Mais même dans ce cas, c'est un problème de 10 ^ 6 points qui se situe au-delà du bord du tractable.
la source
Réponses:
k-means est basé sur des moyennes .
Il modélise les grappes à l'aide de moyens, et donc l'amélioration en ajoutant plus de données est marginale. L'erreur de l'estimation moyenne diminue de 1 / sqrt (n); donc ajouter plus de données rapporte de moins en moins ...
Les stratégies pour des données aussi volumineuses tournent toujours autour de l'échantillonnage:
Si vous voulez une exécution sublinéaire, vous devez faire un échantillonnage!
En fait, les Mini-Batch-Kmeans etc. font exactement cela: échantillonner à plusieurs reprises à partir de l'ensemble de données.
Cependant, l'échantillonnage (en particulier l'échantillonnage non biaisé) n'est pas exactement gratuit non plus ... généralement, vous devrez lire vos données linéairement pour échantillonner, car vous n'avez pas accès de manière aléatoire aux enregistrements individuels.
J'irais avec l'algorithme de MacQueen. C'est en ligne; par défaut, il effectue un seul passage sur vos données (bien qu'il soit courant de répéter cela). Ce n'est pas facile à distribuer, mais je suppose que vous pouvez vous permettre de lire linéairement vos données, disons 10 fois à partir d'un SSD?
la source
Comme commentaire secondaire, notez que l'utilisation de K-means pour les données 10D pourrait se retrouver nulle part selon la malédiction de la dimensionnalité. Bien sûr, cela varie un peu selon la nature des données, mais une fois que j'ai essayé de déterminer le seuil auquel K-Means commence à se comporter bizarrement en ce qui concerne la dimension, j'ai obtenu quelque chose comme 7D. Après 7 dimensions, il a commencé à manquer des clusters corrects (mes données ont été générées manuellement selon 4 distributions gaussiennes bien séparées et j'ai utilisé la fonction kmeans MATLAB pour ma petite expérience).
la source