Nächster Nachbar suchen - Nearest neighbor search

Nearest Neighbour Search ( NNS ), als eine Form der Näherungssuche , ist das Optimierungsproblem , den Punkt in einer gegebenen Menge zu finden, der einem gegebenen Punkt am nächsten (oder am ähnlichsten) ist. Nähe wird typischerweise in Form einer Unähnlichkeitsfunktion ausgedrückt: Je weniger ähnlich die Objekte, desto größer die Funktionswerte.

Formal sind die nächsten Nachbarn (NN) suchen Problem ist wie folgt definiert: ein Satz gegeben S von Punkten in einen Raum M und eine Abfrage Punkt q  ∈  M , den nächsten Punkt in finden S zu q . Donald Knuth in Bd. 3 von The Art of Computer Programming (1973) nannte es das Postamtsproblem und bezog sich auf einen Antrag, einem Wohnort das nächstgelegene Postamt zuzuweisen. Eine direkte Verallgemeinerung dieses Problems ist eine k -NN-Suche, bei der wir die k nächsten Punkte finden müssen.

Am häufigsten ist M ein metrischer Raum und Unähnlichkeit wird als Distanzmetrik ausgedrückt , die symmetrisch ist und die Dreiecksungleichung erfüllt . Noch üblicher wird M als der d- dimensionale Vektorraum angesehen, in dem die Unähnlichkeit unter Verwendung der euklidischen Distanz , der Manhattan-Distanz oder einer anderen Distanzmetrik gemessen wird . Die Unähnlichkeitsfunktion kann jedoch beliebig sein. Ein Beispiel ist die asymmetrische Bregman-Divergenz , für die die Dreiecksungleichung nicht gilt.

Anwendungen

Das Problem der Nächsten-Nachbarn-Suche tritt in zahlreichen Anwendungsgebieten auf, darunter:

Methoden

Es wurden verschiedene Lösungen für das NNS-Problem vorgeschlagen. Die Qualität und Nützlichkeit der Algorithmen werden durch die zeitliche Komplexität der Abfragen sowie die räumliche Komplexität eventuell zu pflegender Suchdatenstrukturen bestimmt. Die informelle Beobachtung, die gewöhnlich als Fluch der Dimensionalität bezeichnet wird, besagt, dass es keine universelle exakte Lösung für NNS im hochdimensionalen euklidischen Raum mit polynomialer Vorverarbeitung und polylogarithmischer Suchzeit gibt.

Genaue Methoden

Lineare Suche

Die einfachste Lösung für das NNS-Problem besteht darin, die Entfernung vom Abfragepunkt zu jedem anderen Punkt in der Datenbank zu berechnen und dabei den "bisher besten" zu verfolgen. Dieser Algorithmus, der manchmal als naiver Ansatz bezeichnet wird, hat eine Laufzeit von O ( dN ), wobei N die Kardinalität von S und d die Dimensionalität von M ist . Es müssen keine Suchdatenstrukturen verwaltet werden, sodass die lineare Suche über die Speicherung der Datenbank hinaus keine Raumkomplexität aufweist. Naive Suche kann im Durchschnitt Raumpartitionierungsansätze in höherdimensionalen Räumen übertreffen.

Raumaufteilung

Seit den 1970er Jahren wird die Branch-and-Bound- Methode auf das Problem angewendet. Im Fall des euklidischen Raums umfasst dieser Ansatz räumliche Index- oder räumliche Zugriffsmethoden. Zur Lösung des NNS-Problems wurden mehrere Raumaufteilungsverfahren entwickelt. Der vielleicht einfachste ist der kd-Baum , der den Suchraum iterativ in zwei Regionen halbiert, die die Hälfte der Punkte der Elternregion enthalten. Abfragen werden durch Durchlaufen des Baums von der Wurzel zu einem Blatt durchgeführt, indem der Abfragepunkt bei jeder Teilung ausgewertet wird. Abhängig von der in der Abfrage angegebenen Entfernung müssen möglicherweise auch benachbarte Zweige ausgewertet werden, die möglicherweise Treffer enthalten. Für eine Abfragezeit mit konstanter Dimension ist die durchschnittliche Komplexität im Fall von zufällig verteilten Punkten O (log  N ), die Komplexität im ungünstigsten Fall ist O ( kN ^(1-1/ k )) Alternativ wurde die R-Baum- Datenstruktur entworfen, um nächste . zu unterstützen Nachbarsuche im dynamischen Kontext, da sie effiziente Algorithmen für Einfügungen und Löschungen wie den R*-Baum hat . R-Bäume können nicht nur für die euklidische Distanz nächste Nachbarn ergeben, sondern können auch mit anderen Distanzen verwendet werden.

Im Fall des allgemeinen metrischen Raums ist der Branch-and-Bound-Ansatz als Metrikbaum- Ansatz bekannt. Besondere Beispiele sind vp-tree- und BK-tree- Methoden.

Unter Verwendung einer Menge von Punkten, die aus einem dreidimensionalen Raum entnommen und in einen BSP-Baum eingefügt werden , und einem aus demselben Raum entnommenen Abfragepunkt wird eine mögliche Lösung für das Problem des Findens des dem Abfragepunkt nächstgelegenen Punktwolkenpunkts gegeben in der folgenden Beschreibung eines Algorithmus. (Streng genommen kann es keinen solchen Punkt geben, da er möglicherweise nicht eindeutig ist. Aber in der Praxis kümmern wir uns normalerweise nur darum, einen der Teilmengen aller Punktwolkenpunkte zu finden, die in der kürzesten Entfernung zu einem bestimmten Abfragepunkt existieren. ) Die Idee ist, für jede Verzweigung des Baums zu schätzen, dass der nächste Punkt in der Wolke in dem Halbraum liegt, der den Abfragepunkt enthält. Dies mag nicht der Fall sein, aber es ist eine gute Heuristik. Nachdem Sie alle Mühen der Lösung des Problems für den geschätzten Halbraum rekursiv durchgearbeitet haben, vergleichen Sie nun die von diesem Ergebnis zurückgegebene Entfernung mit der kürzesten Entfernung vom Abfragepunkt zur Partitionierungsebene. Dieser letztere Abstand ist der zwischen dem Abfragepunkt und dem nächstmöglichen Punkt, der in dem nicht gesuchten Halbraum existieren könnte. Wenn dieser Abstand größer ist als der im vorherigen Ergebnis zurückgegebene, dann besteht offensichtlich keine Notwendigkeit, den anderen Halbraum zu durchsuchen. Wenn eine solche Notwendigkeit besteht, müssen Sie sich die Mühe machen, das Problem für den anderen Halbraum zu lösen, das Ergebnis mit dem vorherigen Ergebnis zu vergleichen und dann das richtige Ergebnis zurückzugeben. Die Leistung dieses Algorithmus liegt näher an der logarithmischen Zeit als an der linearen Zeit, wenn sich der Abfragepunkt in der Nähe der Wolke befindet, da der Algorithmus, wenn sich der Abstand zwischen dem Abfragepunkt und dem nächsten Punktwolkenpunkt Null nähert, nur eine Suche mit den Abfragepunkt als Schlüssel, um das richtige Ergebnis zu erhalten.

Näherungsmethoden

Ein angenäherter Suchalgorithmus für den nächsten Nachbarn darf Punkte zurückgeben, deren Entfernung von der Abfrage höchstens der Entfernung von der Abfrage zu ihren nächsten Punkten entspricht. Der Reiz dieses Ansatzes besteht darin, dass in vielen Fällen ein ungefährer nächster Nachbar fast so gut ist wie der genaue. Insbesondere wenn die Entfernungsmessung den Begriff der Benutzerqualität genau erfasst, sollten kleine Unterschiede in der Entfernung keine Rolle spielen.

Gierige Suche in Nachbarschaftsdiagrammen

Proximity-Graph-Verfahren (wie HNSW) gelten als aktueller Stand der Technik für die Approximation Nearest Neighbour Search.

Die Methoden basieren auf gierigem Traversieren in Proximity-Nachbarschaftsgraphen, in denen jeder Punkt eindeutig einem Knoten zugeordnet ist . Die Suche nach den nächsten Nachbarn einer Anfrage q in der Menge S erfolgt in Form einer Suche nach dem Knoten im Graphen . Der grundlegende Algorithmus – die gierige Suche – funktioniert wie folgt: Die Suche beginnt an einem Eingabepunkt-Scheitelpunkt, indem die Abstände von der Abfrage q zu jedem Scheitelpunkt seiner Umgebung berechnet werden, und findet dann einen Scheitelpunkt mit dem minimalen Abstandswert. Wenn der Abstandswert zwischen der Abfrage und dem ausgewählten Scheitelpunkt kleiner ist als der zwischen der Abfrage und dem aktuellen Element, bewegt sich der Algorithmus zum ausgewählten Scheitelpunkt und wird zum neuen Eingabepunkt. Der Algorithmus stoppt, wenn er ein lokales Minimum erreicht: einen Scheitelpunkt, dessen Umgebung keinen Scheitelpunkt enthält, der näher an der Abfrage liegt als der Scheitelpunkt selbst.

Die Idee von Proximity-Nachbarschaftsgraphen wurde in mehreren Veröffentlichungen genutzt, darunter in der wegweisenden Arbeit von Arya und Mount, im VoroNet-System für das Flugzeug, im RayNet-System für die , und in den Metrized Small World- und HNSW-Algorithmen für den allgemeinen Fall von Räume mit Abstandsfunktion. Diesen Arbeiten ging eine wegweisende Arbeit von Toussaint voraus, in der er das Konzept eines relativen Nachbarschaftsgraphen einführte .

Lokalitätssensitives Hashing

Locality Sensitive Hashing (LSH) ist eine Technik zum Gruppieren von Punkten im Raum in "Buckets", basierend auf einer Entfernungsmetrik, die auf die Punkte angewendet wird. Punkte, die unter der ausgewählten Metrik nahe beieinander liegen, werden mit hoher Wahrscheinlichkeit demselben Bucket zugeordnet.

Nächster-Nachbar-Suche in Räumen mit kleiner Eigendimension

Der Cover-Baum hat eine theoretische Schranke, die auf der Verdopplungskonstante des Datensatzes basiert . Die Suchzeitgrenze ist O ( c 12  log  n ), wobei c die Expansionskonstante des Datensatzes ist.

Projizierte radiale Suche

In dem speziellen Fall, in dem die Daten eine dichte 3D-Karte geometrischer Punkte sind, kann die Projektionsgeometrie der Erfassungstechnik verwendet werden, um das Suchproblem drastisch zu vereinfachen. Dieser Ansatz erfordert, dass die 3D-Daten durch eine Projektion auf ein zweidimensionales Gitter organisiert werden und nimmt an, dass die Daten mit Ausnahme der Objektgrenzen über benachbarte Gitterzellen hinweg räumlich glatt sind. Diese Annahmen gelten für den Umgang mit 3D-Sensordaten in Anwendungen wie Vermessung, Robotik und Stereovision, gelten jedoch möglicherweise nicht für unorganisierte Daten im Allgemeinen. In der Praxis hat diese Technik eine durchschnittliche Suchzeit von O ( 1 ) oder O ( K ) für das k- nächste Nachbarproblem, wenn sie auf reale Stereovisionsdaten angewendet wird.

Vektor-Approximationsdateien

In hochdimensionalen Räumen werden Baumindizierungsstrukturen nutzlos, da ein zunehmender Prozentsatz der Knoten ohnehin untersucht werden muss. Um die lineare Suche zu beschleunigen, wird eine komprimierte Version der im RAM gespeicherten Merkmalsvektoren verwendet, um die Datensätze in einem ersten Durchlauf vorzufiltern. Die endgültigen Kandidaten werden in einem zweiten Schritt unter Verwendung der unkomprimierten Daten von der Diskette zur Entfernungsberechnung bestimmt.

Komprimierungs-/Cluster-basierte Suche

Der VA-Datei-Ansatz ist ein Sonderfall einer komprimierungsbasierten Suche, bei der jede Merkmalskomponente einheitlich und unabhängig komprimiert wird. Die optimale Kompressionstechnik in mehrdimensionalen Räumen ist die Vektorquantisierung (VQ), implementiert durch Clustering. Die Datenbank wird geclustert und die "vielversprechendsten" Cluster werden abgerufen. Es wurden enorme Gewinne gegenüber VA-File, baumbasierten Indizes und sequentiellem Scan beobachtet. Beachten Sie auch die Parallelen zwischen Clustering und LSH.

Varianten

Es gibt zahlreiche Varianten des NNS-Problems und die beiden bekanntesten sind die k- nächste Nachbarsuche und die ε-näherungsweise nächste Nachbarsuche .

k -nächste Nachbarn

Die k- Nächste-Nachbar-Suche identifiziert die obersten k- nächsten Nachbarn der Abfrage. Diese Technik wird häufig in der Vorhersageanalyse verwendet , um einen Punkt basierend auf dem Konsens seiner Nachbarn zu schätzen oder zu klassifizieren. k- nächste Nachbargraphen sind Graphen, in denen jeder Punkt mit seinen k nächsten Nachbarn verbunden ist.

Ungefährer nächster Nachbar

Bei einigen Anwendungen kann es akzeptabel sein, eine "gute Schätzung" des nächsten Nachbarn abzurufen. In diesen Fällen können wir einen Algorithmus verwenden, der nicht garantiert, dass in jedem Fall der tatsächliche nächste Nachbar zurückgegeben wird, im Gegenzug für eine verbesserte Geschwindigkeit oder Speichereinsparungen. Oft findet ein solcher Algorithmus in den meisten Fällen den nächsten Nachbarn, dies hängt jedoch stark vom abgefragten Datensatz ab.

Algorithmen, die die ungefähre Suche nach nächstgelegenen Nachbarn unterstützen, umfassen ortsabhängiges Hashing , Best Bin First und eine Suche auf der Grundlage eines balancierten Kastenzerlegungsbaums .

Abstandsverhältnis des nächsten Nachbarn

Das Entfernungsverhältnis des nächsten Nachbarn wendet den Schwellenwert nicht auf die direkte Entfernung vom ursprünglichen Punkt zum Herausforderer-Nachbarn an, sondern auf ein Verhältnis davon abhängig von der Entfernung zum vorherigen Nachbarn. Es wird in CBIR verwendet , um Bilder durch eine "Abfrage nach Beispiel" abzurufen , wobei die Ähnlichkeit zwischen lokalen Merkmalen verwendet wird. Allgemeiner ist es an mehreren Übereinstimmungsproblemen beteiligt .

Fester Radius in der Nähe von Nachbarn

Fester Radius in der Nähe von Nachbarn ist das Problem, bei dem man alle Punkte im euklidischen Raum innerhalb einer gegebenen festen Entfernung von einem bestimmten Punkt effizient finden möchte . Die Entfernung wird als fest angenommen, aber der Abfragepunkt ist willkürlich.

Alle nächsten Nachbarn

Für einige Anwendungen (zB Entropieschätzung ) haben wir möglicherweise N Datenpunkte und möchten wissen, welcher der nächste Nachbar für jeden dieser N Punkte ist . Dies könnte natürlich durch einmaliges Ausführen einer Nächsten-Nachbar-Suche für jeden Punkt erreicht werden, aber eine verbesserte Strategie wäre ein Algorithmus, der die Informationsredundanz zwischen diesen N Abfragen ausnutzt , um eine effizientere Suche zu erzeugen. Als einfaches Beispiel: Wenn wir die Entfernung von Punkt X zu Punkt Y finden, sagt uns das auch die Entfernung von Punkt Y zu Punkt X , sodass dieselbe Berechnung in zwei verschiedenen Abfragen wiederverwendet werden kann.

Gegeben eine feste Dimension, eine semi-definite positive Norm (damit jede L p Norm eingeschlossen ) und n Punkte in diesem Raum, kann der nächste Nachbar jedes Punktes in O ( n  log  n ) Zeit und die m nächsten Nachbarn von gefunden werden jeder Punkt kann in O ( mn  log  n ) Zeit gefunden werden.

Siehe auch

Verweise

Zitate

Quellen

Weiterlesen

  • Shasha, Dennis (2004). Hochleistungserkennung in Zeitreihen . Berlin: Springer. ISBN 978-0-387-00857-8.

Externe Links

  • Nearest Neighbors and Similarity Search – eine Website für Lehrmaterialien, Software, Literatur, Forscher, offene Probleme und Veranstaltungen im Zusammenhang mit der NN-Suche. Gepflegt von Yury Lifshits
  • Ähnlichkeitssuche-Wiki – eine Sammlung von Links, Personen, Ideen, Schlüsselwörtern, Papieren, Folien, Code und Datensätzen zu den nächsten Nachbarn