Getting Recurssion limit error

here is my code of DBSCAN algorithm

codes.

function cluster = dbscan(iris, Eps, MinPts)
Eps=0.04;
MinPts=4;
cluster = zeros(size(iris,1),1);

classcounter = 0;
doLoop = 1;
while(doLoop)
    classcounter = classcounter + 1;
    notClassified = find(cluster == 0);

      if(sum(notClassified) == 0)
          doLoop = 0;
      else
          cluster(notClassified(1)) = classcounter;
          cluster = dbrec(notClassified(1), iris, Eps, MinPts, cluster);
      end
  end

antal(max(cluster)) = 0;

for i = 1:size(iris,1)
    antal(cluster(i)) = antal(cluster(i)) + 1;
end

temp = find(antal < 3);
for i = 1:size(temp,2)
    cluster(find(cluster == temp(i))) = 0;
end
save cluster;

for dbrec function

function cluster = dbrec(pIdx, M, Eps, MinPts, cluster)

for i=1:size(M,1)
    if(norm(M(i,:) - M(pIdx,:)) < Eps && cluster(i) == 0)
        cluster(i) = cluster(pIdx);
        cluster = dbrec(pIdx, M, Eps, MinPts, cluster);
    end
end

I use a data file which is 4.5lakh values*5 .When i run the code I get Matlab Recurssion limit error. When i change the recurssion limit to 1000 or 2000 i get the same error and when i set it to 2500 the simulation goes on ffor the whole day without results.

I am in a catch 22 situation please help

with regards, mani

Answer 1

[Walter Roberson]

Hypothesize that norm(M(i,:) - M(pIdx,:)) < Eps is true for many "i" values. You initialize cluster to be mostly 0's, so the second condition in your "if" will usually be true, leading the code to call itself recursively for all those places where the norm satisfied that condition. If you can't be certain that there are no more than 100-ish places that the norm is satisfied, then you are going to blow the normal recursion limit.

You should be considering an iterative algorithm instead of a recursive one.

By the way, a side point about efficiency: there is no point in computing the norm() for any i for which cluster(i) is non-zero, so you might as well change the "for" loop to

for i = find(cluster==0,1) : size(M,1)

There is another efficiency to be gained by re-calculating the start index after the recursive dbrec() call; if it is after the current position then you can skip the iterations until that position. A "while" loop would probably work better than a "for" loop for this efficiency.

[Mani]

hello sir,

i am using internet classification data and norm(M(i,:) - M(pIdx,:)) < Eps is usually false. i checked the statement in the debug mode by providing values for M(i,:) and M(pIdx,:). Moreover there are around 420000 rows of data to be evaluated and hence it is becoming confusing for me as to wheather the code reaches Recurssionlimt really or is the code hanging up.

well As you can see in the notClassified variable stores the indices of non`classified data and cluster is differentiated by the increasing the value of classcounter. hence a cluster =0 means not classified data hence i use a cluseter(i)=0 statement.

with regards,

mani