近朱者赤，近墨者黑，相同條件的人總會臭味相投。我們已經在遺漏值介紹過k近鄰法(K-Nearest Neighbours, knn)插入遺漏值的方法。k近鄰法其實是將條件相近的人事物歸類在一起，概念其實非常簡單。例如在同一個社區中的居民會有相似的生活、經濟、文化；同一種動植物會有相似的特徵、生活習性。k近鄰法就是用這種概念來將資料分類。
k近鄰法在機器學習與人工智慧中占有重要地位。例如想要讓電腦區分貓狗照片，我們只要輸入臉型、腳掌、嘴吧等貓狗特徵資料，k近鄰法會將相似特徵歸類。如果再有新照片，電腦就能依據圖中特徵與資料庫比對，判斷出照片中的到底是貓還是狗。相同的技術也可以應用在車輛的自動駕駛，判斷前方到底是來車還是行人、建築物。
與集群分析一樣，k近鄰法也是透過歐幾里德距離(Euclidean distance)來分析資料，可說是最簡單的機器學習法。
腫瘤是良性還是惡性？
我們以醫療上的應用來說明k近鄰法，引用的資料來自github.com/bikramb98上的Prostate_Cancer.csv。這是一個包含100名病患攝護腺腫瘤的診斷資料，記錄腫瘤是良性還是惡性(diagnosis_result)、腫瘤半徑(radius)、紋路(texture)、周長(perimeter)、面積(area)、平滑度(Smoothness)、密實度(Compactness)、對稱度(symmetry)、碎形維度(fractal dimension)。
假設現在有另一名新的病患，測得他的腫瘤半徑30、紋路20、周長150、面積1100、平滑度0.140、密實度0.250、對稱度0.200、碎形維度0.080，請問他的腫瘤是惡性還是良性？我們可以用k近鄰法把他的腫瘤數據拿來和資料庫相比，看看他的腫瘤比較像惡性還是良性。首先載入資料：
> prostate<-read.csv("c:/Users/USER/Downloads/Prostate_Cancer.csv", header=T, sep=",")
> head(prostate)
id diagnosis_result radius texture perimeter area smoothness compactness symmetry fractal_dimension
1 1 M 23 12 151 954 0.143 0.278 0.242 0.079
2 2 B 9 13 133 1326 0.143 0.079 0.181 0.057
3 3 M 21 27 130 1203 0.125 0.160 0.207 0.060
4 4 M 14 16 78 386 0.070 0.284 0.260 0.097
5 5 M 9 19 135 1297 0.141 0.133 0.181 0.059
6 6 B 25 25 83 477 0.128 0.170 0.209 0.076
資料標準化
從上述資料可以看到，腫瘤大小、形狀、面積會影響診斷結果，M代表Malignant惡性、B表示Benign良性。因為測量單位不同，為了計算歐幾里德距離，我們先用scale()指令將資料標準化，並且把用不到的病患id編碼刪除。
> prostate[,c("radius", "texture", "perimeter", "area", "smoothness", "compactness", "symmetry", "fractal_dimension")]<-scale(
+ prostate[,c("radius", "texture", "perimeter", "area", "smoothness", "compactness", "symmetry", "fractal_dimension")]) #將腫瘤半徑、紋路、周長、面積、平滑度、密實度、對稱度、碎形維度數據標準化
> prostate<-prostate[,-c(1)] #刪除病患id
> head(prostate)
diagnosis_result radius texture perimeter area smoothness compactness symmetry fractal_dimension
1 M 1.2604800 -1.1997026 2.2900742 0.7854596 2.750354 2.4745041 1.5861604 1.7556197
2 B -1.6089054 -1.0071340 1.5298135 1.9490108 2.750354 -0.7801312 -0.3953220 -0.9434462
3 M 0.8505678 1.6888269 1.4031034 1.5642883 1.520993 0.5446199 0.4492443 -0.5753918
4 M -0.5841249 -0.4294281 -0.7932053 -0.9911455 -2.235388 2.5726338 2.1708601 3.9639463
5 M -1.6089054 0.1482778 1.6142869 1.8583039 2.613758 0.1030362 -0.3953220 -0.6980766
6 B 1.6703922 1.3036897 -0.5820218 -0.7065133 1.725886 0.7081694 0.5142109 1.3875652
準備分析資料
接下來我們將資料分為兩大部分，用亂數抽取70%的資料，作為k鄰近法的學習模型。剩餘30%的資料將用來驗證k近鄰法的準確度，這30%的資料也可以視為要k近鄰法判斷腫瘤惡性或良性的病患。
> set.seed(1234) #設定亂數種子
> sample_size<-round(0.7*nrow(prostate)) #設定樣本大小為70%
> sample70<-sample(seq_len(nrow(prostate)), size=sample_size) #樣本大小為70%的列
> prostate_train<-prostate[sample70,] #抽出70%待分析的資料作為訓練檔案
> prostate_test<-prostate[-sample70,] #抽出剩下30%待驗證的資料作為測試檔案
Prostate_Cancer已經有腫瘤診斷結果，診斷結果另外儲存為diagnosis_train、diagnosis_test後，刪除原檔案的診斷結果以利後續分析。
> diagnosis_train<-prostate_train$diagnosis_result #70%資料的實際診斷結果
> diagnosis_test<-prostate_test$diagnosis_result #30%資料的實際診斷結果
> prostate_train<-prostate_train[,-c(1)] #刪除訓練檔案的診斷結果
> prostate_test<-prostate_test[,-c(1)] #刪除測試檔案的診斷結果
k近鄰演算法
上述資料都備妥後，已經可以用class套件中的knn()進行k近鄰演算。k近鄰法必須事先決定k數，也就是資料分群數目，通常選擇k數的準則是\(\sqrt{n}\)，我們有70筆資料所以選擇分為8個群。k近鄰演算的訓練資料是prostate_train，驗證資料是prostate_test, 驗證目標是diagnosis_train腫瘤是惡性還是良性。
> library(class)
> diagnosis_predict<-knn(train=prostate_train, test=prostate_test, cl=diagnosis_train, k=8)
> diagnosis_predict #k近鄰法對30名病患的預測結果
[1] M B M M M M M M M M M M M M B B B M B B M B B M M B B M B B
Levels: B M
到此，knn()已經依據prostate_train建立的學習模型，針對prostate_test中的30名病患完成預測。我們可以比較一下預測及實際結果。
> diagnosis_test<-data.frame(diagnosis_test) #將diagnosis_test轉換為資料集
> comparison<-data.frame(diagnosis_predict, diagnosis_test) #合併diagnosis_predict, diagnosis_test兩個資料集
> names(comparison)<-c("Prediction", "Observation") #命名資料集的欄位
> comparison[1:5,] #輸出前五筆比較結果
Prediction Observation
1 M M
2 B M
3 M M
4 M B
5 M M
> table(comparison) #輸出比較表
Observation
Prediction B M
B 7 5
M 4 14
從前五筆資料可以看到k近鄰法預測跟實際還是有不一致的地方，例如第二名病患腫瘤應該是惡性，但電腦判斷為良性。整體而言，30名病患中有7+14名被正確預測，5+4名病患預測錯誤，所以準確率為\(^{7+14}/_{30}=70\%\)。
回到我們一開始的問題，有一名病患的腫瘤半徑30、紋路20、周長150、面積1100、平滑度0.140、密實度0.250、對稱度0.200、碎形維度0.080，請問他的腫瘤是惡性還是良性？
> knn(train=prostate_train, test=data.frame(radius=30, texture=20, perimeter=150, area=1100,
+ smoothness=0.14, compactness=0.25, symmetry=0.2, fractal_dimension=0.08), cl=diagnosis_train, k=8)
[1] M
Levels: B M
k近鄰法演算的結果，這名患者的攝護腺腫瘤為惡性。
銀行該不該同意貸款？
除了class裡的knn()指令，caret套件裡的train()也可以進行k近鄰演算，而且可自動計算最適合的k數。我們以收錄在caret套件裡的GermanCredit為例，說明caret在k近鄰法的應用。
銀行到底要不要提供資金給申貸人，必須仔細評估申貸人的還款能力與信用。GermanCredit是University of Hamburg的Dr. Hans Hofmann所提供的資料，裡面包含了申貸人的帳戶狀態、信用記錄、貸款目的、貸款金額、就業期限、可支配所得、財產、年齡、分期付款計劃、住房等等，可以用來評估申貸人的還款風險。
我們直接載入資料後，一樣將70%的資料用來訓練模型，剩下30%資料則用來驗證申貸人的信用，銀行是不是該貸款給她/他。
> library(caret)
> data(GermanCredit)
> str(GermanCredit[, 1:10])
'data.frame': 1000 obs. of 62 variables:
$ Duration : int 6 48 12 42 24 36 24 36 12 30 ...
$ Amount : int 1169 5951 2096 7882 4870 9055 2835 6948 3059 5234 ...
$ InstallmentRatePercentage : int 4 2 2 2 3 2 3 2 2 4 ...
$ ResidenceDuration : int 4 2 3 4 4 4 4 2 4 2 ...
$ Age : int 67 22 49 45 53 35 53 35 61 28 ...
$ NumberExistingCredits : int 2 1 1 1 2 1 1 1 1 2 ...
$ NumberPeopleMaintenance : int 1 1 2 2 2 2 1 1 1 1 ...
$ Telephone : num 0 1 1 1 1 0 1 0 1 1 ...
$ ForeignWorker : num 1 1 1 1 1 1 1 1 1 1 ...
$ Class : Factor w/ 2 levels "Bad","Good": 2 1 2 2 1 2 2 2 2 1 ...
準備分析資料
可以看到GermanCredit是一個包含1000個樣本，62個變數的資料檔。我們的被解釋變數是Class，也就是信用評等是良好(Good)還是差勁(Bad)。
這個資料集的特色就是都是類別變數，沒有資料標準化的問題而且已經設定好虛變數，可省下不少整理資料的繁雜工作。因此我們直接設定亂數抽樣70%資料當作學習模型。
> set.seed(1234) #亂數種子
> sample_size<-round(0.7*nrow(GermanCredit)) #設定樣本大小為70%
> sample70<-sample(seq_len(nrow(GermanCredit)), size=sample_size) #樣本大小為70%的列
> train<-GermanCredit[sample70,] #70%資料當作學習模型
> test<-GermanCredit[-sample70,] #30%資料當作測試
> train_no_credit<-subset(train, select=-c(Class)) #刪除學習模型中的信用評等結果
> test_no_credit<-subset(test, select=-c(Class)) #刪除測試檔案中的信用評等結果
接下來準備「答案」，把原有的信用評等結果Class保留下來，作為等一下驗證模型準確率之用。配合分析資料，一樣將資料分為7:3。
> credibility<-GermanCredit$Class #保留原資料的信用評等結果
> credibility_train<-credibility[sample70] #評等結果分為7:3比
> credibility_test<-credibility[-sample70] #評等結果分為7:3比
k近鄰演算法
萬事俱備後，可以開始用caret裡面的train()指令，輸入學習用資料train_no_credit，以及它的答案credibility_train，建立k近鄰法的演算模型。
> train_model<-train(train_no_credit, credibility_train, method="knn") #建立學習模型
> train_model
k-Nearest Neighbors
700 samples
61 predictor
2 classes: 'Bad', 'Good'
No pre-processing
Resampling: Bootstrapped (25 reps)
Summary of sample sizes: 700, 700, 700, 700, 700, 700, ...
Resampling results across tuning parameters:
k Accuracy Kappa
5 0.6203836 0.06009299
7 0.6352721 0.06817973
9 0.6419411 0.07448499
Accuracy was used to select the optimal model using the largest value.
The final value used for the model was k = 9.
上述結果顯示，在700位申貸人的學習模型中，k近鄰法分群k=5的時候準確率是62%，k=7的時候準確率是63%，k=9的時候準確率為最高的64%。學習模型完成後，我們現在可以透過這個模型來預測300名申貸人的信用。
> credibility_predict<-predict(train_model, newdata= test_no_credit) #預測300名申貸人信用
> confusionMatrix(credibility_predict, credibility_test) #輸出混淆矩陣
Confusion Matrix and Statistics
Reference
Prediction Bad Good
Bad 12 23
Good 79 186
Accuracy : 0.66
95% CI : (0.6033, 0.7135)
No Information Rate : 0.6967
P-Value [Acc > NIR] : 0.9245
Kappa : 0.0264
Mcnemar's Test P-Value : 5.157e-08
Sensitivity : 0.1319
Specificity : 0.8900
Pos Pred Value : 0.3429
Neg Pred Value : 0.7019
Prevalence : 0.3033
Detection Rate : 0.0400
Detection Prevalence : 0.1167
Balanced Accuracy : 0.5109
'Positive' Class : Bad
結果顯示300人中有12+186人預測正確，正確率為66%。基於這個模型，如果碰到一名新的申貸人，銀行可以據此作為評估是否借款的決策參考。