介紹完決策樹和隨機森林後，今天來介紹的是 K-近鄰演算法(k-nearest neighbor classification)，簡稱為 KNN 。而它的判斷邏輯其實也相當簡單，就是物以類聚。

什麼意思呢？因為它的判斷邏輯就是：
就是假設你的鄰居都是有錢人，那麼你有十之八九也是有錢人。

所以它的運作原理就是先找出距離最近的 K 個鄰居，然後再去分別察看這些鄰居的類別，最後再決定自身的類別。

舉個例子：

以上圖為例，測試樣本為綠色圓型。
如果 K=3 （實線圓圈），測試樣本會被歸類為紅色三角形。
而如果 K=5 （虛線圓圈），測試樣本會被歸類為藍色正方形。

那麼問題來了，我們該如何決定K值？如果K為偶數的話又該怎麼辦呢？

K 值該如何決定？如果是偶數的話該怎麼辦？

如果 K 太大的話，可能會造成欠擬合(underfitting)，準確率過低；
如果 K 太小的話，可能會造成過度擬合(Overfitting)，在測試集內準確率高，但是拿出去做驗證時就成效不加。

由於 KNN 分類對 K 值相當敏感，不同的值有可能帶來不同的結果。在實際中，一般採用交叉驗證（一部分樣本做訓練集，一部分做測試集）或者依靠經驗的方法來選取 K 值。K 值一開始通常都會取一個比較小的數值，之後再不斷來調整 K 的大小直到分類表現達到最佳即可。

通常 K 值一般都會設為奇數。有一個經驗規則是：K 一般低於訓練樣本數的平方根。而我們在選擇 K值的時候，通常都會盡量去避免採用偶數的情況。

那如果 K 真的是偶數的話該怎麼辦？還有一種用加權來解決的方法：
給予距離較近的分類較高的權重，最後由加權後最高的分類勝出。

KNN 的優點與缺點：

優點：

1. 簡單且容易理解，易於實現且無需訓練
2. 精度高、對異常值不敏感
3. 適合於多分類問題

缺點：

1. 時間複雜度高、空間複雜度高、計算量大，記憶體開銷也大
2. 可解釋性較差，無法給出決策樹那樣的規則
3. 當樣本不平衡時，可能導致特定分類佔大多數

實作

透過 iris 資料集，測試其分類的準確率：

from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split

iris=datasets.load_iris()
X=iris.data
y=iris.target

# x是花萼與花瓣的長度、寬度的原始資料
# y是將花分類之後的正確答案

X_train, X_test, y_train, y_test = train_test_split(X, y,test_size=0.3,random_state=1)
clf=KNeighborsClassifier(n_neighbors=3,p=2,weights='distance',algorithm='brute')
clf.fit(X_train,y_train)

# n_neighbors: 要取幾個鄰居(儘量設置奇數)
# p: 選擇距離的計算方式
# weights: 投票方式為距離等權重或加權
# algorithm:演算法的選擇 (計算效率的考慮)

print(clf.score(X_test,y_test))  # 印出準確度分數

## ===============以下為找出 K 的最佳值並秀出來
# accuracy = []
# for k in range(1, 100):
#     knn = KNeighborsClassifier(n_neighbors=k)
#     knn.fit(X_train, y_train)
#     y_pred = knn.predict(X_test)
#     accuracy.append(metrics.accuracy_score(y_test, y_pred))

# k_range = range(1,100)
# plt.plot(k_range, accuracy)
# plt.show()