# How to apply distance-based clustering or dimensionality reduction for too many samples

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 ?

• How many clusters? Aug 4, 2015 at 23:57
• 60 to 70 clusters Aug 5, 2015 at 0:00
• 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. Aug 5, 2015 at 5:44
• 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? Aug 5, 2015 at 10:37
• @ttnphns well, there are quite a lot of distance-based clustering algorithms that do not require a square distance matrix. Aug 5, 2015 at 14:54

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

• 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. Aug 5, 2015 at 5:46
• 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. Aug 5, 2015 at 13:49
• 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. Aug 5, 2015 at 13:52
• 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. Aug 5, 2015 at 13:56
• @rcpinto thanks for your informative comment. I will try these options and let you know the outcome. Aug 5, 2015 at 14:39