DBSCAN - K-distance Graph

K-distance Graph

use K-distance graph to choose epslions
intuition : How far do I have to look to include at least MinPts neighbors?
For a dataset of points, pick a point P

• Compute the distance from P to all other points.
• Sort those distances.
• The k-th smallest distance is called the k-th nearest neighbor distance. use KNN
  Say you have one point P, and distances from P to other points are:
  [0.1,  0.3,  0.05,  0.25,  0.6,  0.2]
• Sort them in ascending : [0.05,  0.1,  0.2,  0.25,  0.3,  0.6]
• If k=3, the 3rd nearest neighbor distance = 0.2.
• If k=5, the 5th nearest neighbor distance = 0.3.
• DBSCAN needs MinPts
• If you set MinPts=5, then k=5.
• That means: “What radius $ϵ$ is needed so every point has at least 5 neighbors?”
  So:
• For each data point → find distance to its k-th closest neighbor.
• Store that number.
• Do this for all points.
  
• The red X is the selected point.
• The blue dots are all the other data points.
• We sort distances from the red point to all others: [0,  0.10,  0.11,  0.97,  0.99,  1.01]
• If we pick k=3:
  • The 3rd nearest neighbor distance = 0.97 (the green circle)
  • That means: to include 3 neighbors, you need a radius of 0.97.
• The orange dashed circles are smaller distances (1st and 2nd nearest neighbors).
  It’s the radius you need around a point so that at least k neighbors fall inside.

Hierarchy DBSCAN solved the weakness of DBSCAN