【机器学习笔记】——k近邻（k-nearest neighbor，k-NN）

目 录

1 k-NN

  k近邻法（k-nearest neighbor，k-NN）是一种基本分类与回归算法。是一种消极学习法（直到给出新的数据才开始进行学习，否则仅存储训练集数据。而积极学习法是根据训练集数据提前训练好模型，当新的数据输入时通过模型进行预测）。

1.1 基本思路

  k-NN的想法非常简单，就是根据最近的k个样本来判断新的样本的分类或值，当模型是分类时用投票原则，当模型是回归时取平均数。显然有三个影响模型效果的三个因素：怎么衡量距离、怎么确定k值、怎么进行决策（如何投票）。此外因为算法是基于距离进行的，因此为了避免某些维度的尺度较大对结果产生额外的影响，需要对数据进行标准化处理

1.1.1 距离度量

  $L_p$距离（又称Minkowski距离）是一组距离。设特征空间 $\mathcal{X}$ 是 $n$ 维向量空间 ${\mathbf{R}}^n$ ， $x_i,x_j\in \mathcal{X}$ ， $x_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)})$ ， $x_j=(x_j^{(1)},x_j^{(2)},\cdots ,x_j^{(n)})$ ， $x_i,x_j$ 的 $L_p$ 距离定义为

$$L_p(x_i,x_j)={\left(\sum _{l=1}^n|x_i^{(l)}-x_j^{(l)}{|}^p\right)}^{\frac{1}{p}},p\ge 1$$

特别地，当 $p=2$ 时，称为欧氏距离，这也是我们比较常用的距离（当特征维度增加时，欧氏距离的结果会变差）：

$$L_2(x_i,x_j)={\left(\sum _{l=1}^n|x_i^{(l)}-x_j^{(l)}{|}^2\right)}^{\frac{1}{2}}$$

当 $p=1$ 时，称为曼哈顿距离：

$$L_1(x_i,x_j)=\sum _{l=1}^n|x_i^{(l)}-x_j^{(l)}|$$

当 $p=\infty$ 时，称为切比雪夫距离：

$$L_{\infty }(x_i,x_j)=\underset{p\to \infty }{\lim }{\left(\sum _{l=1}^n|x_i^{(l)}-x_j^{(l)}{|}^p\right)}^{\frac{1}{p}}=\underset{l}{\max }|x_i^{(l)}-x_j^{(l)}|$$

1.1.2 k值的选择

  当 $k$ 比较小时，学习的训练误差比较小，只有与输入实例较近的训练样本才会起作用，但是测试误差会比较大，模型的鲁棒性较差。一旦邻近的实例点恰巧是噪声，那么预测就会出错。也即是说模型会比较复杂，容易发生过拟合。特别地当