K-Nearest Neighbor (KNN)

knn

K-Nearest Neighbor atau yang lebih dikenal sebagai KNN adalah algoritma Machine Learning yang bersifat supervised learning dan bersifat non-parametrik, yang mengukur kedekatan antar satu poin data ke data lain untuk membuat klasifikasi atau prediksi untuk melakukan pengelompokan titik data dari individual.

Meskipun dapat digunakan untuk masalah regresi, Algoritma K-Nearest Neighbor biasanya digunakan sebagai algoritma klasifikasi, bekerja dengan asumsi bahwa titik yang serupa dapat ditemukan berdekatan satu sama lain.

Untuk masalah klasifikasi, label kelas ditetapkan berdasarkan suara terbanyak yaitu label yang paling sering direpresentasikan di sekitar titik data tertentu digunakan. Meskipun ini secara teknis dianggap sebagai metode pemungutan suara (voting), dalam kata lain “suara mayoritas” yang lebih banyak akan digunakan.

Perbedaan antara istilah-istilah ini adalah bahwa “pemungutan suara mayoritas” secara teknis membutuhkan mayoritas lebih dari 50%, yang terutama berfungsi ketika hanya ada dua kategori. Saat memiliki beberapa kelas(multi-class), mis. empat kategori, Algoritma K-Nearest Neighbors tidak perlu mengambil 50% persetujuan untuk membuat kesimpulan mengenai suatu kelas.

Algoritma K-Nearest Neighbor untuk regresi menggunakan konsep yang mirip dengan masalah klasifikasi, namun, rata-rata neighbor K yang memiliki persamaan yang paling mirip diambil untuk membuat prediksi untuk klasifikasi. Perbedaan utama di sini adalah bahwa klasifikasi digunakan untuk nilai diskrit, sedangkan regresi digunakan dengan nilai kontinu. Namun, sebelum klasifikasi dapat dibuat, jarak harus ditentukan. Jarak Euclidean paling sering digunakan, yang akan kita bahas lebih lanjut di bawah ini.
Perlu juga diketahui bahwa algoritma K-Nearest Neighbor juga merupakan bagian dari keluarga algoritma machine learning yang disebut lazy learner atau pemalas, yang berarti bahwa algoritma K-Nearest Neighbor hanya menyimpan kumpulan data pelatihan untuk melakukan perbandingan dengan data inference. Ini juga berarti bahwa semua perhitungan terjadi ketika klasifikasi atau prediksi sedang dibuat. Karena sangat bergantung pada memori untuk menyimpan semua data pelatihannya, metode ini juga disebut sebagai metode pembelajaran berbasis instance atau berbasis memori.

Untuk menyimpul, tujuan dari algoritma K-Nearest Neighbor adalah untuk mengidentifikasi tetangga terdekat dari titik query yang diberikan, sehingga label dapat ditetapkan ke titik kelas tersebut. Untuk melakukan ini, K-Nearest Neighbor atau KNN memiliki beberapa persyaratan :

Untuk menentukan titik data mana yang paling dekat dengan titik kueri tertentu, jarak antara titik kueri dan titik data lainnya perlu dihitung. Metrik jarak ini membantu membentuk batasan keputusan, yang mempartisi titik kueri ke dalam wilayah yang berbeda. Hasil dari prediksi K-Nearest Neighbor biasanya divisualkan berupa diagram Voronoi.

Jenis Perhitungan Jarak KNN :

Jarak Hamming

Jarak Hamming biasanya digunakan dengan vektor dengan tipe data boolean atau string, yang mengidentifikasi titik di mana vektor tidak cocok. Akibatnya, ini juga disebut sebagai metrik tumpang tindih.

jarak hamming

Jarak Euclidean

Jarak Euclidean adalah ukuran jarak yang paling sering digunakan, dan terbatas pada vektor bernilai bilangan riil. Menggunakan rumus di bawah ini, ini mengukur garis lurus antara titik kueri dan titik lain yang diukur.

jarak euclidean

Jarak Manhattan

Jarak Manhattan juga merupakan metrik jarak populer lainnya, yang mengukur nilai absolut antara dua titik. Ini juga disebut sebagai taxi cab distance.

jarak manhattan

Jarak Minkowski : Ukuran jarak ini hanyalah bentuk satuan dari formulasi jarak Euclidean dan Manhattan. Parameter p, di rumus ini, memungkinkan pembuatan metrik jarak lainnya. Jarak Euclidean diwakili oleh rumus ini ketika nilai p sama dengan dua, dan jarak Manhattan dilambangkan dengan nilai p sama dengan satu.

jarak minkowski

Makna K dalam Algoritma KNN

Nilai K pada algoritma KNN mengartikan berapa banyak tetangga yang akan diperiksa untuk menentukan prediksi / klasifikasi untuk titik query tertentu.

Misalnya, jika k = 1, instance akan ditugaskan ke kelas yang sama dengan tetangga terdekatnya. Mendefinisikan k dapat menjadi tindakan penyeimbang karena nilai yang berbeda dapat menyebabkan overfitting atau underfitting. Nilai k yang lebih rendah dapat memiliki varians yang tinggi dan bias yang rendah, dan nilai k yang lebih besar dapat menyebabkan bias yang 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 titik cross-validation dapat membantu untuk memilih nilai k yang optimal untuk kumpulan suatu data.

Aplikasi Algoritma KNN

Algoritma KNN telah digunakan dalam berbagai aplikasi, sebagian besar dalam klasifikasi. Beberapa kasus penggunaan ini meliputi:

  • Preprocessing data : Kumpulan data sering sekali memiliki nilai yang hilang (nilai NaN), namun algoritma KNN dapat memperkirakan nilai tersebut dalam proses yang lebih dikenal sebagai imputasi data.
  • Recommendationn System : Menggunakan data clickstream dari website, algoritma KNN telah digunakan untuk memberikan rekomendasi otomatis kepada pengguna tentang konten tambahan.
  • Keuangan : Ini telah digunakan dalam berbagai kasus keuangan dan ekonomi. Algoritma KNN sering digunakan untuk menentukan apakah seorang pemohon pinjaman patut divalidasi untuk penggunaan kartu kredit . Algoritma KNN juga sering digunakan untuk menyoroti user untuk mem-forecast pasar saham, nilai tukar mata uang (forex), dan analisis pencucian uang.
  • Kesehatan : KNN juga memiliki bannyak aplikasi dalam industri perawatan kesehatan, membuat prediksi tentang risiko serangan jantung dan kanker prostat. Algoritma KNN bekerja dengan menghitung ekspresi gen yang paling mungkin.
  • Pengenalan Pola : KNN juga telah membantu dalam mengidentifikasi pola, seperti dalam klasifikasi teks dan digit (dataset MNIST). Ini sangat membantu dalam mengidentifikasi nomor tulisan tangan yang mungkin dapat ditemukan pada formulir atau amplop surat.

Implementasi untuk KNN dari scratch dapat dilihat disini :

KNN From Scratch

Tinggalkan Komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *