第三章 k近邻法

1.同一标签的样本通常有很多相似的特征,所以同一类别的可能有扎堆现象，也就是物以类聚。

2.每进来一个样本，我们查看它周围的样本是什么类别的，那它也有极大可能属于该类别。

距离度量Distance measure

首先令 $ x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(n)}\right), x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \ldots, x_{j}^{(n)}\right) $

欧式距离（也称二范数）：

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

曼哈顿距离（也称一范数）：

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

P范数:

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

切比雪夫距离（类似于国际象棋的后）

当 $p=\infty$ 时, 它是各个坐标距离的最大值, 即

$L_{\infty }\left(x_i,x_j\right)={\max }_l\left|x_i^{(l)}-x_j^{(l)}\right|$

k值的选择

k值的选择会对k近邻法的结果产生重大影响。
如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差(approximation error)会减小，只有与输入实例较近的(相似的)训练实例才会对预测结果起作用。但缺点是“学习”的估计误差(estimation error)会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂,容易发生过拟合。

如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例较远的(不相似的)训练实例也会对预测起作用，使预测发生错误。k值的增大就意味着整体的模型变得简单。

如果k =N，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。

在应用中,k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

分类决策规则

k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则(majority voting rule)有如下解释:如果分类的损失函数为0-1损失函数．分类函数为：

f : R n → { c 1 , c 2 , ⋯   , c K } f: \mathbf{R}^{n} \rightarrow\left\{c_{1}, c_{2}, \cdots, c_{K}\right\} f:Rn→{c1​,c2​,⋯,cK​}

那么误分类的概率是

$P(Y\ne f(X))=1-P(Y=f(X))$

对给定的实例 $x \in \mathcal{X} $, 其最近邻的 k 个训练实例点构成集合 $ N_{k}(x) $ 。如果涵盖 $N_{k}(x) $ 的区域的类别是 $c_j$ , 那么误分类率是

$\frac{1}{k}{\sum }_{x_i\in N_k(x)}I\left(y_i\ne c_j\right)=1-\frac{1}{k}{\sum }_{x_i\in N_k(x)}I\left(y_i=c_j\right)$

要使误分类率最小即经验风险最小, 就要使 $ \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right) $ 最大, 所以多数表决规则等价于经验风险最小化。

注意：$I\left(x\right)$为指示函数，即x条件为真，则函数值为1，x条件为假，则函数值为0。

总结Summarization

1. K近邻思想:物以类聚

2. K近邻没有显式的训练过程（新样本与原来样本计算距离度量）

3. 距离度量:
   (1)欧式距离:两点之间直线

   (2)曼哈顿距离:城市街区距

   (3)切比雪夫距离:棋盘距离

4. 分类决策规则:多数表决