Ist k-d-Baum effizient für kNN-Suche. k nächsten Nachbarn Suche

Question

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

Aber Problem ist, dass mein Algorithmus für k sehr schnell = 1, aber so viel wie 2000x langsamer für k> 1 (k = 2,5,10,20,100)

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

Answer 1

Nun, es hängt in erster Linie von Ihrer speziellen Implementierung und dem 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, als ob Sie dies für einen Kurs tun. Versuchen Sie, mit Ihrem Professor, TAs oder Klassenkameraden zu sprechen, um zu sehen, ob Ihre Ergebnisse typisch sind.

Answer 2

Ich weiß, dass diese Frage beantwortet worden ist, aber für weitere Einzelheiten über KNN-Suchen mit k-d-Bäumen siehe Bentley (1975: 514), Communications of the ACM 18 (9), September.