knn算法也稱k最近鄰算法，其乃十大最有影響力的資料挖掘算法之一，該算法是一種有監督的挖掘算法，既可以解決離散因變量的分類問題，也可以做連續因變量的預測問題，而且該算法沒有複雜的資料推導公式、更易于常人了解。接下來我們就來看看這個流行算法到底是個什麼鬼？
k最近鄰算法，從名稱上來看還是比較容易了解的，以分類問題為例，該算法實際上就是尋找與未知分類最近的k個已知分類訓練集，然後通過投票的方式，将票數最多的那個類定性為未知分類樣本。也許你覺得這一長串話太啰嗦，還是不易了解，那我們來看一看下面這張圖：
如圖所示，圖中藍色點為已知分類的訓練集，紅色點為未知分類的測試集，如果需要得知未知分類該屬于哪種類别，可以在其周圍尋找最近的k個藍色點。不妨，我們在紅點周圍尋找到的3個黃點即為最近的點，進而根據3個已知分類的黃色點來判斷紅點屬于哪個類（投票方式）。
OK，了解了上面的過程，就是了解了knn算法的思想。既然是計算距離，那距離如何計算呢？這裡可能面臨着3種情況的距離計算：
1）連續變量間的距離計算？
2）離散變量間的距離計算？
3）含有缺失值的樣本間距離計算？
首先我們擺出計算距離的公式，即最常用的歐式距離：
接下來我們就是利用這個公式，針對以上三種不同的情形計算觀測點之間的距離。我們曾經說過，隻要跟距離相關的算法，一般都需要對原始資料進行标準化處理，目的是避免距離的值受到不同量綱的影響。至于标準化方法，主要有兩種，即Z标準化或0-1标準化處理，具體公式如下：
針對以上三種不同情形計算觀測點之間的距離，我們利用簡單的例子加以說明，目的是幫助讀者有一個很好的了解。
如果手中的訓練樣本如下：
經過0-1标準化的結果為：
則觀測1與其餘觀測之間的距離可計算為：
在這裡給出計算方法的結論：
1）對于連續變量之間的距離可以直接按數值差計算；
2）對于離散變量之間的距離可以按照值是否相同計算，如果值相同則距離內插補點為0，否則內插補點為1；
3）對于離散變量（2個水準以上）需要将其轉換為啞變量，然後再按照2）的方法計算距離。
好了，對于第一和第二種情況的距離計算我們已輕松解決，那如果資料中有缺失值該怎麼辦呢？這裡提供三種解決方案：
1）删除缺失嚴重的列或删除缺失非常少的觀測，然後對無缺失的情況計算距離；
2）使用替補法或多重插補法完成缺失值的填充，然後對清洗後的資料計算距離；
3）将缺失值當作特殊值處理，具體操作如下：
如果原始觀測有缺失值，
資料标準化處理的結果，
計算含缺失值的距離：
在這裡給出計算方法的結論：
1）對于離散變量，如果兩個觀測存在一個或兩個都是缺失，則內插補點為1；
2）對于連續變量，如果兩個觀測都是缺失，則內插補點為1，如果存在一個缺失，則內插補點取這兩個值（|1-x|和|0-x|）的最大值。
對于含缺失值的樣本距離可能會稍微複雜一點，但好在三種情況的距離都可以計算。現在還存在最後一個難題，即knn算法中的k如何确定？到底該選擇最近的幾個點才合适？這個問題一旦解決，knn便可自如行走。
關于k值的确定，一般我們會周遊k的某些值，然後從中選擇誤差率最低或正确率最高的k值即可，正如下圖所示：
圖中的紅圈對應的k值即為我們所要尋找的合理值，因為在該k值下，所計算出來的模型準确率最高。
講完了knn的思想和問題的解決方案，接下來就需要我們做一做實戰的内容了，資料來源于網站http://archive.ics.uci.edu/ml/，後面也會給出資料的下載下傳連結。在講實戰之前，需要介紹一下R落地的函數及參數含義：
knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all= TRUE)
train 指定訓練樣本集；
test 指定測試樣本集；
cl 指定訓練樣本集中分類變量；
k 指定最鄰近的k個已知分類樣本點，預設為1；
l 指定待判樣本點屬于某類的最少已知分類樣本數，預設為0；
prob 設為TRUE時，可以得到待判樣本點屬于某類的機率，預設為FALSE；
use.all 控制節點的處理辦法，即如果有多個第K近的點與待判樣本點的距離相等，預設情況下将這些點都納入判别樣本點，當該參數設為FALSE時，則随機挑選一個樣本點作為第K近的判别點。
實戰：乳腺癌診斷
#資料讀取
cancer <- read.table(file = file.choose(), header = FALSE, sep = ',')
#給原始資料編輯變量名
#資料探索
dim(cancer)
該資料集含有569個樣本和32個變量。
str(cancer)
summary(cancer)
從運作結果看（這裡沒有将結果貼出了，需要讀者自己運作試試），資料集中不含有缺失值，除Diagnosis變量外，其餘變量均為數值型變量，ID變量為編号，沒有任何意義，故在模組化過程中将删除該變量。發現各個變量間存在明顯的量綱大小，需要進一步對原始資料進行标注化。
#建構标準化函數
standard <- function(x) {
(x-mean(x))/sd(x)
}
#将該函數應用到資料框cancer中的每一列（除Diagnosis變量）
cancer_standard <- sapply(X = cancer[,3:32], FUN = standard)
summary(cancer_standard)
#将資料框cancer中的Diagnosis變量合并到cancer_standard中
cancer_standard <- as.data.frame(cbind(cancer$Diagnosis,as.data.frame(cancer_standard)))
names(cancer_standard)[1] <- 'Diagnosis'
Diagnosis變量為因子變量，表示診斷結果，M表示惡性，B表示良性。我們初步檢視一下這兩個水準的統計結果。
freq <- table(cancer_standard$Diagnosis)
prop.table(freq)
#建構訓練集、測試集和驗證集
set.seed(1)
index <- sample(x = 1:2,size = nrow(cancer_standard), replace = TRUE, prob = c(0.7,0.3))
train <- cancer_standard[index == 1,]
test <- cancer_standard[index == 2,]
訓練集和測試集已經抽樣完畢，接下來我們需要檢視訓練集和測試集中因變量的比重是否與總體吻合，進而看抽樣是否具有代表性
抽出來的效果還不錯，訓練集和測試集的因變量比例與總體因變量比例大體相當。
#構模組化型，以循環的方式選擇knn算法中的k值
library(class)
res = NULL
for (i in 1:round(sqrt(nrow(train)))){
model <- knn(train= train[,-1], test = test[,-1], cl = train$Diagnosis, k = i)
Freq <- table(test[,1], model)
accu <- sum(diag(Freq))/sum(Freq)
res <- c(res,accu)
}
plot(1:round(sqrt(nrow(train))),res,type = 'b', pch = 20, col= 'blue',
main = 'k vs. accuracy',
xlab = 'k', ylab = 'accuracy')
我的天呐，當k等于1時，模型的準确達到了最高，那麼我們就不妨使用k=1，作為knn算法的參數。
#模組化
fit <- knn(train = train[,-1], test = test[,-1], cl = train$Diagnosis, k = 17)
fit
此乃模型在測試集上的預測結果。
#檢視模型預測與實際類别的交叉表
Freq <- table(fit, test[,1])
Freq
模型的預測效果确實不錯，僅有5個觀測預測錯誤，即将實際為惡性，錯誤預測為良性的有4條，将實際為為良性錯誤預測為惡性的有1條。
#預判正确率
sum(diag(Freq))/sum(Freq)
通過模型的準确率計算表明，簡單而易用的knn算法能夠有97%的把握，将乳腺癌的良性或惡性診斷出來。
到此為止，我們已把knn算法的來龍去脈做了介紹和應用，希望您在讀完這篇文章後能有所收獲。在接下來的一期中，我們将對文本資料進行處理，并簡單的預測出哪些評論是正面的，哪些是負面的。
每天進步一點點2015
學習與分享，取長補短，關注小号！