K-Nearest Neighbor (KNN): Contoh Perhitungan Manual dan Implementasi

Tutorial ini membahas K-Nearest Neighbor (KNN) dan contoh perhitungannya untuk melakukan klasifikasi berdasarkan kedekatan data. Contoh kasus menggunakan data status pembayaran kredit dengan tiga atribut, yaitu penghasilan, jumlah pinjaman, dan tenor.

Perhitungan dilakukan mulai dari menyiapkan data latih dan data uji, melakukan normalisasi Min-Max, menghitung Euclidean Distance, mengurutkan jarak, memilih K tetangga terdekat, hingga menentukan kelas berdasarkan voting mayoritas.

---

Daftar Isi

• Pengertian K-Nearest Neighbor
• Rumus KNN
• #01 Data Latih
• #02 Data Uji
• #03 Normalisasi Min-Max
• #04 Menentukan Nilai K
• #05 Menghitung Euclidean Distance
• #06 Menentukan Tetangga Terdekat
• #07 Voting Kelas
• #08 Hasil Klasifikasi
• Ringkasan
• FAQ KNN
• Referensi
• Source Code KNN

---

Pengertian K-Nearest Neighbor

K-Nearest Neighbor atau KNN adalah algoritma klasifikasi yang menentukan kelas sebuah data baru berdasarkan kelas dari sejumlah data terdekat di dalam data latih.

Nilai K menunjukkan jumlah tetangga yang digunakan. Setelah jarak setiap data latih terhadap data uji dihitung, data dengan jarak paling kecil dipilih sebanyak K buah. Kelas yang paling banyak muncul menjadi hasil klasifikasi.

Rumus KNN

Normalisasi Min-Max

Karena setiap atribut dapat memiliki skala berbeda, data dinormalisasi terlebih dahulu menggunakan Min-Max Normalization.

$$ x' = \frac{x-x_{min}}{x_{max}-x_{min}} $$

• \(x\): nilai asli
• \(x_{min}\): nilai minimum atribut pada data latih
• \(x_{max}\): nilai maksimum atribut pada data latih
• \(x'\): nilai setelah normalisasi

Euclidean Distance

Jarak antara data uji dan data latih dihitung menggunakan Euclidean Distance.

$$ d(x,y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2} $$

Semakin kecil nilai jarak, semakin mirip data latih tersebut dengan data uji.

#01 Data Latih

Contoh menggunakan 8 data latih. Setiap data sudah memiliki label Lancar atau Macet.

#02 Data Uji

Data berikut belum memiliki label dan akan diklasifikasikan menggunakan KNN.

#03 Normalisasi Min-Max

Sebelum menghitung jarak, nilai setiap atribut dinormalisasi agar perbedaan skala antaratribut tidak mendominasi hasil Euclidean Distance.

Nilai Minimum dan Maksimum

Nilai minimum dan maksimum diambil dari data latih. Sebagai contoh, atribut penghasilan memiliki nilai:

min = 3, max = 8

Contoh Perhitungan Normalisasi

Sebelum melihat tabel normalisasi, berikut contoh cara mendapatkan nilainya untuk D1 - Nasabah 1.

Normalisasi penghasilan: (5 - 3) / (8 - 3) = 0.4

Normalisasi pinjaman: (10 - 10) / (24 - 10) = 0

Normalisasi tenor: (12 - 12) / (30 - 12) = 0

Dengan cara yang sama, seluruh data latih dinormalisasi seperti tabel berikut.

Normalisasi Data Uji

Data uji harus dinormalisasi menggunakan nilai minimum dan maksimum yang sama dari data latih.

Contoh normalisasi penghasilan data uji: (6 - 3) / (8 - 3) = 0.6

#04 Menentukan Nilai K

Pada contoh ini digunakan K = 3. Artinya, hasil klasifikasi akan ditentukan berdasarkan 3 data latih dengan jarak paling dekat terhadap data uji.

Nilai K ganjil sering digunakan pada klasifikasi dua kelas untuk membantu mengurangi kemungkinan voting berakhir seri. Namun pemilihan K yang optimal sebaiknya dievaluasi menggunakan data validasi.

#05 Menghitung Euclidean Distance

Setelah normalisasi, hitung jarak data uji terhadap seluruh data latih.

Contoh Perhitungan Jarak

Sebelum melihat tabel, berikut perhitungan jarak antara data uji dan D1 - Nasabah 1.

$$ d = \sqrt{ (0.6 - 0.4)^2 + (0.4286 - 0)^2 + (0.3333 - 0)^2 } = 0.5786 $$

Perhitungan yang sama dilakukan terhadap seluruh data latih.

#06 Menentukan Tetangga Terdekat

Seluruh nilai jarak diurutkan dari yang terkecil ke terbesar. Karena K = 3, hanya 3 data dengan jarak terkecil yang digunakan.

Dari hasil pengurutan, 3 tetangga terdekat adalah: Nasabah 3 (Lancar), Nasabah 4 (Lancar), Nasabah 2 (Lancar).

#07 Voting Kelas

Setelah 3 tetangga terdekat diperoleh, jumlah kemunculan setiap label dihitung.

Pada contoh ini, label tetangga yang digunakan adalah: Lancar + Lancar + Lancar.

#08 Hasil Klasifikasi

Label dengan jumlah suara terbanyak adalah Lancar. Dengan demikian, data uji diklasifikasikan sebagai Lancar.

Hasil ini diperoleh dari contoh data dan parameter K = 3. Pada penerapan nyata, kualitas model perlu dievaluasi menggunakan data pengujian yang terpisah dan pemilihan K yang sesuai.

Ringkasan

KNN melakukan klasifikasi berdasarkan kedekatan data uji dengan data latih. Pada contoh ini, atribut terlebih dahulu dinormalisasi menggunakan Min-Max, kemudian jarak dihitung dengan Euclidean Distance. Setelah jarak diurutkan, 3 tetangga terdekat dipilih dan kelas ditentukan menggunakan voting mayoritas. Hasil klasifikasi data uji adalah Lancar.

FAQ KNN

Apa fungsi nilai K pada KNN?

Nilai K menentukan jumlah tetangga terdekat yang digunakan untuk menentukan kelas data uji.

Mengapa data perlu dinormalisasi?

Normalisasi membantu menyamakan skala atribut agar atribut dengan nilai besar tidak mendominasi perhitungan jarak.

Apakah KNN selalu menggunakan Euclidean Distance?

Tidak. Euclidean Distance merupakan salah satu metode jarak yang paling umum, tetapi KNN juga dapat menggunakan ukuran jarak lain sesuai karakteristik data.

Bagaimana memilih nilai K?

Nilai K sebaiknya dipilih melalui evaluasi model menggunakan data validasi atau teknik seperti cross-validation.

Apa kekurangan KNN?

KNN dapat menjadi lebih lambat ketika jumlah data latih sangat besar karena jarak terhadap data latih perlu dihitung saat melakukan prediksi.

---

Referensi

1. Cover, T. & Hart, P. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
2. Han, J., Kamber, M. & Pei, J. (2012). Data Mining: Concepts and Techniques, 3rd Edition. Morgan Kaufmann.

---

Source Code Metode KNN

Berikut adalah beberapa source code yang menggunakan metode K-Nearest Neighbor, baik berbasis web maupun desktop.

• Source Code Klasifikasi Metode KNN PHP
• Source Code Data Mining Klasifikasi Metode KNN Gain PHP
• Source Code Klasifikasi Metode KNN VB

Ada yang Ditanyakan?

Jika anda masih ada kesulitan atau kekeliruan tentang penjelasan metode di atas, bisa menghubungi kami lewat WA/Email sesuai halaman Kontak.

Jika ingin memiliki file excel dari metode di atas bisa melihat cara download di halaman Download.

Jika ingin memiliki source code dari metode di atas, baik berbasis web maupun desktop bisa melihat daftar harga donasi di halaman Daftar Source Code.

Donasi ini digunakan oleh penulis untuk membayar server dan membeli kopi sembari membuat tutorial Metode/Algoritma lainnya :).