第3章 K近邻法

3.1 $k$近邻算法 （$k$-nearest neighbor, KNN）

输入： 训练集$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$
输出： 实例$x$所属类别$y$
1-根据给定的距离度量，在训练集$T$中找出与$x$最近邻的$k$个点，涵盖这$k$个点的$x$的领域记作$N_k(x)$;
2-在$N_k(x)$中根据分类决策规则决定$x$的类别$y$：$y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}{I(y_i=c_j)}$，$I$为指示函数。

是一种基本分类与回归方法，没有显式的学习过程

3.2 $k$近邻模型

$k$近邻算法使用的模型实际上对应于对特征空间的划分，模型有三个基本要素：距离度量、$k$值得选择和分类决策规则。

距离度量

欧式距离、$L_p$距离（Minkowski距离）

$L_p(x_i,y_i)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p},p\ge1$
$p=2$，欧式距离；$p=1$，Manhattan距离；$p=\infty$，各个坐标距离的最大值

$k$值的选择

较小值： 相当于在较小邻域中训练实例进行预测，近似误差会减小，估计误差会增大，对近邻点非常敏感。k值减小意味着整体模型变得复杂，容易过拟合。

较大值： 相当于在较大邻域中训练实例进行预测，估计误差会减小，近似误差会增大，对远邻点依然有效，容易误检。k值增大意味着整体模型变得简单，容易欠拟合。

$\mathbf{k=N}$：无论什么输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略了实例中大量有用信息。

3.3 $k$近邻法的实现：$kd$树

以特征$x$的第一维为坐标轴，以中位数为切分点，然后是第二维，第三维，划分得到最后的二叉树。