R之KNN算法

KNN（k-Nearest Neighbor)分類算法是數據挖掘分類技術中較簡單的方法之一。所謂k最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。

例如，上圖中，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。

KNN分類算法，是一個理論上比較成熟的方法，也是較簡單的機器學習算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比。

KNN算法流程： 

1. 準備數據，對數據進行預處理

2. 選用合適的數據結構存儲訓練數據和測試元組

3. 設定參數，如k

4. 維護一個大小為k的的按距離由大到小的優先級隊列，用于存儲最近鄰訓練元組。隨機從訓練元組中選取k個元組作為初始的最近鄰元組，分別計算測試元組到這k個元組的距離，將訓練元組標號和距離存入優先級隊列

5. 遍歷訓練元組集，計算當前訓練元組與測試元組的距離，將所得距離L與優先級隊列中的最大距離Lmax

6. 進行比較。若L>=Lmax，則舍棄該元組，遍歷下一個元組。若L < Lmax，刪除優先級隊列中最大距離的元組，將當前訓練元組存入優先級隊列。

7. 遍歷完畢，計算優先級隊列中k個元組的多數類，并將其作為測試元組的類別。

8. 測試元組集測試完畢后計算誤差率，繼續設定不同的k值重新進行訓練，最后取誤差率最小的k值。

KNN算法優點：

1. 簡單，易于理解，易于實現，無需估計參數，無需訓練；

2. 適合對稀有事件進行分類；

3. 特別適合于多分類問題(multi-modal,對象具有多個類別標簽)，kNN比SVM的表現要好；

KNN算法缺點：

1. 當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。 該算法只計算“最近的”鄰居樣本，某一類的樣本數量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量并不能影響運行結果；

2. 計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點；

3. 可理解性差，無法給出像決策樹那樣的規則；

R語言中有kknn的package實現了weighted k-nearest neighbor，用法如下：

kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.dummy", ordered = "contr.ordinal"))

參數：

formula       A formula object.

train            Matrix or data frame of training set cases.

test             Matrix or data frame of test set cases.

na.action     A function which indicates what should happen when the data contain ’NA’s.

k                  Number of neighbors considered.

distance       Parameter of Minkowski distance.

kernel          Kernel to use. Possible choices are 

"rectangular" (which is standard unweighted knn), 

"triangular", 

"epanechnikov" (or beta(2,2)), 

"biweight" (or beta(3,3)), 

"triweight" (or beta(4,4)), 

"cos", 

"inv", 

"gaussian", 

"rank"

"optimal".

ykernel        Window width of an y-kernel, especially for prediction of ordinal classes.

scale            Logical, scale variable to have equal sd.

contrasts     A vector containing the 'unordered' and 'ordered' contrasts to use

kknn的返回值如下：

fitted.values     Vector of predictions.

CL                    Matrix of classes of the k nearest neighbors.

W                     Matrix of weights of the k nearest neighbors.

D                      Matrix of distances of the k nearest neighbors.

C                      Matrix of indices of the k nearest neighbors.

prob                 Matrix of predicted class probabilities.

response          Type of response variable, one of continuous, nominal or ordinal.

distance           Parameter of Minkowski distance.

call                   The matched call.

terms               The 'terms' object used.

class包中的knn()函數提供了一個標準的kNN算法實現，用法如下：

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

參數:

train      matrix or data frame of training set cases.

test       matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case.

cl           factor of true classifications of training set

k            number of neighbours considered.

l             minimum vote for definite decision, otherwise doubt. (More precisely, less than k-l dissenting votes are allowed, even if k is increased by ties.)

prob      If this is true, the proportion of the votes for the winning class are returned as attribute prob.

use.all    controls handling of ties. If true, all distances equal to the kth largest are included. If false, a random selection of distances equal to the kth is chosen to use exactly k neighbours.

kknn的返回值如下：

Factor of classifications of test set. doubt will be returned as NA.

實例1：

> library(kknn) 

> data(iris) 

> m <- dim(iris)[1]  

> val <- sample(1:m, size = round(m/3), replace = FALSE, prob = rep(1/m, m))  # 選取采樣數據 

> iris.learn <- iris[-val,]  # 建立訓練數據 

> iris.valid <- iris[val,]   # 建立測試數據  

# 調用kknn，formula Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width  

> iris.kknn <- kknn(Species~., iris.learn, iris.valid, distance = 1, kernel = "triangular")  

> summary(iris.kknn)  

> fit <- fitted(iris.kknn)  # 獲取fitted.values 

> table(iris.valid$Species, fit)  # 建立表格檢驗判類準確性

> pcol <- as.character(as.numeric(iris.valid$Species))  

> pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]) 

實例2：

使用UCI機器學習數據倉庫(UCI Machine Learning Repository)的“威斯康星乳腺癌診斷”（Breast Cancer Wisconsin Diagnostic）的數據集，該數據集可以從網站https://archive.ics.uci.edu/ml/獲得。乳腺癌數據包括569例細胞活檢案例，每個案例32個特征。

0. 準備數據

> wbcd<-read.csv('wdbc.data',stringsAsFactors = FALSE)

> str(wbcd)

> wbcd<-wbcd[-1]

> table(wbcd$diagnosis)

> wbcd$diagnosis<-factor(wbcd$diagnosis,levels=c('B','M'),labels=c('Begin','Malignant'))

> round(prop.table(table(wbcd$diagnosis))*100, digits=1)

1. 轉換-min-max標準化數值型數據

> normalize <-function(x){

+ return( (x-min(x)) / (max(x)-min(x)) )

+ }

> wbcd_n <-as.data.frame(lapply(wbcd[2:31],normalize))

> #summary(wbcd_n$mqj1)

2. 數據準備-創建訓練集和測試集

> wbcd_train <- wbcd_n[1:469,]

> wbcd_test <- wbcd_n[470:569,]

> wbcd_train_labels <- wbcd[1:469,1]

> wbcd_test_labels <- wbcd[470:569,1]

3. 訓練模型

> install.packages('class')

> library(class)

> wbcd_test_pred <-knn(train=wbcd_train, test=wbcd_test, cl=wbcd_train_labels, k=21)

4. 評估性能

> install.packages('gmodels')

> library(gmodels)

> CrossTable(x=wbcd_test_labels, y=wbcd_test_pred, prop.chisq = FALSE)

5. 提高模型的性能

5.1 Z-score標準化

> wbcd_z <-as.data.frame(scale(wbcd[-1]))

> wbcd_train <- wbcd_z[1:469,]

> wbcd_test <- wbcd_z[470:569,]

> wbcd_train_labels <- wbcd[1:469,1]

> wbcd_test_labels <- wbcd[470:569,1]

> wbcd_test_pred <-knn(train=wbcd_train, test=wbcd_test, cl=wbcd_train_labels, k=21)

> CrossTable(x=wbcd_test_labels, y=wbcd_test_pred, prop.chisq = FALSE)

5.2 測試其他的K值

變換K的大小，測試假陰性和假陽性。盡量避免假陰性，但是會以增加假陽性代價。