knn

给定一个训练集，对新输入的实例，在训练集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，我们就把该输入实例分为这个类。

算法描述

输入：训练数据集 $T = {x_1, y_1, x_2, y_2, \dots, x_N, y_N}$，其中 $x_i \in X$ 为实例的特征向量，$y_i \in {c_1, c_2, \dots, c_m}$ 为实例的类别；实例特征向量 $x$

输出：实例 $x$ 所属的类别 $y$

1. 根据给定的距离度量方式，在训练集 $T$ 中找到与 $x$ 最邻近的 $k$ 个点，涵盖着 $k$ 个点的区域记住 $N_k(x)$

2. 在 $N_k(x)$ 中根据分类决策规则决定 $x$ 的类别 $y$

$$y = \underset{c_j}{\arg\max} \sum_{x_i \in N_k(x)} I(y_i = c_j)$$

其中 $I(y_i = c_j)$ 为指示函数，当 $y_i = c_j$ 的时候 $I = 1$，否则 $I = 0$

KNN的基本要素

对于一个确定的训练集，只要确定了距离度量、k值和分类决策规则，就能对任何一个新的实例，确定它的分类。

距离度量

距离度量是描述特征空间中两个实例的距离，也是这两个实例的相似程度。在 $n$ 维数向量空间中，我们主要使用的距离度量方式是欧式距离，但也可以使用更加一般化 $L_p$ 距离（闵可夫斯基距离）。

在特征空间中，取出两个特征 $x_i, x_j$，它们分别是 $n$ 维的特征向量。

欧氏距离

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

曼哈顿距离

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

闵可夫斯基距离

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

从上式可以看出，欧氏距离和曼哈顿距离分别是闵可夫斯基距离的（$p = 2$，$p = 1$）特殊情况。

k值的选择

对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，然后通过交叉验证选择一个合适的k值。

• 选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。
• 选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误。换句话说，k值的增大就意味着整体的模型变得简单，容易发生欠拟合。

一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。

kd树

KNN算法最简单的实现方式，就是好计算输入实例和所有训练实例的距离，然后进行排序，取前k个，进行分类。但是训练集特别大的时候，这种方式非常耗时，不可行。下面介绍kd树的方式，kd树是通过减少输入实例和训练实例的计算次数来达到优化的目的。

kd树算法包括三步，第一步是建树，第二部是搜索最近邻，最后一步是预测。

构造kd树

kd树是一种对 $n$ 维空间的实例点进行存储，以便对其进行快速检索的树形结构。kd树是二叉树，构造kd树相当于不断的用垂直于坐标轴的超平面将 $n$ 维空间进行划分，构成一系列的 $n$ 维超矩阵区域。

我们首先来看建树的方法。kd树建树采用的是从 $m$ 个样本的 $n$ 维特征中，分别计算 $n$ 个特征的取值的方差，用方差最大的第 $k$ 维特征 $n_k$ 来作为根节点。对于这个特征，我们选择特征 $n_k$ 的取值的中位数 $n_{kv}$ 对应的样本作为划分点，对于所有第 $k$ 维特征的取值小于 $n_{kv}$ 的样本，我们划入左子树，对于第 $k$ 维特征的取值大于等于 $n_{kv}$ 的样本，我们划入右子树。对于左子树和右子树，我们采用和刚才同样的方法来找方差最大的特征来做根节点，递归生成 kd 树。

下面的流程图更加清晰地描述了 kd 树的构建过程：

构建好的 kd 树
![[Pasted image 20240924161248.png]]

kd树搜索最近邻

当我们生成kd树以后，就可以去预测测试集里面的样本目标点了。预测的过程如下：

1. 对于一个目标点，我们首先在kd树里面找到包含目标点的叶子节点。以目标点为圆心，以目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。
2. 然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻，并且更新超球体。如果不相交那就简单了，我们直接返回父节点的父节点，在另一个子树继续搜索最近邻。
3. 当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。

从上面的描述可以看出，kd树划分后可以大大减少无效的最近邻搜索，很多样本点由于所在的超矩形体和超球体不相交，根本不需要计算距离。大大节省了计算时间。

KNN和KdTree算法实现