1、算法介绍

一个样本对应一个分类，用训练数据训练一个分类器，在输入没有标签的样本时，将新数据与训练集的数据对应特征进行比较，找出“距离”最近的k个数据，选择这k个数据中出现最多的分类作为新数据的分类。

算法描述

1. 计算已知类别数据及中的点与当前点的距离；
   距离计算方法有"euclidean"（欧氏距离）,”minkowski”（明科夫斯基距离）, "maximum"（切比雪夫距离）, "manhattan"（绝对值距离）,"canberra"（兰式距离）, 或 "minkowski"（马氏距离）等.
2. 按距离递增次序排序
3. 选取与当前点距离最小的k个点，
4. 确定前K个点所在类别出现的频率
5. 返回频率最高的类别作为当前类别的预测

特点

KNN是有监督的学习算法，其特点有：

1. 精度高，对异常值不敏感
2. 只能处理数值型属性
3. 计算复杂度高（如已知分类的样本数为n，那么对每个未知分类点要计算n个距离）

存在的问题

KNN算法目前存在的问题：

1. k值的确定是个难题。
2. 如果距离最近的k个已知分类样本中，频数较高的类型有多个（频数相同），如何选择对未知样本的分类？目前看是随机的。
3. 如果有n个未知类型样本，m个已知类型样本，则需要计算n*m个距离，计算量较大，且需存储全部数据集合，空间复杂度也较大。
4. 能否把预测的样本分类加入到已知类别集合中，对剩余的未知类型样本进行分类？
5. 归一化放在所有处理的最前面，这样需要知道全部的样本集合（已知分类+未知分类）来构建分类器，而实际上未知分类的样本并不一定能事先获得，这样如何进行归一化处理，任然是个问题。

应用领域：

1. 计算机视觉：包含字符和面部识别等
2. 推荐系统：推荐受众喜欢电影、美食和娱乐等
3. 基因工程：识别基因数据的模式，用于发现特定的蛋白质或疾病等

2、R算法

1. class函数包中的knn、knn.cv函数；
2. caret函数包中的knn3函数；
3. kknn函数包中的kknn函数；
4. ipred函数包中的ipredknn函数
5. DMwR函数包中的kNN函数

3、案例

实验环境

• 操作系统：

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)

• 数据集
  kaggle上泰坦尼客号数据集
• 说明

• 程序代码
  #数据处理

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 函数包knn实现

2. 基于caret函数包中的knn3函数实现

3. 基于kknn函数包中的kknn函数实现

4. 基于ipred函数包中的ipredknn函数实现

5. 基于DMwR函数包中的kNN函数实现