how to plot a k-distance graph in python

python cluster-analysis dbscan
Mauro Gentile picture Mauro Gentile · Apr 1, 2017 · Viewed 10.3k times · Source

How do I plot (in python) the distance graph for a given value of min-points in DBSCAN???

I am looking for the knee and corresponding epsilon value.

In the sklearn I do not see any method that return such distances.... Am I missing something?

Answer

Haritz Laboa picture Haritz Laboa · Apr 11, 2019

First you can define a function to calculate the distance of each point to its k-th nearest neighbor:

def calculate_kn_distance(X,k):

    kn_distance = []
    for i in range(len(X)):
        eucl_dist = []
        for j in range(len(X)):
            eucl_dist.append(
                math.sqrt(
                    ((X[i,0] - X[j,0]) ** 2) +
                    ((X[i,1] - X[j,1]) ** 2)))

        eucl_dist.sort()
        kn_distance.append(eucl_dist[k])

    return kn_distance

Then, once you have defined your function, you can choose a k value and plot the histogram to find a knee to define an appropriate epsilon value.

eps_dist = calculate_kn_distance(X[1],4)
plt.hist(eps_dist,bins=30)
plt.ylabel('n');
plt.xlabel('Epsilon distance');

enter image description here

In the example above, a vast majority of points lie within 0.12 units from their 4th nearest neighbor. So, a heuristic approach, could be choosing 0.12 as epsilon parameter.

Related questions

DBSCAN for clustering of geographic location data

I have a dataframe with latitude and longitude pairs. Here is my dataframe look like. order_lat order_long 0 19.111841 72.910729 1 19.111342 72.908387 2 19.111342 72.908387 3 19.137815 72.914085 4 19.119677 72.905081 5 19.119677 72.905081 6 19.119677 72.905081 7 19.120217 72.907121 8 19.120217 72.907121 9 19.119677 72.905081 10 19.119677 72.905081 11 19.119677 72.905081 12 19.111860 72.911346 13 19.111860 72.911346 14 19.119677 72.905081 15 19.119677 72.905081 16 19.119677 72.905081 17 19.137815 72.914085 18 19.115380 72.909144 19 19.115380 72.909144 20 19.116168 72.909573 21 19.119677 72.905081 22 19.137815 72.914085 23 19.137815 72.914085 24 19.112955 72.910102 25 19.112955 72.910102 26 19.112955 72.910102 27 19.119677 72.905081 28 19.119677 72.905081 29 19.115380 72.909144 30 19.119677 72.905081 31 19.119677 72.905081 32 19.119677 72.905081 33 19.119677 72.905081 34 19.119677 72.905081 35 19.111860 72.911346 36 19.111841 72.910729 37 19.131674 72.918510 38 19.119677 72.905081 39 19.111860 72.911346 40 19.111860 72.911346 41 19.111841 72.910729 42 19.111841 72.910729 43 19.111841 72.910729 44 19.115380 72.909144 45 19.116625 72.909185 46 19.115671 72.908985 47 19.119677 72.905081 48 19.119677 72.905081 49 19.119677 72.905081 50 19.116183 72.909646 51 19.113827 72.893833 52 19.119677 72.905081 53 19.114100 72.894985 54 19.107491 72.901760 55 19.119677 72.905081 I want to cluster this points which are nearest to each other(200 meters distance) following is my distance matrix. from scipy.…

Read More
DBSCAN in scikit-learn of Python: save the cluster points in an array

following the example Demo of DBSCAN clustering algorithm of Scikit Learning i am trying to store in an array the x, y of each clustering class import numpy as np from sklearn.cluster import DBSCAN from sklearn import metrics from …

Read More
scikit-learn DBSCAN memory usage

UPDATED: In the end, the solution I opted to use for clustering my large dataset was one suggested by Anony-Mousse below. That is, using ELKI's DBSCAN implimentation to do my clustering rather than scikit-learn's. It can be run from the …

Read More