k近邻算法

  k近邻算法是一个基本的分类回归方法，其没有显式的学习过程，而是完全取决于数据，因此k近邻是基于数据的学习算法，其只有唯一的一个参数 $k(k>0,k\in\mathbb{N}_+)$ 。

1、k近邻算法

  给定一组已知数据 $T=\{(x_i,y_i)\}_{i=1}^{i=N}$，其中 $x_i$ 表示样本的特征向量，$y_i$ 是对应的标签。通过这组数据可以构建一个k近邻模型。在测试阶段，给定一个样本 $x_0$，计算其与所有其他训练样本的距离，并得到最近的k个样本，这k个样本中类标最多的作为当前样本 $x_0$的预测结果。

  $k$ 值的选择是该算法唯一的一个超参数。其表示在判断所给定样本的类时，所挑选附近点的个数。如果 $k$ 值过大，说明周围的点数量越多，距离越远的点也会起到分类的作用，模型变得简单，容易产生欠拟合；如果 $k$ 值过小，则所选的点数量少，模型过于复杂， 容易产生过拟合。当 $k=1$ 时，则表示为最近邻，其最近的样本点的类作为预测的类；当 $k=N$ 时，则整个训练集的样本最多的类作为预测值，此时不具有分类效果了，模型变得非常简单。

2、距离函数

  距离度量函数常用的是 $L_p$ 距离，即：

$L_p(x_i,x_j) = (\sum_{l=1}^{n}|x_i^{(l)} - s_{j}^{(l)}|^p)^{\frac{1}{p}}$

当 $p=1$ 时即为曼哈顿距离（绝对值的差）；当 $p=2$ 时表示欧氏距离（平方和的根式）。

  对分类的结果的评价是指所有误分类点的概率，即该点没有被预测为正确类的概率。因此学习的目标则是最小化误分类点的概率，其等价于经验风险最小化。

3、Kd树

  给定一组训练集，首先构建kd树，构建方法可描述为：
（1）假设训练集每个样本只有三个维度的特征，记做$x^{(1)}, x^{(2)}, x^{(3)}$。首先选择第一个维度的特征，其有诸多取值，取出对应的中位数作为分界线。将所有样本分为两类。因此可以构建一个二叉树；
（2）相当于缩小了训练集的空间，将训练集分到两个孩子结点上。对于每个孩子结点，选择第二个特征，并将对应所有样本在该特征的中位数作为分界线，继续往下划分，以此类推；
（3）直到所有的样本都被划分到独立的一个叶子结点（即每个叶子结点只有一个样本点），构建结束。

  kd树将搜索空间缩小，避免计算每个样本点的距离。如何根据kd树来选择最近邻？
（1）给定一个测试集样本 $x_0$，首先其根据构建的规则，从根结点向下进行搜索，最终落到对应的一个叶子结点。此时叶子结点所在的样本 $x_1$ 可以认为是与当前 $x_0$ 的最近邻结点；
（2）显然， $x_1$ 与 $x_0$ 的距离是一个阈值，最近邻一定在这个范围内。因此向上递归，计算 $x_0$ 与父亲结点的距离，并计算对应兄弟结点的距离，根据距离的比较，选择最近的样本作为最近邻；
（3）以此类推，逐个递归到根结点。

  注意的是，如果当前最近邻的范围与kd树划分的区域不重叠时，则不需要进行计算，因此大大降低了计算和搜索空间。

  例如，给定一组训练集 $\{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)\}$， 其可以构建kd树如下所示：

对应的空间划分是：

在搜索过程中，给定一个样本点 $(3,4.5)$，首先可以判断其落在 $(4,7)$ 对应的叶子结点，计算其与该样本的距离为 $\sqrt{(3-4)^2+(4.5-7)^2}=\sqrt{7.25}$。其次向上递归，计算样本 $(5,4)$ 与 $(3,4.5)$ 的距离为 $\sqrt{4.25}$， 发现距离表小，所以最近邻变为点 $(5,4)$。其次在与其另一个孩子结点进行比较，距离为 $\sqrt{3.25}$， 距离再次变小，所以最近邻为 $(2,3)$。继续向上递归，发现点 $(7,2)$ 以及不在以 $(3,4.5)$ 为圆心，$\sqrt{3.25}$为半径的圆范围内，所以根结点的右子树不需要搜索了。