forum.alglib.net

ALGLIB forum
It is currently Thu Dec 05, 2024 12:16 am

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 1 post ] 
Author Message
 Post subject: dbscan code slow
PostPosted: Mon Feb 11, 2019 8:42 pm 
Offline

Joined: Mon Feb 11, 2019 8:34 pm
Posts: 1
Hi,
i am trying to implement the dbscan code in c#(see below). The code takes 408 seconds for a 10000x20 matrix. it takes 20 seconds in matlab. can you point me to the part where i might be doing some thing wrong? matlab also uses kdtree.

public int[] ComputeDbscan(double[,] xtr, double epsilon, int minPts)
{

bool borderpoints = true;
int rows = xtr.GetLength(0);
int cols = xtr.GetLength(1);
bool[] visited = new bool[rows - 1 + 1];
int[] clusterId = new int[rows - 1 + 1];
int[] tags = new int[rows - 1 + 1];
for (int kk = 0; kk <= rows - 1; kk++)
tags[kk] = kk;

List<List<int>> clusterlist = new List<List<int>>();
double[] xtrRow = new double[cols - 1 + 1];
int Nweight;
int j;
int normtype = 2;//euclidean norm
bool selfmatch = true;
int ny = 0; //useless variable
List<int> N = new List<int>();
List<int> N2 = new List<int>();
alglib.kdtree kdt; //defien tree
alglib.kdtreerequestbuffer r1; //define buffer
alglib.kdtreebuildtagged(xtr, tags,rows,cols, ny,normtype, out kdt); //build tree with tags
alglib.kdtreecreaterequestbuffer(kdt, out r1); //create buffer for the tree
for (int kk = 0; kk <= cols - 1; kk++)
xtrRow[kk] = xtr[0, kk];
//Get the epsilon Factor*******************************
double[] nearest = new double[rows - 1 + 1];
if (epsilon == 0.0)
{
for (int i = 0; i <= rows - 1; i++)
{
for (int kk = 0; kk <= cols - 1; kk++)
xtrRow[kk] = xtr[i, kk];
alglib.kdtreequeryknn(kdt, xtrRow, minPts - 1);
double[] dists = new double[minPts-1];
alglib.kdtreequeryresultsdistances(kdt, ref dists);
nearest[i] = dists[minPts - 2];
}
epsilon = GetEPS(nearest); // this returns the best epsilon by simply looking for knee --not a bottleneck, negligible time
}

//***************run the dbscan loop****************************
for (int i = 0; i <= rows - 1; i++) {
if (visited[i] == true)
continue;
for (int kk = 0; kk <= cols - 1; kk++)
xtrRow[kk] = xtr[i, kk];
//Get the nearest collection of points and drop it to a list
alglib.kdtreequeryrnn(kdt, xtrRow, epsilon, selfmatch);
int[] Narray=new int[20];
alglib.kdtreequeryresultstagsi(kdt, out Narray);
//*********************************************************
Nweight = Narray.Length;
if (Nweight < minPts)
continue;
for (int kk = 0; kk <= Narray.Length - 1; kk++)
N.Add(Narray[kk]);
List<int> cluster = new List<int>();
cluster.Add(i);
visited[i] = true;
while (N.Count > 0)
{
j = N.Last();
N.RemoveAt(N.Count - 1);
if (visited[j] == true)
continue;
visited[j] = true;
for (int kk = 0; kk <= cols - 1; kk++)
xtrRow[kk] = xtr[j, kk];
//Get the nearest collection of points and drop it to a list
alglib.kdtreequeryrnn(kdt, xtrRow, epsilon, selfmatch);
int[] N2array = new int[20];
alglib.kdtreequeryresultstagsi(kdt, out N2array);
//*********************************************************
Nweight = N2array.Length;
if (Nweight >= minPts) {
for (int kk = 0; kk <= N2array.Length - 1; kk++)
N2.Add(N2array[kk]);
N = N.Union(N2).ToList();
}
if (Nweight >= minPts || borderpoints == true) {
cluster.Add(j);
}
}
clusterlist.Add(cluster);
N.Clear();
N2.Clear();
cluster = null;
}

for (int k = 0; k <= clusterlist.Count - 1; k++)
{
List<int> cluster = new List<int>();
cluster = clusterlist[k];
for (int m = 0; m <= cluster.Count - 1; m++)
clusterId[cluster[m]] = k + 1;
}
return clusterId;
}


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 1 post ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 13 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group