🏘️ K-Nearest Neighbors (KNN)

"Kamu adalah rata-rata dari 5 teman terdekatmu" — algoritma paling intuitif, tanpa fase training.

🎬 Animasi: KNN: Voting Tetangga Terdekat

Titik baru (bintang) mencari k tetangga terdekat, lalu mengikuti mayoritas kelas mereka.

📌 1. Konsep: Belajar dari Tetangga

Untuk mengklasifikasikan titik baru: cari k titik terdekat di data training, lalu voting mayoritas.

Contoh (k=3):
            o
        o   •   ← titik baru: 3 tetangga terdekat = 2×o, 1×x
            x       → voting: o menang → titik baru = kelas o

Algoritma:
1. Untuk titik baru x: hitung jarak ke SEMUA titik training
2. Ambil k terdekat
3. Voting mayoritas → label x
   (untuk regresi: rata-rata nilai k terdekat)

Karakter khas:
• "Lazy learner" — TIDAK ada fase training; semua komputasi saat prediksi
• Bisa membentuk boundary SEMANGAT (non-linear)
• SANGAT bergantung pada skala fitur → scaling wajib!

📌 2. Jarak & Memilih k

Jarak	Rumus	Karakter
Euclidean	√(Σ(xᵢ-yᵢ)²)	Paling umum; sensitif diagonal
Manhattan	Σ\|xᵢ-yᵢ\|	"Jalan kota"; lebih toleran
Cosine	1 - cos(θ)	Arah vektor; populer di teks (bab 17)

Efek nilai k:
    k kecil (1,3)  → boundary bergerigi, fleksibel, RAPIH di train
                   → tapi rapuh terhadap noise (OVERFITTING)
    k besar (21+) → boundary halus, toleran noise
                   → tapi bisa "kabur" di area sempit (UNDERFITTING)

Aturan praktis: k ganjil (anti-seri), mulai dari √n, lalu tuning.

📌 3. Contoh: KNN 3 Kelas + Bandingkan k

print("=== KNN: 3 KLASTER, BANDINGKAN k ===\n")
random_seed(42)
X, y = make_blobs(120, centers=[(2, 2), (8, 3), (5, 8)], spread=0.8)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3)

def knn_predict(x, k, Xtr, ytr):
    # 1. jarak ke semua training
    dists = sorted((euclidean(x, xt), yt) for xt, yt in zip(Xtr, ytr))
    # 2. ambil k terdekat
    nearest = dists[:k]
    # 3. voting
    votes = {}
    for d, l in nearest:
        votes[l] = votes.get(l, 0) + 1
    return max(votes, key=votes.get)

print("Akurasi test untuk berbagai k:")
for k in [1, 3, 5, 7, 15, 31]:
    pred = [knn_predict(x, k, Xtr, ytr) for x in Xte]
    print("  k=%2d  accuracy = %.1f%%" % (k, accuracy(yte, pred) * 100))

# Tunjukkan satu prediksi secara transparan
x_new = Xte[0]
dists = sorted((euclidean(x_new, xt), yt, i)
               for i, (xt, yt) in enumerate(zip(Xtr, ytr)))
print("\nTransparansi prediksi untuk titik %s:" % [round(v, 2) for v in x_new])
print("  5 tetangga terdekat:")
for d, l, i in dists[:5]:
    print("    jarak=%.2f  label=%d  (training #%d)" % (d, l, i))
print("  → voting: %d" % knn_predict(x_new, 5, Xtr, ytr))

Output:

📌 4. Contoh: k=1 vs k=11 pada Data Moons

k=1 menghafal setiap titik (termasuk noise) → overfitting. k besar menghaluskan boundary. Lihat perbedaannya:

print("=== EFEK k: OVERFITTING vs HALUS ===\n")
random_seed(42)
X, y = make_moons(100, noise=0.25)

def knn_predict(x, k):
    dists = sorted((euclidean(x, xt), yt) for xt, yt in zip(X, y))[:k]
    votes = {}
    for d, l in dists:
        votes[l] = votes.get(l, 0) + 1
    return max(votes, key=votes.get)

print("Akurasi (dihitung di data yang sama = 'hafalan'):")
for k in [1, 3, 5, 11, 21, 41]:
    pred = [knn_predict(x, k) for x in X]
    print("  k=%2d  accuracy = %.1f%%" % (k, accuracy(y, pred) * 100))

print("\nVisualisasi: titik yang SALAH diprediksi k=1 (garis merah 'E'):")
pts = []
for x, l in zip(X, y):
    p1 = knn_predict(x, 1)
    pts.append((x[0], x[1], "E" if p1 != l else ("o" if l == 0 else "x")))
scatter2d(pts, title="k=1: E = titik yang salah (noise diikat)")
print("o=kelas 0, x=kelas 1, E=salah prediksi k=1")
print("→ k=1 'menghukum' noise; k besar lebih bijak.")

Output:

⚠️ KNN lambat saat prediksi (hitung jarak ke semua data). Untuk data besar, praktisi memakai indeks: KD-tree, ball tree, atau approximate nearest neighbor (HNSW).

🧠 Latihan

Ubah jarak Euclidean menjadi manhattan() di contoh 1. Apakah akurasinya berubah signifikan?
Buat KNN untuk REGRESI: prediksi = rata-rata nilai k terdekat. Uji di make_regression() dan bandingkan RMSE-nya dengan model "tebak mean".
Tambahkan distance weighting: bobot suara = 1/jarak. Apakah membantu di area berbatasan?
Jelaskan kenapa KNN wajib scaling. Buat contoh kecil: 2 fitur dengan skala 0–1 dan 0–1000, titik di antara dua klaster.