AI60問- Q26什麼是k(k-Nearest Neighbor)鄰近算法?

by 提拔我園丁
緯育TibaMe AI小教室-Q26什麼是k(k-Nearest Neighbor)鄰近算法?

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個鄰居的類別頻率,我們可以簡化為:找鄰居 + 投票決定 。

  1. 算距離:給定未知物件,計算它與訓練集中的每個物件的距離
  2. 找近鄰:圈定距離最近的k個訓練物件,作為未知物件的近鄰
  3. 做分類:在這k個近鄰中出線次數最多的類別就是測試物件的預測類別

KNN的優點與缺點

優點

— 訓練時間複雜度比支援向量機之類的演算法低
— 非常簡單的分類算法沒有之一,人性化,易於理解,易於實現
— 適合處理多分類問題,比如推薦用戶
— 理論成熟,思想簡單,既可以用來做分類又可以做迴歸

缺點

— 屬於懶惰算法,時間複雜度較高,因為需要計算未知樣本到所有已知樣本的距離
— 樣本平衡度依賴高,當出現極端情況樣本不平衡時,分類絕對會出現偏差
— 可解釋性差,無法給出類似決策樹那樣的規則

KNN的案例

先前在Q23什麼是決策樹演算法?案例中,提到了披薩店顧客滿意度的例子,若套用在KNN演算法中,又是如何操作?

以披薩外送店的顧客評價滿意度為例,
烤箱溫度與烤箱濕度微特徵作分布圖,
進行KNN的範例推演。

在下圖26-1中,k值設定為2,
也就是要找到最靠近目標7的兩個點(兩個最近的鄰居),
分別得到了編號2與編號6。
編號7和編號2的距離是 d27 = 根號2,
編號7和編號6的距離是d67=3。

當k=2時,
靠近的兩個點落在滿意和不滿意的各有一個,
因此無法推測編號7是滿意或不滿意。
圖26-1,k=2時的披薩外送店顧客評價滿意度之KNN
案例2:檢測學生是否健康。
如下圖26-2所示,
我們有學生1,2,3,4,5(新學生)的相關屬性數據(體重、身高),
其中學生1,2,3,4在具備相關屬性基礎上,
還有目標屬性標籤(是否健康)。

我們的問題是通過對學生1,2,3,4的相關屬性、目標屬性數據進行學習,
然後對學生5(即新學生)是否健康做出預測?
圖26-2 檢測學生是否健康 之KNN

那麼結合該問題,我們應用KNN演算法對其進行求解,那在實際計算之前給出KNN演算法的計算流程步驟:

  1. 未分類標籤數據與已知數據一一計算距離
  2. 在1基礎上,找到最為相近的k個鄰居
  3. 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 

AI資料科學家-三階段全方位學程班
AI資料科學家-三階段全方位學程班

每日5分鐘, 提拔我園丁陪你快速添補AI/資料科學知識與技能。

若您想了解更多AI/資料科學的小知識、及各產業的相關應用,歡迎訂閱TibaMe FB及部落格,或你有其他想了解的主題歡迎在下方留言讓我們知道唷!

緯育TibaMe FB

企業人才數位轉型FB

企業AI、數位人才or平台培訓方案請點選

參考資料

分享這篇文章:
0 comment
2

您也許會喜歡

Leave a Comment

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料