Menghitung jarak ke k tetangga terdekat untuk semua titik di set

Untuk aplikasi pembelajaran mesin, kebutuhan kelompok saya untuk menghitung jarak Euclidean ke th tetangga terdekat di set untuk setiap (untuk antara 5 dan sekitar 100, dan beberapa ratus hingga beberapa juta). Kami saat ini menggunakan pendekatan brute force atau yang jelas dengan kd-tree pada $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$ , yang ketika tinggi dan relatif rendah tidak pernah menang. (Semuanya ada di memori.) $d$ $|X|$

Sepertinya harus ada cara yang lebih baik daripada brute-force, meskipun - setidaknya satu yang mengambil keuntungan dari ketimpangan segitiga, atau mungkin dengan hash yang sensitif terhadap lokalitas. Perkiraan yang cukup ketat juga berpotensi oke.

Penelitian yang saya dapat temukan tampaknya berfokus pada masalah menemukan tetangga terdekat tunggal (atau yang kira-kira terdekat). Apakah masalah yang saya cari menggunakan nama lain, atau apakah ada koneksi ke masalah terkait yang belum saya pikirkan?

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

kd-pohon mengambil keuntungan dari ketimpangan segitiga. Sudahkah Anda mencoba menggunakan pohon partisi data spasial lainnya? Hal lain yang mungkin Anda perhatikan (saya tidak tahu apa-apa tentang algoritma pembelajaran mesin Anda) apakah titik-titik tertentu cenderung memiliki struktur, yang mungkin membantu Anda dalam menemukan hyperplanes dengan cepat dan menggunakan yang ada di pohon mirip kd, bukannya median per performa biasa. mengoordinasikan pemisahan yang berkinerja buruk dalam dimensi tinggi.

Ross Snider

@RossSnider terima kasih atas sarannya. Dan tentu saja, pohon KD menggunakan ketimpangan segitiga, tapi saya memikirkan sesuatu yang akan lebih cepat daripada kekerasan. :) Apa jenis pohon partisi data spasial yang akan Anda rekomendasikan? Dari daftar Wikipedia, hanya vp-tree yang tampaknya berlaku, dan mereka sepertinya tidak lebih baik daripada kd-tree untuk jarak Euclidean. Dan saya akan memikirkan jika ada cara khusus masalah yang lebih baik untuk mendefinisikan hyperplanes yang terpisah, tetapi orang tidak terlintas dalam pikiran.

Dougal

X

$X$

k

$k$

k

$k$

Jawaban:

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

Singkatnya, beri saya struktur data cepat untuk menjawab pertanyaan tetangga terdekat, dan saya akan dengan senang hati memberi Anda struktur data cepat dari k-tetangga terdekat.

Sariel Har-Peled
sumber

k

$k$

O (k \log n)

$O(k \log n)$

Menggunakan kembali sampel itu rumit, karena dengan demikian Anda mengharuskan sampel tetap berfungsi untuk kueri APAPUN (kuantifikasi dibalik) sehingga probabilitasnya akan berubah. Gagasan umum kemudian akan membangun satu set sampel dengan ukuran lebih besar (ini tergantung pada # kueri) dan menggunakannya, jika itu masalah.

Suresh Venkat

@ SureshVenkat Ah, tentu saja. Saya akan duduk dan mencari tahu probabilitas yang sebenarnya. Terimakasih semuanya!

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$

Solusi perkiraan murah menggunakan "hash sensitif-lokalitas" adalah mengonversi setiap titik menjadi bentuk yang sedikit disisipkan:

[xxx, yyy, zzz] -> xyzxyzxyz

kemudian radix sort untuk preprocessing.

$k$ $2k$ $kth$

Lihat juga makalah ini oleh Callahan dan Kosaraju.

Chad Brewbaker
sumber