Ich habe n=10000 10-dimensionale Vektoren. Für jeden Vektor v1 möchte ich den Vektor v2 wissen, der den Winkel zwischen v1 und v2 minimiert.Den kleinsten Winkel zwischen Vektoren in logarithmischer Zeit finden
Gibt es eine Möglichkeit, dieses Problem schneller als O(n^2) zu lösen?
Sie können alle Vektoren in O (n) Zeit normalisieren und eine Parametrisierung von ihnen auf die resultierende 9-dimensionale Hypersphäre finden. Sie können dann eine räumliche Suchstruktur im n-1 dimensionalen Raum verwenden, ähnlich einem Kd-Baum, um die Nächste-Nachbar-Abfrage zu beschleunigen. Dafür gibt es bekannte Methoden (ANN).
Wie berechnen Sie Winkel für jeden Vektor (O (n)), dann sortieren Sie das Array basierend auf Winkel (O (nlogn)) und dann durch das Array (O (n)) der nächste Vektor ist entweder i +1 oder i-1.
Bearbeiten: Wie in den Kommentaren darauf hingewiesen, funktioniert dies nur in 2 Dimensionen.
Funktioniert das für mehr als 2 Dimensionen? – WhirlWind
Überhaupt nicht; In> 2 Dimensionen besteht das Äquivalent darin, die Dinge durch Einheitsvektoren zu ersetzen, was die Dimensionalität um eins verringert, aber immer noch zu hoch für eine ordentliche Anordnung lässt. –
Was Sie haben, ist im Wesentlichen das Problem der dichtesten Punkte auf einer Kugel (da der Winkel zwischen Vektoren ungefähr dem Abstand zwischen den Punkten auf der Kugel entspricht, auf der ihre Einheitsvektoren liegen) wahrscheinlich ist eine Art von Binärdatei (vielleicht wäre es ternär, um zu viele Randprobleme zu vermeiden) die Zerlegung der Raumpartitionierung.
Aber das wäre unangenehm zu codieren, und wahrscheinlich nicht viel schneller als die naive Methode für so wenig wie 10.000 Punkte (insbesondere beginnen Sie mit der Teilung der Punkte unter 3^10 = 59049 Boxen, obwohl die meisten davon wäre leer). Einhundert Millionen Zehn-Element-Dot-Produkte sollten gut unter einer Sekunde sein.
Wow. Zehndimensionale Vektoren? Was machst du mit denen?
Ich denke, ich würde damit beginnen, jeden Vektor auf Einheitslänge zu reduzieren - dh auf Punkte auf einer Hypersphäre - dann verwende einen "Nearest Neighbour Search" (NNS) Algorithmus wie kD Baum (k-Dimensional binary tree) , R-Baum, Best Bin zuerst, etc.
Es ist wahrscheinlich unmöglich, dieses Problem schneller als O (n log n) zu lösen, denn wenn Sie dieses Problem schneller lösen könnten, könnten Sie das einfachere "engste Paar" lösen von Punkten Problem "schneller als die aktuelle untere Grenze von O (n log n).
Wie Tom Womack darauf hingewiesen hat, wird der Brute-Force-O (n^2) -Algorithmus weniger tatsächliche Wanduhrzeit als diese ausgefeilteren Algorithmen für "kleine" Datenmengen benötigen und sieht wie "n = 10000 aus "ist relativ klein für 10 Dimensionen.
Ich hoffe, dass "10" binär ist ... –