2016-07-04 14 views
-1

ich versuche, einen KD-Baum von WGS84-Koordinaten zu erstellen und finden Nachbarn in einem gewissen RadiusPython sklearn KDTree mit Haversine Entfernung

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

Aber erhalten folgende Fehlermeldung:

ValueError: metric HaversineDistance is not valid for KDTree 

Wie kann ich Distanz in einem KD-Baum?

Antwort

0

Der k-d-Baum kann (nach bestem Wissen) nur mit Minkowski-Normen verwendet werden.

Es gibt andere Bäume wie der Ball Baum in Sklearn, oder der Baum in ELKI, die mit Haversine Abstand arbeiten, weil es eine Metrik ist.

+0

Sie können auch den KDTree verwenden, aber dann müssen Sie Ihre Längen- und Breitengradpaare in karthesische/euklidische Werte umwandeln und den Entfernungswert zurück in Meilen oder Kilometer umrechnen. Soweit ich weiß, können Sie auch Längen- und Breitengrade in Radianten umrechnen, wodurch Sie die Entfernungen direkt in Kilometern erhalten. Habe das aber nicht getestet. – Matthias

0

KDTree.valid_metrics

Ausgang -

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

Was sagt, kann man nicht haversine mit KDTree verwenden. Der Grund dafür ist haversine Entfernung gibt Ihnen Orthodromic Entfernung, die das Abstandmaß ist, wenn Ihre Punkte in einer Kugel dargestellt werden. Aber in einem kdTree sind die Punkte in einem Baum organisiert, was ihre Verwendung ungültig macht.

+0

Danke für die Erklärung. Irgendeine Idee, wie man es schneller als in O (n^2) laufen lässt (alle Distanzpaare berechnet)? – user307380

+1

Es gibt Bäume, die mit Haversin arbeiten. Aber der kd-Baum nicht. In Python ist der Ball ein Beispiel. –

+0

Oh, das war mir völlig unbekannt. Danke für die Information. Ich werde darüber lesen. – hashcode55