# k-Nearest Neighbors (kNN)
## Apa itu kNN?
Algoritma *k-Nearest Neighbors* (k-NN) merupakan salah satu metode paling sederhana dalam pembelajaran terbimbing (*supervised learning*). Alih-alih membangun model matematis yang kompleks, k-NN bekerja dengan prinsip **“belajar dari tetangga terdekat”**. Algoritma ini hanya menyimpan seluruh data latih, lalu untuk data baru, mencari sejumlah *k* titik data yang paling dekat dengannya dan menentukan kelas berdasarkan informasi dari tetangga tersebut. Meskipun sederhana, kNN dapat digunakan untuk kebutuhan klasifikasi maupun regresi.
* **Untuk klasifikasi**, keputusan ditentukan dengan **voting mayoritas** dari label tetangga.
* **Untuk regresi**, nilai prediksi adalah **rata-rata** dari nilai tetangga terdekat.
Pada modul ini, kita hanya akan berfokus pada pemanfaatan kNN sebagai algoritma klasifikasi.
\
Ilustrasi cara kerja kNN dengan (Muller, 2023)Selanjutnya, dikarenakan keputusan label berdasarkan hasil voting, ada pendapat dan *best practice* yang menyatakan bahwa nilai yang aman adalah nilai ganjil. Hal ini dikarenakan jika jumlah berjumlah genap ada potensi untuk jumlah vote berimbang.
***
### Jarak Pada kNN
Seperti yang telah dijelaskan sebelumnya, kNN menggunakan fungsi jarak untuk menentukan tetangga terdekatnya. Lalu, bagaimana cara menentukan jaraknya? Kita dapat menggunakan fungsi jarak seperti,
1. Euclidean distance (umum digunakan)
2. Manhattan distance
3. Minkowski distance
4. Cosine distance
Penggunaan jenis jarak bergantung dengan kasus yang akan diselesaikan. Namun, dikarenakan terkadang fitur memiliki skala yang berbeda, kita mungkin membutuhkan **proses standardisasi sebelum melakukan perhitungan jarak**.
***
### Analisis Performa kNN
Untuk mengetahui performa dari model kNN, kita dapat melakukan analisis terhadap dua hal, pertama adalah decision boundaries, kedua performa berdasarkan metric klasifikasi untuk setiap nilai . Untuk decision boundaries, cara ini dapat dilakukan dengan amatan visual jika fitur yang dibandingkan tidak lebih dari 3. Decision boundaries akan lebih "halus" jika jumlah tetangga yang digunakan semakin banyak. Akan tetapi, perhatikan jumlah fitur / kompleksitas dari data yang digunakan.
> * Gunakan beberapa (sedikit) tetangga pada model yang kompleks
> * Gunakan banyak tetangga pada model yang sederhana
Sebagai contoh,
```python
# Decision Boundaries - Introduction to Machine Learning
# Andreas C. Müller, Sarah Guido (2023)
# pip install mglearn
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
import mglearn
X, y = mglearn.datasets.make_forge()
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
fig, axes = plt.subplots(1, 3, figsize=(10, 3))
for n_neighbors, ax in zip([1, 3, 9], axes):
# the fit method returns the object self, so we can instantiate
# and fit in one line
clf = KNeighborsClassifier(n_neighbors=n_neighbors).fit(X, y)
mglearn.plots.plot_2d_separator(clf, X, fill=True, eps=0.5, ax=ax, alpha=.4)
mglearn.discrete_scatter(X[:, 0], X[:, 1], y, ax=ax)
ax.set_title("{} neighbor(s)".format(n_neighbors))
ax.set_xlabel("feature 0")
ax.set_ylabel("feature 1")
axes[0].legend(loc=3)
```
Akan menghasilkan,
Dapat dilihat pada gambar sebelah kiri, penggunaan 1 tetangga akan menjadikan decision boundary akan mengikuti pola data dengan "kaku". Jumlah tetangga yang lebih banyak akan menjadikan batas keputusan menjadi lebih halus. Namun apakah dengan cara ini performa dapat lebih baik?
Kita perlu melakukan analisis lebih lanjut untuk siap jumlah tetangga yang digunakan.
Contoh,
```python
# Introduction to Machine Learning
# Andreas C. Müller, Sarah Guido (2023)
from sklearn.datasets import load_breast_cancer
cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(cancer.data, cancer.target, stratify=cancer.target, random_state=66)
training_accuracy = []
test_accuracy = []
# try n_neighbors from 1 to 10
neighbors_settings = range(1, 11)
for n_neighbors in neighbors_settings:
# build the model
clf = KNeighborsClassifier(n_neighbors=n_neighbors)
clf.fit(X_train, y_train)
# record training set accuracy
training_accuracy.append(clf.score(X_train, y_train))
# record generalization accuracy
test_accuracy.append(clf.score(X_test, y_test))
plt.plot(neighbors_settings, training_accuracy, label="training accuracy")
plt.plot(neighbors_settings, test_accuracy, label="test accuracy")
plt.ylabel("Accuracy")
plt.xlabel("n_neighbors")
plt.legend()
```
Hasilnya,
Dari hasil grafik dapat dilihat bahwa, jika tetangga yang digunakan hanya 1, performa data training akan sangat baik akan tetapi bertolak belakang dengan data testing. Hal ini menunjukkan fenomena overfitting dimana model tidak dapat mengeneralisasi data dengan cukup baik. Akan tetapi jika 10 tetangga digunakan, maka kompleksitas model akan menjadi lebih sederhana sehingga performa (akurasi) malah menurun. Dari grafik kita dapat mengetahui bahwa jumlah tetangga yang dapat mengakomodasi performa dengan cukup baik dari sisi training dan testing adalah 6 tetangga dilihat dari grafik performa training dan testing yang hampir berdekatan.
