# Knn distance plot for determining eps of DBSCAN

I would like to use the knn distance plot to be able to figure out which eps value should I choose for the DBSCAN algorithm. Based on this page:

The idea is to calculate, the average of the distances of every point to its k nearest neighbors. The value of k will be specified by the user and corresponds to MinPts. Next, these k-distances are plotted in an ascending order. The aim is to determine the “knee”, which corresponds to the optimal eps parameter.

Using python with numpy/sklearn, I have the following points, with the following distance for 6-knn:

X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
nbrs = NearestNeighbors(n_neighbors=len(X)).fit(X)
distances, indices = nbrs.kneighbors(X)

# Indices

[[0 1 2 3 4 5]
[1 0 2 3 4 5]
[2 1 0 3 4 5]
[3 4 5 0 1 2]
[4 3 5 0 1 2]
[5 4 3 0 1 2]]

# Distances
[[ 0.          1.          2.23606798  2.82842712  3.60555128  5.        ]
[ 0.          1.          1.41421356  3.60555128  4.47213595  5.83095189]
[ 0.          1.41421356  2.23606798  5.          5.83095189  7.21110255]
[ 0.          1.          2.23606798  2.82842712  3.60555128  5.        ]
[ 0.          1.          1.41421356  3.60555128  4.47213595  5.83095189]
[ 0.          1.41421356  2.23606798  5.          5.83095189  7.21110255]]


then I computed the average distance:

distances.mean()
2.9269575028354495


The problem is I don't understand how exactly could I represent the same plot as them with distances in y-axis and number of points according to the distances on the x-axis using python.

Thank for your help.

You

1. take the last column of that matrix
2. sort descending
3. plot index, distance
4. hope to see a knee (if the distance does not work well. there might be none)
• On the same plot, I do this for different k? or only one k for one plot as in the example? and what do you mean by "index" – Marc Lamberti Feb 9 '16 at 20:53
• Using the 6NN when you only have 6 points is of course nonsense. Do it for an appropriate k. Index as in "array index". because you need 2d to plot. – Has QUIT--Anony-Mousse Feb 9 '16 at 20:57
• And i only use the last column of the distance matrix. Because in the example they talk about averaging distances.. – Marc Lamberti Feb 9 '16 at 22:26
• That post is incorrect there and in at least another place (you don't need to set a seed) – Has QUIT--Anony-Mousse Feb 9 '16 at 22:46
• You only have one k. Why don't you use the DBSCAN paper. but mash-up various low-quality websites? – Has QUIT--Anony-Mousse Feb 9 '16 at 22:53