Algoritmo de clustering eficiente en memoria para conjuntos de datos de series temporales grandes

Question

Tengo una tarea de simulación en curso con ~1e6 series temporales que deben agruparse en función de medidas estadísticas cada pocos días en la simulación. La mayoría de los métodos de agrupamiento que conozco requieren la construcción de una matriz de afinidad. Dado que tengo memoria limitada, me gustaría trabajar con una solución que sea preferiblemente lineal en requisitos de memoria, incluso si lleva más tiempo calcularlo.

No he tenido mucho éxito encontrando un buen conjunto de algoritmos en los que pueda empezar a investigar. k-means es un algoritmo en el que estoy trabajando, pero requiere que el número de particiones se especifique a priori, lo cual no está disponible en mi problema. Por lo tanto, no es el mejor algoritmo para mis propósitos.

Si tienes algún consejo sobre este tema que pueda ayudarme a empezar, te lo agradecería mucho.

Answer 1

Puedes echar un vistazo a una lista de algoritmos de clustering disponibles en sklearn aquí, pero creo que todos ellos tienen una complejidad de $O(n^2$). Además, echa un vistazo al algoritmo de clustering TSNE, que se supone que es $O(log(n)*n)$, pero esto puede no ser cierto dependiendo de una implementación particular. Un caso concreto es de nuevo la implementación de TSNE en Python en sklearn, los problemas de memoria de los cuales se discuten aquí.