KNN ( classification )

K Nearest Neighbor

經由前面的文章瞭解到分類與回歸模型的評估指標有哪些，接著就讓我們進到機器學習模型的介紹吧！

目錄
1. KNN介紹
2. KNN演算法流程
  2.1 決定 K 值
  2.2 計算新樣本與鄰居間的距離
  2.3 新樣本類別預測
3. 參考資料

1. KNN 介紹

本篇將介紹機器學習中相對單純的一種演算法－KNN ( K Nearest Neighbor, K-近鄰演算法)，KNN 屬於監督式學習並可用於分類及回歸問題上，這次主要會介紹 KNN 分類器的作法。

KNN 在分類時是基於特徵相似度來預測新加入樣本的類別，簡單來說，KNN 就是將一個新樣本加入後，去看附近大多數的人長怎樣就判定他是同一群的人，正所謂「物以類聚、人以群分」啊！

如 [圖1] 所示，一群已分類好的樣本群（Class A和 Class B）中加入了一個未知分類的紅色星星樣本，KNN 就會透過附近的鄰居們來判定紅色星星屬於類別 A 還是 B。

[圖1] 圖片來源：k-Nearest Neighbors (KNN) in Python

那接著就來講講 KNN 判定的流程吧！

2. KNN 演算法流程

用 KNN 做分類任務時，必定先擁有標記好的資料，因 KNN 的運算較簡易，可在訓練前先去除類別中的雜訊，以達到較好的分類結果。

K Nearest Neighbor 意思為用新樣本的 K 個鄰近樣本來預測新樣本的所屬類別，因此首先需決定 K 值大小，如 [圖1] 所示：

• 當 K = 3 時有「1 個藍點、2 個綠點」，紅色星星歸類至 Class B
• 當 K = 6 時有「4 個藍點、2 個綠點」，紅色星星歸類至 Class A

2.1 決定 K 值

K 值為 KNN 中唯一需要調整的超參數，掌控著模型預測的準確度，因此在 K 值得選擇上可不能亂來啊！而該如何為不同的 Dataset 決定合適的 K 值並沒有一定的流程，但以下幾個是可以供大家參考的作法：

1. 使用總樣本數的平方根作為 K 值：sqart(n)
2. 使用奇數：因偶數會有「同票」的情形，也就是不同類別數量相等導致決定不了的情況，所以可以盡量避免選擇偶數
3. 多嘗試幾組 K 值並比較模型預測的準確率
4. 避免選擇過大或過小的數值

過小的 K 值（如1）：噪點很大，且可能會將新樣本預測為異常值（Outlier）
過大的 K 值：會不斷的過濾掉較少樣本的類別

例：總共有 16 個樣本，平方根為 4 ，且要避免選擇偶數，則 K 值可為3 or 5

除了以上較簡易的 K 值判斷方式之外，也能運用訓練誤差 (training error)以及驗證誤差 (Validation error) 來觀察不同 K 值的結果，透過驗證誤差曲線 (Validation error curve) 的最低點來找到理想的 K 值！

更詳細的內容可以參考這一篇文章來學習：K Nearest Neighbors — 簡介。

2.2 計算新樣本與鄰居間的距離

因 KNN 是基於特徵相似度來預測新樣本的類別，在樣本空間中兩個樣本間的距離就代表著特徵的相似程度，距離越小相似程度越高 ; 反之，距離越大相似程度越低。

所以 KNN 會先計算所有樣本與新樣本之間的距離，這樣將距離由近排到遠就能得知新樣本周遭的樣本有哪些，同時也是特徵相似程度高的幾個樣本。

[圖2] 圖片來源：k-Nearest Neighbors

計算距離的方式通常會使用的是歐幾里得距離 ( Euclidean distance )

歐幾里得距離 ( Euclidean distance )
座標(x1,y1)、(x2,y2)兩點之間的距離：√[(x1-x2)²+(y1-y2)²]

除此之外，還可使用閔可夫基斯距離 ( Minkowski Distance )、曼哈頓距離 ( Manhattan Distance )

2.3 新樣本類別預測

當決定好 K 值，並計算好樣本之間的距離後，就能找到與新樣本最相近的 K 個樣本，最後進行類別的判定：

1. 看選定的 K 個鄰居中哪一種類別佔的數量最多，就會將新樣本判定為該類別。（因此前面 K 值選擇奇數可以避免很多同票的情況）
2. 若還是遇到類別數同票時，我們則可選擇將新樣本歸類至其中一個類別中，或是直接選擇不歸類

知道了整個 KNN 的流程後，我們再來看一次前面這張圖，以及預測結果。

當 K = 3 時有「1 個藍點、2 個綠點」，紅色星星歸類至 Class B

當 K = 6 時有「4 個藍點、2 個綠點」，紅色星星歸類至 Class A

大家有沒有發現，K 值的決定是會直接影響至預測結果的，因此決定 K 值一定要小心，最好反覆測試後再決定！

3. 參考資料

1. StatQuest: K-nearest neighbors, Clearly Explained
2. KNN Algorithm In Machine Learning | KNN Algorithm Using Python | K Nearest Neighbor | Simplilearn
3. [Day 10] 近朱者赤，近墨者黑 — KNN
4. [Machine Learning] kNN分類演算法
5. K Nearest Neighbors — 簡介

教育部補助大專院校STEM領域及女性研發人才培育計畫目標為建構一個「以智慧物聯技術與實務應用為基礎的教育環境和實作場域」，並規劃出符合此STEM教育領域的創新特色課程，以畢業前進入企業實習的方式，讓學生了解相關產業界所面對的問題，再輔以業界實作場域的教育訓練活動，共同帶領學生發展出動手做、判斷與解決問題的相關技能；本計畫也規劃讓學生以專題實作的組隊方式，跟業界協力領導學生對外參與智慧物聯技術的應用競賽，不僅可以累積學生實務開發的能力，更能激發其潛能來幫助企業解決所面臨的難題。

Data Science Meetup 台灣資料科學社群的使命是「為資料科學人士與企業創建經濟機會」。我們相信大數據蘊藏著巨量的信息和價值，如何處理好大數據並發掘其潛藏的商業價值，就要靠資料科學有效的應用。21世紀是資料科學決勝時代，我們社群將為大家提供與資料科學相關的最新技術和資訊實戰攻略，並透過全球業界人士和學者幫助相關職業規劃與挑戰，社群活動包含

• 台北實體版聚
• 線上版聚
• Mentorship Program

歡迎加入我們社團瞭解更多資訊：
https://www.facebook.com/groups/datasciencemeetup