Ist der k-d-Baum effizient für die kNN-Suche? k Nächsten Nachbarn suchen

Question

Ist der k-d-Baum effizient für die kNN-Suche? k Nächsten Nachbarn suchen

8

Ich muss k nächsten Nachbarn suchen nach 10-dimensionalen Daten in kd-Baum.

Aber das Problem ist, dass mein Algorithmus sehr schnell ist für k = 1, aber bis zu 2000x langsamer für k & gt; 1 (k = 2,5,10,20,100)

Ist das normal für kd Bäume, oder mache ich etwas worng?

search kdtree nearest-neighbor knn

Andraz 09.01.2010, 17:24

quelle

2 Antworten

5

Ich weiß, dass diese Frage beantwortet wurde, aber für weitere Einzelheiten über KNN-Suchen mit kd-Bäumen siehe Bentley (1975: 514), Mitteilungen der ACM 18 (9), September.

fluffels 14.08.2010 10:02

quelle

Tags und Links search kdtree nearest-neighbor knn

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Kakao Fehler 256 Kerndaten

score 7 · Accepted Answer

Nun, es hängt in erster Linie von Ihrer speziellen Implementierung und Ihrem Datensatz ab.

Ein schlecht ausgewogener Baum bedeutet, dass Sie viel mehr Daten suchen müssen, als Sie benötigen. Stellen Sie sicher, dass Ihre Baumkonstruktion gesund ist.

Es könnte auch davon abhängen, wie Sie die k Nachbarn finden. Wenn Ihr Algorithmus den Baum nach dem nächsten Nachbarn durchsucht und ihn speichert, dann nach dem zweitnächsten sucht und diesen usw. speichert, dann machen Sie die Suche nicht sehr effizient. Stattdessen halten Sie eine laufende Liste der k nächsten Nachbarn und Bump Punkte aus der Liste, wie Sie nähere diejenigen finden, die den Baum überqueren. Auf diese Weise suchen Sie einmal statt k mal.

Wie auch immer, es klingt so, als würden Sie das für einen Kurs machen. Versuchen Sie, mit Ihrem Professor, TAs oder Klassenkameraden zu sprechen, um zu sehen, ob Ihre Ergebnisse typisch sind.