K-Nearest Neighbor (KNN): Contoh Perhitungan Manual

K-Nearest Neighbor (KNN) adalah algoritma supervised learning yang dapat digunakan untuk klasifikasi maupun regresi. Pada klasifikasi, KNN menentukan kelas data baru berdasarkan kelas dari sejumlah K tetangga terdekat.

Tutorial ini menggunakan contoh klasifikasi sederhana dengan dua atribut numerik. Perhitungan dilakukan mulai dari menentukan nilai K, menghitung Euclidean Distance, mengurutkan jarak, memilih tetangga terdekat, hingga menentukan kelas menggunakan majority voting.

Untuk membandingkan metode klasifikasi lain, lihat juga algoritma ID3, Decision Tree C4.5, dan metode Bayes. Jika ingin melihat metode lain yang juga menggunakan konsep kemiripan atau kedekatan kasus, lihat Case Based Reasoning.

Daftar Isi

• Pengertian KNN
• Cara Kerja KNN
• Rumus Euclidean Distance
• #01 Menyiapkan Data Latih
• #02 Menentukan Data Uji
• #03 Menentukan Nilai K
• #04 Menghitung Jarak
• #05 Mengurutkan Tetangga Terdekat
• #06 Majority Voting
• #07 Hasil Klasifikasi
• Kelebihan dan Kekurangan
• KNN vs CBR
• Ringkasan
• FAQ KNN
• Referensi
• Source Code KNN

Pengertian KNN

K-Nearest Neighbor adalah algoritma yang menentukan hasil prediksi berdasarkan data latih yang paling dekat dengan data baru.

Pada klasifikasi:

Data uji
↓
Hitung jarak ke seluruh data latih
↓
Urutkan dari jarak terkecil
↓
Ambil K tetangga terdekat
↓
Hitung jumlah kelas
↓
Pilih kelas mayoritas

KNN tidak membangun model pohon atau rule pada tahap pelatihan. Data latih digunakan langsung ketika proses prediksi dilakukan.

Cara Kerja KNN

Tahapan dasar KNN untuk klasifikasi:

1. Menyiapkan data latih yang sudah memiliki label kelas.
2. Menentukan nilai K.
3. Menghitung jarak data uji terhadap seluruh data latih.
4. Mengurutkan jarak dari yang terkecil.
5. Mengambil K data terdekat.
6. Melakukan majority voting.
7. Menentukan kelas data uji.

Rumus Euclidean Distance

Untuk dua data:

dan:

Euclidean Distance:

Untuk dua atribut:

Nilai jarak yang lebih kecil menunjukkan data yang lebih dekat.

#01 Menyiapkan Data Latih

Contoh berikut merupakan data ilustratif untuk menjelaskan perhitungan manual KNN.

Pada contoh ini terdapat dua kelas:

Reguler
Prioritas

#02 Menentukan Data Uji

Data baru yang akan diklasifikasikan:

X1 = 5
X2 = 5

Sehingga:

Kelas data uji belum diketahui.

#03 Menentukan Nilai K

Pada contoh digunakan:

Artinya hasil klasifikasi ditentukan dari 3 tetangga terdekat.

Nilai K pada sistem nyata perlu dipilih dan dievaluasi sesuai karakteristik data. Nilai K pada tutorial ini hanya digunakan untuk memudahkan perhitungan manual.

#04 Menghitung Jarak

Contoh Jarak Data D1

D1:

Data uji:

Maka:

Contoh Jarak Data D5

D5:

Maka:

Hasil seluruh jarak:

#05 Mengurutkan Tetangga Terdekat

Jarak kemudian diurutkan dari nilai terkecil.

Karena:

maka tiga tetangga yang digunakan adalah:

#06 Majority Voting

Tiga tetangga terdekat adalah:

D5 → Prioritas
D6 → Prioritas
D4 → Prioritas

Jumlah kelas:

Prioritas = 3
Reguler   = 0

Kelas mayoritas adalah:

#07 Hasil Klasifikasi

Data uji:

dengan:

diklasifikasikan sebagai:

Hasil tersebut berlaku untuk data ilustratif, nilai K, dan distance metric yang digunakan pada contoh ini.

Kelebihan dan Kekurangan

Kelebihan KNN

• Konsep mudah dipahami.
• Tidak membutuhkan proses pembentukan model yang kompleks.
• Dapat digunakan untuk klasifikasi maupun regresi.
• Dapat menggunakan berbagai ukuran jarak sesuai kebutuhan data.

Kekurangan KNN

• Prediksi dapat menjadi lebih berat ketika data latih sangat besar.
• Hasil sensitif terhadap nilai K.
• Skala atribut dapat memengaruhi perhitungan jarak.
• Hasil dapat dipengaruhi data yang tidak relevan atau noise.

KNN vs CBR

KNN dan Case Based Reasoning sama-sama dapat menggunakan konsep kedekatan, tetapi tujuan dan prosesnya berbeda.

Untuk klasifikasi berbasis pohon keputusan, bandingkan juga dengan ID3 dan C4.5.

Ringkasan

Pada contoh ini:

Jumlah data latih = 8
K = 3
Data uji = (5,5)

Tiga tetangga terdekat:

D5 = 1.0000 → Prioritas
D6 = 1.0000 → Prioritas
D4 = 1.4142 → Prioritas

Hasil majority voting:

Prioritas = 3
Reguler   = 0

Sehingga data uji diklasifikasikan sebagai:

Prioritas

FAQ KNN

Apa kepanjangan KNN?

KNN adalah singkatan dari K-Nearest Neighbor.

Apa fungsi nilai K?

K menentukan jumlah tetangga terdekat yang digunakan untuk menghasilkan prediksi.

Apakah KNN hanya untuk klasifikasi?

Tidak. KNN juga dapat digunakan untuk regresi dengan mekanisme agregasi nilai tetangga.

Mengapa normalisasi data penting?

Jika atribut memiliki skala yang sangat berbeda, atribut dengan rentang besar dapat lebih dominan pada perhitungan jarak.

Apa perbedaan KNN dan Decision Tree?

KNN menentukan prediksi berdasarkan kedekatan data, sedangkan Decision Tree membentuk struktur keputusan berdasarkan pemisahan atribut.

Apa yang terjadi jika voting seri?

Implementasi perlu menentukan aturan tie-breaking, misalnya mempertimbangkan jarak yang lebih dekat atau menggunakan nilai K yang berbeda.

Referensi

1. Cover, T. M., & Hart, P. E. (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. Morgan Kaufmann.

Source Code KNN

Source Code Klasifikasi Metode KNN VB

Rp500,000

Source Code Data Mining Klasifikasi Metode KNN Gain PHP

Rp600,000

Source Code Klasifikasi Metode KNN PHP

Rp500,000