發信人: LinuxBoy.bbs@ptt2.cc (LinuxBoy.bbs@ptt2.cc), 看板: LinuxBoy
標 題: [分享] KNN演算法
發信站: Group.NCTU.edu.tw (Wed May 16 19:34:27 2007)
轉信站: SayYa!Group.NCTU!grouppost!Group.NCTU!ptt2.cc!LinuxBoy.bbs
Origin: group.nctu.edu.tw
作者: BBIO (mustard seed) 看板: AAAAAAAA
標題: [分享] KNN演算法
時間: Wed May 16 02:42:41 2007
KNN演算法
http://mmdays.wordpress.com/2007/05/16/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就是一種非監督式的學習法。首先，我們要替每一筆資料定出一個位置，像是下圖：
http://www.vias.org/tmdatanaleng/img/hl_knn.png
我們的目標是要機器學會怎樣子分出紅點和藍點。每個點在平面上有個位置，分別用
(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演算法囉！
總結
演算法是一些步驟的集合，包含重覆部分與依條件執行的部分
機器學習可分為監督和非監督兩種學習法，差別在於有無訓練資料(訓練資料裡面有正確
答案給機器參考)
KNN是一種非監督式學習演算法，是參考最近k個鄰居的答案來做判斷
某些問題上(例如語意問題)以及特徵的選擇，是使用KNN需要注意的地方
參考資料
KNN Algorithm (Wikipedia)
http://en.wikipedia.org/wiki/Nearest_neighbor_(pattern_recognition)
演算法Algorithm (Wikipedia)
http://en.wikipedia.org/wiki/Algorithm
—
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 61.230.1.51
※ [1;32mterris [0;32m:轉錄至看板 SmileSeven [m 05/16 02:49
※ [1;32mlinkent [0;32m:轉錄至某隱形看板 [m 05/16 02:57
※ [1;32mAsh [0;32m:轉錄至某隱形看板 [m 05/16 02:57
※ [1;32medcyc [0;32m:轉錄至某隱形看板 [m 05/16 03:05
※ [1;32mhymanguo [0;32m:轉錄至看板 IceSugar [m 05/16 03:08
※ [1;32mvicall [0;32m:轉錄至看板 vicall [m 05/16 03:12
※ [1;32mLITTLEN [0;32m:轉錄至某隱形看板 [m 05/16 03:22
※ [1;32mogau [0;32m:轉錄至某隱形看板 [m 05/16 03:32
※ [1;32mMagicFX [0;32m:轉錄至某隱形看板 [m 05/16 03:32
※ [1;32mCharlieL [0;32m:轉錄至看板 learner [m 05/16 04:32
※ [1;32mbubblet [0;32m:轉錄至某隱形看板 [m 05/16 04:36
※ [1;32measygo [0;32m:轉錄至看板 easygo [m 05/16 04:48
[1;31m→ [33myoubet [m [33m:借轉謝謝^^ [m推 05/16 06:58
※ [1;32myoubet [0;32m:轉錄至看板 matrix [m 05/16 06:58
※ [1;32maulx8x8 [0;32m:轉錄至看板 murmurmiao [m 05/16 07:26
[1;31m→ [33mlhp [m [33m:supervised/unsupervised不是這樣定義的，請看原網頁的回覆 [m推 05/16 08:18
※ [1;32mjai166 [0;32m:轉錄至看板 jai166 [m 05/16 10:00
※ [1;32mwrm [0;32m:轉錄至看板 NeverKnow [m 05/16 10:15
※ [1;32mnalthax [0;32m:轉錄至某隱形看板 [m 05/16 10:36
※ [1;32mABJones [0;32m:轉錄至看板 ABJones [m 05/16 11:49
※ [1;32mtbuabsas [0;32m:轉錄至看板 Tubabrabra [m 05/16 12:59
※ [1;32mgralin [0;32m:轉錄至看板 mgt [m 05/16 14:04
※ [1;32mgilberthsu [0;32m:轉錄至看板 gilberthsu [m 05/16 19:07