Metode Non-Parametrik Seperti K-Nearest-Neighbors di Ruang Fitur Dimensi Tinggi

Gagasan utama k-Nearest-Neighbor memperhitungkan titik terdekat dan memutuskan klasifikasi data berdasarkan suara terbanyak. Jika demikian, maka seharusnya tidak memiliki masalah dalam data dimensi yang lebih tinggi karena metode seperti hashing sensitif lokalitas dapat secara efisien menemukan tetangga terdekat. $k$

Selain itu, pemilihan fitur dengan jaringan Bayesian dapat mengurangi dimensi data dan membuat pembelajaran lebih mudah.

Namun, makalah ulasan oleh John Lafferty dalam pembelajaran statistik menunjukkan bahwa pembelajaran non-parametrik dalam ruang fitur dimensi tinggi masih merupakan tantangan dan belum terpecahkan.

Apa yang salah?

machine-learning artificial-intelligence Strin
sumber

Tolong beri referensi lengkap untuk kertas; penulis tampaknya tidak muncul (mencolok) di dalamnya.

Raphael

Jawaban:

Masalah ini dikenal sebagai kutukan dimensi . Pada dasarnya, ketika Anda meningkatkan jumlah dimensi, , titik-titik di ruang umumnya cenderung menjadi jauh dari semua titik lainnya. Ini membuat partisi ruang (seperti yang diperlukan untuk klasifikasi atau pengelompokan) sangat sulit. $d$

Anda dapat melihatnya sendiri dengan sangat mudah. Saya menghasilkan titik dimensi acak dalam unit hypercube pada 20 nilai dipilih secara merata dari . Untuk setiap nilai saya menghitung jarak dari titik pertama ke yang lainnya dan mengambil rata-rata jarak ini. Merencanakan ini, kita dapat melihat bahwa jarak rata-rata meningkat dengan dimensi meskipun ruang di mana kita menghasilkan titik di setiap dimensi tetap sama. $50$ $d$ $d$ $1..1000$ $d$

Jarak rata-rata vs. dimensi

Nick
sumber

Tentu saja. Anda meningkatkan jumlah titik dalam hypersphere jari-jari tetap secara eksponensial dalam dimensi, jadi jika Anda memilih 50 titik secara seragam secara acak, ini harus terjadi. Oleh karena itu, jika alasan Anda benar, partisi seharusnya menjadi mudah jika saya memiliki banyak sampel; Apakah begitu?

Raphael

Saya yakin Anda memilikinya terbalik. Dengan meningkatkan dimensi, saya MENGURANGI jumlah titik di dalam hypersphere. Partisi menjadi lebih sulit karena ukuran jarak pada dasarnya kehilangan maknanya (misalnya semuanya jauh).

Nick

k

$k$

N^{n}

$\mathbb{N}^n$

| N^{n} \cap S_{n} (k) |

$|\mathbb{N}^n \cap S_n(k)|$

n

$n$

n

$n$

d

$d$

n << d

$n << d$

Saya tidak melihat bahwa ini sesuai dengan definisi; tampaknya konvensi berdasarkan pengalaman.

Raphael

Bukan jawaban yang lengkap, tetapi halaman wikipedia yang Anda kutip menyatakan:

Keakuratan algoritma k-NN dapat sangat terdegradasi oleh kehadiran fitur yang bising atau tidak relevan, atau jika skala fitur tidak konsisten dengan kepentingannya.

Kemungkinan terjadinya peningkatan ini di hadapan ruang fitur dimensi tinggi.

Dave Clarke
sumber

Tapi saya pikir dengan PCA (analisis komponen utama) atau metode lain untuk mengurangi dimensi dan menghapus data yang tidak relevan, k-NN masih dapat berfungsi. Dan apa yang dimaksud dengan halaman wikipedia adalah k-NN naif akan gagal. Jadi ini tidak menjelaskan makalah tinjauan.

Strin

PCA pasti dapat bekerja, tetapi tidak dalam semua situasi.

Dave Clarke