Ich habe eine große Menge von 2-dimensionalen Punkten und möchte in der Lage sein, die Menge für die k-Nearest-Neighbours eines beliebigen Punktes schnell abzufragen der 2-d Raum. Da es niedrigdimensional ist, scheint ein KD-Baum ein guter Weg zu sein. Mein erster Datensatz wird nur sehr selten aktualisiert, daher sollte mir die Zeit für die Abfrage eines Punktes wichtiger sein als die Bauzeit. Aber jedes Mal, wenn ich das Programm starte, muss ich das Objekt neu laden, also brauche ich auch eine Struktur, die schnell gespeichert und neu geladen werden kann.Geschwindigkeit von K-Nearest-Neighbour Build/Suche mit SciKit-learn und SciPy
Die beiden verfügbaren Optionen sind die KDTree-Strukturen in SciPy und in SciKit-learn. Im Folgenden profiliere ich die beiden für Build-Geschwindigkeit und Abfrage-Geschwindigkeit über einen großen Bereich von Listenlängen. Ich picke auch die SciKit-learn-Struktur und zeige die Zeit, um das Objekt von der Gurke wieder zu laden. Diese werden in einem Diagramm verglichen, und der Code, der zum Erzeugen der Zeitabläufe verwendet wird, ist unten enthalten.
Wie ich in der Grafik zeige, ist das Laden von einer Beize schneller als das Erstellen von Null um eine halbe Größenordnung für große N, was zeigt, dass die KDTree für meinen Anwendungsfall (dh häufige Neuladungen aber seltene Neubauten).
# Profiling the building time for the two KD-tree structures and re-loading from a pickle
import math, timeit, pickle, sklearn.neighbors
the_lengths = [100, 1000, 10000, 100000, 1000000]
theSciPyBuildTime = []
theSklBuildTime = []
theRebuildTime = []
for length in the_lengths:
dim = 5*int(math.sqrt(length))
nTimes = 50
from random import randint
listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]
setup = """import scipy.spatial
import sklearn.neighbors
length = """ + str(length) + """
dim = """ + str(dim) + """
from random import randint
listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]"""
theSciPyBuildTime.append(timeit.timeit('scipy.spatial.KDTree(listOfRandom2DPoints, leafsize=20)', setup=setup, number=nTimes)/nTimes)
theSklBuildTime.append(timeit.timeit('sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20)', setup=setup, number=nTimes)/nTimes)
theTreeSkl = sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20, metric='euclidean')
f = open('temp.pkl','w')
temp = pickle.dumps(theTreeSkl)
theRebuildTime.append(timeit.timeit('pickle.loads(temp)', 'from __main__ import pickle,temp', number=nTimes)/nTimes)
-Code-Abfrage-Zeiten vergleichen:
-Code build-Zeiten vergleichen
# Profiling the query time for the two KD-tree structures
import scipy.spatial, sklearn.neighbors
the_lengths = [100, 1000, 10000, 100000, 1000000, 10000000]
theSciPyQueryTime = []
theSklQueryTime = []
for length in the_lengths:
dim = 5*int(math.sqrt(length))
nTimes = 50
listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]
setup = """from __main__ import sciPiTree,sklTree
from random import randint
length = """ + str(length) + """
randPoint = [randint(0,""" + str(dim) + """),randint(0,""" + str(dim) + """)]"""
sciPiTree = scipy.spatial.KDTree(listOfRandom2DPoints, leafsize=20)
sklTree = sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20)
theSciPyQueryTime.append(timeit.timeit('sciPiTree.query(randPoint,10)', setup=setup, number=nTimes)/nTimes)
theSklQueryTime.append(timeit.timeit('sklTree.query(randPoint,10)', setup=setup, number=nTimes)/nTimes)
Fragen:
Das Ergebnis: Obwohl sie näher bei sehr großer N bekommen, Scikit-Learn scheint SciPy zu schlagen sowohl Zeit als auch Abfrage der Zeit bauen. Haben andere Personen das gefunden?
Die Mathematik: Gibt es dafür bessere Strukturen? Ich arbeite nur in einem 2D-Raum (obwohl die Daten werden ziemlich dicht, so Brute Force ist out), gibt es eine bessere Struktur für niedrigdimensionalen kNN sucht?
Das Speed : Es sieht aus wie die Build-Zeit für die beiden Ansätze ist immer näher an großen N aber mein Computer gab auf mir - kann jemand dies für eine größere N für mich überprüfen ?! Vielen Dank!! Wird die Zeit für die Rekonstruktion weiterhin linear erhöht?
Praktisch: Der SciPy KDTree wird nicht pikieren. Wie in this post berichten, habe ich folgende Fehlermeldung gegeben „PicklingError: Kann nicht Gurke: es ist nicht so scipy.spatial.kdtree.innernode gefunden hat“ - Ich denke, das ist darauf zurückzuführen, es ist eine verschachtelte Struktur zu sein. Gemäß einer in this post, berichteten Antwort können verschachtelte Strukturen mit Dill gebeizt werden. Allerdings gibt mir dill den gleichen Fehler - warum ist das so?