k-近邻算法介绍

  k-近邻算法是一种简单的算法，基本的算法思想是通过相似性的比较，最终得到最相似的k类中最为相似的。

  在k-近邻算法中有几个很重要的地方：第一是k的取值，其实k的取值就是模型的选择，模型的选择可以采用交叉验证的方式或者通过正则化的方式，显然这里是 采用交叉验证的方式。第二点就是实例的距离度量。第三是分类决策规则的选取。kNN唯一的也可以说最致命的缺点就是判断一篇新文档的类别时，需要把它与现 存的所有训练文档全都比较一遍，这个计算代价并不是每个系统都能够承受的 （比如我将要构建的一个文本分类系统，上万个类，每个类即便只有20个训练样本，为了判断一个新文档的类别，也要做20万次的向量比较！）。一些基于 kNN的改良方法比如Generalized Instance Set就在试图解决这个问题。

    k-近邻算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类

  算法如下所示：

    上文提到的k值的选取：k值如果选择过小，就相当于用较小的邻域实例进行预测，这样会减小近似误差，但是同时也会使得模型对邻域实例变得异常敏感，如果邻 域实例恰巧是噪声，那该实例被分错的可能性就会变得异常大（增大了估计误差）。换句话说，较小的k值会使得模型变得复杂，容易发生过拟合现象。

    k值选取过大，离预测实例较远的数据也会起作用，估计误差会减少，但是这会增加结果的近似误差，使 预测发生错误。k值的增大意味着模型会变得较为简单。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最有的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。

   距离度量：特征空间中两个实例点的距离是两个实例点相似程度的反映，kNN模型的特征空间一般是n维实数向量空间Rn。距离计算方法：欧式距离、Lp距离或Minkowski距离等。

   分类决策规则：该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别。

    k紧邻算法的实现需要考虑如何快速搜索k个最近邻点。kd树是一种便于对k维空间的中的数据进行快速检索的数据结构。kd树是一种二叉树，表示对k维空间 的一个划分，其每个节点对应于k维空间划分中的一个超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

kd tree的构造：

kd tree的最近邻搜索：