Besoins en mémoire de

8

Quelqu'un peut-il me dire les facteurs qui affectent les besoins en mémoire de k-signifie un regroupement avec un peu d'explication?

clustering k-means Martin
la source
4
k -moyen est NP-difficile, il y a donc beaucoup d'heuristiques qui diffèrent considérablement, également dans la consommation des ressources; êtes-vous intéressé par un algorithme spécifique?
2
Faites-vous référence à l'algorithme de Lloyd? Si tel est le cas, je pense que les besoins en mémoire pour une implémentation standard seraient O (log k * n) car vous devrez stocker une liste de paires (point, cluster) pour l'étape de mise à jour. Parce que k est généralement petit, je suppose que vous pouvez généralement vous contenter de stocker un court pour chaque point, mais je n'ai pas examiné d'implémentations spécifiques.
rm999
Vous n'avez vraiment besoin que d'un stockage intermédiaire de taille , si vous êtes prêt à stocker les données sur le disque et à les analyser à chaque passage. Bien sûr, cela est très lent, et il y a donc des compromis à faire. Que cherchais-tu précisément? k
Suresh Venkatasubramanian

Réponses:

1

Des algorithmes comme Lloyds peuvent être implémentés aveck⋅(2⋅ré+1)valeurs en virgule flottante mémoire uniquement. L'algorithme k-means de MacQueens ne devrait avoir besoink⋅(ré+1) Mémoire.

Cependant, comme la plupart des utilisateurs voudront savoir quel point appartient à quel cluster, presque toutes les implémentations que vous trouverez utiliseront O(n+k⋅ré) Mémoire.

En d'autres termes, l'utilisation de la mémoire par k-means est essentiellement la taille des données de sortie .

A QUIT - Anony-Mousse
la source
0

Je suis récemment tombé sur une note d'une implémentation scipy de l'algorithme k-means dans scipy.cluster.vq.py

Notes
-----
This could be faster when number of codebooks is small, but it
becomes a real memory hog when codebook is large. It requires
N by M by O storage where N=number of obs, M = number of
features, and O = number of codes.

la source