I have 1 million rows with 20 attributes to do hierarchical clustering. When I want to build a distance matrix on this data by dist() in R, it says that it needs 5 TB memory. I have these approaches:

  1. Reduce the number of rows by sampling
  2. Change the method of clustering
  3. ?

Now, do you suggest another approach? And I have an idea, I think if I reduce the accuracy of the values and then doing "group by", then I can remove duplicated rows and have a new column with the count of duplicates for each row. Is there any R package that can do hierarchical clustering with these data?

"group by": count number of duplicated rows and add a column that say how many times this row was duplicated in source.

  • $\begingroup$ But generally agglomerative clustering is $ O(n^{2}\log(n))$ which makes them too slow for large datasets. Even single-linkage and complete-linkage is only $O(n^{2})$. But Brian's answer below is interesting $\endgroup$ Sep 14 '16 at 19:20
  • $\begingroup$ The method you propose (removing duplicates) is just hiding the main problem and is not scalable... Even if it was working in your case, the method would not be valid anymore if you had 2 millions samples (rows)... $\endgroup$
    – Eskapp
    Dec 13 '16 at 19:53
  • $\begingroup$ You offer 2.Change the method of clustering Do you really need the hierarchy or do you just need clustering? Also, would it be adequate to have a partial hierarchy, i.e. only the top part, but it only goes down so far and below that there is no hierarchy? $\endgroup$
    – G5W
    Jan 14 '17 at 13:10
  • $\begingroup$ Have you looked at multicollinearity to reduce the number of features? $\endgroup$
    – Paul
    Sep 11 '17 at 1:41

You have n=20000000 data points and d=20 attributes.

Approach 1

The hierarchical agglomerative clustering has a time complexity of O(n^3) and requires O(n^2) memory. Therefore it is infeasible for large data sets (not to mention big data)

What you can do is first use some nearly-linear-time clustering algorithm to cluster your data to, let as say, 2000 clusters. This algorithm can be, for example, K-Means. See this stackoverflow answer for its time complexity. This is actually an alternative to your discussion of 'reduce accuracy and group'. Then you apply hierarchical clustering to the found 2000 clusters.

Approach 2 Use the algorithm, which is specially designed for large data. For example, Birch algorithm


See Steve Mosher's blog post where he solves this problem: "Nick Stokes Distance code, now with Big Memory".

  • 1
    $\begingroup$ Thanks for the answer! Can you summarize the main ideas in your answer here? We want to be more than just a link farm pointing to links elsewhere; and if the link stops working, this answer becomes rather useless. $\endgroup$
    – D.W.
    Jan 13 '17 at 23:01
  • 1
    $\begingroup$ This is not an answer but a link. It makes more sense to have this in the comments. Or you can summarize in this context $\endgroup$ Feb 8 '18 at 11:50

You are asking for more ideas here, not for concrete solutions, right?

Well, maybe try RWeka's implementation of kmeans, SimpleKMeans()? it has hyperparameters allowing you to implicitly preprocess the data with a Canopy algorithm, before running KMeans. Canopy (has nothing to do with Python) can run in either batch or incremental mode.

Weka also has a standalone implementation of the Canopy Clusterer built-in, which you can use via the Explorer GUI. However with RWeka you have to use the RWeka::make_Weka_clusterer() mechanism of calling the appropriate Java class that implements Canopy. So in R, you don't have to wrap it in SimpleKMeans() but then use RWeka::make_Weka_clusterer().

Canopy "is intended to speed up clustering operations on large data sets". As I understand the Wikipedia article, Canopy also removes some redundancy in the dataset, but in a different manner, not by building weights as you propose. See also this answer from stats.SE.

If all your attributes have low cardinality (= few unique values), I'd say just take samples (your option #1).


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.