kNN mit dynamischen Einfügungen im hochdunklen Raum

Question

Ich suche nach einer Methode, um den nächsten Nachbarn (hoffentlich O (log n)) für hochdimensionale Punkte (typischerweise ~ 11-13 dimensional) zu machen. Ich möchte, dass es sich beim Einfügen nach der Initialisierung der Struktur optimal verhält. KD-Tree kam mir in den Sinn, aber wenn Sie nicht Bulk-Laden tun, sondern dynamische Insertionen, dann kd Baum wird nicht mehr ausgeglichen und Afaik Balancing ist eine teure Operation.

Also wollte ich wissen, welche Datenstrukturen Sie für solche Einstellungen bevorzugen würden. Sie haben hochdimensionale Punkte und möchten Einfügungen vornehmen und nach dem nächsten Nachbarn suchen.

Answer 1

Die Curse of Dimensionality kommt hier in die Quere. Sie könnten in Erwägung ziehen, die Hauptkomponentenanalyse (PCA) anzuwenden, um die Dimensionalität zu reduzieren, aber soweit ich weiß, hat niemand eine großartige Antwort darauf.

Ich habe mit dieser Art von Problem vor (in Audio-und Video-Fingerabdruck), manchmal mit bis zu 30 Dimensionen behandelt. Die Analyse ergab normalerweise, dass einige der Dimensionen keine relevanten Informationen für die Suche enthielten (eigentlich unscharfe Suche, mein Hauptziel), also habe ich sie aus den Indexstrukturen weggelassen, um auf die Daten zuzugreifen, aber sie in die Logik einbezogen, um Übereinstimmungen von a zu bestimmen Liste der Kandidaten, die während der Suche gefunden wurden. Dies reduzierte effektiv die Dimensionalität auf ein kontrollierbares Niveau.

Ich vereinfachte die Dinge weiter, indem ich die verbleibenden Dimensionen stark quantisierte, so dass der gesamte multidimensionale Raum in eine 32-Bit-Ganzzahl abgebildet wurde. Ich benutzte dies als Schlüssel in einer STL-Map (ein rot-schwarzer Baum), obwohl ich eine Hash-Tabelle hätte verwenden können. Ich konnte in einer Minute oder zwei Millionen solcher Datensätze dynamisch zu einer solchen Struktur hinzufügen (RAM-basiert), und die Suche dauerte durchschnittlich etwa eine Millisekunde, obwohl die Daten keineswegs gleichmäßig verteilt waren. Die Suche erforderte eine sorgfältige Aufzählung der Werte in den Dimensionen, die dem 32-Bit-Schlüssel zugeordnet wurden. Sie waren jedoch so zuverlässig, dass sie in einem kommerziellen Produkt verwendet werden konnten. Ich glaube, dass es bis heute in iTunes Match verwendet wird, wenn meine Quellen korrekt sind. :)

Die Quintessenz ist, dass ich empfehle Ihnen einen Blick auf Ihre Daten und tun etwas Brauch, das Features nutzt es für die schnelle Indizierung und Suche. Finde die Dimensionen, die am meisten variieren und voneinander am meisten unabhängig sind. Quantisieren Sie diese und verwenden Sie sie als Schlüssel in einem Index. Jeder Bucket im Index enthält alle Elemente, die diesen Schlüssel gemeinsam haben (es wird wahrscheinlich mehr als einen geben). Um die nächsten Nachbarn zu finden, klicken Sie auf "nahe" Tasten und suchen Sie in jedem Bereich nach Werten in der Nähe. Viel Glück.

p.s. Ich schrieb ein Papier über meine Technik, verfügbar here. Entschuldigung wegen der Paywall. Vielleicht finden Sie eine kostenlose Kopie an anderer Stelle. Lass es mich wissen, wenn du Fragen dazu hast.

Answer 2

Eine andere Datenstruktur, die mir in den Sinn kommt, ist der Cover Tree. Im Gegensatz zu KD-Bäumen, die ursprünglich für die Beantwortung von Bereichsabfragen entwickelt wurden, ist diese Datenstruktur optimal für Abfragen am nächsten Nachbarn. Es wurde in n-Körper-Problemen verwendet, bei denen die k nächsten Nachbarn aller Datenpunkte berechnet werden. Solche Probleme treten auch bei Dichteschätzungsschemata (Parzen-Fenster) auf. Ich weiß nicht genug über Ihr spezifisches Problem, aber ich weiß, dass es Online-Versionen dieser Datenstruktur gibt. Schauen Sie sich Alexander Greys Seite an und diese link

Answer 3

Wenn Sie einen Bucket Kd-Tree mit einer ziemlich großen Bucket-Größe verwenden, kann der Baum eine bessere Vorstellung davon bekommen, wo er aufgeteilt werden soll, wenn die Blätter zu voll werden. Die Jungs in Robocode tun dies unter extrem harten Zeitbeschränkungen, mit zufälligen Einfügungen, die im Fluge passieren, und kNN mit k> 80, d> 10 und n> 30k in weniger als 1 ms. Schauen Sie sich diese kD-Tree Tutorial an, die eine Reihe von kD-Tree-Erweiterungen und deren Implementierung erklärt.

Answer 4

Meiner Erfahrung nach ist 11-13 Dimensionen nicht schlecht - wenn Sie in loser Schüttung. Sowohl in großen Mengen geladene R-Bäume (im Gegensatz zu k-d-Bäumen bleiben diese im Gleichgewicht!) Als auch in k-d-Bäumen sollte immer noch viel besser funktionieren als lineares Scannen.

Sobald Sie voll dynamisch gehen, sind meine Erfahrungen viel schlimmer. Grob gesagt: Bei Bäumen, die voll ausgelastet sind, sehe ich 20x Beschleunigungen, mit inkrementell gebauten R-Bäumen nur 7x. So ist es tut sich auszahlen, um den Baum häufig neu aufzubauen. Je nachdem, wie Sie Ihre Daten organisieren, ist dies möglicherweise viel schneller als Sie denken. Die Massenlast für den k-d-Baum, den ich verwende, ist O(n log n), und ich habe gelesen, dass es auch eine O(n log log n) Variante gibt. Mit einem niedrigen konstanten Faktor. Für den R-Baum ist Sort-Tile-Recursive die beste Massenlast, die ich bisher gesehen habe, und auch O(n log n) mit einem niedrigen konstanten Faktor.

Also ja, in Hochdimensionalität würde ich erwägen, den Baum von Zeit zu Zeit neu zu laden.