1、算法介紹

一個樣本對應(yīng)一個分類，用訓(xùn)練數(shù)據(jù)訓(xùn)練一個分類器，在輸入沒有標(biāo)簽的樣本時，將新數(shù)據(jù)與訓(xùn)練集的數(shù)據(jù)對應(yīng)特征進行比較，找出“距離”最近的k個數(shù)據(jù)，選擇這k個數(shù)據(jù)中出現(xiàn)最多的分類作為新數(shù)據(jù)的分類。

算法描述

1. 計算已知類別數(shù)據(jù)及中的點與當(dāng)前點的距離；
   距離計算方法有"euclidean"（歐氏距離）,”minkowski”（明科夫斯基距離）, "maximum"（切比雪夫距離）, "manhattan"（絕對值距離）,"canberra"（蘭式距離）, 或 "minkowski"（馬氏距離）等.
2. 按距離遞增次序排序
3. 選取與當(dāng)前點距離最小的k個點，
4. 確定前K個點所在類別出現(xiàn)的頻率
5. 返回頻率最高的類別作為當(dāng)前類別的預(yù)測

特點

KNN是有監(jiān)督的學(xué)習(xí)算法，其特點有：

1. 精度高，對異常值不敏感
2. 只能處理數(shù)值型屬性
3. 計算復(fù)雜度高（如已知分類的樣本數(shù)為n，那么對每個未知分類點要計算n個距離）

存在的問題

KNN算法目前存在的問題：

1. k值的確定是個難題。
2. 如果距離最近的k個已知分類樣本中，頻數(shù)較高的類型有多個（頻數(shù)相同），如何選擇對未知樣本的分類？目前看是隨機的。
3. 如果有n個未知類型樣本，m個已知類型樣本，則需要計算n*m個距離，計算量較大，且需存儲全部數(shù)據(jù)集合，空間復(fù)雜度也較大。
4. 能否把預(yù)測的樣本分類加入到已知類別集合中，對剩余的未知類型樣本進行分類？
5. 歸一化放在所有處理的最前面，這樣需要知道全部的樣本集合（已知分類+未知分類）來構(gòu)建分類器，而實際上未知分類的樣本并不一定能事先獲得，這樣如何進行歸一化處理，任然是個問題。

應(yīng)用領(lǐng)域：

1. 計算機視覺：包含字符和面部識別等
2. 推薦系統(tǒng)：推薦受眾喜歡電影、美食和娛樂等
3. 基因工程：識別基因數(shù)據(jù)的模式，用于發(fā)現(xiàn)特定的蛋白質(zhì)或疾病等

2、R算法

1. class函數(shù)包中的knn、knn.cv函數(shù)；
2. caret函數(shù)包中的knn3函數(shù)；
3. kknn函數(shù)包中的kknn函數(shù)；
4. ipred函數(shù)包中的ipredknn函數(shù)
5. DMwR函數(shù)包中的kNN函數(shù)

3、案例

實驗環(huán)境

• 操作系統(tǒng)：

Mac OS X High Sierra 10.13.1+2.5 GHz Intel Core i7+16 GB 1600 MHz DDR3
R version 3.4.2 (2017-09-28)

• 數(shù)據(jù)集
  kaggle上泰坦尼客號數(shù)據(jù)集
• 說明

• 程序代碼
  #數(shù)據(jù)處理

library("class")
library("caret")
library("kknn")
library("ipred")
library("DMwR")#加載程序包
library('dplyr')
test<-read.csv("./test.csv",stringsAsFactors = F)
train<-read.csv("./train.csv",stringsAsFactors = F)
test$datatype<-"test"
train$datatype<-"train"
full  <-bind_rows(train, test)
full$Sex[full$Sex=="female"]<-1
full$Sex[full$Sex=="male"]<-0
full$Sex<-as.numeric(full$Sex)
full$Embarked [full$Embarked =="S"]<-1
full$Embarked [full$Embarked =="C"]<-2
full$Embarked [full$Embarked =="Q"]<-3
full$Embarked <-as.numeric(full$Embarked )
full$Age[is.na(full$Age)]<--1
full$Fare[is.na(full$Fare)]<-8.05
full$Embarked[is.na(full$Embarked)]<-2
full$Pclass<-as.numeric(full$Pclass)
full$SibSp<-as.numeric(full$SibSp)
full$Parch<-as.numeric(full$Parch)


train <- full[1:891,]
test <- full[892:1309,]

用Pclass 、Sex 、Age、SibSp、Parch 、Fare、Embarked進行建模

1. 基于class 函數(shù)包knn實現(xiàn)

2. 基于caret函數(shù)包中的knn3函數(shù)實現(xiàn)

3. 基于kknn函數(shù)包中的kknn函數(shù)實現(xiàn)

4. 基于ipred函數(shù)包中的ipredknn函數(shù)實現(xiàn)

5. 基于DMwR函數(shù)包中的kNN函數(shù)實現(xiàn)