Apa algoritma k-tetangga terdekat (KNN)?

Meskipun algoritma KNN dapat digunakan untuk masalah regresi atau klasifikasi, algoritma ini biasanya digunakan sebagai algoritma klasifikasi, dengan asumsi bahwa titik-titik yang serupa dapat ditemukan berdekatan satu sama lain.

Untuk masalah klasifikasi, label kelas ditetapkan berdasarkan suara terbanyak—yaitu label yang paling sering diwakili di sekitar titik data yang diberikan. Meskipun secara teknis dianggap sebagai “pemungutan suara pluralitas”, istilah “suara mayoritas” lebih umum digunakan dalam literatur. Perbedaan antara kedua terminologi ini adalah bahwa “pemungutan suara mayoritas” secara teknis membutuhkan mayoritas lebih dari 50%, yang terutama berlaku jika hanya ada dua kategori. Ketika Anda memiliki beberapa kelas—mis. empat kategori, Anda tidak membutuhkan 50% suara untuk membuat kesimpulan tentang sebuah kelas; Anda dapat memberikan label kelas dengan suara lebih besar dari 25%. University of Wisconsin-Madison merangkum ini dengan baik dengan contoh di sini.

Masalah regresi menggunakan konsep yang mirip dengan masalah klasifikasi, tetapi dalam kasus ini, rata-rata dari k tetangga terdekat diambil untuk membuat prediksi tentang klasifikasi. Perbedaan utama di sini adalah bahwa klasifikasi digunakan untuk nilai diskrit, sedangkan regresi digunakan untuk nilai kontinu. Namun, sebelum klasifikasi dapat dibuat, jarak harus ditentukan. Jarak Euclidean adalah yang paling umum digunakan, yang akan kita bahas lebih lanjut di bawah ini.

Perlu juga dicatat bahwa algoritma KNN juga merupakan bagian dari keluarga model “pembelajaran malas“, yang berarti bahwa algoritma ini hanya menyimpan kumpulan data pelatihan dan bukan menjalani tahap pelatihan. Ini juga berarti bahwa semua perhitungan terjadi ketika klasifikasi atau prediksi dibuat. Karena metode ini sangat bergantung pada memori untuk menyimpan semua data pelatihannya, metode ini juga disebut sebagai metode pembelajaran berbasis contoh atau berbasis memori.

Evelyn Fix dan Joseph Hodges dikreditkan dengan ide-ide awal seputar model KNN dalam makalah tahun 1951 ini sementara Thomas Cover memperluas konsep mereka dalam penelitiannya, “Klasifikasi Pola Tetangga Terdekat.” Meskipun tidak sepopuler dulu, algoritma ini masih menjadi salah satu algoritma pertama yang dipelajari dalam ilmu data karena kesederhanaan dan keakuratannya. Namun, seiring bertambahnya kumpulan data, KNN menjadi semakin tidak efisien, mengorbankan kinerja model secara keseluruhan. Ini sering digunakan untuk sistem rekomendasi sederhana, pengenalan pola, penggalian data, prediksi pasar keuangan, deteksi intrusi, dan lain-lain.

Singkatnya, tujuan dari algoritma k-tetangga terdekat adalah untuk mengidentifikasi tetangga terdekat dari titik kueri tertentu, sehingga kita dapat menetapkan label kelas ke titik itu. Untuk melakukan ini, KNN memiliki beberapa persyaratan:

Untuk menentukan titik data mana yang paling dekat dengan titik kueri yang diberikan, jarak antara titik kueri dan titik data lainnya perlu dihitung. Metrik jarak ini membantu membentuk batas keputusan, yang mempartisi titik kueri ke wilayah yang berbeda. Anda biasanya akan melihat batas-batas keputusan yang divisualisasikan dengan diagram Voronoi.

Meskipun ada beberapa ukuran jarak yang dapat Anda pilih, artikel ini hanya akan mencakup hal-hal berikut:

Jarak Euclidean (p=2): Ini adalah ukuran jarak yang paling umum digunakan, dan terbatas pada vektor bernilai riil. Dengan menggunakan rumus di bawah ini, ia mengukur garis lurus antara titik kueri dan titik lain yang diukur.

Jarak Manhattan (p = 1): Ini juga merupakan metrik jarak populer lainnya, yang mengukur nilai absolut antara dua titik. Jarak ini juga disebut sebagai jarak taksi atau jarak blok kota karena biasanya divisualisasikan dengan kisi-kisi, yang mengilustrasikan bagaimana seseorang dapat menavigasi dari satu alamat ke alamat lainnya melalui jalan-jalan kota.

Jarak Minkowski: Ukuran jarak ini adalah bentuk umum dari metrik jarak Euclidean dan Manhattan. Parameter, p, dalam rumus di bawah ini, memungkinkan pembuatan metrik jarak lainnya. Jarak Euclidean diwakili oleh rumus ini ketika p sama dengan dua, dan jarak Manhattan dilambangkan dengan p sama dengan satu.

Jarak Hamming: Teknik ini biasanya digunakan dengan vektor Boolean atau vektor string, untuk mengidentifikasi titik-titik di mana vektor tidak cocok. Akibatnya, ini juga disebut sebagai metrik tumpang tindih. Ini dapat direpresentasikan dengan rumus berikut:

Sebagai contoh, jika Anda memiliki senar berikut, jarak hamming akan menjadi 2 karena hanya dua nilainya yang berbeda.

Nilai k dalam algoritma k-NN menentukan berapa banyak tetangga yang akan diperiksa untuk menentukan klasifikasi titik kueri tertentu. Misalnya, jika k=1, instance akan ditetapkan ke kelas yang sama dengan tetangga terdekat tunggalnya.

Mendefinisikan k dapat menjadi tindakan penyeimbangan karena nilai yang berbeda dapat menyebabkan overfitting atau underfitting. Nilai k yang lebih rendah dapat memiliki varians tinggi, tetapi bias rendah, dan nilai k yang lebih besar dapat menyebabkan bias tinggi dan varians yang lebih rendah. Pilihan k akan sangat bergantung pada data input karena data dengan lebih banyak outlier atau noise kemungkinan akan berkinerja lebih baik dengan nilai k yang lebih tinggi. Secara keseluruhan, disarankan untuk memiliki angka ganjil untuk k untuk menghindari ikatan dalam klasifikasi, dan taktik validasi silang dapat membantu Anda memilih k yang optimal untuk kumpulan data Anda.

Untuk mempelajari lebih dalam, Anda dapat mempelajari lebih lanjut tentang algoritma k-NN dengan menggunakan Python dan scikit-learn (juga dikenal sebagai sklearn). Tutorial di Watson Studio kami membantu Anda memahami sintaks dasar dari perpustakaan ini, yang juga mengandung beberapa pustaka populer lainnya, seperti NumPy, pandas, dan Matplotlib. Kode berikut adalah contoh cara membuat dan memprediksi dengan model KNN:

Algoritma k-NN telah digunakan dalam berbagai aplikasi, sebagian besar dalam klasifikasi. Beberapa contoh penggunaan ini meliputi:

• Prapemrosesan data: Kumpulan data sering kali memiliki missing values, tetapi algoritma KNN dapat memperkirakan nilai tersebut dalam proses yang dikenal sebagai imputasi data yang hilang.
  
  
• Mesin Rekomendasi: Menggunakan data clickstream dari situs web, algoritma KNN telah digunakan untuk memberikan rekomendasi otomatis kepada pengguna tentang konten tambahan. Penelitian ini menunjukkan bahwa pengguna ditugaskan ke grup tertentu, dan berdasarkan perilaku pengguna grup tersebut, mereka diberi rekomendasi. Namun, mengingat masalah penskalaan dengan KNN, pendekatan ini mungkin tidak optimal untuk kumpulan data yang lebih besar.
  
  
• Keuangan: Ini juga telah digunakan dalam berbagai contoh penggunaan keuangan dan ekonomi. Misalnya, satu makalah menunjukkan bagaimana menggunakan KNN pada data kredit dapat membantu bank menilai risiko pinjaman kepada organisasi atau individu. Ini digunakan untuk menentukan kelayakan kredit pemohon pinjaman. Jurnal lain menyoroti penggunaannya dalam forecasting pasar saham, nilai tukar mata uang, perdagangan berjangka, dan analisis pencucian uang.
  
  
• Layanan Kesehatan: KNN juga telah digunakan dalam industri kesehatan, memprediksi risiko serangan jantung dan kanker prostat. Algoritma bekerja dengan menghitung ekspresi gen yang paling mungkin.
  
  
• Pengenalan Pola: KNN juga telah membantu dalam mengidentifikasi pola, seperti dalam teks dan klasifikasi angka. Hal ini telah sangat membantu dalam mengidentifikasi nomor tulisan tangan yang Anda mungkin akan temukan pada formulir atau amplop surat.

Sama seperti algoritma machine learning lainnya, k-NN memiliki kekuatan dan kelemahannya. Tergantung pada proyek dan aplikasi, itu mungkin atau mungkin bukan pilihan yang tepat.

• Mudah diterapkan: Mengingat kesederhanaan dan akurasi algoritma, ini adalah salah satu pengklasifikasi pertama yang akan dipelajari oleh ilmuwan data baru.
  
  
• Beradaptasi dengan mudah: Saat sampel pelatihan baru ditambahkan, algoritma menyesuaikan untuk memperhitungkan data baru, karena semua data pelatihan disimpan ke dalam memori.
  
  
• Beberapa hiperparameter: KNN hanya membutuhkan nilai a k dan metrik jarak, yang rendah jika dibandingkan dengan algoritma machine learning lainnya.

• Tidak terskala dengan baik: Karena KNN adalah algoritma yang malas, maka dibutuhkan lebih banyak memori dan penyimpanan data dibandingkan dengan pengklasifikasi lainnya. Ini bisa mahal dari perspektif waktu dan uang. Lebih banyak memori dan penyimpanan akan meningkatkan pengeluaran bisnis dan lebih banyak data dapat memakan waktu lebih lama untuk dihitung. Meskipun struktur data yang berbeda, seperti Ball-Tree, telah dibuat untuk mengatasi ketidakefisienan komputasi, pengklasifikasi yang berbeda mungkin lebih ideal, bergantung pada masalah bisnis.
  
  
• Kutukan dimensionalitas: Algoritma KNN cenderung menjadi korban kutukan dimensionalitas, yang berarti ia tidak bekerja baik dengan input data berdimensi tinggi. Hal ini terkadang juga disebut sebagai fenomena puncak, di mana setelah algoritma mencapai jumlah fitur optimal, fitur tambahan meningkatkan jumlah kesalahan klasifikasi, terutama ketika ukuran sampel lebih kecil.
  
  
• Rentan terhadap overfitting: Karena “kutukan dimensi”, KNN juga lebih rentan terhadap overfitting. Meskipun teknik seleksi fitur dan pengurangan dimensi dimanfaatkan untuk mencegah hal ini terjadi, nilai k juga dapat memengaruhi perilaku model. Nilai k yang lebih rendah dapat membuat data menjadi overfit, sedangkan nilai k yang lebih tinggi cenderung “memperhalus” nilai prediksi karena nilai rata-rata di area yang lebih luas, atau lingkungan. Namun, jika nilai k terlalu tinggi, maka itu bisa kurang sesuai dengan data.