Dalam Elemen Pembelajaran Statistik , masalah diperkenalkan untuk menyoroti masalah dengan k-nn dalam ruang dimensi tinggi. Ada titik data yang terdistribusi secara seragam dalam satuan bola -dimensi.p
Jarak median dari titik asal ke titik data terdekat diberikan oleh ekspresi:
Ketika , rumus memecah menjadi setengah jari-jari bola, dan saya bisa melihat bagaimana titik terdekat mendekati perbatasan sebagai , sehingga membuat intuisi di balik knn memecah dalam dimensi tinggi. Tapi saya tidak bisa mengerti mengapa formula ini bergantung pada N. Bisakah seseorang tolong klarifikasi?p → ∞
Juga buku ini membahas masalah ini lebih lanjut dengan menyatakan: "... prediksi jauh lebih sulit di dekat tepi sampel pelatihan. Seseorang harus memperkirakan dari titik sampel tetangga daripada interpolasi di antara mereka". Ini sepertinya pernyataan yang mendalam, tapi sepertinya saya tidak bisa memahami artinya. Adakah yang bisa menulis ulang?
sumber
Jawaban:
Volume hyperball dimensional dari jari-jari memiliki volume yang proporsional dengan .r r pp r rp
Jadi proporsi volume lebih dari jarak dari titik asal adalah .r p - ( k r ) pkr rp−(kr)prp=1−kp
Probabilitas bahwa semua poin yang dipilih secara acak lebih dari jarak dari asal adalah . Untuk mendapatkan jarak median ke titik acak terdekat, setel probabilitas ini sama dengan . Jadik r ( 1 - k p ) N 1N kr (1−kp)N (1-kp)N=112
Secara intuitif ini membuat semacam akal: poin lebih acak ada, semakin dekat Anda harapkan yang terdekat ke asal menjadi, sehingga Anda harus mengharapkan menjadi fungsi penurunan . Di sini adalah fungsi penurunan dari , jadi adalah fungsi yang meningkat dari , dan dengan demikian adalah suatu penurunan fungsi seperti yang akar th.N 2 1 / N N 1k N 21/N N N1-1121/N N Np1−121/N N p
sumber
Dan sekarang tanpa melambaikan tangan
Untuk setiap urutan iid rv's, mana adalah CDF umumF
Jadi jika kita memiliki iid mendistribusikan secara seragam dalam satuan bola dalam dimensi , maka di mana adalah CDF umum dari jarak, . Akhirnya, apa CDF, , untuk titik yang terdistribusi secara merata di bola unit dalam ? Probabilitas bahwa titik terletak pada bola jari-jari r di dalam bola jari-jari satuan sama dengan rasio volume:N Xi p
Demikian solusi untuk
adalah
Juga pertanyaan Anda tentang ketergantungan pada ukuran sampel, . Untuk fix, karena bola terisi lebih banyak poin, tentu saja jarak minimum ke titik asal harus lebih kecil.pN p
Akhirnya, ada sesuatu yang salah dalam rasio volume Anda. Sepertinya harus menjadi volume bola unit dalam .R pk Rp
sumber
Ringkas tetapi dalam kata-kata:
Kami ingin menemukan jarak median dari titik terdekat ke titik asal di titik terdistribusi seragam di bola pada titik asal jari-jari satuan dalam dimensi . Probabilitas bahwa jarak terkecil melebihi , (sebut ungkapan kuantitas ini [1]) adalah kekuatan dari probabilitas bahwa satu titik terdistribusi secara seragam melebihi , karena kemandirian statistik. Yang terakhir adalah satu dikurangi probabilitas bahwa titik terdistribusi tunggal yang seragam kurang dari . Yang terakhir adalah rasio volume bola jari-jari dengan bola jari-jari satuan, atau . Kita sekarang dapat menulis ekspresi [1] sebagaiN p r Nth r r r rp
Untuk menemukan median distribusi minimum jarak, atur probabilitas di atas menjadi dan selesaikan untuk , dapatkan jawabannya.1/2 r
sumber