Kapan "Tetangga Terdekat" bermakna, hari ini?

Pada tahun 1999, Beyer et al. bertanya, Kapan "Tetangga Terdekat" bermakna?

Adakah cara yang lebih baik untuk menganalisis dan memvisualisasikan efek jarak rata pada pencarian NN sejak 1999?

Apakah set data yang diberikan memberikan jawaban yang berarti untuk masalah 1-NN? Masalah 10-NN? Masalah 100-NN?

Bagaimana Anda para pakar mendekati pertanyaan ini hari ini?

Suntingan Senin 24 Jan:

Bagaimana dengan "distance whiteout" sebagai nama yang lebih pendek untuk "distance flatness dengan meningkatnya dimensi"?

Cara mudah untuk melihat "jarak whiteout" adalah menjalankan 2-NN, dan plot jarak ke tetangga terdekat dan tetangga kedua terdekat. Plot di bawah ini menunjukkan dist ₁ dan dist ₂ untuk berbagai nclusters dan dimensi, oleh Monte Carlo. Contoh ini menunjukkan kontras jarak yang cukup baik untuk perbedaan absolut yang diskalakan | dist ₂ - dist ₁ | (Perbedaan relatif | dist ₂ / dist ₁ | → 1 sebagai dimensi → ∞, jadi menjadi tidak berguna.)

Apakah kesalahan absolut atau kesalahan relatif harus digunakan dalam konteks yang diberikan tentu saja tergantung pada noise "nyata" yang ada: sulit.

Saran: selalu jalankan 2-NN; 2 tetangga berguna saat mereka dekat, dan berguna saat tidak.

masukkan deskripsi gambar di sini

machine-learning k-nearest-neighbour denis
sumber

Beyer et al. tampaknya menangani aspek yang sedikit berbeda dari masalah NN. Tetapi, untuk tujuan klasifikasi (biner), dalam kondisi ringan, ini adalah hasil klasik bahwa klasifikasi 1-NN, dalam kasus terburuk , memiliki kemungkinan kesalahan klasifikasi Bayes (yaitu, optimal) dua kali lipat secara asimtotik. Dengan kata lain, tetangga terdekat pertama berisi "setidaknya setengah informasi" tentang label target seperti yang dilakukan oleh penggolong terbaik. Dalam hal ini, 1-NN tampaknya cukup relevan. (Lihat Sampul & Hart (1967) untuk lebih. Saya terkejut Beyer dkk. Tidak mengutipnya.)

kardinal

@ cardinal, Cover-Hart terikat tampaknya tidak bergantung pada dimensi sama sekali, seperti yang Anda katakan aspek yang berbeda?

denis

ya saya percaya ini benar dan ini, sebagian besar, poin saya dalam mengemukakannya. 1-NN tampaknya cukup relevan dalam arti itu, yaitu kenyataan bahwa ia bekerja (jadi) dengan baik (secara teoritis) secara seragam dalam dimensi ruang fitur tampaknya membantunya berdiri sendiri, terlepas dari apa perilaku terdekat dan tetangga terjauh adalah dalam ruang dimensi besar. Itu membuat saya bertanya-tanya apakah Beyer menyadari semua hasil (klasik) ini.

kardinal

@ cardinal Bagian atas halaman 24 di Cover and Hart terlihat seperti tempat di mana suatu masalah berpotensi muncul dalam pembuktiannya, pada langkah di mana Cover dan Hart berpendapat bahwa setiap RV x \ in X memiliki properti yang dimiliki setiap ruang terbuka tentang x memiliki ukuran tidak nol. Jika kita mempertimbangkan geometri hypersphere kita melihat bahwa volume interior hypersphere menyusut dengan meningkatnya dimensi sehingga, dalam batasnya, bola terbuka tentang x hanya berisi x dalam interiornya. Atau, melalui SLLN, RV iid x dalam ruang metrik X semua terletak di permukaan hypersphere dengan probabilitas satu.

Bob Durrant

Lihat juga metrik L1 atau L.5 untuk pengelompokan .

denis

Jawaban:

Saya tidak punya jawaban penuh untuk pertanyaan ini, tetapi saya bisa memberikan jawaban parsial pada beberapa aspek analitis. Peringatan: Saya telah mengerjakan masalah lain sejak makalah pertama di bawah ini, jadi sangat mungkin ada hal-hal baik di luar sana yang tidak saya sadari.

Pertama saya pikir perlu dicatat bahwa meskipun judul makalah mereka "Kapan` tetangga terdekat 'bermakna ", Beyer et al sebenarnya menjawab pertanyaan yang berbeda, yaitu kapan NN tidak bermakna. Kami membuktikan kebalikan dari teorema mereka, di bawah beberapa asumsi ringan tambahan pada ukuran sampel, di When Is 'Nearest Neighbor' Berarti: Teorema dan Implikasi Konversi. Journal of Complexity, 25 (4), Agustus 2009, hlm 385-397.dan menunjukkan bahwa ada situasi ketika (secara teori) konsentrasi jarak tidak akan muncul (kami memberikan contoh, tetapi pada dasarnya jumlah fitur non-noise perlu tumbuh dengan dimensi sehingga tentu saja mereka jarang muncul dalam praktik). Referensi 1 dan 7 yang dikutip dalam makalah kami memberikan beberapa contoh cara di mana konsentrasi jarak dapat dikurangi dalam praktik.

Sebuah makalah oleh atasan saya, Ata Kaban, melihat apakah masalah konsentrasi jarak ini tetap ada meskipun menerapkan teknik pengurangan dimensi dalam Kesadaran Konsentrasi Jarak Jauh pada Teknik Pengurangan Data Tertentu. Pengenalan Pola. Vol. 44, Edisi 2, Februari 2011, hal.265-277. . Ada beberapa diskusi yang bagus di sana juga.

$k$

Bob Durrant
sumber

Terima kasih Bob, +1. Pertanyaan terkait, apakah Anda memiliki aturan praktis untuk memilih nilai fraksional-metrik q (atau haruskah saya menanyakannya sebagai pertanyaan terpisah)?

denis

q = 1 / p

$q=1/p$

p > 1

$p>1$

p

$p$

l_{0}

$l_0$

p = 1

$p=1$

l_{1}

$l_{1}$

l_{q = 1 / p}

$l_{q=1/p}$

p > 1

$p>1$

p

$p$

\sum | a_{j} - b_{j} |^{q}

$\sum |a_j - b_j|^q$

1 / q

$1/q$

< q <

$< q <$

ℓ_{p}

$\ell_{p}$

Anda mungkin juga tertarik dengan analisis komponen lingkungan oleh Goldberger et al.

Di sini, transformasi linier dipelajari untuk memaksimalkan titik-titik yang diklasifikasikan dengan benar yang diharapkan melalui pemilihan lingkungan terdekat stokastik.

Sebagai efek samping, jumlah (yang diharapkan) dari tetangga ditentukan dari data.

bayerj
sumber

Terima kasih bayer. Tampaknya "pembelajaran metrik jarak" sedang booming - scholar.goo memiliki 50 judul sejak 2008. Tetapi apakah kertas booming, atau penggunaan nyata? Catatan kaki, kode untuk nca mengatakan "iterasi ... setidaknya 100000 untuk hasil yang baik". Catatan kaki 2, sebagian besar pekerjaan pada pembelajaran metrik jarak tampaknya memodelkan jarak Mahalanobis; apakah Anda tahu model jarak lain?

denis

Saya memiliki pengalaman berbeda dengan NCA - biasanya menyatu cukup cepat untuk saya. Checkout "pengurangan dimensi melalui pembelajaran pemetaan invarian" oleh LeCun dan "Minimal Loss Hashing untuk Compact Binary Codes" oleh Norouzi.

bayerj