KNN（k-Nearest Neighbor）又被稱為「近鄰算法」， 它是監督式機器學習中分類演算法的一種。KNN的主要概念是利用樣本點跟樣本點之間特徵的距離遠近，進一步判斷新的資料比較像哪一類。KNN中的k值就是計算有幾個最接近的鄰居。
它的核心思想是：物以類聚，人以群分
假設一個未知樣本數據x需要歸類，總共有ABC三個類別，那麼離x距離最近的有k個鄰居，這k個鄰居里有k1個鄰居屬於A類，k2個鄰居屬於B類，k3個鄰居屬於C類，如果k1>k2>k3，那麼x就屬於A類，也就是說x的類別完全由鄰居來推斷出來。
KNN鄰近算法操作步驟
按照距離的遠近順序，統計k個鄰居的類別頻率，我們可以簡化為：找鄰居 + 投票決定 。
- 算距離：給定未知物件，計算它與訓練集中的每個物件的距離
- 找近鄰：圈定距離最近的k個訓練物件，作為未知物件的近鄰
- 做分類：在這k個近鄰中出線次數最多的類別就是測試物件的預測類別
KNN的優點與缺點
優點
— 訓練時間複雜度比支援向量機之類的演算法低
— 非常簡單的分類算法沒有之一，人性化，易於理解，易於實現
— 適合處理多分類問題，比如推薦用戶
— 理論成熟，思想簡單，既可以用來做分類又可以做迴歸
缺點
— 屬於懶惰算法，時間複雜度較高，因為需要計算未知樣本到所有已知樣本的距離
— 樣本平衡度依賴高，當出現極端情況樣本不平衡時，分類絕對會出現偏差
— 可解釋性差，無法給出類似決策樹那樣的規則
KNN的案例
先前在Q23什麼是決策樹演算法？案例中，提到了披薩店顧客滿意度的例子，若套用在KNN演算法中，又是如何操作？
以披薩外送店的顧客評價滿意度為例， 烤箱溫度與烤箱濕度微特徵作分布圖， 進行KNN的範例推演。 在下圖26-1中，k值設定為2， 也就是要找到最靠近目標7的兩個點(兩個最近的鄰居)， 分別得到了編號2與編號6。 編號7和編號2的距離是 d27 = 根號2， 編號7和編號6的距離是d67=3。 當k=2時， 靠近的兩個點落在滿意和不滿意的各有一個， 因此無法推測編號7是滿意或不滿意。
案例2：檢測學生是否健康。 如下圖26-2所示， 我們有學生1,2,3,4,5（新學生）的相關屬性數據（體重、身高）， 其中學生1,2,3,4在具備相關屬性基礎上， 還有目標屬性標籤（是否健康）。 我們的問題是通過對學生1,2,3,4的相關屬性、目標屬性數據進行學習， 然後對學生5（即新學生）是否健康做出預測？
那麼結合該問題，我們應用KNN演算法對其進行求解，那在實際計算之前給出KNN演算法的計算流程步驟：
- 未分類標籤數據與已知數據一一計算距離
- 在1基礎上，找到最為相近的k個鄰居
- k個鄰居的類別統計，將最多類別的標籤賦值給未分類標籤數據
接下來，我們仍舊以上述學生1,2,3,4,5（新學生）為例，假設自定義k值為3，距離採用歐式距離計算，用x代表體重，y代表身高。
那麼結合算計步驟：
第一步：算新學生與所有已知學生的距離
第二步：根據距離排序，找到最相近的k=3個鄰居
即與學生5(新學生)最相近的k=3個鄰居分別為:學生1，學生2，學生4。
第三步：統計鄰居類別
也就是2個健康，1個亞健康，採用少數服從多數原則，那麼在k=3的前提下，學生5(新學生)可判別為健康狀態。
以上即為KNN演算法實例計算全部過程，由於演算法的K值可自定義，所以k可以取2,3,4,5,6,7……。其計算過程仍舊可以參考上述計算過程。
緯育TibaMe已經有10萬人次來學習AI/資料科學知識或技術，若你想進一步了解或學習 AI / 資料科學的相關知識或技能，歡迎來TibaMe 👉 https://www.tibame.com/eventpage/ai_datascientist
每日5分鐘， 提拔我園丁陪你快速添補AI/資料科學知識與技能。
若您想了解更多AI/資料科學的小知識、及各產業的相關應用，歡迎訂閱TibaMe FB及部落格，或你有其他想了解的主題歡迎在下方留言讓我們知道唷！
參考資料
- 每日頭條–幾分鐘了解一下K近鄰算法（KNN）原理及實踐
- 每日頭條–機器學習-KNN（k-nearest neighbor）最近鄰算法
- KNN演算法優缺點
- 鴻海教育基金會-人工智慧導論
- 詳細的KNN算法原理步驟