Requisitos de memoria de la agrupación de medios

8

¿Alguien puede decirme los factores que afectan los requisitos de memoria de significa clustering con un poco de explicación?k

clustering k-means Martín
fuente
44
k significa es NP-duro, por lo que hay muchas heurísticas que difieren significativamente, también en el consumo de recursos; ¿estás interesado en algún algoritmo específico?
2
¿Te refieres al algoritmo de Lloyd? Si es así, creo que los requisitos de memoria para una implementación estándar serían O (log k * n) porque tendría que almacenar una lista de pares (punto, clúster) para el paso de actualización. Debido a que k suele ser pequeño, supongo que generalmente podría salirse con el almacenamiento solo un corto para cada punto, pero no he visto ninguna implementación específica.
rm999
Realmente solo necesita un almacenamiento intermedio de tamaño , si está dispuesto a almacenar los datos en el disco y escanearlos en cada pasada. Por supuesto, esto es muy lento, por lo que hay compensaciones involucradas. ¿Qué estabas buscando específicamente? k
Suresh Venkatasubramanian

Respuestas:

1

Algoritmos como Lloyds pueden implementarse con valores de coma flotante que solo se usan en la memoria. El algoritmo MacQueens k-means solo debería necesitar memoria .k⋅(2⋅d+1)k⋅(d+1)

Sin embargo, como la mayoría de los usuarios querrán saber qué punto pertenece a qué clúster, casi todas las implementaciones que encontrarán usarán memoria .O(n+k⋅d)

En otras palabras, el uso de memoria por k-means es esencialmente el tamaño de los datos de salida .

HA SALIDO - Anony-Mousse
fuente
0

Hace poco me encontré con una nota de una implementación descuidada del algoritmo k-means en 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.

fuente