最新消息

機器學習演算法 – K 近鄰

  K 近鄰(K Nearest Neighbors),我們簡稱 KNN,他是機器學習當中最簡單也 是最直觀的演算法。其觀念是根據資料彼此之間的距離進行分類,距離哪一種類 別最近,就分到哪一類,所以 KNN 常被用於分類問題。

  如下圖 1,KNN 分類演算法的分類預測過程十分簡單並容易理解:對於一個 需要預測的輸入向量 x,我們只需要在訓練資料集中尋找 k 個與向量 x 最近的向 量的集合,然後把 x 的類別預測為這 k 個樣本中類別數最多的那一類。如圖所 示,ω1、ω2、ω3 分別代表訓練集中的三個類別。其中,與x𝑢最相近的 5 個點 (k=5)如圖中箭頭所指,很明顯與其最相近的 5 個點中最多的類別為ω1,因此, KNN 演算法將x𝑢的類別預測為ω1。

圖 1. KNN 演算法分類示意圖(K=5 結果) (圖片來源)

  • KNN 的演算法步驟如下:
    • KNN 中的 K 代表找出距離你最近的 K 筆資料進行分類。
    • 假設 K 是 3,代表找出前三筆相近的資料。
    • 當這 K 筆資料被選出後,就以投票的方式統計哪一種類的資料量最多,然後就被分到哪一個類別。

思想與「近朱者赤,近墨者黑」有異曲同工之妙!

  • KNN 演算法情境舉例:
    政治大學是一間強調因材施教的學校,其教育方針是儘量將同質性高的學 生分成一組,然後進行教學,你如果是一位導師,在新學期收到一位轉學 生,你如何替他/她分組?分組的方式有很多種,例如:此學生傾向於理工 思考、文組思維?你要用什麼樣的方式,將新學生編入適合的組別?
    • 作法:給這位學生考試,發現數學 90 分,國文 50 分,是不是就傾向理工組了呢?

 

▼ 如下表一為政治大學分組考試後,六位學生針對四個科目的考試分數,學校 會依照這個分數來分發所屬的組別。

表一. 學生考試對應所屬組別 

                                    

今天有一位轉學生進來叫 Anderson,也進行了這項分組考試,他的分數如下表二:

表二. 新同學考試結果,要分配哪一個組別? 

我們將套入 KNN 演算法步驟:
假設政治大學使用 KNN 將學生做分組(K = 3),那麼 Anderson 入學之後會被分 到哪一組?

  • Step1:計算距離(歐氏距離):我們將 Anderson 的考試分數與其他每一 位考生之分數距離來計算,如下結果:

    所以 Anderson 與 Frank 之間分數距離為 44.63,距離越小代表性質越相近 (理想值為 0)
    因此我們將 Anderson 對應每一個學生的分數距離都算出 來,如下表三所示:

表三. Anderson 與每一位學生的分數距離 

  • Step2:選取距離較近的 K 個鄰居
    從 Step1 中計算出分數距離,我們可以發現最近最相近的三位學生分別是 Frank, Bob, and Merry,
    對應的組別是理組、理組、商科,下表四所示:

表四. 選取距離較近的 K 個鄰居(K=3)

  • Step3:
    我們選出三個科目:理組、理組、商科,進行投票,可以得到結果, 如下表五:
    理組2票、商科1票
    因此 Anderson 就會被歸類在 「理組」

表五. Anderson 歸類組別結果


以上,就是整個 KNN 的執行過程,新輸入的資料就可以透過 KNN 分群或是分類到適合的群組與類別,而且其分類精確度非常高,很被廣範應用喔!是常被推廣 的演算法。

 

◎ 想想看:
1. 如果今天 Anderson 每一科滿分,他要被分到哪一組?有哪些解決方法?

◎ 補充與延伸:

  • 前面我們用 K = 3,當作例子,我們再進一步去分析,如下圖 2:

圖 2. K=3 分類示意圖 (圖片來源)

  • 那今天選擇 k = 5 情況下,如下圖 3:

 

圖 3. K=5 分類示意圖 (圖片來源)

  • 我們來看 k = 4 的情況,一樣我們會去計算距離,如下圖 4:

 

圖 4. K=4 無法分類結果 (圖片來源)

我們發現結果投票各占一半,k = 4是沒有答案的

因此在使用 KNN,在選擇 K 的時候,通常不會選偶數。

如果我們一直遇到每票且票票等值的情況下,要如何解決?

  • 答:使用「加權投票法」,概念: 距離近的給予比較高的權重,因此在 K = 4 如下圖就會判定歸類藍色水滴類別。

圖 5. K=4 無法分類結果 (圖片來源)

前面所述距離,我們使用歐氏距離(歐幾里德距離),求空間中兩點之間距離計 算大小,如下我們也可以用其它公式來計算兩點距離:

總結:

  • 所以 KNN 不只可以處理離散型的資料,想可以處理連續型的資料。
  • K值選擇為預測準確程度的關鍵,且最好選擇奇數以避免投票平常手的狀 況發生。
    • K 值越大,可能會包含不相關的樣本點進來,K 值太小又會被會為是噪 音的干擾(雜訊),因為參考的樣本數不夠多,通常都會把 K 值控制在 樣本數平方根以下,是最好的結果。
    • 因為我們不知道哪一個 K 值是最好的,我們可以去切割樣本去做交叉 驗證找到適合的 K 值。選擇適合的距離計算方式。

 KNN 的優點:

  • 簡單易懂
  • 資料型態不受限(離散型:取眾數,連續型:取平均值)
  • 在多種類別預測有較好的表現

 KNN 的缺點:

  • 計算本成本高:因為他要不斷地計算點跟點之間的距離
  • 資料不平衡時容易產生預測不準確的狀況發生

參考資料

選擇的能力 – 探索人工智慧的核心 陳永維 李厚均 著 TKB

機器學習首部曲--- K-近鄰演算法 KNN (字幕)

 

撰文者:政大人工智慧與數位教育中心   黃啟賢研究員