KNN: 1-tetangga terdekat

9

Pertanyaan saya adalah tentang pengelompokan tetangga terdekat 1 dan tentang pernyataan yang dibuat dalam buku The Elements of Statistics Learning, karya Hastie, Tibshirani, dan Friedman. Pernyataannya adalah (hlm. 465, bagian 13.3):

"Karena hanya menggunakan titik pelatihan yang paling dekat dengan titik kueri, bias dari estimasi tetangga 1-terdekat sering rendah, tetapi variansnya tinggi."

Buku ini tersedia di
http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.html

Sebagai permulaan, kita dapat menentukan apa bias dan varians. Dari pertanyaan "bagaimana-dapat-meningkatkan-dimensi-meningkatkan-varians-tanpa-meningkatkan-bi-" , kita memiliki itu:

"Pertama-tama, bias dari classifier adalah perbedaan antara rata-rata estimasi dan fungsi sebenarnya, sedangkan varians dari classifier adalah perbedaan yang diharapkan dari fungsi prediksi estimasi dari nilai rata-rata (yaitu seberapa tergantung classifier pada acak pengambilan sampel dilakukan di set pelatihan).

Oleh karena itu, kehadiran bias menunjukkan sesuatu yang pada dasarnya salah dengan model, sedangkan varians juga buruk, tetapi model dengan varian tinggi setidaknya bisa memprediksi dengan baik rata-rata. "

Bisakah seseorang tolong jelaskan mengapa variansnya tinggi dan biasnya rendah untuk classifier tetangga 1-terdekat?

FredikLAa
sumber

Jawaban:

13

Biasnya rendah, karena Anda menyesuaikan model Anda hanya dengan titik 1-terdekat. Ini berarti model Anda akan sangat dekat dengan data pelatihan Anda.

Variansnya tinggi, karena mengoptimalkan hanya pada titik 1-terdekat berarti bahwa probabilitas Anda memodelkan noise dalam data Anda sangat tinggi. Mengikuti definisi Anda di atas, model Anda akan sangat bergantung pada subset poin data yang Anda pilih sebagai data pelatihan. Jika Anda secara acak mengubah titik data yang Anda pilih, modelnya akan sangat berbeda di setiap iterasi. Begitu

perbedaan yang diperkirakan dari fungsi prediksi yang diperkirakan dari nilai rata-rata (yaitu seberapa tergantung pengklasifikasi pada pengambilan sampel acak yang dibuat dalam rangkaian pelatihan)

akan tinggi, karena setiap kali model Anda akan berbeda.

Contoh Secara umum, model k-NN cocok dengan titik tertentu dalam data dengan N titik data terdekat di set pelatihan Anda. Untuk 1-NN titik ini hanya bergantung pada 1 titik lainnya. Misalnya Anda ingin membagi sampel Anda menjadi dua kelompok (klasifikasi) - merah dan biru. Jika Anda melatih model Anda untuk titik p tertentu yang 4 tetangga terdekat akan berwarna merah, biru, biru, biru (naik dengan jarak ke p). Kemudian 4-NN akan mengklasifikasikan titik Anda menjadi biru (3 kali biru dan 1 kali merah), tetapi model 1-NN Anda mengklasifikasikannya menjadi merah, karena merah adalah titik terdekat. Ini berarti, bahwa model Anda sangat dekat dengan data pelatihan Anda dan oleh karena itu biasnya rendah. Jika Anda menghitung RSS antara model Anda dan data pelatihan Anda mendekati 0. Berbeda dengan ini, varians dalam model Anda tinggi, karena model Anda sangat sensitif dan goyah. Seperti yang ditunjukkan di atas, pengacakan acak set latihan Anda kemungkinan akan mengubah model Anda secara dramatis. Sebaliknya, 10-NN akan lebih kuat dalam kasus tersebut, tetapi bisa menjadi kaku. K yang akan dipilih tergantung pada kumpulan data Anda. Ini sangat tergantung padaBias-Variance-Tradeoff , yang sebenarnya berkaitan dengan masalah ini.

Alex VII
sumber
Terima kasih @alexvii. Anda mengatakan bahwa untuk titik baru, pengklasifikasi ini akan menghasilkan titik baru yang "meniru" set tes dengan sangat baik. Dan jika set tes bagus, prediksi akan mendekati kebenaran, yang menghasilkan bias rendah? Benar? Atau apakah saya melewatkan sesuatu?
FredikLAa
Saya menambahkan beberapa informasi untuk menjelaskan maksud saya.
Alex VII
Satu hal lagi: Jika Anda menggunakan tiga tetangga terdekat dibandingkan dengan yang terdekat, tidakkah Anda akan lebih "yakin" bahwa Anda benar, dan tidak mengklasifikasikan pengamatan "baru" ke titik yang bisa "tidak konsisten" dengan poin lain , dan dengan demikian menurunkan bias?
FredikLAa
Ini dijelaskan dengan cukup baik pada halaman wikipedia di bawah titik K-tetangga terdekat hampir di akhir halaman.
Alex VII
11

Anda harus ingat bahwa 1-Nearest Neighbor classifier sebenarnya adalah model tetangga terdekat yang paling kompleks . Yang paling rumit, maksud saya, itu memiliki batas keputusan yang paling bergerigi, dan kemungkinan besar akan overfit. Jika Anda menggunakan N-terdekat tetangga classifier (N = jumlah poin pelatihan), Anda akan mengklasifikasikan semuanya sebagai kelas mayoritas. Permutasi yang berbeda dari data akan memberi Anda jawaban yang sama, memberi Anda satu set model yang memiliki nol varians (mereka semua persis sama), tetapi bias tinggi (mereka semua secara konsisten salah). Mengurangi pengaturan K membuat Anda lebih dekat dan lebih dekat ke data pelatihan (bias rendah), tetapi model akan jauh lebih tergantung pada contoh pelatihan khusus yang dipilih (varian tinggi).

Wang Nuklir
sumber
terima kasih @Matt. Satu pertanyaan: bagaimana Anda tahu bahwa bias adalah yang terendah untuk tetangga 1-terdekat? Bagaimana Anda tahu bahwa tidak menggunakan tiga tetangga terdekat akan lebih baik dalam hal bias?
FredikLAa
Bayangkan masalah kNN diskrit di mana kita memiliki jumlah data yang sangat besar yang sepenuhnya mencakup ruang sampel. Setiap titik uji dapat diklasifikasikan dengan benar dengan membandingkannya dengan tetangga terdekatnya, yang sebenarnya merupakan salinan dari titik uji. Bias adalah nol dalam hal ini. Jika kita menggunakan lebih banyak tetangga, kesalahan klasifikasi dimungkinkan, akibat dari bias meningkat. Contoh ini berlaku untuk ukuran set pelatihan yang sangat besar. Pada kenyataannya, dimungkinkan untuk mencapai bias yang lebih rendah secara eksperimental dengan beberapa tetangga, tetapi tren umum dengan banyak data adalah lebih sedikit tetangga -> bias lebih rendah.
Nuklir Wang
3

Berikut ini adalah posting blog yang sangat menarik tentang bias dan perbedaan. Bagian 3.1 membahas tentang algoritma knn dan menjelaskan mengapa k rendah menyebabkan variasi tinggi dan bias rendah.

Gambar 5 sangat menarik: Anda dapat melihat secara real time bagaimana model berubah saat k meningkat. Untuk k rendah, ada banyak overfitting (beberapa "pulau" terisolasi) yang mengarah ke bias rendah tetapi varians tinggi. Untuk k yang sangat tinggi, Anda memiliki model yang lebih halus dengan varian rendah tetapi bias tinggi. Dalam contoh ini, nilai k antara 10 dan 20 akan memberikan model keturunan yang cukup umum (varians yang relatif rendah) dan cukup akurat (bias yang relatif rendah).

Anil Narassiguin
sumber