Python: Nächster Nachbar (oder engste Übereinstimmung) Filtern auf Datensätzen (Liste der Tupel)

Ich versuche, eine Funktion zu schreiben, die eine Liste von Tupeln (Mimage einer In-Memory-Datenbank) filtern wird, indem sie einen "Nachbar-" oder "Nearest Match" -Typ-Algorithmus verwendet.

Ich möchte die beste (dh die meisten Pythonic) Weg, um dies zu tun wissen. Der Beispielcode unten zeigt hoffentlich, was ich versuche zu tun.

datarows = [(10,2.0,3.4,100), (11,2.0,5.4,120), (17,12.9,42,123)] filter_record = (9,1.9,2.9,99) # record that we are seeking to retrieve from 'database' (or nearest match) weights = (1,1,1,1) # weights to approportion to each field in the filter def get_nearest_neighbour(data, criteria, weights): for each row in data: # calculate 'distance metric' (eg simple differencing) and multiply by relevant weight # determine the row which was either an exact match or was 'least dissimilar' # return the match (or nearest match) pass if __name__ == '__main__': result = get_nearest_neighbour(datarow, filter_record, weights) print result 

Für das Snippet oben sollte die Ausgabe sein:

(10,2,0,3,4,100)

Da es die "am nächsten" zu den Beispieldaten ist, die an die Funktion get_nearest_neighbour () übergeben wurden.

Meine Frage ist dann, was ist der beste Weg, um get_nearest_neighbour () zu implementieren? Für den Zweck der Kürze usw., nehmen wir an, dass wir nur mit numerischen Werten zu tun haben und dass die "Distanzmetrik", die wir verwenden, einfach eine arithmentische Subtraktion der Eingangsdaten aus der aktuellen Zeile ist.

3 Solutions collect form web for “Python: Nächster Nachbar (oder engste Übereinstimmung) Filtern auf Datensätzen (Liste der Tupel)”

Einfache Out-of-the-Box-Lösung:

 import math def distance(row_a, row_b, weights): diffs = [math.fabs(ab) for a,b in zip(row_a, row_b)] return sum([v*w for v,w in zip(diffs, weights)]) def get_nearest_neighbour(data, criteria, weights): def sort_func(row): return distance(row, criteria, weights) return min(data, key=sort_func) 

Wenn du mit riesigen Datensätzen arbeiten musst, solltest du auf Numpy umschalten und Numpys KDTree , um die nächsten Nachbarn zu finden. Der Vorteil der Verwendung von Numpy ist, dass es nicht nur einen fortschrittlicheren Algorithmus verwendet, sondern auch ein Top of hoch optimierte LAPACK (Linear Algebra PACKage) .

Verwenden Sie heapq.nlargest auf einem Generator, der die Distanz * Gewicht für jeden Datensatz berechnet.

etwas wie:

 heapq.nlargest(N, ((row, dist_function(row,criteria,weight)) for row in data), operator.itemgetter(1)) 

Über naiv-NN:

Viele dieser anderen Antworten schlagen einen "naiven Nachbarn" vor, der ein O(N*d) -per-Abfrage-Algorithmus ist (d ist die Dimensionalität, die in diesem Fall konstant erscheint, also ist es O(N) -per-Abfrage ).

Während ein O(N) -per-Abfrage-Algorithmus ist ziemlich schlecht, können Sie in der Lage, weg mit ihm, wenn Sie weniger als irgendwelche von (zum Beispiel):

  • 10 Abfragen und 100000 Punkte
  • 100 Abfragen und 10000 Punkte
  • 1000 Abfragen und 1000 Punkte
  • 10000 Abfragen und 100 Punkte
  • 100000 Abfragen und 10 Punkte

Besser machen als naiv-NN:

Andernfalls möchten Sie eine der Techniken (insbesondere eine nächstgelegene Nachbardatenstruktur) verwenden, die in:

Besonders wenn Sie planen, Ihr Programm mehr als einmal auszuführen. Es gibt wahrscheinlich Bibliotheken zur Verfügung. Andernfalls würde eine NN-Datenstruktur nicht zu viel Zeit in Anspruch nehmen, wenn Sie ein großes Produkt von #queries * #points haben. Wie der Benutzer 'dsign' in den Kommentaren hervorhebt, kannst du probaby einen großen zusätzlichen konstanten Geschwindigkeitsfaktor ausdrücken, indem du die numpy Bibliothek verwende.

Allerdings, wenn Sie weg mit der einfach-zu-implementieren naive-NN aber können Sie es verwenden.

Python ist die beste Programmiersprache der Welt.