KNN演算法

Posted By Mr. Thursday 

各位看到標題,如果沒有聽過KNN演算法,會不會覺得疑惑:KNN是甚麼呢?是不是CNN看久了,就變成DNN、ENN、最後變成KNN了呢?當然不是啦 XD!KNN全名是k-th nearest neighbor,中文意思是「第k位最接近的鄰居」。甚麼是「第k位最接近的鄰居」呢?假設在一個廣場上,有100個朋友,每位朋友都是你的鄰居,最接近你的鄰居,就是「第一位距離最近的鄰居」了,比第一位稍微遠一點的鄰居,就是「第二位距離最近的鄰居」了,以此類推,第10位距離最近的鄰居,就是k=10的時候了。

至於KNN演算法是甚麼,又有甚麼特別呢?之前提過了「人工智慧與機器學習」。KNN演算法就是一種機器學習的演算法。在進一步探討甚麼是KNN演算法之前,我們先介紹一下甚麼是演算法。演算法可以看成是一種「步驟」的集合。舉例來說:我們煮一道菜,第一步是先洗菜,第二步切菜,第三步放油,第四步快炒,第五步加點水悶幾分鐘,第六步再炒幾分鐘,最後第七步加鹽和味精,然後炒到菜煮熟為止。演算法就是這樣子,把工作分成詳細的步驟,有些步驟可能會重複執行,像是菜不夠鹹,就再加點鹽,一直到口味對了為止。有時候會依照情況的不同而有不同的步驟,像是過馬路的時候,如果是紅燈,我們重複「等待」的步驟,如果是綠燈,我們會進行「走路過斑馬線」的步驟。

由於電腦本身就是執行一道一道的指令,因此演算法詳細列出來的步驟,已經很接近電腦執行工作的語言。至於KNN演算法又是由哪些步驟所組成的呢?在這之前,我們再稍微提一下KNN演算法和機器學習之間的關係。之前在「人工智慧與機器學習」的文章中稍微提了一下,機器學習就是讓機器接收外界輸入的資料以後,依照某種演算法(一些步驟的集合),訓練出一種模型,這個模型是一種從資料學習出來的東西,有了這個東西,機器看到新的資料的時候,不會空空如也,而是有某種程度的經驗和智慧,可以了解新的資料了。

在這個過程中,有兩種訓練的方法:監督式和非監督式的學習。所謂監督式的學習,是指在訓練機器學出一個模型的之前,會先有一段訓練的時間,在這段時間裡面,每一筆資料會有一個正確答案,機器學習以後,會根據答案調整自己學習的方法。舉例來說:我們學習數學的時候,可能會練習一些題目,練習以後,會對一下答案,如果算錯了,就會調整自己的計算方式,或是檢查有沒有粗心算錯的地方。機器學習裡面的監督式學習正是如此,訓練之後,才開始有預測的階段,這個時候輸入機器的資料沒有正確答案,機器必須根據他之前學習的模型來判斷,預測新的資料應該輸出哪一個正確答案,而不像再訓練階段的時候,輸入的資料會有人類提供的正確答案了。

另外一種非監督式的學習,則是連訓練的階段都沒有。我們只給予機器簡單的學習方法,或是一個簡單的價值觀,然後就開始把資料輸入機器,讓機器自行判斷正確答案。舉例來說:我們還沒上小學之前,已經有了一些基本的說話能力。我們從嬰兒開始啞啞學語,我們並不曉得,甚麼是主詞、動詞、受詞。我們可能連注音符號都不曉得。但是我們的父母一直跟我們講話,我們有一天就突然蹦出一些詞,第一句可能是「媽媽」!第二句可能是「爸爸」!之後可能開始簡單的對話,最後在上小學之前,我們至少會問簡單的問題,老師講的句子也都聽的懂,才有辦法起立、立正、敬禮,還有學習注音符號,練習寫字了。非監督式的學習就是類似如此,我們給機器資料簡單的規則價值觀,剩下的就交給機器一邊學習一邊預測正確答案是甚麼了。

KNN就是一種非監督式的學習法。首先,我們要替每一筆資料定出一個位置,像是下圖:

我們的目標是要機器學會怎樣子分出紅點和藍點。每個點在平面上有個位置,分別用(x,y)來代表,舉個例子來說:紅點代表女生的大頭照,藍點代表男生的大頭照,x軸代表照片中頭髮的長度,y軸代表照片中臉面積的大小。現在機器已經知道某些點是男生的大頭照(藍色的點)、某些是女生的大頭照(紅色的點)。當一張新的大頭照輸入機器以後(圖片裡面打問號沒有顏色的點),KNN演算法就先計算這個點,和其他已經知道男生或女生的資料點之間的距離(圖裡面畫了幾條線代表在計算距離)。今天KNN的K如果設定成1,也就是(1-NN)的話,代表機器會找第一位距離最近的點,然後看這個點是男生(圖中藍色點)或是女生(圖中紅色點)。如果這個點是男生,那麼我們也預測剛才打問號的這個點(新的資料點)是男生的大頭照。之後這個問號點就變成藍色的,然後繼續反覆同樣的動作在下一個新輸入的資料點,預測新的問號點是男生或是女生。

如果k=3,也就是使用3-NN學習,情況會變成怎樣子呢?機器同樣先計算圖中打問號的點和各個顏色的點的距離,接著選出前三名距離最近的點,然後看看裡面紅色的點比較多(2個以上的點是紅色)還是藍色的點比較多(2個以上的點是藍色),如果藍色點比較多,就判斷這個新問號點,是男生的大頭照了。以此類推,會有5-NN,7-NN,9-NN學習法,端看問題的需要而定。

KNN學習法就是如此。他的好處是簡單,而且是一種非監督式學習方法,讓人們省去準備訓練資料(資料和對應的正確答案)的時間。然而KNN也有他困難的地方。首先是每個機器學習法都要面對的問題,就是選擇特徵,用剛才的例子,我們用頭髮長度和臉大小的面積來讓機器學習,如果遇到留長髮的男生或是輪廓比較大的女生,可能就判斷不大出來:或是說,如果我們改用膚色來判斷,比較白的是女生,比較黑的是男生,萬一這個規則拿來判斷歐洲人,可能也不大行。

另一個困難則是距離的訂定。剛才的例子中,頭髮長度如果用公分來算,差距1公分的頭髮長度,可能有辦法分辨男女。如果是用頭髮的顏色來判斷的話,那麼顏色的「距離」就不知道要怎麼定了,或許可以定成光線頻率的距離,那機器還可以學習,不然「紅色」和「黑色」兩種顏色之間的距離,可能就不知道要怎麼定了。這個問題在語意的問題上,也特別重要。如果我們要判斷兩個詞是否屬於同一類東西,但是只看兩個詞差別的字數,用相異字數的個數來當做座標上的距離,就會出現一些意想不到的狀況。譬如說:「巴黎鐵塔」、和「巴黎蛋塔」,只差了一個字,和「巴黎聖母院」差了三個字,所以「巴黎鐵塔」和「巴黎蛋塔」比較接近,屬於同一類,那麼機器學出來的東西,可能就不是我們想要的了。

因此,KNN是個好用的機器學習法,然而在某些問題上,仍然有改進的空間了!希望大家讀完這一篇以後,都能了解KNN演算法囉!

總結

  1. 演算法是一些步驟的集合,包含重覆部分與依條件執行的部分
  2. 機器學習可分為監督和非監督兩種學習法,差別在於有無訓練資料(訓練資料裡面有正確答案給機器參考)
  3. KNN是一種非監督式學習演算法,是參考最近k個鄰居的答案來做判斷
  4. 某些問題上(例如語意問題)以及特徵的選擇,是使用KNN需要注意的地方

參考資料

  1. KNN Algorithm (Wikipedia)
  2. 演算法Algorithm (Wikipedia)
喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!
  • Gage

    上了很棒的一課~感恩^^

  • Gage

    上了很棒的一課~感恩^^

  • ZEEBRA

    我想還有幾個困難點(其實困難點會依據資料特性產生,所以可能也很難完整列舉就是了),例如要是男生跟女生的數量差異相當大而且相當不對稱,在空間中紅色散佈極為廣,而藍色集中在一個很小的區域,那這時候預測也會變得不可靠,因為以空間來說歸類在紅色的機率會大增。另外如果是以議題來看,如果我們是做癌症的預測,然而在大多人中只有少部分人有罹患癌症的可能性,在這種不對稱資料中誤判的成本更會隨著資料分佈不對秤而加大。

    另外要是初始資料是完全對稱的,這時候的偏誤將會是新資料加入的順序所產生的,假使資料完全左右對稱,新加入node的順序由偏向左方的點開始加入的話,那麼最終學習的結果也是會形成一個向左邊偏誤的結果。

    由於有這麼多的限制與問題存在,這個領域才不斷有人做改良,產生更多有趣的方法。

  • ZEEBRA

    我想還有幾個困難點(其實困難點會依據資料特性產生,所以可能也很難完整列舉就是了),例如要是男生跟女生的數量差異相當大而且相當不對稱,在空間中紅色散佈極為廣,而藍色集中在一個很小的區域,那這時候預測也會變得不可靠,因為以空間來說歸類在紅色的機率會大增。另外如果是以議題來看,如果我們是做癌症的預測,然而在大多人中只有少部分人有罹患癌症的可能性,在這種不對稱資料中誤判的成本更會隨著資料分佈不對秤而加大。

    另外要是初始資料是完全對稱的,這時候的偏誤將會是新資料加入的順序所產生的,假使資料完全左右對稱,新加入node的順序由偏向左方的點開始加入的話,那麼最終學習的結果也是會形成一個向左邊偏誤的結果。

    由於有這麼多的限制與問題存在,這個領域才不斷有人做改良,產生更多有趣的方法。

  • CharlieL

    我必須指出來,在一般我所看到的文件中,k Nearest Neighbor 並不是非監督(unsupervised)的方法。實際上,在 wikipedia 裡

    http://en.wikipedia.org/wiki/Supervised_learning

    很明確的把 kNN 列為 supervised 的方法。一般 supervised 和 unsupervised 的分別,是前者有資料的標記(label),像您的例子裡的紅點或藍點。而 unsupervised 的方法,則是連點的顏色都不給,由機器自行歸納。所以您舉的例子,其實是個 supervised learning 的例子,因為訓練資料裡,其實是有標記/答案的。

  • CharlieL

    我必須指出來,在一般我所看到的文件中,k Nearest Neighbor 並不是非監督(unsupervised)的方法。實際上,在 wikipedia 裡

    http://en.wikipedia.org/wiki/Supervised_learning

    很明確的把 kNN 列為 supervised 的方法。一般 supervised 和 unsupervised 的分別,是前者有資料的標記(label),像您的例子裡的紅點或藍點。而 unsupervised 的方法,則是連點的顏色都不給,由機器自行歸納。所以您舉的例子,其實是個 supervised learning 的例子,因為訓練資料裡,其實是有標記/答案的。

  • CharlieL大神說得沒錯,KNN本身是supervised learning,也許Thursday在寫KNN的時候,不小心想到K-means去了?另一方面,superivised和unsupervised在本質上也相當不同,唯有在相當少數的情況下,我們可以把unsupervised learning的問題轉換成supervised learning,例如說在處理density estimation的問題時,我們可以轉換該問題變成是supervised function approximation的問題,當然,這又是另一個故事了。

  • CharlieL大神說得沒錯,KNN本身是supervised learning,也許Thursday在寫KNN的時候,不小心想到K-means去了?另一方面,superivised和unsupervised在本質上也相當不同,唯有在相當少數的情況下,我們可以把unsupervised learning的問題轉換成supervised learning,例如說在處理density estimation的問題時,我們可以轉換該問題變成是supervised function approximation的問題,當然,這又是另一個故事了。

  • 非常感謝CharlieL的指正
    我會找個時間寫一下更正錯誤的敘述
    剛才看了Wikipedia之後
    也才發現k-NN是instance-based learning
    但是因為資料有label…所以是supervised learning了
    有時間我也會再翻翻課本裡面對於supervised/unsupervised learning的敘述
    也謝謝CharlieL讓我不至於錯的連自己都不知道了
    謝謝啦!

  • 非常感謝CharlieL的指正
    我會找個時間寫一下更正錯誤的敘述
    剛才看了Wikipedia之後
    也才發現k-NN是instance-based learning
    但是因為資料有label…所以是supervised learning了
    有時間我也會再翻翻課本裡面對於supervised/unsupervised learning的敘述
    也謝謝CharlieL讓我不至於錯的連自己都不知道了
    謝謝啦!

  • Pingback: Ben Crox on Blog » 看得明白的請舉手()

  • Pingback: 本體論: 讓舉一反三變得可能 - MMDays()

  • Pingback: Research & Development » 什麼是機器學習(Machine Learning)?()

  • Jtop0

    太好了 ,浅显易懂!赞一个!

  • Ken

    好屌,非專業領域的人應該都可以看懂!這種文章時在少有

  • neketsushonen

    太清楚了!非總感謝!

  • 庭鋒 朱

    非常淺顯易懂,感謝你