DBSCAN choice of epsilon through elbow method

user_14974763 0
Viewed 778

i am not sure to have understood why the elbow method is an approximate right way to determine a value of epsilon for DBSCAN algorithm. For instance, in the example below:

enter image description here

I considered the distance from the 5-th nearest neighbors and the points are arranged from the one with the minimum 5th-neighbor distance to the one that is at most distance from the 5th-neighbor.

I considered euclidean distane for the plot.

So i know that point 0-20, for instance, are the ones that are the most close to their 5-th nearest neighbor, then the points in the elbow are the one at intermediate distance from their 5-th nearest neighbor, and so they have a medium density. Then we reach point of very low density, far from their 5-th closest neighbor.

But I can't understand why it is reasonable to choose as the value of epsilon the distance between the k-th closest neigbor of points in the elbow.

Thanks for the help.

dbscan
1 Answers

From the paper dbscan: Fast Density-Based Clustering with R (page 11)

To find a suitable value for eps, we can plot the points’ kNN distances (i.e., the distance of each point to its k-th nearest neighbor) in decreasing order and look for a knee in the plot. The idea behind this heuristic is that points located inside of clusters will have a small k-nearest neighbor distance, because they are close to other points in the same cluster, while noise points are more isolated and will have a rather large kNN distance.

We need a cutoff to decide what k-NN distance is considered "small" and what is "large." The knee heuristic identifies such a cutoff for epsilon as the k-NN distance where the distance starts to increase rapidly.

user_38208370
Related