k近邻法

前言

k近邻法输入的是实例的特征向量，对应着空间的点，输出的是实例的类别。k临近法假设给定一个训练数据集，其中的实例类别已定，分类时对新的实例，根据其k个最临界的训练实例的类别，通过多数表决等的方式确定该实例的类别。因此k临近法不同于感知机那样有明确形式的数学表达式，也不具有显示的学习过程，它是对训练实例的空间划分的一种方法。k临近法主要包含三个要素：

1. k值的选择
2. 距离的度量
3. 分类决策规则

其中k值选择决定了由多少个训练实例进行投票以确定新实例的类别；距离的度量用来衡量实例之间的相似程度；分类决定规则用来决定投票的方式如多数表决。k临近法的内容就是确定以上三个要素的过程。

模型

输入训练数据集：$T=\lbrace(x_1,y_1) ,(x_2,y_2) ,···,(x_N,y_N) \rbrace$T={(x1​,y1​),(x2​,y2​),⋅⋅⋅,(xN​,yN​)}其中$x_i \in X \subseteq R^n$xi​∈X⊆Rn为实例的特征向量，$y_i \in Y= \lbrace c_1,c_2,···,c_k\rbrace$yi​∈Y={c1​,c2​,⋅⋅⋅,ck​}为实例的类别。
k临近法包含以下两个过程：

1. 输入新的实例$x$x,根据给定的距离度量，在训练实例$T$T中找到k个(k值的选择)与实例$x$x最临近的k个点(训练实例)，涵盖这k个点的$x$x的邻域记作集合$N_k(x)$Nk​(x)。
2. 在集合$N_k(x)$Nk​(x)中利用分类决策规则(多数表决等)，确定实例$x$x的类别$y$y:$y=\argmax_{c_j}\sum_{x_i \in N_k(x)}I(y_i=c_j) i=1,2,···,N;j=1,2,···，K$y=cj​argmax​xi​∈Nk​(x)∑​I(yi​=cj​)i=1,2,⋅⋅⋅,N;j=1,2,⋅⋅⋅，K 其中$I$I为指示函数，即当$y_i=x_j$yi​=xj​时为1，否则为0。

k临近法实际上就是对训练实例进行一种空间划分的方法如下图直观的表示：

模型的度量

k临近法是$n$n维实数空间向量$R^n$Rn，一般使用欧氏距离，也使用更一般的$L_p$Lp​距离。
设特征空间$X$X为$n$n维实数向量空间$R^n$Rn，点$x_i,x_j \in X$xi​,xj​∈X，即$x_i=\lbrace x_i^{(1)},x_i^{(2)},···,x_i^{(n)}\rbrace$xi​={xi(1)​,xi(2)​,⋅⋅⋅,xi(n)​}，$x_j=\lbrace x_j^{(1)},x_j^{(2)},···,x_j^{(n)}\rbrace$xj​={xj(1)​,xj(2)​,⋅⋅⋅,xj(n)​}
$x_i$xi​与$x_j$xj​的$L_p$Lp​距离定义为：$L_p(x_i,x_j)=(\sum_{k=1}^n |x_i^{(k)}-x_j^{(k)}|^{\frac{1}{p}})^{\frac{1}{p}}$Lp​(xi​,xj​)=(k=1∑n​∣xi(k)​−xj(k)​∣p1​)p1​$p=2$p=2时为欧氏距离，$p=1$p=1时为曼哈顿距离，$p=\infty$p=∞时为各个坐标的最大值即$L_{\infty}(x_i,x_j)=\max_{k}|x_i^{(k)}-x_j^{(k)}|$L∞​(xi​,xj​)=maxk​∣xi(k)​−xj(k)​∣。以2维空间距离原点为1为例，不同距离的图像表示：

$x_i=(0,0)$xi​=(0,0),$x_j$xj​与$x_i$xi​的距离为1，上图为不同距离的$x_j$xj​的图像表示。需要注意的是使用不同的距离度量的方式所计算得到的最临近的点可能是不同的。

k值的选择

k值的选择主要与模型的泛化能力有关，当k值很小时，相当于用更少的训练实例来决定新实例的类别，当训练实例有噪音时，预测就会出错。这就意味着k值减小整体模型复杂度升高，容易产生过拟合降低泛化能力。而k值过大时如$k=N$k=N，这样无论什么实例的输入模型都会简单的预测为包含训练实例最多的那个类别，使模型丧失其意义。在应用中，k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

分类决策规则

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

kd树

kd树是k临近法的一种实现方式，k临近方法最直接的实现方式是对训练数据进行线性的扫描，这样的方式在数据量很大时难以实现，因此kd树实际上就是一种储存训练实例的方法，它与搜索算法匹配使用能够快速搜索训练实例。kd树主要包含kd树的构造与kd树的搜索两部分。

kd树的构造

kd树是一个二叉树，其是不断的用垂直于坐标轴的超平面对k维空间进行切分，最后得到了k维的超矩形区域。kd树的每一个结点对应着一个超矩形区域。如下kd树的构造过程：
已知训练数据集$T$T,其中$x_i = \lbrace x_i^{(1)},x_i^{(2)},···,x_i^{(k)} \rbrace$xi​={xi(1)​,xi(2)​,⋅⋅⋅,xi(k)​}

1. 以$x^{(1)}$x(1)为切分坐标轴，以所有训练实例的$x^{(1)}$x(1)坐标的中位数为切分点，把特征空间切分为深度为1的左右两个空间，即根节点的左右两个子节点。
2. 对深度为$j$j的子节点，以$x^{(l)}$x(l)为坐标轴其中$l=j \mod k+1$l=jmodk+1,以$x^{(l)}$x(l)所包含的空间中所有实例的$x^{(1)}$x(1)坐标的中位数为切分点，继续节分。
3. 不断的重复以上过程，直至所有的实例点都变成的树的结点，即结点包含的子区域中没有实例为止。

通过以上过程就可以创建包含所有训练实例的二叉树结构，以中位数为切分点的kd树称为平衡kd树。

kd树的搜索

利用kd树可以省去大部分的数据的搜索因此效率大为提高。kd树的具体搜索过程如下所示：

1. 确定输入实例所在的叶节点的区域。从根节点出发，递归的搜索kd树，根据当前深度确定输入数据的当前维度，如果当前维度的坐标大于切分点的坐标则移到右节点，否则移到左结点。这样不断的搜索直到到达叶节点。该叶节点作为当前最近点。

2. 向上回退,对每个结点做以下操作，找到最近点。
   (1). 如果当前结点比当前最近点更近(根据距离的度量)则把当前结点作为当前最近点。
   (2).检查当前结点的另一个子节点，具体操作为：该子节点对应的超矩形区域是否与以输入实例为圆心，以输入实例与当前最近点的距离为半径的圆相交，如果相交那么可能该子节点中包含更近的结点，移动到该子节点进行操作1(kd搜索)，否则回退到上一个结点。

3. 不断的重复2向上回退直至到达根节点，此时的当前最近点就为全局最近点。

如果实例点是随机分布的，kd树搜索的平均计算复杂度是O(logN)，这里N是训练实例 数。kd树更适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。