1
$\begingroup$

How to apply CSR Matrix on DBSCAN algorithm in python without using any libraries?

Update: Matrix size (8580, 126356)

I have given a shot and implemented the algorithm. It runs rather slow. I guess its because regionQuery function calculates the euclidean distance between a chosen point and every other point in the dataset.

Is there any way this problem can be solved?

$\endgroup$
  • 1
    $\begingroup$ I guess it's better to use prewritten libraries. They usually use optimization techniques that are so useful for accelerating operations. $\endgroup$ – Media Apr 21 '18 at 14:46
  • $\begingroup$ It is CSR means sparse matrix ? $\endgroup$ – KyBe Apr 22 '18 at 0:27
3
$\begingroup$
  1. Write the DBSCAN code yourself.
  2. Run the code.
  3. Observe that your code likely will be a lot slower than the libraries code.
| improve this answer | |
$\endgroup$
  • $\begingroup$ totally agree with 3. +1 ;-) $\endgroup$ – MaxU Apr 21 '18 at 13:25
  • $\begingroup$ Yes. I gave it a shot and implemented the algorithm. I concur that my implementation takes a while to compute. $\endgroup$ – saranyavsr Apr 21 '18 at 15:09
  • $\begingroup$ For DBSCAN to be fast, you also need to implement a fast region query, using an index structure. $\endgroup$ – Has QUIT--Anony-Mousse Apr 21 '18 at 19:40
1
$\begingroup$

As @Anony-Mousse pointed it, on DBSCAN index structures are often used in order to decrease execution times. K-d-trees are one example but this one works well just in small dimensions.

You had right intuition about what slowing down, the computation of every distance from all point to one is O(n) time complexity but applied to every points it becomes O(n2) which is something we desire to avoid on important set of points.

Moreover you may reconsider your clustering approach because DBSCAN is known to works well with small dimensional datasets due to hyperball volume fast decrease with higher dimensions.

Keep trying implementing algorithms by yourself it is best way to learn even if existing mature library do often a better job but are also more difficult to understand, one step after another you will be able to write better algorithms and contribute to open source libraries.

| improve this answer | |
$\endgroup$
-1
$\begingroup$

It also depends on the data spread. When I had data between 0-1 it worked well. When I tried to threshold some data inside so I had many samples with very small values. It started to work slowly.

| improve this answer | |
$\endgroup$

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.