knn到底咋回事？（修改版）

作者：劉順祥 公眾號：每天進步一點點2015 (微信ID：lsxxx2011)

配套教程：手把手教你做文本挖掘 https://edu.hellobi.com/course/181

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 = NULLfor (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 = 1)fit

此乃模型在測試集上的預測結果。

#查看模型預測與實際類別的交叉表Freq <- table(fit, test[,1])Freq

模型的預測效果確實不錯，僅有5個觀測預測錯誤，即將實際為惡性，錯誤預測為良性的有4條，將實際為為良性錯誤預測為惡性的有1條。

#預判正確率sum(diag(Freq))/sum(Freq)

通過模型的準確率計算表明，簡單而易用的knn演算法能夠有97%的把握，將乳腺癌的良性或惡性診斷出來。

到此為止，我們已把knn演算法的來龍去脈做了介紹和應用，希望您在讀完這篇文章後能有所收穫。在接下來的一期中，我們將對文本數據進行處理，並簡單的預測出哪些評論是正面的，哪些是負面的。

原文的數據鏈接：http://pan.baidu.com/s/1pL6lVTp

推薦閱讀：