# [ML] K-最近鄰演算法

###### tags: `ML`

**K-最近鄰**（**k-nearest neighbor, KNN**）演算法是一種監督式學習（supervised learning）演算法，可以用於分類或回歸。

## KNN 演算法簡介
### KNN 分類演算法
KNN 分類演算法是一個基於投票的演算法，其流程如下：
1. 決定 $k$ 值
3. 求每個鄰居跟自己之間的**距離**
4. 找出跟自己最近的 $k$ 個鄰居，查看**屬於哪一組的鄰居數量最多，就加入那一組**

實務上，為了避免票數相同造成無法決定實例在哪一組的情形，對於二元分類（只有兩個類別），會選擇奇數的 $k$ 值。

在求距離的這個步驟，還隱含了一個選擇距離度量的過程。有哪些距離度量可以選，我們在後面會說明。

$k$ 的大小會影響模型最終的分類結果。以下圖為例，假設綠色點是新的資料。當 $k = 3$ 時會搜尋離綠色點最近的鄰居，我們可以發現藍色三角形為預測的結果。當 $k = 5$ 的時候結果又不一樣了，我們發現距離最近的三個鄰居為紅色正方形。

$k$ 的選擇是KNN演算法的核心。事實上，越大的 $k$ 傾向於給出越平滑的分類邊界。想像一個極端情形：當 $k$ 等於資料集的實例數時，任何的測試資料都只會被分到實例數較多的那一類，這時是不會有任何的邊界的。


我們可以說，太小的 $k$ 容易給出**過擬合**（**overfitting**）的結果；太大的 $k$ 容易給出**欠擬合**（**underfitting**）的結果。
### KNN 回歸演算法
KNN 回歸演算法的流程和KNN分類演算法類似，但其輸出不是類別，而是一個連續數值：
1. 決定 $k$ 值
3. 求每個鄰居跟自己之間的**距離**
4. 找出跟自己最近的 $k$ 個鄰居，**對這些鄰居的值取平均，作為自己的值**

我們可以發現，在KNN回歸演算法中，$k$ 的選擇依舊是核心。越大的 $k$ 同樣傾向於給出越平滑的結果；越小的 $k$ 也越容易 overfitting。以下圖為例（資料共250筆），當 $k=250$ 時回歸的結果永遠都是所有資料點的平均值。

## 距離度量的選擇
對於兩個在空間中的點，分別用向量 $\mathbf{x}$ 和 $\mathbf{y}$ 來表示，我們想要瞭解這兩個點的距離多大，以 $d(\mathbf{x}, \mathbf{y})$ 表示，為此必須定義一個距離的度量（metric），這個距離度量 $d(\mathbf{x}, \mathbf{y})$ 必須滿足以下幾個條件：
1. **非負**
$$
d(\mathbf{x}, \mathbf{y}) \geq 0
$$其中等號只成立於 $\mathbf{x} = \mathbf{y}$ 時。也就是說，兩個不同的點間之距離為正值，且僅在同個點間的距離為零。
2. **對稱性**
$$
d(\mathbf{x}, \mathbf{y}) = d(\mathbf{y}, \mathbf{x})
$$不管先考慮 $\mathbf{x}$ 還是 $\mathbf{y}$，距離要是相同的。
3. **三角不等式**
$$
d(\mathbf{x}, \mathbf{z}) \leq d(\mathbf{x}, \mathbf{y}) + d(\mathbf{y}, \mathbf{z})
$$兩點間的距離是所有路徑裡的最短距離。

### 歐幾里德距離
歐幾里德距離（Euclidean distance），又稱歐氏距離，是我們一般在二維平面上計算距離的常用方法，計算方式如下：
$$
d(\mathbf{x}, \mathbf{y})=
\sqrt{(x_1 -y_1)^2 + (x_2 -y_2)^2 + \dots}=
\sqrt{\sum_i (x_i -y_i)^2}
$$這個公式可以很容易地透過建構直角三角形，並利用畢氏定理來導出。


### 曼哈頓距離
曼哈頓距離（Manhattan distance），又稱為 L1 距離或城市區塊距離，定義如下：
$$
d(\mathbf{x}, \mathbf{y})=
|x_1 - y_1| + |x_2 - y_2| + \dots = \sum_i |x_i - y_i|
$$

曼哈頓與歐幾里得距離：紅、藍與黃線分別表示所有曼哈頓距離都擁有一樣長度（$12$），而綠線表示歐幾里得距離有$6\times \sqrt{2} ≈ 8.48$的長度。

一些scikit-learn支援的距離度量如下：

## 程式實作
程式實作可以參考[這篇](https://ithelp.ithome.com.tw/articles/10197110)，作者介紹了如何使用sklearn提供的API來進行鳶尾花資料集的分類任務。