13
$\begingroup$

I'm new to data science and have a problem finding clusters in a data set with 200,000 rows and 50 columns in R.

Since the data have both numeric and nominal variables, methods like K-means which uses Euclidean distance measure doesn't seems like an appropriate choice. So I turn to PAM, agnes and hclust which accepts a distance matrix as input.

The daisy method can work on mixed-type data but the distance matrix is just too big: 200,000 times 200,000 is much larger than 2^31-1 (the vector length limit before R 3.0.0.)

The new R 3.0.0 released yesterday supports long vectors with length longer than 2^31-1. But a double matrix of 200,000 by 200,000 requires a continuous RAM larger than 16Gb which is not possible on my machine.

I read about parallel computing and bigmemory package and am not sure if they are going to help: if I'm using daisy, it will generates a big matrix which cannot fit in memory anyway.

I also read about the post about sampling: Is sampling relevant in the time of 'big data'?

So in my case, is it relevant to use sampling on the data set, cluster on the sample and then infer the structure of the whole data set?

Can you please give me some suggestion? Thank you!

About my machine:

R version 3.0.0 (2013-04-03)

Platform: x86_64-w64-mingw32/x64 (64-bit)

OS: Windows 7 64bit

RAM: 16.0GB

$\endgroup$
1
  • $\begingroup$ The only clustering method I know which is for big data (e.g. millions of cases) and can accept nominal variables along with numeric ones is TwoStep cluster found in SPSS. $\endgroup$
    – ttnphns
    Apr 4 '13 at 20:52
4
$\begingroup$

As you have noticed, any method that requires a full distance matrix won't work. Memory is one thing, but the other is runtime. The typical implementations of hierarchical clustering are in $O(n^3)$ (I know that ELKI has SLINK, which is an $O(n^2)$ algorithm to single-link clustering). This just does not scale to large data sets.

PAM itself should not require a complete distance matrix, but the algorithm is known to scale badly, because it then needs to (re-)compute all pairwise distances within each cluster on each iteration to find the most central elements. This is much less if you have a large number of clusters, but nevertheless quite expensive!

Instead, you should look into methods that can use index structures for acceleration. With a good index, such clustering algorithms can run in $O(n log n)$ which is much better for large data sets.

However, for most of these algorithms, you first need to make sure your distance function is really good; then you need to consider ways to accelerate queries by using appropriate indexes.

Also note that in many cases - and this may well hold for PAM - you can run the algorithm on a sample first, then only refine it on the full data set. If your sample is representative, algorithms such as k-means and PAM should give you essentially the same result as on the complete data set.

$\endgroup$
3
  • $\begingroup$ Won't help the OP here, but in case someone else comes along who has "intermediate" sample numbers: there is also fastcluster for R (see math.stanford.edu/~muellner/fastcluster.html). $\endgroup$ Apr 5 '13 at 15:35
  • $\begingroup$ Hi Anony-Mousse, could you please point me to some of the algorithms that uses index structure acceleration? Thanks a lot! $\endgroup$
    – user23915
    Apr 5 '13 at 15:40
  • $\begingroup$ For example DBSCAN can be accelerated well with indexes that support epsilon range queries. Probably mean shift clustering, too. OPTICS, which can also be accelerated this way, can be seen as a more advanced version of linkage clustering (you could call it "hierarchical density linkage clustering") $\endgroup$ Apr 5 '13 at 17:03
3
$\begingroup$

try the CLARA function from the cluster package in R. It implements a pam-like algorithm by subsampling your data (make sure you provide subsample sizes that make sense for your data because the defaults are purposefully too small). It works especially well if the mediods in your data can be represented by a small sample of the total data (ie - there are relatively fewer clusters in the dataset). This way you can cluster efficiently with a small random sample and add points to the precomputed clustering solution.

http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/CLARA

$\endgroup$
2
  • $\begingroup$ hi zzk, thanks for the reply. I read about clara before but it seems that it only provides euclidean and manhattan metric. The main problem is that my dataset has both numeric and nominal variables. So using neither metric for distance measurement are not appropriate. $\endgroup$
    – user23915
    Apr 6 '13 at 14:34
  • $\begingroup$ ah yes, that's currently a limitation for me as well. I believe the method actually can be done on any arbitrary distance, but I haven't bothered to look through the source code yet to see if it can be changed. $\endgroup$
    – zzk
    Apr 7 '13 at 18:11
0
$\begingroup$

You can also apply multiple correspondence analysis on your qualitative variables and make transformations into a numeric variable.

$\endgroup$
1
  • 2
    $\begingroup$ This seems like a good idea, but it may be a little sparse. Can you flesh this out a bit to explain what it is & why that would help? $\endgroup$ Jan 23 '16 at 0:10

Your Answer

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