Kapan saya harus bergerak melampaui k tetangga terdekat

Untuk banyak proyek pembelajaran mesin yang kami lakukan, kami mulai dengan pengklasifikasi k Nearest Neighbor. Ini adalah pengklasifikasi awal yang ideal karena kami biasanya memiliki waktu yang cukup untuk menghitung semua jarak dan jumlah parameter terbatas (k, metrik jarak, dan bobot)

Namun, ini sering memiliki efek bahwa kita tetap dengan classifier knn karena kemudian dalam proyek tidak ada ruang untuk beralih ke classifier lain. Apa yang menjadi alasan bagus untuk mencoba classifier baru. Yang jelas adalah ingatan dan batasan waktu, tetapi adakah kasus ketika classifier lain benar-benar dapat meningkatkan akurasi?

k-NN menggeneralisasi dalam arti yang sangat terbatas. Ini hanya menggunakan kelancaran prior (atau asumsi kontinuitas). Asumsi ini menyiratkan bahwa pola yang dekat dalam ruang fitur kemungkinan besar milik kelas yang sama. Tidak ada keteraturan fungsional dalam distribusi pola yang dapat dipulihkan oleh k-NN.

Dengan demikian, diperlukan sampel pelatihan yang representatif, yang bisa sangat besar terutama dalam kasus ruang fitur yang sangat dimensional. Lebih buruk lagi, sampel ini tidak tersedia. Akibatnya, ia tidak dapat mempelajari invarian. Jika pola dapat mengalami beberapa transformasi tanpa mengubah labelnya, dan sampel pelatihan tidak mengandung pola yang ditransformasikan dalam semua cara yang dapat diterima, k-NN tidak akan pernah mengenali pola transformasi yang tidak disajikan selama pelatihan. Ini benar, misalnya, untuk gambar yang digeser atau diputar, jika mereka tidak diwakili dalam beberapa bentuk invarian sebelum menjalankan k-NN. k-NN bahkan tidak bisa abstrak dari fitur yang tidak relevan.

Contoh lain yang agak artifisial adalah mengikuti. Bayangkan bahwa pola milik kelas yang berbeda didistribusikan secara berkala (misalnya sesuai dengan sinus - jika kurang dari 0, maka pola milik satu kelas, dan lebih besar, maka pola milik kelas lain). Set pelatihan terbatas. Jadi, itu akan berlokasi di wilayah yang terbatas. Di luar wilayah ini, kesalahan pengenalan adalah 50%. Orang dapat membayangkan regresi logistik dengan fungsi basis periodik yang akan berkinerja lebih baik dalam kasus ini. Metode lain akan dapat mempelajari keteraturan lainnya dalam distribusi pola dan memperkirakan dengan baik.

Jadi, jika seseorang menduga bahwa kumpulan data yang tersedia tidak representatif, dan invariansi terhadap beberapa transformasi pola harus dicapai, maka ini adalah kasusnya, di mana seseorang harus bergerak melampaui k-NN.

Jika Anda akan dibatasi oleh kompleksitas komputasi, pohon keputusan (Quinal, 1986) sulit dikalahkan (terutama ketika kerangka kerja menawarkan konversi langsung model DT ke banyak ifpernyataan - seperti Accord.NET ).

Untuk data dimensi tinggi, gagasan jarak, yang menjadi dasar k-NN menjadi tidak berharga (Kriegel, Kröger, Zimek, 2009) (juga: artikel Wikipedia ). Jadi pengklasifikasi lain, seperti SVM (Corter, Vapnik, 1995) atau Random Forests (Breiman, 2001) , mungkin berkinerja lebih baik.

Referensi:

• Kriegel, Hans-Peter; Kröger, Peer; Zimek, Arthur (2009), "Pengelompokan data dimensi tinggi: Sebuah survei tentang pengelompokan ruang, pengelompokan berbasis pola, dan pengelompokan korelasi", Transaksi ACM tentang Penemuan Pengetahuan dari Data (New York, NY: ACM) 3 (1): 1–58

• Cortes, Corinna; dan Vapnik, Vladimir N.; "Jaringan Dukungan-Vektor", Pembelajaran Mesin, 20, 1995

• Leo Breiman. 2001. Hutan Acak. Mach Belajar. 45, 1 (Oktober 2001), 5-32.

• JR Quinlan. 1986. Induksi Pohon Keputusan. Mach Belajar. 1, 1 (Maret 1986), 81-106.

kNN berguna untuk sampel data berukuran besar

Namun kelemahannya adalah:

1. Bias dengan nilai k.
2. Kompleksitas Komputasi
3. Batasan Memori
4. Menjadi algoritma malas belajar yang diawasi
5. Mudah tertipu oleh atribut yang tidak relevan.
6. Akurasi prediksi dapat dengan cepat menurun ketika jumlah atribut meningkat.

Biasanya hanya efektif jika data pelatihan besar, dan pelatihan sangat cepat.