Requisitos de memória do armazenamento em cluster -eans

8

Alguém pode me dizer os fatores que afetam os requisitos de memória do cluster mean com um pouco de explicação?k

clustering k-means Martin
fonte
4
k -means é NP-difícil, então há muitas heurísticas que diferem significativamente, também no consumo de recursos; você está interessado em algum algoritmo específico?
2
Você está se referindo ao algoritmo de Lloyd? Nesse caso, acredito que os requisitos de memória para uma implementação padrão seriam O (log k * n) porque você precisaria armazenar uma lista de pares (ponto, cluster) para a etapa de atualização. Como k geralmente é pequeno, meu palpite é que você geralmente pode armazenar apenas um pequeno para cada ponto, mas eu não observei nenhuma implementação específica.
Rm999 6/06/11
Você realmente só precisa de armazenamento intermediário do tamanho , se estiver disposto a armazenar os dados no disco e digitalizá-los em cada passagem. Obviamente, isso é muito lento e, portanto, há trocas envolvidas. O que especificamente você estava procurando. k
precisa saber é o seguinte

Respostas:

1

Algoritmos como Lloyds podem ser implementados com valores de ponto flutuante usando apenas a memória. O algoritmo k-means do MacQueens deve precisar apenas de memória .k⋅(2⋅d+1)k⋅(d+1)

No entanto, como a maioria dos usuários deseja saber qual ponto pertence a qual cluster, quase todas as implementações que você encontrará usarão memória .O(n+k⋅d)

Em outras palavras, o uso da memória por k-means é essencialmente o tamanho dos dados de saída .

Possui QUIT - Anony-Mousse
fonte
0

Recentemente, deparei-me com uma nota explicativa de uma implementação do algoritmo k-means em 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.

fonte