CODEWITHSUNDEEP
pythonscikit-learnkdtree
user307380
user307380

Reputation: 75

python sklearn KDTree with haversine distance

I try to create a KD tree of WGS84 coordinates and find neighbors within a certain radius

from sklearn.neighbors.dist_metrics import DistanceMetric
from sklearn.neighbors.kd_tree import KDTree    
T = KDTree([[47.8665, 8.90123]], metric=DistanceMetric.get_metric('haversine'))

But get the following error:

ValueError: metric HaversineDistance is not valid for KDTree

How can I use haversine distance in a KD-Tree?

Upvotes: 6

Views: 4088

Answers (2)

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

The k-d-tree can (to the best of my knowledge) only be used with Minkowski norms.

There are other trees such as the ball tree in sklearn, or the covertree in ELKI that work with Haversine distance because it is a metric.

Upvotes: 4

hashcode55
hashcode55

Reputation: 5860

KDTree.valid_metrics

Output - 

['p',
 'l1',
 'chebyshev',
 'manhattan',
 'minkowski',
 'cityblock',
 'l2',
 'euclidean',
 'infinity']

Which tells, you can't use haversine with KDTree. The reason behind it is haversine distance gives you Orthodromic distance which is the distance measure used when your points are represented in a sphere. But in a kdTree the points are organised in a tree which makes it invalid to use.

Upvotes: 0

Related Questions