Python sklearn KDTree с хаверсинусным расстоянием

Пытаюсь создать KD-дерево координат WGS84 и найти соседей в определенном радиусе

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'))

Но получаю следующую ошибку:

ValueError: metric HaversineDistance is not valid for KDTree

Как я могу использовать гаверсинусное расстояние в KD-дереве?


python scikit-learn kdtree
person user307380    schedule 04.07.2016    source источник

Ответы (2)


arrow_upward
4
arrow_downward

K-d-дерево может (насколько мне известно) использоваться только с нормами Минковского.

Существуют и другие деревья, такие как дерево шаров в sklearn или скрытое дерево в ELKI, которые работают с расстоянием Хаверсинуса, потому что это метрика.

person Has QUIT--Anony-Mousse    schedule 05.07.2016
comment
Вы также можете использовать KDTree, но тогда вам нужно преобразовать ваши пары долготы и широты в карфесские / евклидовы значения и преобразовать значение расстояния обратно в мили или километры, чем. Насколько мне известно, вы также можете конвертировать долготу и широту в радианы, что дает вам расстояния прямо в километрах. Но не проверял это. - person Matthias; 16.08.2017

arrow_upward
0
arrow_downward

KDTree.valid_metrics

Выход -

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

Это говорит о том, что вы не можете использовать haversine с KDTree. Причина этого в том, что haversine расстояние дает вам ортодромное расстояние, которое используется при измерении расстояния точки представлены в сфере. Но в kdTree точки организованы в виде дерева, что делает его недопустимым для использования.

person hashcode55    schedule 04.07.2016
comment
Спасибо за объяснение. Есть идеи, как заставить его работать быстрее, чем за O (n ^ 2) (вычисление всех пар расстояний)? - person user307380; 05.07.2016
comment
Есть деревья, которые работают с гаверсином. Но kd-tree этого не делает. В Python примером является дерево мячей. - person Has QUIT--Anony-Mousse; 05.07.2016
comment
О, я совершенно не знал об этом. Спасибо за информацию. Я прочитаю об этом. - person hashcode55; 06.07.2016