K近邻法

k近邻法（k-nearest neighbor, k-NN）是一种基本分类与回归方法。这里只讨论分类问题中的k近邻法。k近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方法进行预测。当K=1时，就是我们所熟悉的最近邻方法（NN）。因此，k近邻法不具有显式的学习过程。k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。

k近邻算法

输入：训练数据集:$T={ (x_1,y_1),(x_2,y_2),\cdots (x_N,y_N)}$,其中,$x_i\in R^n$为实例的特征向量，$y_i\in{c_1,c_2,\cdots c_k}$ 为实例的类别。

输出：实例x所属的类y

（1）根据给定的距离度量，在训练集T中找出与x最近邻的k个点，涵盖这k个点的邻域记作$N_k(x)$;
（2）在$Nk(x)$中根据分类决策规则（如多数表决）决定x的类别y：$y=arg max{cj} \sum{x_i\in N_k(x)}I(y_i=c_j),i=1,2,\cdots N,j=1,2,\cdots K$

由这个简单的算法过程可以看出来，距离的选择、以及k的选择都是很重要的，这恰好对应的三个要素中的两个，另一个为分类决策规则，一般来说是多数表决法。

k近邻模型

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

KNN是一种memory-based learning，也叫instance-based learning，属于lazy learning。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。具体是每次来一个未知的样本点，就在附近找K个最近的点进行投票。

相当于把特征空间划分为许多块。

距离度量

特征空间中俩个实例的距离是俩个实例点相似程度的反映，k近邻中一般使用欧氏距离，本文中主要只介绍这一种。

设特征空间是维实数向量空间，，,,的距离定义为

当p=2时，称为欧氏距离(Euclidean distance).

K值的选择

K值的选择对最终的结果有很大的影响.

如果选择较小的k值，就相当于用较小的领域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例相近的（相似的）训练实例才会对预测结果起作用。但是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。
如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。k值的增大意味着整体的模型变得简单。
如果k=N，那么无论输入实例是什么，都将简单的预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。
在应用中，k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

分类决策规则

k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则等价于经验风险最小化。

实现-构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

构造平衡kd树

输入：k维空间数据集$T={ x_1,x_2,\cdots, x_N}$，其中$x_i=(x_i^{(1)},x_i^{(2)}, \cdots x_i^{(k)})^T,i=1,2,\cdots,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树可以省去对大部分数据点的搜索，从而减少搜索的即使是算量。这里以最近邻（k=1）为例加以叙述，同样的方法可以应用到k近邻。
用kd树的最近邻搜索
输入：已构造的kd树，目标点x；
输出：x的最近邻
（1）在kd树中找到包含目标点x的叶结点：从根结点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶节点为止。
（2）以此叶节点为“当前最近点”
（3）递归地向上回退，在每个结点进行以下操作：
（a）如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”
（b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点对应的区域是否与以目标点为球心，以目标点与“当前最近点”间的距离为半径的超球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标更近的点，移动到另一个子结点，接着，递归地进行最近邻搜索：
如果不相交，向上回退
（4）当回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。

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