kNN

17106050001 – Aprilia Nuryanti

k-nearest neighbor (kNN) termasuk kelompok instance-based learning. Algoritma ini juga merupakan salah satu teknik lazy learning. kNN dilakukan  dengan mencari kelompok k objek dalam data training yang paling dekat (mirip) dengan objek pada data baru atau data testing.  Contoh kasus, misal diinginkan untuk mencari solusi terhadap masalah seorang pasien baru dengan menggunakan solusi dari pasien lama. Untuk mencari solusi dari pasien baru tersebut digunakan kedekatan dengan kasus pasien lama, solusi dari kasus lama yang memiliki kedekatan dengan kasus baru digunakan sebagai solusinya.

Pada Algoritma kNN terdapat beberapa metode perhitungan seperti Euclidean Distance dan Manhattan. untuk bisa memahami kedua metode perhitungan tersebut, maka perhatikan contoh berikut:

Contoh Perhitungan KNN Metode Euclidean Distance

Diketahui data berikut kemudian lakukan perhitungan Euclidean Distance:

Keterangan: NIM 1-10 merupakan data lama, sedangkan NIM 11-13 merupakan data baru. ingat jika IPK < 3 = Mengecewakan, sedangkan
jika IPK >= 3 = Memuaskan

Kemudian hitung euclidean distance dari masing-masing data setiap nim terhadap masing-masing data baru (nim 11-13) dengan menggunakan rumus:

serta tidak lupa untuk menentukan nilai terdekat (nilai euclidean terkecil) dengan cara dibuat urutan jarak dari terkecil hingga terbesar.
sehingga didapatkan hasil perhitungan untuk data baru pertama (NIM 11):

Dari hasil perhitungan diatas dengan menggunakan K=3, maka di dapatkan 3 nilai kategori yang semuanya menunjukkan kategori memuaskan. maka dapat disimpulkan bahwa nilai prediksi kategori IPK untuk data baru dengan nim 11 adalah “Memuaskan“.

hasil perhitungan untuk terhadap data baru kedua (NIM 12):

Dari hasil perhitungan diatas dengan menggunakan K=3, maka di dapatkan 3 nilai kategori yang menunjukkan kategori memuaskan, memuaskan, dan mengecewakan. maka dapat disimpulkan bahwa nilai prediksi kategori IPK untuk data baru dengan nim 12 adalah “Memuaskan“.

hasil perhitungan untuk terhadap data baru ketiga (NIM 13):

Dari hasil perhitungan diatas dengan menggunakan K=3, maka di dapatkan 3 nilai kategori yang menunjukkan kategori memuaskan, mengecewakan, dan mengecewakan. maka dapat disimpulkan bahwa nilai prediksi kategori IPK untuk data baru dengan nim 13 adalah “Mengecewakan“.

Setelah menguji 3 data uji, kita mendapatkan nilai prediksi dari setiap data uji yaitu:

selanjutkan kita akan mencari precission, recall, dan accuracy. dari perhitungan diatas.

perlu di pahami :

TP = True Positive

TN =True Negative

FP = False Positive

FN = False Negative

	Rumus	Perhitungan	Hasil
Precission	TP/TP+FP	1/(1+1)	50%
Recall	TP/TP+FN	1/(1+0)	100%
Accuracy	TP+TN/TP+TN+FP+FN	(1+1)/(1+1+1+0)	67%

Contoh Perhitungan KNN Metode Manhattan

Diketahui data berikut kemudian lakukan perhitungan dengan metode Manhattan:

Keterangan: NIM 1-10 merupakan data lama, sedangkan NIM 11-13 merupakan data baru. ingat jika IPK < 3 = Mengecewakan, sedangkan
jika IPK >= 3 = Memuaskan

Kemudian hitung Manhattan dari masing-masing data setiap nim terhadap masing-masing data baru (nim 11-13) dengan menggunakan rumus yang hampir sama dengan rumus euclidean distance hanya saja tidak menggunakan akar.

d_ij = ∑W_k|x_ik – c_jk|.

serta tidak lupa untuk menentukan 3 nilai terdekat (nilai Manhattan terkecil). sehingga didapatkan hasil perhitungan untuk data baru pertama (NIM 11):

Dari hasil perhitungan diatas dengan menggunakan K=3, maka di dapatkan 3 nilai kategori yang semuanya menunjukkan kategori memuaskan. maka dapat disimpulkan bahwa nilai prediksi kategori IPK untuk data baru dengan nim 11 adalah “memuaskan“.

hasil perhitungan untuk terhadap data baru kedua (NIM 12):

Dari hasil perhitungan diatas dengan menggunakan K=3, maka di dapatkan 3 nilai kategori yang menunjukkan kategori memuaskan, mengecewakan, mengecewakan. maka dapat disimpulkan bahwa nilai prediksi kategori IPK untuk data baru dengan nim 12 adalah “Mengecewakan“.

hasil perhitungan untuk terhadap data baru ketiga (NIM 13):

Dari hasil perhitungan diatas dengan menggunakan K=3, maka di dapatkan 3 nilai kategori yang semuanya menunjukkan kategori memuaskan, mengecewakan, mengecewakan. maka dapat disimpulkan bahwa nilai prediksi kategori IPK untuk data baru dengan nim 13 adalah “Mengecewakan“.

Setelah menguji 3 data uji, kita mendapatkan nilai prediksi dari setiap data uji yaitu:

Kemudian kita hitung nilai Presisi, Recall, Akurasi :

Presisi	1/(1+0)*100%	100%
Recall	1/(1+0)*100%	100%
Akurasi	(1+2)/(1+2+0+0)*100%	100%

sumber: https://media.neliti.com/media/publications/155541-ID-penerapan-algoritma-k-nearest-neighbor-u.pdf