KNN mit dynamischen Einfügungen im hoch-dimensionalen Raum

Question

Ich suche nach einer Methode, um schnelle Nachbarsuche (höchstwahrscheinlich O(log n)) für hochdimensionale Punkte (typischerweise ~11-13 dimensionale) durchzuführen. Ich möchte, dass es sich optimal verhält, nachdem die Struktur initialisiert wurde. Ein KD-Baum ist mir eingefallen, aber wenn Sie keine Stapelverarbeitung durchführen, sondern dynamische Einfügungen vornehmen, dann ist der KD-Baum nicht mehr ausgeglichen und meiner Meinung nach ist das Ausbalancieren eine teure Operation.

Also wollte ich wissen, welche Datenstrukturen Sie für eine solche Einstellung bevorzugen würden. Sie haben hochdimensionale Punkte und möchten Einfügungen vornehmen und Nachbarnachrichten abfragen.

Answer 1

Der Fluch der Dimensionalität hindert uns hier daran. Du könntest in Betracht ziehen, Principal Component Analysis (PCA) anzuwenden, um die Dimensionalität zu reduzieren, aber soweit ich weiß, hat niemand eine großartige Antwort darauf.

Ich habe mich mit diesem Problem bereits beschäftigt (in Audio- und Video-Fingerprinting), manchmal sogar mit bis zu 30 Dimensionen. Die Analyse ergab in der Regel, dass einige der Dimensionen keine relevanten Informationen für Suchvorgänge enthielten (eigentlich unscharfe Suchvorgänge, mein Hauptziel), also habe ich sie aus den Indexstrukturen ausgelassen, die für den Zugriff auf die Daten verwendet wurden, aber in der Logik zur Bestimmung von Übereinstimmungen aus einer Liste von Kandidaten, die während der Suche gefunden wurden, eingeschlossen. Dadurch wurde die Dimensionalität effektiv auf ein handhabbares Niveau reduziert.

Ich habe die Dinge weiter vereinfacht, indem ich die verbleibenden Dimensionen stark quantisiert habe, so dass der gesamte multidimensionale Raum in eine 32-Bit-Ganzzahl abgebildet wurde. Ich habe dies als Schlüssel in einer STL-Map (einem Rot-Schwarz-Baum) verwendet, obwohl ich auch eine Hashtabelle hätte verwenden können. Ich konnte Millionen von Datensätzen dynamisch zu einer solchen Struktur (natürlich basierend auf RAM) in etwa einer Minute oder zwei hinzufügen, und Suchvorgänge dauerten im Durchschnitt etwa eine Millisekunde, obwohl die Daten keineswegs gleichmäßig verteilt waren. Suchvorgänge erforderten eine sorgfältige Aufzählung von Werten in den Dimensionen, die in den 32-Bit-Schlüssel abgebildet waren, waren jedoch zuverlässig genug, um sie in einem kommerziellen Produkt zu verwenden. Ich glaube, dass es auch heute noch in iTunes Match verwendet wird, wenn meine Quellen stimmen. :)

Letztendlich empfehle ich Ihnen, sich Ihre Daten anzusehen und etwas Individuelles daraus zu machen, das Merkmale ausnutzt, um eine schnelle Indizierung und Suche zu ermöglichen. Finden Sie die Dimensionen, die am meisten variieren und am unabhängigsten voneinander sind. Quantisieren Sie diese und verwenden Sie sie als Schlüssel in einem Index. Jeder Eimer im Index enthält alle Elemente, die diesen Schlüssel teilen (wahrscheinlich mehr als einen). Um die nächsten Nachbarn zu finden, betrachten Sie "nahegelegene" Schlüssel und suchen Sie innerhalb jedes Eimers nach nahegelegenen Werten. Viel Glück.

p.s. Ich habe eine Arbeit über meine Technik verfasst, die hier verfügbar ist. Entschuldigen Sie die Paywall. Vielleicht können Sie anderswo eine kostenlose Kopie finden. Lassen Sie mich wissen, wenn Sie Fragen dazu haben.

Answer 2

Ein weiterer Datenstruktur, der mir einfällt, ist der Cover Tree. Im Gegensatz zu KD-Bäumen, die ursprünglich zur Beantwortung von Bereichsanfragen entwickelt wurden, ist diese Datenstruktur optimal für Anfragen nach nächsten Nachbarn. Sie wurde in n-Körper-Problemen verwendet, die die k nächsten Nachbarn aller Datenpunkte berechnen. Solche Probleme treten auch in Dichteschätzverfahren (Parzen-Fenster) auf. Ich kenne nicht genug über Ihr spezifisches Problem, aber ich weiß, dass es Online-Versionen dieser Datenstruktur gibt. Schauen Sie sich die Seite von Alexander Gray und diesen Link an

Answer 3

Wenn Sie einen Bucket Kd-Tree mit einer ziemlich großen Eimergröße verwenden, bekommt der Baum eine bessere Vorstellung davon, wo er aufteilen soll, wenn die Blätter zu voll werden. Die Leute in Robocode machen das unter extrem harten Zeitbeschränkungen, mit zufälligen Einfügungen, die direkt passieren, und kNN mit k>80, d>10 und n>30k in unter 1 ms. Schauen Sie sich dieses kD-Tree Tutorial an, das eine Menge kD-Tree-Verbesserungen erklärt und wie man sie implementiert.

Answer 4

In meiner Erfahrung ist 11-13 Dimensionen nicht zu schlecht - wenn Sie massenhaft laden. Sowohl massiv geladene R-Bäume (im Gegensatz zu k-d-Bäumen bleiben diese ausbalanciert!) als auch k-d-Bäume sollten immer noch viel besser funktionieren als lineares Scannen.

Sobald Sie vollständig dynamisch werden, sind meine Erfahrungen viel schlechter. Grob gesagt: Mit massenhaft geladenen Bäumen sehe ich 20-fache Geschwindigkeitssteigerungen, mit inkrementell aufgebauten R-Bäumen nur 7-fache. Es lohnt sich also tatsächlich, den Baum häufig neu aufzubauen. Und je nachdem, wie Sie Ihre Daten organisieren, kann es viel schneller sein, als Sie denken. Die massenhafte Beladung für den von mir verwendeten k-d-Baum beträgt O(n log n), und ich habe gelesen, dass es auch eine O(n log log n) Variante gibt. Mit einem niedrigen Konstantenfaktor. Für den R-Baum ist Sort-Tile-Recursive bisher die beste Massenbeladung, auch O(n log n) mit einem niedrigen Konstantenfaktor.

Also ja, bei hoher Dimensionalität würde ich in Betracht ziehen, den Baum von Zeit zu Zeit einfach neu zu laden.