Saya membaca buku Kevin Murphy: Machine Learning-A probabilistic Perspective. Dalam bab pertama penulis menjelaskan kutukan dimensi dan ada bagian yang saya tidak mengerti. Sebagai contoh, penulis menyatakan:
Pertimbangkan input didistribusikan secara seragam di sepanjang unit D-dimensi cube. Misalkan kita memperkirakan kepadatan label kelas dengan menumbuhkan hiper kubus di sekitar x sampai berisi fraksi diinginkan dari titik data. Panjang tepi yang diharapkan dari kubus ini adalah .
Ini adalah formula terakhir yang tidak bisa saya dapatkan. tampaknya jika Anda ingin menutup katakanlah 10% dari titik dari panjang tepi harus 0,1 sepanjang setiap dimensi? Saya tahu alasan saya salah, tetapi saya tidak mengerti mengapa.
self-study
k-nearest-neighbour
high-dimensional
pengguna42140
sumber
sumber
Jawaban:
Itulah perilaku tak terduga jarak dalam dimensi tinggi. Untuk 1 dimensi, Anda memiliki interval [0, 1]. 10% poin berada dalam segmen panjang 0,1. Tetapi apa yang terjadi ketika dimensi ruang fitur bertambah?
Ungkapan itu memberi tahu Anda bahwa jika Anda ingin memiliki 10% poin untuk 5 dimensi, Anda harus memiliki panjang untuk kubus 0,63, dalam 10 dimensi 0,79 dan 0,98 untuk 100 dimensi.
Seperti yang Anda lihat, untuk meningkatkan dimensi Anda perlu melihat lebih jauh untuk mendapatkan jumlah poin yang sama. Terlebih lagi, memberi tahu Anda bahwa sebagian besar titik berada di batas kubus karena jumlah dimensi meningkat. Yang tidak terduga.
sumber
Saya pikir hal utama yang perlu diperhatikan adalah ekspresi
benar-benar curam di awal. Ini berarti bahwa ukuran tepi yang Anda perlukan untuk mencakup fraksi tertentu dari volume akan meningkat secara drastis, khususnya di awal. yaitu tepi yang Anda butuhkan akan menjadi sangat besar ketika bertambah.D
Untuk membuatnya lebih jelas, ingat alur yang ditunjukkan Murphy:
jika Anda perhatikan, untuk nilai , kemiringannya sangat besar dan karenanya, fungsi tersebut tumbuh sangat curam di awal. Ini dapat lebih dihargai jika Anda mengambil turunan dari :e D ( f )D > 1 eD( f)
Karena kami hanya mempertimbangkan peningkatan dimensi (yaitu nilai integer), kami hanya memperhatikan nilai integer . Ini berarti . Pertimbangkan ekspresi tepi sebagai berikut:1 - D < 0D > 1 1 - D < 0
Pemberitahuan bahwa kami menaikkan ke daya kurang dari 0 (yaitu negatif). Ketika kita menaikkan angka ke kekuatan negatif kita pada suatu titik melakukan kebalikan (yaitu ). Melakukan kebalikan ke nomor yang sudah sangat kecil (ingat karena kami hanya mempertimbangkan sebagian kecil dari volume, karena kami melakukan KNN, yaitu data terdekat menunjukkan dari total ) berarti angka itu akan "menumbuhkan banyak ". Oleh karena itu, kita mendapatkan perilaku yang diinginkan, yaitu bahwa ketika meningkatkan daya menjadi lebih negatif dan karenanya, tepi yang dibutuhkan tumbuh banyak tergantung seberapa besar meningkatkan eksponen.x - 1 = 1f f<1kNDDx- 1= 1x f< 1 k N D D
(perhatikan bahwa tumbuh secara eksponensial dibandingkan dengan divisi yang dengan cepat menjadi tidak signifikan).f1 - D 1D
sumber
Ya, jadi jika Anda memiliki unit cube, atau dalam kasus Anda satu unit garis, dan data terdistribusi secara seragam maka Anda harus panjang 0,1 untuk menangkap 10% dari data. Sekarang ketika Anda meningkatkan dimensi, D meningkat, yang menghilangkan daya dan f menjadi kurang dari 1, akan meningkat, sehingga jika D pergi hingga tak terbatas Anda harus menangkap semua kubus, e = 1.
sumber
Saya pikir untuk jarak kNN memainkan peran yang lebih besar. Apa yang terjadi pada kubus (hiper) adalah analog dengan apa yang terjadi pada jarak antar titik. Ketika Anda meningkatkan jumlah dimensi, rasio antara jarak terdekat dengan jarak rata-rata tumbuh - ini berarti bahwa titik terdekat hampir sejauh dari titik rata-rata, maka itu hanya memiliki kekuatan prediksi sedikit lebih dari titik rata-rata. Artikel ini menjelaskannya dengan baik
sumber