# 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? – rcpinto Aug 4 '15 at 23:57
• 60 to 70 clusters – Matin Kh Aug 5 '15 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. – Has QUIT--Anony-Mousse Aug 5 '15 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? – ttnphns Aug 5 '15 at 10:37
• @ttnphns well, there are quite a lot of distance-based clustering algorithms that do not require a square distance matrix. – Has QUIT--Anony-Mousse Aug 5 '15 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. – Has QUIT--Anony-Mousse Aug 5 '15 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. – Matin Kh Aug 5 '15 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. – rcpinto Aug 5 '15 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. – rcpinto Aug 5 '15 at 13:56
• @rcpinto thanks for your informative comment. I will try these options and let you know the outcome. – Matin Kh Aug 5 '15 at 14:39