Berurusan dengan ikatan, bobot dan pemungutan suara di kNN

Saya memprogram algoritma kNN dan ingin mengetahui yang berikut:

Tie-breaks:

1. Apa yang terjadi jika tidak ada pemenang yang jelas dalam pemungutan suara mayoritas? Misalnya semua k tetangga terdekat berasal dari kelas yang berbeda, atau untuk k = 4 ada 2 tetangga dari kelas A dan 2 tetangga dari kelas B?
2. Apa yang terjadi jika tidak mungkin menentukan dengan tepat k tetangga terdekat karena ada lebih banyak tetangga yang memiliki jarak yang sama? Misalnya untuk daftar jarak (x1;2), (x2;3.5), (x3;4.8), (x4;4.8), (x5;4.8), (x6;9.2)tidak mungkin untuk menentukan k = 3 atau k = 4 tetangga terdekat, karena tetangga ke-3 hingga ke-5 semuanya memiliki jarak yang sama.

Berat:

1. Saya membaca itu baik untuk menimbang k-tetangga terdekat sebelum memilih kelas yang menang. Bagaimana cara kerjanya? Yaitu bagaimana tetangga tertimbang dan bagaimana kemudian kelas ditentukan?

Alternatif suara mayoritas:

1. Apakah ada aturan / strategi lain untuk menentukan kelas pemenang selain suara terbanyak?

Cara ideal untuk mematahkan dasi untuk tetangga terdekat k dalam pandangan saya adalah mengurangi k dengan 1 sampai Anda telah memutuskan dasi. Ini akan selalu berfungsi terlepas dari skema penimbangan suara, karena dasi tidak mungkin ketika k = 1. Jika Anda ingin menambah k , menunggu skema penimbangan Anda dan jumlah kategori, Anda tidak akan dapat menjamin istirahat tie.

Ketika melakukan kNN, Anda perlu mengingat satu hal, yaitu bahwa itu bukan algoritma yang diturunkan secara matematis, melainkan pengelompokan / regressor sederhana berdasarkan satu intuisi - fungsi yang mendasarinya tidak banyak berubah ketika argumen tidak berubah banyak. Atau dengan kata lain fungsi yang mendasarinya adalah hampir konstan. Dengan asumsi ini, Anda dapat memperkirakan nilai fungsi yang mendasari di setiap titik tertentu, dengan rata-rata (mungkin tertimbang) dari nilai-nilai titik k terdekat.

Dengan mengingat hal ini, Anda dapat menyadari bahwa tidak ada keharusan yang jelas tentang apa yang harus dilakukan ketika tidak ada pemenang yang jelas dalam pemilihan suara mayoritas. Anda bisa selalu menggunakan k aneh, atau menggunakan bobot injeksi.

Dalam kasus tetangga 3 sampai 5 berada pada jarak yang sama dari tempat tujuan, Anda dapat menggunakan hanya dua, atau menggunakan semua 5. Sekali lagi, perlu diingat kNN bukan beberapa algoritma yang berasal dari analisis matematika yang kompleks, tetapi hanya sebuah intuisi sederhana. Terserah Anda bagaimana Anda ingin menangani kasus-kasus khusus itu.

$\frac{1}{||x-y||^2}$, atau lainnya yang relatif besar ketika jarak kecil, dan relatif kecil ketika jarak antara titik besar (jadi mungkin kebalikan dari beberapa fungsi metrik kontinu).

Ada juga makalah yang bagus oleh Samory Kpotufe dan Abdeslam Boularias tahun ini tentang NIPS yang membahas masalah menemukan bobot yang tepat. Intuisi umumnya, adalah bahwa fungsi yang mendasarinya bervariasi secara berbeda dalam arah yang berbeda (yaitu, turunan parsial yang berbeda memiliki besaran yang berbeda), oleh karena itu akan bijaksana untuk dalam beberapa hal mengubah metrik / pembobotan menurut intuisi ini. Mereka mengklaim trik ini umumnya meningkatkan kinerja kNN dan regresi kernel, dan saya pikir mereka bahkan memiliki beberapa hasil teoretis untuk mendukung klaim ini (walaupun saya tidak yakin apa yang sebenarnya diklaim oleh hasil teoritis itu, saya tidak punya waktu untuk pergi melalui seluruh kertas belum). Makalah ini dapat diunduh secara gratis dari situs mereka, atau setelah Googling "Bobot Gradien membantu Regresi Nonparametrik".

Sekarang, Anda mungkin ingin tahu bagaimana Anda bisa menemukan tindakan k, metrik, pembobotan, yang tepat untuk dilakukan ketika ada undian dan sebagainya. Yang menyedihkan adalah, bahwa pada dasarnya sulit untuk sampai pada hyperparameters yang tepat setelah beberapa pemikiran mendalam, Anda mungkin perlu menguji tandan yang berbeda dari hyperparameters dan melihat mana yang bekerja dengan baik pada beberapa set validasi. Jika Anda memiliki beberapa sumber daya komputasi, dan ingin tiba pada parameter yang tepat secara otomatis pada set hyperparameter yang baik, ada ide baru-baru ini (yang sangat saya sukai) untuk menggunakan proses Gaussian untuk optimasi bebas derivatif dalam pengaturan itu.

Biarkan saya menguraikan - menemukan set hyperparameters (yaitu, yang meminimalkan kesalahan pada data validasi), dapat dilihat sebagai masalah optimasi. Sayangnya, dalam pengaturan ini kita tidak bisa mendapatkan gradien dari fungsi yang kita coba optimalkan (yang biasanya ingin kita lakukan, untuk melakukan gradient descent atau beberapa metode yang lebih maju). Proses Gaussian dapat digunakan dalam pengaturan ini, untuk menemukan set hiperparameter, yang memiliki peluang besar, untuk berkinerja lebih baik daripada yang terbaik yang kami temukan sampai saat ini. Oleh karena itu Anda dapat menjalankan algoritma dengan iteratif dengan beberapa set hiperparameter, lalu tanyakan proses Gaussian mana yang terbaik untuk dicoba berikutnya, coba yang itu, dan seterusnya.

Untuk detailnya, lihat kertas "Optimalisasi Bayesian Praktis dari Algoritma Pembelajaran Mesin" oleh Jasper Snoek, Hugo Larochelle dan Ryan P Adams (juga dapat ditemukan di situs web mereka atau melalui Google).

Tentang bagian pengikatan ini, ide dasar terbaik untuk pengikatan biasanya adalah pemecahan acak, sehingga memilih kelas acak dari semua yang memenangkan pemungutan suara dan secara acak memilih subset objek terikat yang cukup besar untuk mengisi k.

Solusi semacam itu menekankan fakta bahwa itu adalah kasus patologis yang tidak memberikan informasi yang cukup untuk membuat keputusan dalam rezim kNN. BTW jika mereka umum untuk data Anda, mungkin Anda harus mencoba beberapa jarak yang lebih berbeda?

Salah satu cara yang mungkin adalah memiliki algoritma yang secara otomatis meningkat atau menurun hingga Anda mendapatkan pemenang yang jelas.