Memory-Efficient Clustering for Large Time-Series Collections

Summary

The document asks how to cluster roughly one million time series using statistical features while keeping memory use near linear. It notes that many familiar clustering methods rely on an affinity matrix, which can become a memory bottleneck, and raises k-means as a possible starting point despite needing the number of clusters in advance.

The response suggests consulting the clustering methods available in scikit-learn, while cautioning that many have quadratic complexity. It also points to t-SNE as a possible approach with a reported complexity near n log n, but warns that this depends on the implementation; the scikit-learn version is cited as having memory issues. The exchange offers starting points rather than a tested algorithm or a complete solution. It does not specify how to choose features, determine cluster count, or validate results, and it gives no benchmark showing that t-SNE meets the stated memory constraint at the proposed scale.

Key ideas

• Affinity-based clustering can require substantial memory for very large datasets.
• K-means requires the user to choose the number of clusters in advance.
• The response recommends reviewing available clustering algorithms and comparing their complexity.
• The claimed t-SNE complexity may depend on the implementation, and memory use remains a caveat.

Tags

# Memory-efficient clustering algorithm for large time-series datasets


# Memory-efficient clustering algorithm for large time-series datasets












I have a simulation task at hand with ~1e6 time series to be clustered on the basis of statistical measures every few days in the simulation. Most clustering methods I'm aware of require an affinity matrix to be constructed. Given that I've limited memory, I would like to work with a solution that is preferably linear in memory requirements, even if it takes longer to compute.

I have not had much success figuring out a good set of algorithms I can start looking into. k-means is one algo I'm looking at but it requires the number of partitions to be specified a-priori which is not available in my problem. So, it is not the best algo for my purposes.

If you have any advice on this topic which could help me get started, I'd really appreciate it.

## Answer by Sergey Bushmanov (score 1)

https://quant.stackexchange.com/a/22915

You may have a look at a list of clustering algos available in `sklearn` here, but I think all of them are of $O(n^2$) complexity. As well, have a look at the TSNE clustering algo, which is supposed to be $O(log(n)*n)$, but this may not be the fact depending on a particular implementation. A particular case in point is again Python `sklearn` implementation of TSNE, the memory problems with which are discussed here.

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.