Tetangga terdekat dalam data dimensi tinggi?

Saya telah mengajukan pertanyaan beberapa hari yang lalu tentang bagaimana menemukan tetangga terdekat untuk vektor yang diberikan. Vektor saya sekarang 21 dimensi dan sebelum saya melangkah lebih jauh, karena saya bukan dari domain Machine Learning atau Matematika, saya mulai bertanya pada diri sendiri beberapa pertanyaan mendasar:

• Apakah jarak Euclidean metrik yang baik untuk menemukan tetangga terdekat di tempat pertama? Jika tidak, apa opsi saya?
• Selain itu, bagaimana cara menentukan ambang batas yang tepat untuk menentukan tetangga k? Apakah ada beberapa analisis yang dapat dilakukan untuk mengetahui nilai ini?
• Sebelumnya, saya disarankan untuk menggunakan kd-Trees tetapi halaman Wikipedia dengan jelas mengatakan bahwa untuk dimensi tinggi, kd-Tree hampir setara dengan pencarian kasar. Dalam hal itu, apa cara terbaik untuk menemukan tetangga terdekat dalam sejuta titik dataset secara efisien?

Dapatkah seseorang tolong menjelaskan beberapa (atau semua) pertanyaan di atas?

Saat ini saya mempelajari masalah seperti itu - klasifikasi, pencarian tetangga terdekat - untuk pengambilan informasi musik.

Anda mungkin tertarik dengan algoritme Approximate Nearest Neighbor ( ANN ). Idenya adalah Anda mengizinkan algoritme untuk mengembalikan tetangga yang cukup dekat (mungkin bukan tetangga terdekat); dengan melakukan itu, Anda mengurangi kerumitan. Anda menyebutkan pohon kd ; itu adalah salah satu contohnya. Tapi seperti yang Anda katakan, pohon kd bekerja buruk di dimensi tinggi. Faktanya, semua teknik pengindeksan saat ini (berdasarkan partisi ruang) terdegradasi ke pencarian linear untuk dimensi yang cukup tinggi [1] [2] [3].

Di antara algoritma JST yang diusulkan baru-baru ini, mungkin yang paling populer adalah Locality-Sensitive Hashing ( LSH ), yang memetakan serangkaian titik dalam ruang dimensi tinggi ke dalam satu set tempat sampah, yaitu, tabel hash [1] [3]. Tetapi tidak seperti hash tradisional, hash yang peka terhadap tempat menempatkan titik terdekat ke tempat sampah yang sama.

LSH memiliki beberapa keuntungan besar. Pertama, itu sederhana. Anda cukup menghitung hash untuk semua poin di database Anda, lalu buat tabel hash dari mereka. Untuk kueri, hitung saja hash dari titik kueri, lalu ambil semua titik di nampan yang sama dari tabel hash.

Kedua, ada teori ketat yang mendukung kinerjanya. Dapat ditunjukkan bahwa waktu kueri adalah sublinear dalam ukuran database, yaitu, lebih cepat dari pencarian linear. Seberapa cepat tergantung pada seberapa banyak perkiraan yang bisa kita toleransi.

Akhirnya, LSH kompatibel dengan norma Lp untuk 0 < p <= 2. Oleh karena itu, untuk menjawab pertanyaan pertama Anda, Anda dapat menggunakan LSH dengan metrik jarak Euclidean, atau Anda dapat menggunakannya dengan metrik jarak Manhattan (L1). Ada juga varian untuk jarak Hamming dan kesamaan cosinus.

Tinjauan yang layak ditulis oleh Malcolm Slaney dan Michael Casey untuk IEEE Signal Processing Magazine pada 2008 [4].

LSH tampaknya telah diterapkan di mana-mana. Anda mungkin ingin mencobanya.

[1] Datar, Indyk, Immorlica, Mirrokni, "Skema Hashing Lokalitas-Sensitif Berdasarkan Distribusi p-Stable," 2004.

[2] Weber, Schek, Blott, "Sebuah analisis kuantitatif dan studi kinerja untuk metode pencarian kesamaan dalam ruang dimensi tinggi," 1998.

[3] Gionis, Indyk, Motwani, "Pencarian kesamaan dalam dimensi tinggi melalui hashing," 1999.

[4] Slaney, Casey, "hashing yang sensitif terhadap lokalitas untuk menemukan tetangga terdekat", 2008.

I. Metrik Jarak

Pertama, jumlah fitur (kolom) dalam kumpulan data bukan merupakan faktor dalam memilih metrik jarak untuk digunakan di kNN. Ada beberapa studi yang diterbitkan yang ditujukan untuk pertanyaan ini, dan dasar yang biasa untuk perbandingan adalah:

• distribusi statistik yang mendasari data Anda;

• hubungan di antara fitur-fitur yang terdiri dari data Anda (apakah mereka independen - yaitu, seperti apa bentuk matriks kovarians); dan

• ruang koordinat tempat data Anda diperoleh.

Jika Anda tidak memiliki pengetahuan sebelumnya tentang distribusi dari mana data Anda diambil sampelnya, setidaknya satu (didokumentasikan dengan baik dan menyeluruh) penelitian menyimpulkan bahwa jarak Euclidean adalah pilihan terbaik.

Metrik YEuclidean digunakan dalam Mesin Rekomendasi Web skala besar dan juga dalam penelitian akademik saat ini. Jarak yang dihitung oleh Euclidean memiliki makna intuitif dan skala perhitungan - yaitu, jarak Euclidean dihitung dengan cara yang sama, apakah dua titik berada dalam dua dimensi atau dalam ruang dua puluh dua dimensi.

Itu hanya gagal untuk saya beberapa kali, masing-masing kasus jarak Euclidean gagal karena sistem koordinat yang mendasari (cartesian) adalah pilihan yang buruk. Dan Anda biasanya akan mengenali ini karena misalnya panjang jalur (jarak) tidak lagi aditif - misalnya, ketika ruang metrik adalah papan catur, jarak Manhattan lebih baik daripada Euclidean, demikian juga ketika ruang metrik adalah Bumi dan jarak Anda trans penerbangan internasional, metrik jarak yang cocok untuk sistem koordinat kutub adalah ide yang baik (misalnya, London ke Wina adalah 2,5 jam, Wina ke St. Petersburg adalah 3 jam lagi, kurang lebih dalam arah yang sama, namun London ke St Petersburg bukan 5,5 jam, lebih dari 3 jam.)

Tetapi terlepas dari kasus-kasus di mana data Anda termasuk dalam sistem koordinat non-kartesius, pilihan metrik jarak biasanya tidak material. (Lihat posting blog ini dari seorang siswa CS, membandingkan beberapa metrik jarak dengan memeriksa efeknya pada pengklasifikasi kNN - chi square memberikan hasil terbaik, tetapi perbedaannya tidak besar; Studi yang lebih komprehensif ada di makalah akademis, Studi Banding Fungsi Jarak untuk Tetangga Terdekat - Mahalanobis (pada dasarnya Euclidean dinormalisasi dengan memperhitungkan kovarian dimensi) adalah yang terbaik dalam penelitian ini.

Satu syarat penting: agar perhitungan metrik jarak menjadi bermakna, Anda harus kembali skaladata Anda - jarang mungkin untuk membangun model kNN untuk menghasilkan prediksi yang akurat tanpa melakukan ini. Misalnya, jika Anda sedang membangun model kNN untuk memprediksi kinerja atletik, dan variabel harapan Anda adalah tinggi (cm), berat (kg), lemak tubuh (%), dan denyut nadi istirahat (denyut per menit), maka titik data tipikal mungkin Terlihat seperti ini: [180.4, 66.1, 11.3, 71]. Jelas perhitungan jarak akan didominasi oleh ketinggian, sedangkan kontribusi oleh bodyfat% akan hampir diabaikan. Dengan kata lain, jika sebaliknya, data dilaporkan secara berbeda, sehingga berat badan dalam gram daripada kilogram, maka nilai asli 86,1, akan menjadi 86.100, yang akan memiliki efek besar pada hasil Anda, yang persis seperti apa yang Anda lakukan. mau.

X_new = (X_old - mu) / sigma

II Struktur Data

Jika Anda khawatir tentang kinerja struktur kd-tree, A Voronoi Tessellation adalah wadah yang secara konsep sederhana namun secara drastis akan meningkatkan kinerja dan skala yang lebih baik daripada kd-Trees.

Ini bukan cara yang paling umum untuk mempertahankan data pelatihan kNN, meskipun penerapan VT untuk tujuan ini, serta keuntungan kinerja konsekuensinya, didokumentasikan dengan baik (lihat misalnya laporan Penelitian Microsoft ini ). Signifikansi praktis dari hal ini adalah bahwa, asalkan Anda menggunakan bahasa 'arus utama' (misalnya, dalam Indeks TIOBE ) maka Anda harus menemukan perpustakaan untuk melakukan VT. Saya tahu dengan Python dan R, ada beberapa opsi untuk setiap bahasa (misalnya, paket voronoi untuk R tersedia di CRAN )

Menggunakan VT untuk kNN bekerja seperti ini ::

Dari data Anda, pilih poin w secara acak - ini adalah pusat Voronoi Anda. Sel Voronoi merangkum semua titik tetangga yang terdekat dengan setiap pusat. Bayangkan jika Anda menetapkan warna yang berbeda untuk masing-masing pusat Voronoi, sehingga setiap titik yang ditugaskan ke pusat yang diberikan dicat warna itu. Selama Anda memiliki kepadatan yang cukup, melakukan ini akan dengan baik menunjukkan batas-batas masing-masing pusat Voronoi (sebagai batas yang memisahkan dua warna.

Bagaimana cara memilih Voronoi Center? Saya menggunakan dua pedoman ortogonal. Setelah memilih titik w secara acak, hitung VT untuk data pelatihan Anda. Selanjutnya periksa jumlah titik data yang ditetapkan untuk masing-masing pusat Voronoi - nilai-nilai ini harus hampir sama (diberikan kerapatan titik seragam di seluruh ruang data Anda). Dalam dua dimensi, ini akan menyebabkan VT dengan ubin dengan ukuran yang sama. Itulah aturan pertama, inilah yang kedua. Pilih w dengan iterasi - jalankan algoritma kNN Anda dengan w sebagai parameter variabel, dan ukur kinerja (waktu yang diperlukan untuk mengembalikan prediksi dengan menanyakan VT).

Jadi bayangkan Anda memiliki satu juta titik data ..... Jika titik-titik itu bertahan dalam struktur data 2D biasa, atau dalam kd-tree, Anda akan melakukan rata-rata beberapa juta perhitungan jarak untuk setiaptitik data baru yang variabel responsnya ingin Anda prediksi. Tentu saja, perhitungan tersebut dilakukan pada satu set data tunggal. Dengan V / T, pencarian tetangga terdekat dilakukan dalam dua langkah satu demi satu, terhadap dua populasi data yang berbeda - pertama melawan pusat Voronoi, kemudian setelah pusat terdekat ditemukan, titik-titik di dalam sel sesuai dengan pusat tersebut dicari untuk menemukan tetangga terdekat yang sebenarnya (dengan perhitungan jarak berurutan) Dikombinasikan, kedua pencarian ini jauh lebih cepat daripada pencarian dengan kekuatan kasar tunggal. Itu mudah dilihat: untuk 1M titik data, misalkan Anda memilih 250 pusat Voronoi untuk memeriksa ruang data Anda. Rata-rata, setiap sel Voronoi akan memiliki 4.000 poin data. Jadi alih-alih melakukan perhitungan rata-rata 500.000 jarak (brute force), Anda melakukan jauh lebih sedikit, rata-rata hanya 125 + 2.000.

AKU AKU AKU. Menghitung Hasil (variabel respons yang diprediksi)

Ada dua langkah untuk menghitung nilai prediksi dari serangkaian data pelatihan kNN. Yang pertama adalah mengidentifikasi n, atau jumlah tetangga terdekat yang digunakan untuk perhitungan ini. Yang kedua adalah bagaimana bobot kontribusi mereka terhadap nilai prediksi.

W / r / t komponen pertama, Anda dapat menentukan nilai terbaik dari n dengan menyelesaikan masalah optimasi (sangat mirip dengan optimasi kuadrat terkecil). Itulah teorinya; dalam praktiknya, kebanyakan orang hanya menggunakan n = 3. Bagaimanapun, sangat mudah untuk menjalankan algoritma kNN Anda di atas serangkaian contoh uji (untuk menghitung nilai prediksi) untuk n = 1, n = 2, n = 3, dll. Dan plot kesalahan sebagai fungsi dari n. Jika Anda hanya ingin nilai yang masuk akal untuk memulai, sekali lagi, gunakan saja n = 3.

Komponen kedua adalah bagaimana menghitung kontribusi masing-masing tetangga (dengan asumsi n> 1).

Teknik pembobotan yang paling sederhana adalah hanya mengalikan setiap tetangga dengan koefisien pembobotan, yang hanya 1 / (dist * K), atau kebalikan dari jarak dari tetangga itu ke contoh uji yang sering dikalikan dengan beberapa konstanta yang diturunkan secara empiris, K. I Saya bukan penggemar teknik ini karena sering kali lebih berat dari tetangga terdekat (dan secara bersamaan kurang berat yang lebih jauh); signifikansi ini adalah bahwa prediksi yang diberikan dapat hampir seluruhnya bergantung pada satu tetangga, yang pada gilirannya meningkatkan sensitivitas algoritma terhadap noise.

Fungsi pembobotan yang lebih baik, yang secara substansial menghindari batasan ini adalah fungsi gaussian , yang dalam python, terlihat seperti ini:

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

Untuk menghitung nilai prediksi menggunakan kode kNN Anda, Anda akan mengidentifikasi n tetangga terdekat ke titik data yang variabel responsnya ingin Anda prediksi ('test instance'), lalu panggil fungsi weight_gauss, satu kali untuk masing-masing n tetangga, lewat dalam jarak antara masing-masing tetangga titik uji. Fungsi ini akan mengembalikan berat untuk masing-masing tetangga, yang kemudian digunakan sebagai koefisien tetangga dalam perhitungan rata-rata tertimbang.

Apa yang Anda hadapi dikenal sebagai kutukan dimensi . Kadang-kadang berguna untuk menjalankan algoritma seperti PCA atau ICA untuk memastikan bahwa Anda benar-benar membutuhkan semua 21 dimensi dan mungkin menemukan transformasi linier yang akan memungkinkan Anda untuk menggunakan kurang dari 21 dengan kualitas hasil yang kira-kira sama.

Pembaruan: Saya menemukan mereka di sebuah buku berjudul Biomedical Signal Processing oleh Rangayyan (saya harap saya mengingatnya dengan benar). ICA bukan teknik sepele, tetapi dikembangkan oleh peneliti di Finlandia dan saya pikir kode Matlab untuk itu tersedia untuk umum untuk diunduh. PCA adalah teknik yang lebih banyak digunakan dan saya percaya Anda harus dapat menemukan R atau implementasi perangkat lunak lainnya. PCA dilakukan dengan menyelesaikan persamaan linear secara iteratif. Saya sudah melakukannya terlalu lama untuk mengingat bagaimana. =)

Idenya adalah bahwa Anda memecah sinyal Anda menjadi vektor eigen independen (fungsi eigen diskrit, sebenarnya) dan nilai eigennya, 21 dalam kasus Anda. Setiap nilai eigen menunjukkan jumlah kontribusi yang diberikan masing-masing fungsi eigen pada masing-masing pengukuran Anda. Jika nilai eigen kecil, Anda bisa sangat mewakili sinyal tanpa menggunakan fungsi eigen yang sesuai sama sekali, dan itulah cara Anda menyingkirkan dimensi.

Jawaban teratas baik tetapi lama, jadi saya ingin menambahkan jawaban 2016 .

Seperti yang dikatakan, dalam ruang berdimensi tinggi, kutukan dimensionalitas bersembunyi di sudut, membuat pendekatan tradisional, seperti pohon kd populer, menjadi selambat pendekatan brute force. Sebagai hasilnya, kami mengalihkan minat kami pada Perkiraan Penelusuran Tetangga Terdekat (JST) , yang mendukung akurasi, mempercepat proses. Anda mendapatkan perkiraan NN yang tepat, dengan propabilitas yang baik.

Topik hangat yang mungkin layak:

1. Pendekatan modern LSH , seperti Razenshteyn 's.
2. Hutan RKD : Hutan acak pohon kd (RKD), seperti yang dijelaskan dalam FLANN , atau dalam pendekatan yang lebih baru yang saya ikuti , kd-GeRaF .
3. LOPQ yang merupakan singkatan dari Kuantisasi Produk yang Dioptimalkan Secara Lokal, seperti dijelaskan di sini . Hal ini sangat mirip dengan yang baru Babenko + Lemptitsky ini pendekatan .

Anda juga dapat memeriksa jawaban saya yang relevan:

1. Dua set titik dimensi tinggi: Temukan tetangga terdekat di set lainnya
2. Perbandingan runtime permintaan Neighbor Terdekat pada struktur data yang berbeda
3. Implementasi PCL kd-tree sangat lambat

Untuk menjawab pertanyaan Anda satu per satu:

• Tidak, jarak euclidean adalah metrik buruk di ruang dimensi tinggi. Pada dasarnya dalam dimensi tinggi, titik data memiliki perbedaan besar antara satu sama lain. Itu mengurangi perbedaan relatif dalam jarak antara titik data yang diberikan dan tetangga terdekat dan terjauh.
• Banyak makalah / penelitian ada di data dimensi tinggi, tetapi sebagian besar barang membutuhkan banyak kecanggihan matematika.
• Pohon KD buruk untuk data dimensi tinggi ... menghindarinya dengan segala cara

Ini adalah kertas bagus untuk membantu Anda memulai ke arah yang benar. " Kapan di Nearest Neighbor bermakna ?" oleh Beyer et all.

Saya bekerja dengan data teks dimensi 20K ke atas. Jika Anda menginginkan saran terkait teks, saya mungkin dapat membantu Anda.

Kesamaan cosine adalah cara umum untuk membandingkan vektor dimensi tinggi. Perhatikan bahwa karena itu adalah kemiripan bukan jarak, Anda ingin memaksimalkannya bukan menguranginya. Anda juga dapat menggunakan cara khusus domain untuk membandingkan data, misalnya jika data Anda adalah sekuens DNA, Anda bisa menggunakan kesamaan urutan yang memperhitungkan probabilitas mutasi, dll.

Jumlah tetangga terdekat untuk digunakan bervariasi tergantung pada jenis data, seberapa banyak noise yang ada, dll. Tidak ada aturan umum, Anda hanya perlu menemukan yang terbaik untuk data dan masalah spesifik Anda dengan mencoba semua nilai dalam rentang . Orang-orang memiliki pemahaman intuitif bahwa semakin banyak data yang ada, semakin sedikit tetangga yang Anda butuhkan. Dalam situasi hipotetis di mana Anda memiliki semua data yang mungkin, Anda hanya perlu mencari tetangga terdekat untuk mengklasifikasikan.

Metode k Nearest Neighbor dikenal mahal secara komputasi. Itu salah satu alasan utama orang beralih ke algoritma lain seperti mesin vektor dukungan.

kd-tree memang tidak akan bekerja dengan baik pada data dimensi tinggi. Karena langkah pemangkasan tidak lagi banyak membantu, karena ujung terdekat - deviasi 1 dimensi - hampir selalu lebih kecil daripada deviasi dimensi penuh ke tetangga terdekat yang dikenal.

Tapi lebih jauh lagi, kd-tree hanya bekerja dengan baik dengan norma Lp untuk semua yang saya tahu, dan ada efek konsentrasi jarak yang membuat algoritma berbasis jarak menurun dengan meningkatnya dimensi.

Untuk informasi lebih lanjut, Anda mungkin ingin membaca tentang kutukan dimensi, dan berbagai variasinya (ada lebih dari satu sisi untuk itu!)

Saya tidak yakin ada banyak kegunaan untuk hanya membabi buta mendekati Euclidean tetangga terdekat misalnya menggunakan LSH atau proyeksi acak. Mungkin perlu untuk menggunakan fungsi jarak yang jauh lebih baik di tempat pertama!

Banyak tergantung pada mengapa Anda ingin tahu tetangga terdekat. Anda mungkin melihat ke dalam algoritma pergeseran rata-rata http://en.wikipedia.org/wiki/Mean-shift jika apa yang Anda inginkan adalah menemukan mode kumpulan data Anda.

Saya pikir cosinus pada tf-idf fitur boolean akan bekerja dengan baik untuk sebagian besar masalah. Itu karena heuristik yang sudah terbukti digunakan di banyak mesin pencari seperti Lucene. Jarak Euclidean dalam pengalaman saya menunjukkan hasil yang buruk untuk data seperti teks. Memilih bobot dan contoh-k yang berbeda dapat dilakukan dengan data pelatihan dan pemilihan parameter brute-force.

iDistance mungkin adalah yang terbaik untuk pengambilan knn yang tepat dalam data dimensi tinggi. Anda dapat melihatnya sebagai perkiraan penutupan Voronoi.

Saya pernah mengalami masalah yang sama dan bisa mengatakan yang berikut.

1. Jarak Euclidean adalah metrik jarak yang baik, namun secara komputasi lebih mahal daripada jarak Manhattan , dan terkadang menghasilkan hasil yang sedikit lebih buruk, jadi, saya akan memilih nanti.

2. Nilai k dapat ditemukan secara empiris. Anda dapat mencoba nilai yang berbeda dan memeriksa kurva ROC yang dihasilkan atau ukuran presisi / penarikan lainnya untuk menemukan nilai yang dapat diterima.

3. Baik jarak Euclidean dan Manhattan menghargai ketimpangan Segitiga , sehingga Anda dapat menggunakannya di pohon metrik. Memang, pohon-KD memiliki kinerja sangat terdegradasi ketika data memiliki lebih dari 10 dimensi (saya sendiri pernah mengalami masalah itu). Saya menemukan pohon VP menjadi pilihan yang lebih baik.

Pohon KD bekerja dengan baik untuk 21 dimensi, jika Anda berhenti lebih awal, setelah melihat katakanlah 5% dari semua poin. FLANN melakukan ini (dan speedup lainnya) untuk mencocokkan dengan vektor SIFT 128-dim. (Sayangnya FLANN hanya melakukan metrik Euclidean, dan scipy.spatial.cKDTree yang cepat dan solid hanya melakukan metrik Lp; ini mungkin atau mungkin tidak memadai untuk data Anda .) Tentu saja ada tradeoff kecepatan-akurasi di sini.

(Jika Anda dapat mendeskripsikan Ndata, Nquery, distribusi data Anda, yang mungkin membantu orang untuk mencoba data yang serupa.)

Ditambahkan 26 April, jalankan kali untuk cKDTree dengan cutoff pada ppc mac lama saya, untuk memberikan gagasan kelayakan yang sangat kasar:

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 %
3.5 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.253

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 %
15 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.245

Anda bisa mencoba kurva pesanan az. Mudah untuk 3 dimensi.

Apakah jarak Euclidean metrik yang baik untuk menemukan tetangga terdekat di tempat pertama? Jika tidak, apa opsi saya?

Saya akan menyarankan pengelompokan ruang bagian lunak , pendekatan yang cukup umum saat ini, di mana bobot fitur dihitung untuk menemukan dimensi yang paling relevan. Anda dapat menggunakan bobot ini saat menggunakan jarak euclidean, misalnya. Lihat kutukan dimensi untuk masalah umum dan juga artikel ini dapat menerangi Anda entah bagaimana:

Algoritma pengelompokan tipe k-means untuk pengelompokan ruang bagian dari kumpulan data numerik dan kategorikal