1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I already looked at sklearn and a few other libraries to check if they had something that would do the job. But, almost all algorithms are atleast O(2) in memory. That being said, tSNE looks better in memory requirements and I'm trying it out on my dataset right now. Thanks for the suggestions Sergey! $\endgroup$ Commented Jan 28, 2016 at 6:33
  • $\begingroup$ Practically speaking, I did K-Means clustering with 1mln+ time series on a 4Gb RAM laptop, but t-SNE threw an error at me, which tells me K-means is somehow more efficient in using memory than t-SNE, at least in Python. Regarding your mentioning "# of clusters is not available to you", you may try identifying it yourself with scree plot. See this (R) or this (Python) posts. $\endgroup$ Commented Jan 28, 2016 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.