Berechnung der Entfernung zum k-ten nächsten Nachbarn für alle Punkte in der Menge

Für eine Anwendung zum maschinellen Lernen muss meine Gruppe den euklidischen Abstand zum ten nächsten Nachbarn in einer Menge für jedes (für zwischen 5 und etwa 100 und berechnen einige hundert bis einige Millionen). Wir verwenden derzeit entweder den Brute-Force- Ansatz oder den offensichtlichen mit einem kd-Baum auf $k$ $X$ $x \in (X \cup Y) \subset \mathbb R^d$ $d$ $|X| \approx |Y|$ $O(d \lvert X \rvert \lvert X \cup Y \rvert)$ $X$ , was, wenn hoch ist und ist relativ niedrig gewinnt nie. (Alles ist in Erinnerung.) $d$ $|X|$

Es scheint jedoch, dass es einen besseren Weg als Brute-Force geben muss - zumindest einen, der die Dreiecksungleichheit ausnutzt, oder vielleicht mit lokalitätssensitiven Hashes. Eine einigermaßen enge Annäherung ist möglicherweise auch in Ordnung.

Die Forschung, die ich finden konnte, scheint sich auf das Problem zu konzentrieren, den nächsten Nachbarn (oder einen, der ungefähr am nächsten ist) zu finden. Hat das gesuchte Problem einen anderen Namen oder besteht eine Verbindung zu einem verwandten Problem, an das ich nicht gedacht habe?

reference-request cg.comp-geom near-neighbors Dougal
quelle

kd-Bäume nutzen die Dreiecksungleichung aus. Haben Sie versucht, andere räumliche Datenpartitionierungsbäume zu verwenden? Eine andere Sache, die Sie untersuchen könnten (ich weiß nichts über Ihren Algorithmus für maschinelles Lernen), ob die spezifischen Punkte tendenziell strukturiert sind, was Ihnen helfen könnte, Hyperebenen schnell zu finden und diese in einem kd-ähnlichen Baum anstelle des üblichen Medianwerts zu verwenden Koordinatenteilung, die in hohen Dimensionen schlecht funktioniert.

Ross Snider

@ RossSnider danke für die Vorschläge. Natürlich verwenden KD-Bäume die Dreiecksungleichung, aber ich dachte an etwas, das schneller als rohe Gewalt wäre. :) Welche anderen Arten von Geodaten-Partitionierungsbäumen würden Sie empfehlen? Von der Wikipedia-Liste scheinen nur vp-Bäume anwendbar zu sein, und sie scheinen nicht besser zu sein als kd-Bäume für die euklidische Entfernung. Und ich werde darüber nachdenken, ob es einen besseren problemspezifischen Weg gibt, trennende Hyperebenen zu definieren, aber einer fällt mir nicht ein.

Dougal

X

$X$

k

$k$

k

$k$

Antworten:

$O(k \log n)$ $O( k \log n)$

Kurz gesagt, geben Sie mir eine schnelle Datenstruktur für die Beantwortung von Fragen zum nächsten Nachbarn, und ich würde Ihnen gerne eine schnelle Datenstruktur zum k-nächsten Nachbarn geben.

Sariel Har-Peled
quelle

k

$k$

O (k \log n)

$O(k \log n)$

Die Wiederverwendung der Stichproben ist schwierig, da Sie dann verlangen, dass eine feste Stichprobe für JEDE Abfrage funktioniert (die Quantifizierung wird umgedreht), sodass sich die Wahrscheinlichkeiten ändern würden. Die allgemeine Idee wäre dann, eine Reihe von Stichproben größerer Größe zu erstellen (dies hängt von den # Abfragen ab) und sie zu verwenden, wenn dies ein Problem darstellt.

Suresh Venkat

@ SureshVenkat Ah, natürlich. Ich werde mich hinsetzen und die tatsächlichen Wahrscheinlichkeiten herausfinden. Vielen Dank an alle!

Dougal

O (k \log (1 / δ))

$O( k \log (1/\delta))$

\geq 1 - δ

$\geq 1-\delta$

O (k \log n)

$O(k \log n)$

O (n / k)

$O( n/k)$

k

$k$

Eine billige ungefähre Lösung unter Verwendung eines "lokalitätssensitiven Hash" wäre, jeden Punkt in seine bitverschachtelte Form umzuwandeln:

[xxx, yyy, zzz] -> xyzxyzxyz

dann Radix-Sortierung für die Vorverarbeitung.

$k$ $2k$ $kth$

Siehe auch dieses Papier von Callahan und Kosaraju.

Chad Brewbaker
quelle