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.

$\endgroup$
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.

$\endgroup$
  • $\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$ – Mindstorm Jan 28 '16 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$ – Sergey Bushmanov Jan 28 '16 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.