2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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$
    – Rizky Luthfianto
    Sep 14, 2016 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, 2016 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, 2017 at 13:10
  • $\begingroup$ Have you looked at multicollinearity to reduce the number of features? $\endgroup$
    – Paul
    Sep 11, 2017 at 1:41

3 Answers 3

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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, 2017 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$
    – Vivek Kalyanarangan
    Feb 8, 2018 at 11:50
0
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

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

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