总览

基于邻居的方法称为非泛化机器学习方法，因为它们只是简单地“记住”它的所有训练数据(可能转换成一个快速的索引结构，例如球树或KD树).

尽管它的简单性，最近的邻居已经成功地解决了大量的分类和回归问题，包括手写数字和卫星图像场景。它作为一种非参数方法，在决策边界非常不规则的情况下往往是成功的。

在数据不是均匀采样的情况下，基于半径的邻域分类RadiusNeighborsClassifier可能是个更好的选择。用户指定固定半径。r，这样，在比较稀疏的社区中，使用较少的近邻来进行分类。对于高维参数空间，这种方法由于所谓的“维数诅咒”而变得不那么有效。

KNN算法实现　

算法基本步骤：

1）计算待分类点与已知类别的点之间的距离

2）按照距离递增次序排序

3）选取与待分类点距离最小的k个点

4）确定前k个点所在类别的出现次数

5）返回前k个点出现次数最高的类别作为待分类点的预测分类

由上面的例子可见：该算法在分类时有个重要的不足是，当样本不平衡时，即：一个类的样本容量很大，而其他类样本数量很小时，很有可能导致当输入一个未知样本时，该样本的K个邻居中大数量类的样本占多数。但是这类样本并不接近目标样本，而数量小的这类样本很靠近目标样本。这个时候，我们有理由认为该位置样本属于数量小的样本所属的一类，但是，KNN却不关心这个问题，它只关心哪类样本的数量最多，而不去把距离远近考虑在内，因此，我们可以采用权值的方法来改进。和该样本距离小的邻居权值大，和该样本距离大的邻居权值则相对较小，由此，将距离远近的因素也考虑在内，避免因一个样本过大导致误判的情况。

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。这在特征空间的维数大及训练数据容量大时尤其必要。k近邻法最简单的实现是线性扫描（穷举搜索），即要计算输入实例与每一个训练实例的距离。计算并存储好以后，再查找K近邻。当训练集很大时，计算非常耗时。为了提高kNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减小计算距离的次数。

ball tree 和 kd tree

kd树是是一种二叉树，表示对k维空间的一个划分，构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分，构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

　类比“二分查找”：给出一组数据：[9 1 4 7 2 5 0 3 8]，要查找8。如果挨个查找（线性扫描），那么将会把数据集都遍历一遍。而如果排一下序那数据集就变成了：[0 1 2 3 4 5 6 7 8 9]，按前一种方式我们进行了很多没有必要的查找，现在如果我们以5为分界点，那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。因此，根本久没有必要进入第一个簇，可以直接进入第二个簇进行查找。把二分查找中的数据点换成k维数据点，这样的划分就变成了用超平面对k维空间的划分。空间划分就是对数据点进行分类，“挨得近”的数据点就在一个空间里面。

　利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。下面以搜索最近邻点为例加以叙述：给定一个目标点，搜索其最近邻，首先找到包含目标点的叶节点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最近邻的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。

但是我们会发现，因为使用kd树最近邻预测时，矩形与超球面易于相交，时常会因为菱角相交导致一些，无关多余的搜索，球树就是在kd树这个缺点上进行改进而生，通过将特征点转化为球状分割，从而减少无效相交。

球树，顾名思义，就是每个分割块都是超球体，而不是KD树里面的超矩形体。

sklearn.neighbors.KNeighborsRegressor(n_neighbors, weights="uniform")

选择默认的"uniform"，意味着所有最近邻样本权重都一样，在做预测时一视同仁。如果是"distance"，则权重和距离成反比例，即距离预测目标更近的近邻具有更高的权重，这样在预测类别或者做回归时，更近的近邻所占的影响因子会更加大。当然，我们也可以自定义权重，即自定义一个函数，输入是距离值，输出是权重值。这样我们可以自己控制不同的距离所对应的权重。

一般来说，如果样本的分布是比较成簇的，即各类样本都在相对分开的簇中时，我们用默认的"uniform"就可以了，如果样本的分布比较乱，规律不好寻找，选择"distance"是一个比较好的选择。如果用"distance"发现预测的效果的还是不好，可以考虑自定义距离权重来调优这个参数。