[R] ML4B 課堂重溫 - 淺談 KNN (K-th Nearest Neighbors) 算法

將今個星期二的 R Machine Learning 堂記錯成星期三，錯過最重要的最後一堂(哭)。 原本想打得太慢的記錄可以等埋最後一堂。算了吧.... 當上一堂講了Regression model，第3堂開始講分類Classification的問題。從使用 KNN (K-th Nearest Neighbors) 算法，在Class套件中的knn() 開始，一路講了 Logistics regression 的 glm()、分類樹的rpart()、支持向量機（Support Vector Machine）的svm()，最後在垃圾郵件的分類時，提到為中文句子斷詞的JiebaR套件。

這種分類問題的簡單例子，例如你找來了100個男生的資料，包括資產、收入、樣貌、才華、談吐等評分。再找女生們去評定他是否「荀盤」。有了這組Training Set的數據，可以用來訓練你的電腦中的一個「荀盤分類器」。讓它透過學習這群女生的判斷結果，從而當有新一筆資料(男生)時，可以從他的「Package」判別他是否女生心目中的荀盤。又或者，找出要成為荀盤的條件，看看你....在哪方面可以改進改進。

How a Math Genius Hacked OkCupid to Find True Love

拿KNN 算法來解釋，這算法是利用特徵空間中"距離"最近的K個鄰居去預測目標（或者是你）的分類。例如，當相近的5個近鄰中有3個是＋，2個是－，就預測自己也是＋ 。就是一種物以類聚，人以群分的想法。當然這鄰居不是指在你生活圈子中身邊附近的人（但大概你們也有某些相似之處），而是考慮上面所收集的一組多維度的「Package」中各個因素的接近程度。

k=3：預測= ▲
k=5：預測= ■

不過在面對不同特徵(features)時，總不能把樣貌的1分、身高的1厘米、收入的\$1 HKD同等看待。一個方法是先將所有特徵的量度做Normalization. 例如 $ \frac{X-\bar{X}}{std(X)}$ 或者$\frac{X-\bar{X}}{Spread(X)}$ 。然後，就算是同一特徵之下，銀行戶口裡只有 \$10,000港元資產 和 擁有\$10,000K 港元資產的人，那個1蚊港幣的重要性很不同，這是經濟上Marginal Utility，或者行為金融中的效用函數Utility Function，例如：$U_{\lambda}(X)=\frac{X^{\lambda}-1}{\lambda}$。另外，又或者你會明白高得來不能太瘦，都要身型健碩，考慮: $BMI=體重/身高^2$，這類用兩個特徵交互去建立一個新的特徵，等等⋯⋯這些統統都是預先對X做的變換。

多維度之下的距離該怎麼算呢？對於距離的計法可以有很多，簡單地將3維空間中的距離推廣，就是典型是歐氏距離：$d(A,B)=\sqrt{\sum_i (A_i-B_i)^2}$。其他變型就有不同的距離量尺，例如 $d(A,B)=\sqrt{\sum_i  | A_i-B_i |}$。不過，如非必要也不必多弄複雜化的事，一般歐氏距離就夠好理解了。"Class"套件中的knn()就是用它，如果其他套件或者自行寫的話才會用的。

Class套件中的 knn()是給你用來做預測的，一個knn()的用法是像這樣的

knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE)

當中 train 是只說是已有的Traning Set所使用的特徵；test 是新測試者的特徵；cl 是Training Set 的荀盤分類；k 就是要參考多少個近鄰；l 是可選撰是否要 k 個當中有一個特定的票數 l 以上才分類；prob 是當只告訴妳 是／否 還不滿意，更好是給妳一個「荀盤分數」，告訴妳C君有60%像荀盤，R君有100%像荀盤；use.all 是當多過幾個第k-th位的近鄰時是否把它們全都考慮。

課堂例子：

## Classification problem: which your y is categorical.
## Yes / No
require(tidyverse)
### generate some rubbish data
gp1 <- data_frame(x = rnorm(300, mean = 9, sd = 5), y = rnorm(300, mean = 3, sd = 2), gp = 'A')
gp2 <- data_frame(x = rnorm(300, mean = 3, sd = 5), y = rnorm(300, mean = 10, sd = 3), gp = 'B')
rubbish <- rbind(gp1, gp2)[sample(1:600, size = 600),] 

ggplot(rubbish, aes(x = x, y = y, color = gp)) + geom_point()
ggplot(rubbish, aes(y, fill=gp)) + geom_histogram(binwidth = 0.5)
ggplot(rubbish, aes(x, fill=gp)) + geom_histogram(binwidth = 0.5)

### Split the data
set.seed(777)
train <- sample(1:600, size = 500)

## KNN
require(class)
knn(rubbish[train, -3], rubbish[train, -3], rubbish$gp[train], k = 3)

基本上，我們已經可以建立一個分類模型。但這個好的模型嗎？怎樣才是一個好的模型？很重要，所以再說一次：「我們是為了做預測的」，為了用來為新的/未分類的男生去預測他的分類。無論KNN 或者其他的模型，我們在建模的時候都只會用大部份的數據(大約是2/3吧)當Training Set，而非所有的數據，剩下的1/3就是我們的Testing Set，用來測試一下這個「荀盤分類器」模型在預測時的準確度。好的模型應該在Training Data 和Testing Data時的準確度都差不多的高（愈接近100%愈好）；低（接近50%）的話就和其實在亂估沒分別，可能是一個Underfit的模型；更低（接近0%）的話，恭喜妳找到一個廢男分類器，大概一生中也總會算到幾個的，好好的善用吧⋯⋯如果Training Data 和Testing Data的準確度很大分別呢？今次才引發起我留意這個問題。較少出現的是Testing比Training更準，想想看，這就是撞彩吧！就應該要再研究研究這些數據和模型。較多出現的是Testing比Training差，其實就是一個不太好的模型，可能對Training Data 的特徵 Overfit了。

table(knn(rubbish[train, -3], rubbish[train, -3], rubbish$gp[train], k = 3), rubbish$gp[train])
table(knn(rubbish[train, -3], rubbish[-train, -3], rubbish$gp[train], k = 3), rubbish$gp[-train])

得到一個好的模型，才有意思去了解它，不過怎樣演繹，也是跟你的模型有關的。如果是Logistic Regression的話，可以劃出一條分界線，和得出每個特徵因素的影響力；分類樹的話就是什麼回溯什麼因素可以讓你較大機會跌入那個分類；Support Vector Machine像是容許一條彎彎曲曲的分類線，去仔細處理邊界上的情況。這裡的是KNN模型，試好了K值、特徵因素、型式、距離等之後，其實就沒有什麼訓練一個分類器的工夫，其他模型不一定這樣的。而KNN背後的想法就是用最近的K點來預測你嘛，當知道什麼特徵能很好地預測分辨的話，那就要看看自己怎樣最少改變才能走到「最近」的荀盤堆。(記往：不只是「結識」這種意義的埋堆，而是你要擁有荀盤堆中之人的特質)。