K-Nearest Neighbors (KNN): Konsep dan Cara Kerja

1. Apa itu KNN?

K-Nearest Neighbor (KNN) adalah algoritma supervised learning yang paling sederhana. Prinsipnya:

"Data baru diklasifikasikan berdasarkan kelas mayoritas dari K tetangga terdekatnya."

1.1. Analogi Sehari-hari

Bayangkan Anda pindah ke kota baru dan ingin tahu apakah lingkungan tersebut aman atau tidak:

Anda bertanya kepada K orang tetangga terdekat Anda
Jika mayoritas tetangga bilang "aman" → Anda simpulkan lingkungan tersebut aman
Jika mayoritas tetangga bilang "tidak aman" → Anda simpulkan tidak aman

Itulah prinsip KNN — keputusan berdasarkan mayoritas tetangga terdekat.

Istilah Penting

Istilah	Penjelasan
K	Jumlah tetangga terdekat yang akan dilihat (ditentukan oleh pengguna)
Neighbor (tetangga)	Data training yang jaraknya paling dekat dengan data baru
Jarak	Ukuran kedekatan antar data (biasanya Euclidean distance)
Majority voting	Kelas yang paling banyak muncul di antara K tetangga

1.2. Algoritma KNN Langkah demi Langkah

Langkah 1 = Tentukan nilai K (jumlah tetangga)
Langkah 2 = Hitung jarak dari data baru ke semua data training
Langkah 3 = Urutkan jarak dari yang terkecil ke terbesar
Langkah 4 = Ambil K data terdekat (tetangga terdekat)
Langkah 5 = Lihat kelas/label dari K tetangga tersebut
Langkah 6 = Tentukan kelas data baru berdasarkan majority voting (kelas terbanyak)

Ilustrasi Sederhana:

Misalnya K=3, dan 3 tetangga terdekat memiliki kelas: A, A, B

→ Kelas A = 2, Kelas B = 1

→ Mayoritas = Kelas A

→ Data baru diklasifikasikan sebagai Kelas A

2. Perhitungan Jarak (Euclidean Distance)

2.1. Mengapa Perlu Menghitung Jarak?

KNN bekerja berdasarkan kedekatan antar data. Untuk menentukan data mana yang "dekat" dan mana yang "jauh", kita perlu mengukur jarak antar titik data. Metode jarak yang paling umum digunakan adalah Euclidean Distance.

2.2. Rumus Euclidean Distance

Untuk 2 fitur (2 dimensi):

Jika data A berada di koordinat $(x_1, y_1)$ dan data B berada di $(x_2, y_2)$ , maka:

d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}

Untuk n fitur (n dimensi):

Jika data memiliki fitur, rumus umumnya:

d(A, B) = \sqrt{\sum_{i=1}^{n} (a_i - b_i)^2}

2.3. Contoh Perhitungan (2 Fitur)

Misalkan:

Data A = (2, 3)
Data B = (5, 7)

Langkah 1: Hitung selisih setiap fitur:

Selisih fitur 1: $5-2 =3$
Selisih fitur 2: $7-4=3$

Langkah 2: Kuadratkan setiap selisih:

$(3)^2=9$
$(4)^2=16$

Langkah 3: Jumlahkan semua kuadrat:

$9+16=25$

Langkah 4: Akar kuadrat dari jumlah total:

$\sqrt{25} = 5$

d(A, B) = \sqrt{(5 - 2)^2 + (7 - 3)^2} = \sqrt{9 + 16} = \sqrt{25} = 5

Maka dapat divisualisasikan seperti berikut:

2.4. Jenis-jenis Jarak Lainnya

Metode	Rumus	Keterangan
Euclidean	$\sqrt{\sum (a_i - b_i)^2}$	Jarak garis lurus (paling umum)
Manhattan	$\sum \|a_i - b_i\|$	Jarak "blok kota" (tanpa diagonal)
Minkowski	$(\sum \|a_i - b_i\|^p)^{1/p}$	Generalisasi Euclidean dan Manhattan

Pengaruh Nilai K

Pemilihan nilai K sangat mempengaruhi hasil klasifikasi KNN:

3. Apa yang Terjadi dengan K Berbeda?

Nilai K	Karakteristik	Risiko
K kecil (misal K=1)	Sangat sensitif terhadap data terdekat	Overfitting — terlalu mengikuti noise/outlier
K sedang (misal K=5)	Seimbang antara detail dan generalisasi	Pilihan yang sering digunakan
K besar (misal K=9)	Sangat halus, tidak sensitif terhadap noise	Underfitting — terlalu general, kehilangan pola

3.1. Ilustrasi Analogi

Bayangkan Anda pindah ke kota baru dan ingin tahu restoran terbaik:

K=1: Tanya 1 orang terdekat → bisa jadi dia punya selera unik
K=5: Tanya 5 orang → pendapat lebih beragam dan seimbang
K=semua: Tanya semua orang → hasilnya terlalu umum

3.2. Tips Memilih K

Gunakan K ganjil → menghindari seri (tie) pada voting
K tidak boleh terlalu kecil → rentan terhadap noise
K tidak boleh terlalu besar → batas tidak relevan ikut mempengaruhi
Rule of thumb: $k = \sqrt{n}$ di mana $n$ = jumlah data training
Cross-validation: cara terbaik untuk menemukan K optimal

4. Kelebihan dan Keterbatasan KNN

4.1. Kelebihan KNN

No	Kelebihan	Penjelasan
1	Sederhana & mudah dipahami	Konsepnya intuitif — cukup hitung jarak dan voting
2	Tidak ada fase training	KNN adalah lazy learner — tidak membangun model, langsung prediksi saat dibutuhkan
3	Fleksibel	Bisa digunakan untuk klasifikasi maupun regresi
4	Non-parametrik	Tidak mengasumsikan bentuk distribusi data tertentu
5	Mudah ditambah data baru	Cukup tambahkan data baru ke dataset, tidak perlu re-training

4.2. Keterbatasan KNN

No	Keterbatasan	Penjelasan
1	Lambat untuk data besar	Harus menghitung jarak ke semua data training setiap prediksi
2	Sensitif terhadap skala fitur	Fitur dengan range besar mendominasi perhitungan jarak → perlu normalisasi
3	Curse of Dimensionality	Performa menurun drastis ketika jumlah fitur (dimensi) sangat banyak
4	Sensitif terhadap noise/outlier	Data yang salah label dapat mempengaruhi hasil, terutama jika K kecil
5	Pemilihan K tidak trivial	Tidak ada rumus pasti untuk K terbaik — perlu eksperimen
6	Butuh memori besar	Menyimpan seluruh dataset di memori (instance-based learning)