2
$\begingroup$

I have a dataset with 200K samples (cases) and 30 variables. Every distance-based method for clustering or dimension reduction technique that I use, such as DBSCAN, Hierarchical Clustering, LLE, Isomap and ... fail to run on my machine (normally I get R Session Terminated error) due to the large distance file being generated. (Distance calculation requires o(n^2) time and space)

Is there any solution to handle this problem? Is there any good package for the mentioned clustering or dimensionality reduction in R or Matlab that is suitable ?

Improve this question
$\endgroup$
6
  • $\begingroup$ How many clusters? $\endgroup$
    – rcpinto
    Aug 4, 2015 at 23:57
  • $\begingroup$ 60 to 70 clusters $\endgroup$
    – Matin Kh
    Aug 5, 2015 at 0:00
  • 2
    $\begingroup$ Use better implementations. For example, try DBSCAN in ELKI with index acceleration. It does not need O(n^2) memory and was 100x faster than R fpc. $\endgroup$
    – Has QUIT--Anony-Mousse
    Aug 5, 2015 at 5:44
  • $\begingroup$ You are speaking of distance-based clustering but, at the same time, requesting not to mess with the square distance matrix. This looks contradictory at first glance. Perhaps what you want is a special form of storage of the big matrix? $\endgroup$
    – ttnphns
    Aug 5, 2015 at 10:37
  • $\begingroup$ @ttnphns well, there are quite a lot of distance-based clustering algorithms that do not require a square distance matrix. $\endgroup$
    – Has QUIT--Anony-Mousse
    Aug 5, 2015 at 14:54

1 Answer 1

Reset to default
0
$\begingroup$

Maybe you could try Mini-Batch K-Means. I have Matlab code for it:

function [c,counts,idx] = mbkmeans(x,k,c,counts)
    [N,D] = size(x);
    if ~exist('c','var') || isempty(c)
        c = x(1:min([k N]),:) + bsxfun(@times,randn(min([k N]),D)*0.001,std(x));
        if N < k
            c(N+1:k,:) = bsxfun(@plus,mean(x),bsxfun(@times,randn(k-N,D),std(x)));
        end;
    end;
    if ~exist('counts','var') || isempty(counts)
        counts = zeros(k,1);
    end;
    idx = knnsearch(c,x,'k',1);
    add = full(sparse(idx,1,1));
    counts(idx) = counts(idx) + add(idx);
    lr = 1 ./ counts(idx);   
    for i = 1:N
        c(idx(i),:) = (1 - lr(i)) * c(idx(i),:) + lr(i) * x(i,:);
    end;

Usage:

clusters = mbkmeans(yourdata,numberofclusters);

You may feed it your entire dataset at once and you're done. Or you may feed it smaller subsets. In this case, use it like this:

[c1, counts1] = mbkmeans(subset1,numberofclusters);
[c2, counts2] = mbkmeans(subset2,numberofclusters, c1, counts1); %start clustering using previously created clusters
[c3, counts3] = mbkmeans(subset3,numberofclusters, c2, counts2);
...
[cn, countsn, indices] = mbkmeans(subsetn,numberofclusters, c(n-1), counts(n-1));

For R, there is the stream package (explanation here). You may also take a look at this, this and this.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Regular k-means should be fine too, it also does not use pairwise distances. But k-means isn't on hist wish list, he probably already tried that... minibatch then does not help. $\endgroup$
    – Has QUIT--Anony-Mousse
    Aug 5, 2015 at 5:46
  • $\begingroup$ Just like @Anony-Mousse said, k-means works fine. I would like to know if I can apply any distance-based technique to my dataset. $\endgroup$
    – Matin Kh
    Aug 5, 2015 at 13:49
  • $\begingroup$ So you should look at the second 'this' in my answer. It shows that DBScan does not need to store the entire distance matrix, so your problem is implementation specific. $\endgroup$
    – rcpinto
    Aug 5, 2015 at 13:52
  • 1
    $\begingroup$ This is the syntax of the DBScan algorithm in R: dbscan(data, eps, MinPts, scale, method, seeds, showplot, countmode) What you need to change is the 'method' parameter: method: Configures memory usage by constraining performance, there are three options: "raw": treats data as raw data and avoids calculating a distance matrix (saves memory but may be slow). "dist": treats data as distance matrix (relatively fast but memory expensive). "hybrid": expects also raw data, but calculates partial distance matrices (very fast with moderate memory requirements. $\endgroup$
    – rcpinto
    Aug 5, 2015 at 13:56
  • $\begingroup$ @rcpinto thanks for your informative comment. I will try these options and let you know the outcome. $\endgroup$
    – Matin Kh
    Aug 5, 2015 at 14:39

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.