-1
$\begingroup$

I'm making a simple C implementation of DBSCAN following his pseudocode.

If I well underand how DBSCAN works, I may represent my set of N elements (each with M features) with a NxM matrix.

When it comes to write regionQuery(), I need calculate the distance between two points: if I was in an Euclidean plane (let's say in a Nx2 matrix), I'd use this formula; since I'm in a M-dimensional space, what is the proper formula?

$\endgroup$
  • $\begingroup$ Please paste in whatever context is necessary to understand & answer your question. We want this thread to remain valuable even if the link goes dead. $\endgroup$ – gung - Reinstate Monica Feb 6 '16 at 15:00
2
$\begingroup$

You can still calculate Euclidean distance in M dimensions, the proper formula can be found on the same page, where in this case n is M.

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

You wrote that you have N elements.

You distance matrix will be N*N (and not as written in the question), since you want to calculate the distance between all the points.

When coming to compute the distance between two specific points, you use the M features. As @Archie wrote, you have the formula at the same page. Note that $p_{i}$ is the i'th feature of the point p.

Other than that, remember that in many cases the proper distance matrix is domain dependent. Thought the Euclidian distance function is a common default, it does't fit all cases. For example, it assigns the same weight to all features. It is also very sensitive to scale (so most time performs better on normalized features).

I suggest that you will receive the distance function as an input to your DBSCAN algorithm (or just get the distance matrix as input). This way your algorithm will be flexible and you'll be able to use it with different distance functions too.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.