k近邻法(KNN)

机器学习

k近邻法(k-nearest neighbor, k-NN)是一种基本的分类与回归方法。它的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。

k近邻法假设给定一个训练实例的类别，通过多数表决等方式急性预测。对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。

k近邻法实际上利用驯良数据集对特征向量空间进行划分，并作为其分类的“模型”，k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。

k近邻算法

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

k近邻算法

输入 : 训练数据集

$$T = \{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}$$
其中， $x_i \in \chi \subseteq R^{\ n}$ 为实例的特征向量， $y_i \in \gamma = \{c_1, c_2, ..., c_K\}$ 为实例的类别， $i = 1, 2, ..., N$；实例特征向量 $x$ ；
输出 : 实例 $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 = 1, 2, ..., N; \ \ j = 1, 2, ..., k$$
   其中， $I$ 为指示函数，即当 $y_i = c_j$ 时 $I$ 为1，否则 $I$ 为0.

当 k = 1 时该算法称为最近邻算法，对输入的实例点（特征向量）x，最近邻算法将训数据集中与 x 最近邻点的类作为 x 的类别。

k近邻模型

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

k近邻法中，当训练集，距离度量（如欧氏距离）、k值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一确定。

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间 $R^{\ n}$，使用的距离是一般是欧式距离，也可以是其他距离。

设特征空间 $\chi$ 是n维实数向量空间 $R^{\ n}$，$x_i, x_j \in \chi, x_i = ({x_i}^{(1)}, {x_i}^{(2)}, ..., {x_i}^{(n)})^T$，$({x_j}^{(1)}, {x_j}^{(2)}, ..., {x_j}^{(n)})^T$， $x_i, x_j$ 的 $L_p$ 距离定义为

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

下图展示了二维空间中p取不同值时，与原点的 $L_p$ 距离为 $1(L_p = 1)$ 的点的图形。

由不同的距离度量所确定的最近邻点是不同的。

k值的选择

k值的大小决定了邻域的大小。

较小的k值使得预测结果对近邻的点非常敏感，如果近邻的点恰好是噪声，则预测便会出错。话句话说，k值的减小意味着整体模型变得复杂，容易发生过拟合。

较大的k值会让输入实例中较远的（不相似的）训练实例对预测起作用，使预测发生错误，k值的增大意味着整体模型变得简单。

在应用中，k值一般选较小的数值，然后采用交叉验证法选取最优的k值。

分类决策规则

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

参照《统计学习方法》中的证明，多数表决规则等价于经验风险最小化。

k近邻法的实现 : kd树

为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。这里介绍kd树（kd tree）方法。

kd树是一种对k维空间的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分(partition)，构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树中的没改节点对应一个k维超矩形区域。

构造平衡kd树

输入 : k维空间数据集 $T = \{x_1, x_2, ..., x_N\}$，其中 $x_i = ({x_i}^{(1)}, {x_i}^{(2)}, ..., {x_i}^{(k)})^T, i = 1, 2, ..., N$；

输出 : kd树；

1. 开始 : 构造根结点，根结点对应于包含T的k维空间的超矩形区域；

   选择 $x^{(1)}$ 为坐标轴，以T中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。

   由根结点生成深度为1的左右子结点：左结点对应于坐标 $x^{(1)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(1)}$ 大于切分点的子区域。

2. 重复 : 对深度为j的结点，选择 $x^{(l)}$ 为切分的坐标轴，$l = (j \mod k) + 1$，以该结点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该节点对应的超平面区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。

   由该结点生成深度为 $j + 1$ 的左、右子节点: 左子结点对应于 $x^{(l)}$ 小于切分点的子区域，右子结点对应坐标 $x^{(l)}$ 大于切分点的子区域。
   将落在切分超平面上的实例点保存在该结点。

3. 结束 : 直到两个子区域没有实例存在时停止。从而形成kd树的区域划分。

kd树构造完成后，对于给定的一个目标点，搜索其最近邻。首先找到包含目标点的叶结点；然后从该叶结点出发，依次退回到父结点；不断查找与目标点最近邻的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大大提高。

搜索kd树

输入 : 已构造的kd树；目标点 x；

输出 : x的最近邻；

1. 在kd 树中找出包含目标节点x的叶结点：从根结点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子节点。直到子节点为叶结点为止。
2. 以此节点为“当前最近点”。
3. 递归地向上回退，在每个结点进行以下操作 :
   
   1. 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”.
   2. 当前最近点一定存在于该结点一个子节点对应的区域。检查该子节点的父节点的另一子节点对应的区域是否有更近的点。具体的，检查另一子节点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交
      如果相交，可能在另一个子节点对应区域内存在距目标点更近的点，移动到另一子节点。接着，递归地进行最近邻搜索；
      如果不相交，向上回退。
4. 当回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。

kd树适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近于训练实例数时，它的效率会迅速下降，几乎接近于线性扫描。