一、工作机制

给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

二、k值的选取

在实际中，k值得选取决定于要学习概念的难度和训练数据中案例的数量。通常k为2~10。一种常见的做法是设置k等于训练集中案例数量的平方根。例如，在上述案例中可以设置k=2，因为训练集中有3个案例，3的平方根是1.732。 但是这种规则并不一定总是适用，因此另一种方法是来测试多个k值，选择一个可以提供最好分类性能的k值。

三、样本的距离

由于k近邻法将样本包含的m个观测数据看成n维（n个输入变量）特征空间中的点，所以可以在特征空间中定义某种距离。常用的距离有欧氏距离、绝对距离和切比雪夫距离。

闵可夫斯基距离是两个观测点n个变量值绝对差p次方总和的p次方根（p可以任意指定）。数学公式为：

\[d(x,y) = \sqrt[p]{{\sum\limits_{i = 1}^n {{{\left| {{x_i} - {y_i}} \right|}^p}} }}\]

（1）当p=1时，为绝对距离，也成为曼哈顿距离。数学公式为：

\[d(x,y) = {\sum\limits_{i = 1}^n {{{\left| {{x_i} - {y_i}} \right|}}} }\]

（2）当p=2时，为欧氏距离。数学公式为：

\[d(x,y) = \sqrt{{\sum\limits_{i = 1}^n {{{\left| {{x_i} - {y_i}} \right|}^2}} }}\]

（3）当\[p \to \infty \]时，即为切比雪夫距离。数学公式为：

\[d(x,y) = \max (\left| {{x_i} - {y_i}} \right|), (i=1,2,…,n)\]

但在传统上，kNN算法一般采用的是采用的是欧氏距离。

三、R中k近邻所用函数

knn（train=训练样本集，test=测试样本集，cl=输出变量，k=近邻个数，prob=FALSE）

train和test分别代表训练集和测试集；cl用于指定训练样本集中哪个变量为输出变量。k为控制最近邻域大小的参数；Prob取TRUE表示函数返回为预测类别的概率值，取FALSE表示函数的返回值为预测类别。

四、算例

1.天气数据集

天气分为两类：1为晴天，2为雨天

G=c(1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

x1表示温度

x1=c(-1.9,-6.9,5.2,5.0,7.3,6.8,0.9,-12.5,1.5,3.8,0.2,-0.1,0.4,2.7,2.1,-4.6,-1.7,-2.6,2.6,-2.8)

x2表示湿度

x2=c(3.2,0.4,2.0,2.5,0.0,12.7,-5.4,-2.5,1.3,6.8,6.2,7.5,14.6,8.3,0.8,4.3,10.9,13.1,12.8,10.0)

构建数据框a

a=data.frame(G,x1,x2)

画出散点图

plot(x1,x2)
text(x1,x2,G,adj=-0.5)

加载class包

library(class)

使用knn()函数构建

k1=knn(a,a,cl=a[,1],k=1)

当k=1，显示估计结果

k1
##  [1] 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
## Levels: 1 2
k2=knn(a,a,cl=a[,1],k=2)

当k=2，显示估计结果

k2
##  [1] 1 1 1 1 1 1 1 1 1 2 2 2 2 1 2 1 2 2 2 2
## Levels: 1 2
k3=knn(a,a,cl=a[,1],k=3)

当k=3，显示估计结果

k3
##  [1] 2 1 1 1 1 2 1 1 1 2 2 2 2 2 1 1 2 2 2 2
## Levels: 1 2