Nächste Nachbarn in hochdimensionalen Daten?

Ich habe vor ein paar Tagen eine Frage gestellt, wie man die nächsten Nachbarn für einen bestimmten Vektor findet. Mein Vektor hat jetzt 21 Dimensionen und bevor ich fortfahre, beginne ich mir einige grundlegende Fragen zu stellen, da ich weder aus dem Bereich des maschinellen Lernens noch der Mathematik stamme:

• Ist die euklidische Entfernung überhaupt eine gute Metrik, um die nächsten Nachbarn zu finden? Wenn nicht, welche Möglichkeiten habe ich?
• Wie entscheidet man sich außerdem über die richtige Schwelle zur Bestimmung der k-Nachbarn? Gibt es eine Analyse, die durchgeführt werden kann, um diesen Wert herauszufinden?
• Früher wurde mir vorgeschlagen, kd-Trees zu verwenden, aber auf der Wikipedia-Seite steht eindeutig, dass kd-Tree für große Dimensionen fast einer Brute-Force-Suche entspricht. Was ist in diesem Fall der beste Weg, um die nächsten Nachbarn in einem Millionen-Punkte-Datensatz effizient zu finden?

Kann jemand bitte einige (oder alle) der oben genannten Fragen klären?

Ich untersuche derzeit solche Probleme - Klassifizierung, Suche nach dem nächsten Nachbarn - für das Abrufen von Musikinformationen.

Möglicherweise interessieren Sie sich für ANN- Algorithmen ( Approximate Nearest Neighbor ). Die Idee ist, dass Sie dem Algorithmus erlauben, ausreichend nahe Nachbarn zurückzukehren (möglicherweise nicht dem nächsten Nachbarn); Auf diese Weise reduzieren Sie die Komplexität. Sie haben den kd-Baum erwähnt ; das ist ein Beispiel. Aber wie Sie sagten, funktioniert kd-tree in hohen Dimensionen schlecht. Tatsächlich verschlechtern sich alle aktuellen Indizierungstechniken (basierend auf der Raumaufteilung) auf die lineare Suche nach ausreichend hohen Dimensionen [1] [2] [3].

Unter den kürzlich vorgeschlagenen ANN- Algorithmen ist das Locality-Sensitive Hashing ( LSH ) vielleicht das beliebteste , bei dem eine Reihe von Punkten in einem hochdimensionalen Raum in eine Reihe von Bins, dh eine Hash-Tabelle, abgebildet wird [1] [3]. Im Gegensatz zu herkömmlichen Hashes platziert ein ortsabhängiger Hash in der Nähe Punkte in demselben Bin.

LSH hat einige große Vorteile. Erstens ist es einfach. Sie berechnen einfach den Hash für alle Punkte in Ihrer Datenbank und erstellen daraus eine Hash-Tabelle. Berechnen Sie zum Abfragen einfach den Hash des Abfragepunkts und rufen Sie dann alle Punkte im selben Bin aus der Hash-Tabelle ab.

Zweitens gibt es eine strenge Theorie, die ihre Leistung unterstützt. Es kann gezeigt werden, dass die Abfragezeit in der Größe der Datenbank sublinear ist , dh schneller als die lineare Suche. Wie viel schneller, hängt davon ab, wie viel Annäherung wir tolerieren können.

Schließlich ist LSH mit jeder Lp-Norm für kompatibel 0 < p <= 2. Um Ihre erste Frage zu beantworten, können Sie LSH mit der euklidischen Distanzmetrik oder mit der Manhattan-Distanzmetrik (L1) verwenden. Es gibt auch Varianten für Hamming-Abstand und Kosinusähnlichkeit.

Ein anständiger Überblick wurde 2008 von Malcolm Slaney und Michael Casey für das IEEE Signal Processing Magazine geschrieben [4].

LSH wurde scheinbar überall angewendet. Vielleicht möchten Sie es versuchen.

[1] Datar, Indyk, Immorlica, Mirrokni, "Lokalitätssensitives Hashing-Schema basierend auf p-stabilen Verteilungen", 2004.

[2] Weber, Schek, Blott, "Eine quantitative Analyse und Leistungsstudie für Ähnlichkeitssuchmethoden in hochdimensionalen Räumen", 1998.

[3] Gionis, Indyk, Motwani, "Ähnlichkeitssuche in hohen Dimensionen durch Hashing", 1999.

[4] Slaney, Casey, "Lokalitätssensitives Hashing zur Suche nach nächsten Nachbarn", 2008.

I. Die Entfernungsmetrik

Erstens ist die Anzahl der Merkmale (Spalten) in einem Datensatz kein Faktor bei der Auswahl einer Abstandsmetrik zur Verwendung in kNN. Es gibt einige veröffentlichte Studien, die sich genau mit dieser Frage befassen, und die üblichen Vergleichsgrundlagen sind:

• die zugrunde liegende statistische Verteilung Ihrer Daten;

• die Beziehung zwischen den Merkmalen, aus denen Ihre Daten bestehen (sind sie unabhängig - dh wie sieht die Kovarianzmatrix aus); und

• Der Koordinatenraum, aus dem Ihre Daten stammen.

Wenn Sie keine vorherige Kenntnis der Verteilung haben (s) , von dem die Daten abgetastet wurden, mindestens ein (gut dokumentiert und gründlich) Studie kommt zu dem Schluss , dass euklidischer Abstand die beste Wahl ist.

YEuklidische Metrik, die in Mega-Web-Empfehlungs-Engines sowie in der aktuellen akademischen Forschung verwendet wird. Von Euklidisch berechnete Entfernungen haben eine intuitive Bedeutung und die Berechnungsskalen - dh die euklidische Entfernung wird auf dieselbe Weise berechnet, unabhängig davon, ob sich die beiden Punkte in zwei Dimensionen oder im Raum mit zweiundzwanzig Dimensionen befinden.

Es ist für mich nur ein paar Mal gescheitert, jeder dieser Fälle ist fehlgeschlagen, weil das zugrunde liegende (kartesische) Koordinatensystem eine schlechte Wahl war. Und Sie werden dies normalerweise erkennen, weil beispielsweise Pfadlängen (Entfernungen) nicht mehr additiv sind - z. B. wenn der metrische Raum ein Schachbrett ist, ist die Manhattan-Entfernung besser als die euklidische, ebenso wenn der metrische Raum Erde ist und Ihre Entfernungen trans sind -Kontinentalflüge, eine für ein Polarkoordinatensystem geeignete Entfernungsmetrik ist eine gute Idee (z. B. London nach Wien dauert 2,5 Stunden, Wien nach St. Petersburg weitere 3 Stunden, mehr oder weniger in die gleiche Richtung, London nach St. Petersburg ist nicht 5,5 Stunden, sondern etwas mehr als 3 Stunden.)

Abgesehen von den Fällen, in denen Ihre Daten zu einem nicht kartesischen Koordinatensystem gehören, ist die Wahl der Entfernungsmetrik normalerweise nicht wesentlich. (Siehe diesen Blog-Beitrag eines CS-Studenten, in dem verschiedene Entfernungsmetriken verglichen werden, indem ihre Wirkung auf den kNN-Klassifikator untersucht wird. Das Chi-Quadrat liefert die besten Ergebnisse, aber die Unterschiede sind nicht groß. Eine umfassendere Studie finden Sie in der wissenschaftlichen Arbeit Comparative Study of Entfernungsfunktionen für die nächsten Nachbarn - Mahalanobis (im Wesentlichen euklidisch normalisiert durch, um die Dimensionskovarianz zu berücksichtigen) war die beste in dieser Studie.

Eine wichtige Voraussetzung: Damit Entfernungsmetrikberechnungen aussagekräftig sind, müssen Sie neu skalierenIhre Daten - selten ist es möglich, ein kNN-Modell zu erstellen, um genaue Vorhersagen zu generieren, ohne dies zu tun. Wenn Sie beispielsweise ein kNN-Modell erstellen, um die sportliche Leistung vorherzusagen, und Ihre Erwartungsvariablen Größe (cm), Gewicht (kg), Körperfett (%) und Ruhepuls (Schläge pro Minute) sind, kann dies ein typischer Datenpunkt sein sehen ungefähr so ​​aus: [180.4, 66.1, 11.3, 71]. Es ist klar, dass die Entfernungsberechnung von der Höhe dominiert wird, während der Beitrag von Körperfett% fast vernachlässigbar sein wird. Anders ausgedrückt: Wenn stattdessen die Daten anders angegeben würden, sodass das Körpergewicht in Gramm statt in Kilogramm angegeben würde, wäre der ursprüngliche Wert von 86,1 86.100, was einen großen Einfluss auf Ihre Ergebnisse hätte, und genau das tun Sie will nicht.

X_new = (X_old - mu) / sigma

II. Die Datenstruktur

Wenn Sie sich Gedanken über die Leistung der kd-Baumstruktur machen, ist A Voronoi Tessellation ein konzeptionell einfacher Container, der jedoch die Leistung drastisch verbessert und besser skaliert als kd-Bäume.

Dies ist nicht die gebräuchlichste Methode, um kNN-Trainingsdaten beizubehalten, obwohl die Anwendung von VT für diesen Zweck sowie die daraus resultierenden Leistungsvorteile gut dokumentiert sind (siehe z. B. diesen Microsoft Research-Bericht ). Die praktische Bedeutung davon ist, dass Sie, vorausgesetzt Sie verwenden eine 'Mainstream'-Sprache (z. B. im TIOBE-Index ), eine Bibliothek finden sollten, um VT durchzuführen. Ich weiß, dass es in Python und R für jede Sprache mehrere Optionen gibt (z. B. das auf CRAN verfügbare Voronoi- Paket für R ).

Die Verwendung eines VT für kNN funktioniert folgendermaßen:

Wählen Sie aus Ihren Daten zufällig w Punkte aus - dies sind Ihre Voronoi-Zentren. Eine Voronoi-Zelle kapselt alle benachbarten Punkte, die jedem Zentrum am nächsten liegen. Stellen Sie sich vor, Sie weisen jedem Voronoi-Zentrum eine andere Farbe zu, sodass jeder Punkt, der einem bestimmten Zentrum zugewiesen ist, in dieser Farbe gezeichnet wird. Solange Sie eine ausreichende Dichte haben, werden auf diese Weise die Grenzen jedes Voronoi-Zentrums gut angezeigt (als die Grenze, die zwei Farben trennt.

Wie wähle ich die Voronoi-Zentren aus? Ich benutze zwei orthogonale Richtlinien. Berechnen Sie nach zufälliger Auswahl der w-Punkte die VT für Ihre Trainingsdaten. Überprüfen Sie als Nächstes die Anzahl der Datenpunkte, die jedem Voronoi-Zentrum zugewiesen sind. Diese Werte sollten ungefähr gleich sein (bei gleichmäßiger Punktdichte über Ihren Datenraum). In zwei Dimensionen würde dies eine VT mit Kacheln gleicher Größe verursachen. Dies ist die erste Regel, hier die zweite. Wählen Sie w durch Iteration aus - führen Sie Ihren kNN-Algorithmus mit w als variablem Parameter aus und messen Sie die Leistung (Zeit, die erforderlich ist, um eine Vorhersage durch Abfragen der VT zurückzugeben).

So stellen Sie haben eine Million Datenpunkte ..... Wenn die Punkte in einer gewöhnlichen 2D - Datenstruktur beibehalten wurden, oder in einem kd-Baum, würden Sie im Durchschnitt ein paar Millionen Abstandsberechnungen für führen jedenneue Datenpunkte, deren Antwortvariable Sie vorhersagen möchten. Natürlich werden diese Berechnungen an einem einzelnen Datensatz durchgeführt. Bei einem V / T wird die Suche nach dem nächsten Nachbarn in zwei Schritten nacheinander gegen zwei verschiedene Datenpopulationen durchgeführt - zuerst gegen die Voronoi-Zentren, dann, sobald das nächste Zentrum gefunden ist, entsprechen die Punkte innerhalb der Zelle Diese Zentren werden durchsucht, um den tatsächlichen nächsten Nachbarn zu finden (durch aufeinanderfolgende Entfernungsberechnungen). Zusammen sind diese beiden Suchvorgänge viel schneller als eine einzelne Brute-Force-Suche. Das ist leicht zu erkennen: Angenommen, Sie wählen für 1 Millionen Datenpunkte 250 Voronoi-Zentren aus, um Ihren Datenraum zu tesselieren. Im Durchschnitt hat jede Voronoi-Zelle 4.000 Datenpunkte. Anstatt durchschnittlich 500.000 Entfernungsberechnungen (Brute Force) durchzuführen, führen Sie weitaus weniger aus, im Durchschnitt nur 125 + 2.000.

III. Berechnung des Ergebnisses (der vorhergesagten Antwortvariablen)

Es gibt zwei Schritte zum Berechnen des vorhergesagten Werts aus einem Satz von kNN-Trainingsdaten. Der erste ist die Identifizierung von n oder der Anzahl der nächsten Nachbarn , die für diese Berechnung verwendet werden sollen. Die zweite ist, wie ihr Beitrag zum vorhergesagten Wert gewichtet wird.

Mit der ersten Komponente können Sie den besten Wert von n bestimmen, indem Sie ein Optimierungsproblem lösen (sehr ähnlich der Optimierung der kleinsten Quadrate). Das ist die Theorie; In der Praxis verwenden die meisten Leute nur n = 3. In jedem Fall ist es einfach, Ihren kNN-Algorithmus über eine Reihe von Testinstanzen (um vorhergesagte Werte zu berechnen) für n = 1, n = 2, n = 3 usw. auszuführen und den Fehler als Funktion von n darzustellen. Wenn Sie nur einen plausiblen Wert für n haben möchten, verwenden Sie einfach n = 3.

Die zweite Komponente ist die Gewichtung des Beitrags jedes Nachbarn (unter der Annahme von n> 1).

Die einfachste Gewichtungstechnik besteht darin, jeden Nachbarn mit einem Gewichtungskoeffizienten zu multiplizieren, der nur 1 / (dist * K) ist, oder die Umkehrung des Abstands von diesem Nachbarn zur Testinstanz, häufig multipliziert mit einer empirisch abgeleiteten Konstante K. I. Ich bin kein Fan dieser Technik, weil sie oft die nächsten Nachbarn übergewichtet (und gleichzeitig die entfernteren Nachbarn untergewichtet). Die Bedeutung davon ist, dass eine gegebene Vorhersage fast vollständig von einem einzelnen Nachbarn abhängig sein kann, was wiederum die Empfindlichkeit des Algorithmus gegenüber Rauschen erhöht.

Eine bessere Gewichtungsfunktion, die diese Einschränkung im Wesentlichen vermeidet, ist die Gauß-Funktion , die in Python folgendermaßen aussieht:

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

Um einen vorhergesagten Wert unter Verwendung Ihres kNN-Codes zu berechnen, identifizieren Sie die n nächsten Nachbarn zu dem Datenpunkt, dessen Antwortvariable Sie vorhersagen möchten ('Testinstanz'), und rufen dann die Funktion weight_gauss einmal für jeden der n übergebenen Nachbarn auf in der Entfernung zwischen jedem Nachbarn der Testpunkt. Diese Funktion gibt das Gewicht für jeden Nachbarn zurück, das dann als Koeffizient dieses Nachbarn in der Berechnung des gewichteten Durchschnitts verwendet wird.

Was Sie sehen, ist als Fluch der Dimensionalität bekannt . Es ist manchmal nützlich, einen Algorithmus wie PCA oder ICA auszuführen , um sicherzustellen, dass Sie wirklich alle 21 Dimensionen benötigen und möglicherweise eine lineare Transformation finden, mit der Sie weniger als 21 mit ungefähr derselben Ergebnisqualität verwenden können.

Update: Ich habe sie in einem Buch namens Biomedical Signal Processing von Rangayyan gesehen (ich hoffe, ich erinnere mich richtig daran). ICA ist keine triviale Technik, aber sie wurde von Forschern in Finnland entwickelt und ich denke, Matlab-Code dafür ist öffentlich zum Download verfügbar. PCA ist eine weit verbreitete Technik, und ich glaube, Sie sollten in der Lage sein, ihre R- oder andere Software-Implementierung zu finden. PCA wird durchgeführt, indem lineare Gleichungen iterativ gelöst werden. Ich habe es vor zu langer Zeit getan, um mich daran zu erinnern, wie. =)

Die Idee ist, dass Sie Ihre Signale in unabhängige Eigenvektoren (wirklich diskrete Eigenfunktionen) und deren Eigenwerte 21 aufteilen, in Ihrem Fall. Jeder Eigenwert gibt den Beitrag an, den jede Eigenfunktion zu jeder Ihrer Messungen leistet. Wenn ein Eigenwert winzig ist, können Sie die Signale sehr genau darstellen, ohne die entsprechende Eigenfunktion zu verwenden, und auf diese Weise wird eine Dimension entfernt.

Die besten Antworten sind gut, aber alt, daher möchte ich eine Antwort für 2016 zusammenfassen .

Wie gesagt, in einem hochdimensionalen Raum lauert der Fluch der Dimensionalität um die Ecke und macht die traditionellen Ansätze wie den beliebten kd-Baum so langsam wie einen Brute-Force-Ansatz. Infolgedessen wenden wir uns der ANNS (Approximate Nearest Neighbor Search) zu , die den Prozess zugunsten einer gewissen Genauigkeit beschleunigt. Sie erhalten eine gute Annäherung an die genaue NN mit einer guten Propabilität.

Heiße Themen, die es wert sein könnten:

1. Moderne Ansätze von LSH wie Razenshteyns .
2. RKD-Wald : Wald (e) von randomisierten kd-Bäumen (RKD), wie in FLANN beschrieben , oder in einem neueren Ansatz, an dem ich beteiligt war, kd-GeRaF .
3. LOPQ steht für Local Optimized Product Quantization, wie hier beschrieben . Es ist dem Ansatz des neuen Babenko + Lemptitsky sehr ähnlich .

Sie können auch meine relevanten Antworten überprüfen:

1. Zwei Sätze hochdimensionaler Punkte: Finden Sie den nächsten Nachbarn im anderen Satz
2. Vergleich der Laufzeit von Nearest Neighbor-Abfragen in verschiedenen Datenstrukturen
3. PCL kd-tree Implementierung extrem langsam

Um Ihre Fragen einzeln zu beantworten:

• Nein, der euklidische Abstand ist eine schlechte Metrik im hochdimensionalen Raum. Grundsätzlich weisen Datenpunkte in hohen Dimensionen große Unterschiede auf. Dies verringert den relativen Unterschied in der Entfernung zwischen einem bestimmten Datenpunkt und seinem nächsten und am weitesten entfernten Nachbarn.
• Viele Artikel / Forschungsergebnisse sind in hochdimensionalen Daten enthalten, aber die meisten Dinge erfordern viel mathematische Raffinesse.
• KD-Baum ist schlecht für hochdimensionale Daten ... vermeiden Sie es auf jeden Fall

Hier ist ein schönes Papier, mit dem Sie in die richtige Richtung starten können. " Wann im nächsten Nachbarn sinnvoll ?" von Beyer et al.

Ich arbeite mit Textdaten mit den Abmessungen 20K und höher. Wenn Sie textbezogene Ratschläge wünschen, kann ich Ihnen möglicherweise weiterhelfen.

Die Kosinusähnlichkeit ist ein üblicher Weg, um hochdimensionale Vektoren zu vergleichen. Da es sich um eine Ähnlichkeit und nicht um eine Entfernung handelt, möchten Sie diese maximieren und nicht minimieren. Sie können die Daten auch domänenspezifisch vergleichen. Wenn es sich bei Ihren Daten beispielsweise um DNA-Sequenzen handelt, können Sie eine Sequenzähnlichkeit verwenden, die die Wahrscheinlichkeiten von Mutationen usw. berücksichtigt.

Die Anzahl der zu verwendenden nächsten Nachbarn hängt von der Art der Daten, dem Rauschen usw. ab. Es gibt keine allgemeinen Regeln. Sie müssen nur herausfinden, was für Ihre spezifischen Daten und Probleme am besten geeignet ist, indem Sie alle Werte innerhalb eines Bereichs ausprobieren . Die Menschen haben ein intuitives Verständnis dafür, dass je mehr Daten vorhanden sind, desto weniger Nachbarn Sie benötigen. In einer hypothetischen Situation, in der Sie alle möglichen Daten haben, müssen Sie nur nach dem nächsten Nachbarn suchen, um ihn zu klassifizieren.

Es ist bekannt, dass die k Nearest Neighbor-Methode rechenintensiv ist. Dies ist einer der Hauptgründe, warum Menschen sich anderen Algorithmen wie Support-Vektor-Maschinen zuwenden.

kd-Bäume funktionieren bei hochdimensionalen Daten in der Tat nicht sehr gut. Weil der Schnittschritt nicht mehr viel hilft, da die nächste Kante - eine eindimensionale Abweichung - fast immer kleiner ist als die volldimensionale Abweichung zu den bekannten nächsten Nachbarn.

Darüber hinaus funktionieren kd-Bäume meines Wissens nur gut mit Lp-Normen, und es gibt den Effekt der Entfernungskonzentration, der dazu führt, dass sich entfernungsbasierte Algorithmen mit zunehmender Dimensionalität verschlechtern.

Für weitere Informationen möchten Sie vielleicht den Fluch der Dimensionalität und die verschiedenen Varianten davon nachlesen (es gibt mehr als eine Seite!).

Ich bin nicht davon überzeugt, dass es sinnvoll ist, die nächsten euklidischen Nachbarn blind zu approximieren, z. B. mithilfe von LSH oder zufälligen Projektionen. Es kann notwendig sein, überhaupt eine viel feiner abgestimmte Distanzfunktion zu verwenden!

Viel hängt davon ab, warum Sie die nächsten Nachbarn kennenlernen möchten. Sie können sich den Mean-Shift-Algorithmus http://en.wikipedia.org/wiki/Mean-shift ansehen, wenn Sie wirklich die Modi Ihres Datensatzes finden möchten.

Ich denke, Cosinus auf tf-idf von booleschen Funktionen würde für die meisten Probleme gut funktionieren. Das liegt daran, dass die bewährte Heuristik in vielen Suchmaschinen wie Lucene verwendet wird. Die euklidische Distanz zeigt meiner Erfahrung nach schlechte Ergebnisse für textähnliche Daten. Die Auswahl verschiedener Gewichte und k-Beispiele kann mit Trainingsdaten und Brute-Force-Parameterauswahl erfolgen.

iDistance ist wahrscheinlich das Beste für den exakten Knn-Abruf in hochdimensionalen Daten. Sie können es als ungefähre Voronoi-Tessalisierung ansehen.

Ich habe das gleiche Problem erlebt und kann Folgendes sagen.

1. Die euklidische Entfernung ist eine gute Entfernungsmetrik, jedoch rechenintensiver als die Manhattan-Entfernung und führt manchmal zu etwas schlechteren Ergebnissen. Daher würde ich die spätere wählen.

2. Der Wert von k kann empirisch ermittelt werden. Sie können verschiedene Werte ausprobieren und die resultierenden ROC-Kurven oder ein anderes Präzisions- / Rückrufmaß überprüfen , um einen akzeptablen Wert zu finden.

3. Sowohl die euklidischen als auch die Manhattan-Entfernungen berücksichtigen die Dreiecksungleichung , sodass Sie sie in metrischen Bäumen verwenden können. In der Tat ist die Leistung von KD-Bäumen stark beeinträchtigt, wenn die Daten mehr als 10 Dimensionen haben (ich habe dieses Problem selbst erlebt). Ich fand VP-Bäume eine bessere Option.

KD-Bäume funktionieren in 21 Dimensionen einwandfrei, wenn Sie vorzeitig beenden, nachdem Sie beispielsweise 5% aller Punkte betrachtet haben. FLANN führt dies (und andere Beschleunigungen) durch, um 128-dim-SIFT-Vektoren abzugleichen. (Leider führt FLANN nur die euklidische Metrik durch, und der schnelle und solide scipy.spatial.cKDTree führt nur Lp-Metriken aus. Diese können für Ihre Daten geeignet sein oder auch nicht .) Hier gibt es natürlich einen Kompromiss zwischen Geschwindigkeit und Genauigkeit.

(Wenn Sie Ihre Ndata, Nquery, Datenverteilung beschreiben könnten, könnte dies den Leuten helfen, ähnliche Daten auszuprobieren.)

Hinzugefügt am 26. April, Laufzeiten für cKDTree mit Cutoff auf meinem alten Mac-PC, um eine sehr grobe Vorstellung von der Machbarkeit zu geben:

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 %
3.5 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.253

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 %
15 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.245

Sie könnten eine Ordnungskurve versuchen. Es ist einfach für 3 Dimensionen.

Ist die euklidische Entfernung überhaupt eine gute Metrik, um die nächsten Nachbarn zu finden? Wenn nicht, welche Möglichkeiten habe ich?

Ich würde Soft Subspace Clustering vorschlagen , ein heutzutage weit verbreiteter Ansatz, bei dem Feature-Gewichte berechnet werden, um die relevantesten Dimensionen zu finden. Sie können diese Gewichte beispielsweise verwenden, wenn Sie den euklidischen Abstand verwenden. Siehe Fluch der Dimensionalität für häufige Probleme und auch dieser Artikel kann Sie irgendwie aufklären:

Ein Clustering-Algorithmus vom Typ k-means für das Subraum-Clustering von gemischten numerischen und kategorialen Datensätzen