本文主要内容来自周志华《机器学习》和Peter Flach 《机器学习》

在k-近邻算法1、k-近邻算法2, k-近邻算法3三篇文章从实践上学习了k-近邻算法， 本文从理论上学习k-近邻算法。

k-近邻(k-Nearest Neighbor, 简称kNN)算法是一种常用的监督学习方法，其工作机制：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息进行预测。通常在分类任务中，使用多数表决法(majority vote method, 也叫投票法)，即选择这k个样本中出现最多的类别标签作为预测结果；在回归任务中使用平均法(verage method)，即将这k个样本的输出数值的平均值作为预测结果；另外，基于距离远近进行加权投票或加权平均，如距离大小与样本权重成反比。

从实践上，我们发现k-近邻算法没有训练过程，它只是把训练样本保存起来，训练开销为零，收到测试样本后才进行处理，它是典型的懒惰学习(lazy learning)；相应的，那些在训练过程阶段对训练样本进行学习处理的方式，被称为急切学习(eager learning)。

由k-近邻算法的工作机制可知，距离度量的定义和k值的选取是非常重要的。

定义(距离度量): 设实例空间为\(H\)，该空间中的一个距离函数可定义为映射\(D: H \times H \to R\)，则对任意\(\mathbf{x},\mathbf{y},\mathbf{z} \in H\)，有

如果把第一条改为，当\(\mathbf{x}\not=\mathbf{y}\)时也成立\(D(\mathbf{x},\mathbf{y}) = 0\)，则\(D\)为伪度量(pseudo-metric)

闵可夫斯基距离(Minkowski distance)：对于\(n\)维向量\(\mathbf{x}\)和\(\mathbf{y}\),

其中，\(\|\mathbf{x}\|_p=(\sum\limits_{i=1}^n |x_i|^p)^{\frac{1}{p}}\)为向量\(\mathbf{x}\)的\(p\)范数(也称\(L_p\)范数)。

当\(p sit 替换k为s sitt –> sit 删除t sittin –> sitting 插入g

马氏距离(Mahalanobis distance)，记\(\mathbf{x}\)和\(\mathbf{y}\)之间的协方差为\(\Sigma\)

马氏距离表示两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。如果协方差矩阵为单位矩阵，那么马氏距离简化为欧氏距离，如果协方差矩阵为对角阵，则其可称为正规化的欧氏距离

还有一些距离度量如余弦距离(Cosine distance)、杰卡德距离(Jaccard distance)、相关距离(Correlation distance)和信息熵(Information Entropy)，可参考机器学习——几种距离度量方法比较

k是一个重要参数，当k选不同值时会产生不同的结果。

如下图，当k取为3时，结果为红色三角形，而当k取为5时，结果为蓝色正方形。

k值设置过小会降低分类精度；若设置过大且测试样本属于训练集中包含数据较少的类，则会增加噪声，降低分类效果。

通常，k值的设定采用交叉检验的方式（以k=1为基准）

经验规则：k一般低于训练样本数的平方根