Nächste-Nachbar-Suche

Die Nächste-Nachbarn-Suche ( NNS ) ist eine Form der Proximitätssuche und das Optimierungsproblem , denjenigen Punkt in einer gegebenen Menge zu finden, der einem gegebenen Punkt am nächsten (oder ähnlichsten) liegt. Die Nähe wird typischerweise durch eine Unähnlichkeitsfunktion ausgedrückt: Je unähnlicher die Objekte sind, desto größer sind die Funktionswerte.

Formal ist das Problem der Nächste-Nachbarn-Suche (NN-Suche) wie folgt definiert: Gegeben eine Menge S von Punkten in einem Raum M und ein Anfragepunkt q , finde den nächstgelegenen Punkt in S zu q . Donald Knuth nannte es in Band 3 von „The Art of Computer Programming “ (1973) das Poststellenproblem und bezog sich damit auf die Anwendung, einer Wohnadresse die nächstgelegene Poststelle zuzuordnen. Eine direkte Verallgemeinerung dieses Problems ist die k -NN-Suche, bei der die k nächstgelegenen Punkte gefunden werden müssen . ${\displaystyle q\in M}$

Üblicherweise ist M ein metrischer Raum , und die Unähnlichkeit wird als Distanzmetrik ausgedrückt , die symmetrisch ist und die Dreiecksungleichung erfüllt . Noch häufiger wird M als d -dimensionaler Vektorraum betrachtet, in dem die Unähnlichkeit mithilfe 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. ^{[ 1 ]}

Das Problem der Suche nach dem nächsten Nachbarn tritt in zahlreichen Anwendungsgebieten auf, darunter:

• Mustererkennung – insbesondere für die optische Zeichenerkennung
• Statistische Klassifizierung – siehe k-Nächste-Nachbarn-Algorithmus
• Computer Vision – für die Punktwolkenregistrierung ^{[ 2 ]}
• Computergeometrie – siehe Problem des nächstgelegenen Punktepaares
• Kryptoanalyse – für Gitterproblem ^{[ 3 ]}
• Datenbanken – z. B. inhaltsbasierte Bildsuche
• Codierungstheorie – siehe Maximum-Likelihood-Decodierung
• Semantische Suche
• Vektordatenbanken , bei denen die Suche nach dem nächsten Nachbarn über Einbettungen verwendet wird, um semantisch ähnliche Datensätze abzurufen.
• Retrieval-augmented generation systems, where nearest-neighbor retrieved over embeddings is used to get candidate passages or documents before generation ^{[ 4 ] [ 5 ].}
• Datenkomprimierung – siehe MPEG-2- Standard
• Robotische Sensorik ^{[ 6 ]}
• Empfehlungssysteme , siehe z. B. kollaboratives Filtern
• Internetmarketing – siehe kontextbezogene Werbung und verhaltensbasiertes Targeting
• DNA-Sequenzierung
• Rechtschreibprüfung – Vorschläge zur korrekten Schreibweise
• Plagiatserkennung
• Ähnlichkeitswerte zur Vorhersage von Karrierewegen professioneller Sportler.
• Clusteranalyse – Zuordnung einer Menge von Beobachtungen zu Teilmengen (Clustern), sodass Beobachtungen im selben Cluster in gewisser Hinsicht ähnlich sind, üblicherweise basierend auf der euklidischen Distanz.
• Chemische Ähnlichkeit
• Stichprobenbasierte Bewegungsplanung

Es wurden verschiedene Lösungsansätze für das NNS-Problem vorgeschlagen. Die Qualität und Nützlichkeit der Algorithmen hängen von der Zeitkomplexität der Anfragen sowie der Speicherkomplexität der zu verwaltenden Suchdatenstrukturen ab. Die informelle Beobachtung, die gemeinhin als „ Fluch der Dimensionalität“ bezeichnet wird , besagt, dass es keine universelle exakte Lösung für NNS im hochdimensionalen euklidischen Raum gibt, die polynomische Vorverarbeitung und polylogarithmische Suchzeit verwendet.

Die einfachste Lösung für das NNS-Problem besteht darin, die Distanz vom Suchpunkt zu jedem anderen Punkt in der Datenbank zu berechnen und den bisher besten Wert zu speichern. Dieser Algorithmus, auch als naiver Ansatz bezeichnet, hat eine Laufzeit von O(dN), wobei N die Kardinalität und d die Dimensionalität von S ist . Da keine Suchdatenstrukturen verwaltet werden müssen , benötigt die lineare Suche außer dem Speicherplatz der Datenbank keine zusätzliche Speicherkapazität. Die naive Suche kann im Durchschnitt raumpartitionierende Verfahren in höherdimensionalen Räumen übertreffen. ^{[ 7 ]}

Für den Distanzvergleich ist die absolute Distanz nicht erforderlich, sondern nur die relative. In geometrischen Koordinatensystemen lässt sich die Distanzberechnung erheblich beschleunigen, indem man die Quadratwurzelberechnung zwischen zwei Koordinaten weglässt. Der Distanzvergleich liefert dennoch identische Ergebnisse.

Seit den 1970er Jahren wird das Branch-and-Bound -Verfahren zur Lösung des Problems eingesetzt. Im euklidischen Raum umfasst dieser Ansatz räumliche Indexierungs- oder Zugriffsverfahren. Zur Lösung des NNS-Problems wurden verschiedene Raumpartitionierungsverfahren entwickelt. Das einfachste ist der kd-Baum , der den Suchraum iterativ in zwei Regionen unterteilt, die jeweils die Hälfte der Punkte der übergeordneten Region enthalten. Anfragen werden durch Traversierung des Baums von der Wurzel zu einem Blatt durchgeführt, wobei der Anfragepunkt bei jeder Teilung ausgewertet wird. Abhängig von der in der Anfrage angegebenen Distanz müssen gegebenenfalls auch benachbarte Zweige, die Treffer enthalten könnten, ausgewertet werden. Bei konstanter Dimension beträgt die durchschnittliche Komplexität O (log  N ) ^{[ 8 ]} , im Fall zufällig verteilter Punkte O ( kN ^(1-1/ k )) ^{[ 9 ].} Alternativ wurde die R-Baum -Datenstruktur entwickelt, um die Nächste-Nachbar-Suche in dynamischen Kontexten zu unterstützen, da sie effiziente Algorithmen für Einfügungen und Löschungen wie den R*-Baum bietet . ^{[ 10 ]} R-Bäume können die nächsten Nachbarn nicht nur für die euklidische Distanz liefern, sondern können auch mit anderen Distanzen verwendet werden.

Im Fall allgemeiner metrischer Räume wird das Branch-and-Bound-Verfahren als metrisches Baumverfahren bezeichnet . Beispiele hierfür sind das VP-Baum- und das BK-Baum- Verfahren.

Unter Verwendung einer Menge von Punkten aus einem dreidimensionalen Raum, die in einen BSP-Baum eingefügt werden , und eines gegebenen Anfragepunkts aus demselben Raum, wird in der folgenden Beschreibung eines Algorithmus eine mögliche Lösung für das Problem der Suche nach dem nächstgelegenen Punkt in der Punktwolke zum Anfragepunkt angegeben.

Streng genommen existiert ein solcher Punkt möglicherweise nicht, da er nicht eindeutig sein muss. In der Praxis geht es uns jedoch meist nur darum, einen der Punkte in der Punktwolke zu finden, die den kürzesten Abstand zu einem gegebenen Anfragepunkt haben. Die Idee ist, für jeden Zweig des Baums anzunehmen, dass der nächstgelegene Punkt in der Punktwolke in dem Halbraum liegt, der den Anfragepunkt enthält. Dies muss nicht der Fall sein, ist aber eine gute Heuristik. Nachdem das Problem für den angenommenen Halbraum rekursiv gelöst wurde, wird der so ermittelte Abstand mit dem kürzesten Abstand vom Anfragepunkt zur Partitionierungsebene verglichen. Dieser Abstand ist der zwischen dem Anfragepunkt und dem nächstgelegenen möglichen Punkt im noch nicht durchsuchten Halbraum. Ist dieser Abstand größer als der im vorherigen Ergebnis ermittelte, besteht offensichtlich keine Notwendigkeit, den anderen Halbraum zu durchsuchen. Besteht jedoch eine Notwendigkeit, muss das Problem für den anderen Halbraum gelöst, dessen Ergebnis mit dem vorherigen verglichen und das entsprechende Ergebnis zurückgegeben werden. Die Leistung dieses Algorithmus ist eher logarithmisch als linear, wenn sich der Abfragepunkt in der Nähe der Punktwolke befindet, denn wenn der Abstand zwischen dem Abfragepunkt und dem nächstgelegenen Punkt in der Punktwolke gegen Null geht, muss der Algorithmus nur noch eine Suche durchführen, bei der der Abfragepunkt als Schlüssel dient, um das richtige Ergebnis zu erhalten.

Ein approximativer Nächste-Nachbar-Suchalgorithmus darf Punkte zurückgeben, deren Abstand zur Anfrage höchstens das 1/2-fache des Abstands der Anfrage zu ihren nächsten Punkten beträgt. Der Vorteil dieses Ansatzes liegt darin, dass ein approximativer Nächster Nachbar in vielen Fällen fast genauso gut ist wie ein exakter. Insbesondere wenn das Abstandsmaß die Benutzerqualität präzise erfasst, sollten kleine Unterschiede im Abstand keine Rolle spielen. ^{[ 11 ]}${\displaystyle c}$

Proximity-Graph-Methoden (wie navigierbare Small-World-Graphen ^{[ 12 ]} und HNSW ^{[ 13 ] [ 14 ]} ) gelten als der aktuelle Stand der Technik für die approximative Suche nach nächsten Nachbarn.

Die Methoden basieren auf der gierigen Suche in Nachbarschaftsgraphen, in denen jedem Punkt ein eindeutiger Knoten zugeordnet ist . Die Suche nach den nächsten Nachbarn einer Anfrage q in der Menge S entspricht der Suche nach dem Knoten im Graphen . Der Basisalgorithmus – die gierige Suche – funktioniert wie folgt: Die Suche beginnt an einem Startknoten, indem die Distanzen der Anfrage q zu jedem Knoten seiner Nachbarschaft berechnet werden . Anschließend wird der Knoten mit der minimalen Distanz ermittelt. Ist die Distanz zwischen der Anfrage und dem ausgewählten Knoten kleiner als die Distanz zwischen der Anfrage und dem aktuellen Knoten, springt der Algorithmus zum ausgewählten Knoten, der dann zum neuen Startknoten wird. Der Algorithmus stoppt, sobald er ein lokales Minimum erreicht: einen Knoten, dessen Nachbarschaft keinen Knoten enthält, der näher an der Anfrage liegt als der Knoten selbst. ${\displaystyle G(V,E)}$${\displaystyle x_{i}\in S}$${\displaystyle v_{i}\in V}$${\displaystyle G(V,E)}$${\displaystyle v_{i}\in V}$${\displaystyle \{v_{j}:(v_{i},v_{j})\in E\}}$

Die Idee von Nachbarschaftsgraphen mit Nähe wurde in zahlreichen Publikationen genutzt, darunter die wegweisende Arbeit von Arya und Mount ^{[ 15 ]} , das VoroNet-System für die Ebene ^{[ 16 ]} , das RayNet-System für den Raum [ ^{17 ] sowie} die Algorithmen Navigable Small World ^{[ 12 ]} , Metrized Small World ^{[ 18 ]} und HNSW ^{[ 13 ] [ 14 ]} für den allgemeinen Fall von Räumen mit Distanzfunktion. Diesen Arbeiten ging eine Pionierarbeit von Toussaint voraus, in der er das Konzept eines relativen Nachbarschaftsgraphen einführte ^{[ 19 ]} .${\displaystyle \mathbb {E} ^{n}}$

Locality Sensitive Hashing (LSH) ist eine Technik zur Gruppierung von Punkten im Raum in „Buckets“ basierend auf einer Distanzmetrik, die auf die Punkte angewendet wird. Punkte, die gemäß der gewählten Metrik nahe beieinander liegen, werden mit hoher Wahrscheinlichkeit demselben Bucket zugeordnet. ^{[ 20 ]}

Der Überdeckungsbaum besitzt eine theoretische Schranke, die auf der Verdopplungskonstante des Datensatzes basiert . Die Suchzeit ist durch O ( c²  log  n ) begrenzt ^, wobei c die Expansionskonstante des Datensatzes ist.

Im Spezialfall dichter 3D-Karten geometrischer Punkte kann die Projektionsgeometrie des Sensorverfahrens die Suche erheblich vereinfachen. Dieser Ansatz setzt voraus, dass die 3D-Daten durch eine Projektion auf ein zweidimensionales Gitter organisiert sind und dass die Daten – mit Ausnahme von Objektgrenzen – zwischen benachbarten Gitterzellen räumlich glatt sind. Diese Annahmen sind bei 3D-Sensordaten in Anwendungen wie Vermessung, Robotik und Stereovision gültig, gelten aber möglicherweise nicht für unstrukturierte Daten im Allgemeinen. In der Praxis weist dieses Verfahren bei Anwendung auf reale Stereovisionsdaten eine durchschnittliche Suchzeit von O ( 1 ) bzw. O ( K ) für das k -nächste-Nachbarn-Problem auf. ^{[ 6 ]}

In hochdimensionalen Räumen werden Baumindizierungsstrukturen unbrauchbar, da ohnehin ein zunehmender Anteil der Knoten 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 mithilfe der unkomprimierten Daten von der Festplatte zur Distanzberechnung ermittelt. ^{[ 21 ]}

Der VA-File-Ansatz ist ein Spezialfall der kompressionsbasierten Suche, bei der jede Merkmalskomponente einheitlich und unabhängig komprimiert wird. Die optimale Komprimierungstechnik in mehrdimensionalen Räumen ist die Vektorquantisierung (VQ), implementiert durch Clustering. Die Datenbank wird geclustert und die vielversprechendsten Cluster werden ermittelt. Im Vergleich zu VA-File, baumbasierten Indizes und sequenziellen Scans wurden erhebliche Vorteile erzielt. ^{[ 22 ] [ 23 ]} Beachten Sie auch die Parallelen zwischen Clustering und LSH.

Es gibt zahlreiche Varianten des NNS-Problems, wobei die beiden bekanntesten die k -nächste-Nachbarn-Suche und die ε-approximative nächste-Nachbarn-Suche sind .

Die k -Nächste-Nachbarn-Suche ermittelt die k nächsten Nachbarn einer Suchanfrage. Dieses Verfahren wird häufig in der prädiktiven Analytik eingesetzt , um einen Punkt anhand des Konsens seiner Nachbarn zu bewerten oder zu klassifizieren. k -Nächste-Nachbarn-Graphen sind Graphen, in denen jeder Punkt mit seinen k nächsten Nachbarn verbunden ist

In manchen Anwendungen kann es ausreichend sein, eine gute Schätzung des nächsten Nachbarn zu erhalten. In solchen Fällen kann ein Algorithmus verwendet werden, der nicht garantiert, in jedem Fall den tatsächlichen nächsten Nachbarn zu finden, um dadurch die Geschwindigkeit zu erhöhen oder Speicherplatz zu sparen. Oft findet ein solcher Algorithmus in den meisten Fällen den nächsten Nachbarn, dies hängt jedoch stark vom abgefragten Datensatz ab.

Zu den Algorithmen, die die approximative Suche nach dem nächsten Nachbarn unterstützen, gehören Locality-Sensitive Hashing , Best Bin First und die Suche auf Basis eines balancierten Box-Decomposition-Baums . ^{[ 24 ]}

Das Nearest-Neighbor-Distanzverhältnis (NNR) verwendet nicht die direkte Distanz vom Ausgangspunkt zum nächsten Nachbarn als Schwellenwert, sondern ein Verhältnis dieser Distanz, das von der Distanz zum vorherigen Nachbarn abhängt. Es wird in der datenbankbasierten Bildsuche (CBIR) eingesetzt , um Bilder mittels „Beispielabfrage“ anhand der Ähnlichkeit lokaler Merkmale abzurufen. Allgemeiner findet es Anwendung in verschiedenen Matching- Problemen.

Bei der Suche nach nächsten Nachbarn mit festem Radius geht es darum, effizient alle Punkte im euklidischen Raum zu finden, die sich innerhalb eines vorgegebenen festen Abstands von einem bestimmten Punkt befinden. Der Abstand wird als fest angenommen, der gesuchte Punkt jedoch als beliebig.

Für manche Anwendungen (z. B. Entropieschätzung ) haben wir N Datenpunkte und möchten für jeden dieser N Punkte den nächsten Nachbarn ermitteln . Dies ließe sich natürlich erreichen, indem man für jeden Punkt eine Nächste-Nachbar-Suche durchführt. Eine verbesserte Strategie wäre jedoch ein Algorithmus, der die Informationsredundanz zwischen diesen N Anfragen nutzt, um eine effizientere Suche zu ermöglichen. Ein einfaches Beispiel: Wenn wir die Entfernung von Punkt X zu Punkt Y berechnen , erhalten wir gleichzeitig die Entfernung von Punkt Y zu Punkt X. Dieselbe Berechnung kann also in zwei verschiedenen Anfragen wiederverwendet werden.

Bei gegebener Dimension, einer semidefiniten positiven Norm (die jede L ^{^p} -Norm einschließt ) und n Punkten in diesem Raum kann der nächste Nachbar jedes Punktes in O ( n  log  n ) Zeit und die m nächsten Nachbarn jedes Punktes in O ( mn  log  n ) Zeit gefunden werden . ^{[ 25 ] [ 26 ]}

• Andrews, L. (November 2001). „Eine Vorlage für das Nächste-Nachbar-Problem“ . C/C++ Users Journal . 19 (11): 40–49 . ISSN  1075-2838 .
• Arya, S.; Mount, D. M .; Netanyahu, N. S .; Silverman, R .; Wu, A. Y. (1998). „Ein optimaler Algorithmus für die approximative Suche nach dem nächsten Nachbarn in festen Dimensionen“. Journal of the ACM . 45 (6): 891–923 . CiteSeerX  10.1.1.15.3125 . doi : 10.1145/293347.293348 . S2CID  8193729 .
• Beyer, K.; Goldstein, J.; Ramakrishnan, R.; Shaft, U. (1999). „Wann ist der nächste Nachbar sinnvoll?“. Proceedings of the 7th ICDT .
• Chen, Chung-Min; Ling, Yibei (2002). „Ein stichprobenbasierter Schätzer für Top-k-Anfragen“. ICDE : 617–627 .
• Samet, H. (2006). Grundlagen mehrdimensionaler und metrischer Datenstrukturen . Morgan Kaufmann. ISBN 978-0-12-369446-1Die
• Zezula, P.; Amato, G.; Dohnal, V.; Batko, M. (2006). Ähnlichkeitssuche – Der metrische Raumansatz . Springer. ISBN 978-0-387-29146-8Die

• Shasha, Dennis (2004). Hochleistungsfähige Zeitreihenanalyse . Berlin: Springer. ISBN 978-0-387-00857-8Die

• Nächste Nachbarn und Ähnlichkeitssuche – eine Website mit Lehrmaterialien, Software, Literatur, Forschern, offenen Problemen und Veranstaltungen zum Thema Nächste-Nachbarn-Suche. Betreut von Yury Lifshits.
• Similarity Search Wiki – eine Sammlung von Links, Personen, Ideen, Schlüsselwörtern, Artikeln, Präsentationen, Code und Datensätzen zu nächsten Nachbarn