最近邻

发表于 | 分类于

一、最近邻

最近邻方法背后的原理是从训练样本中找到与新点在距离上最近的预定数量的几个点，然后从这些点中预测标签。 这些点的数量可以是用户自定义的常量（K-最近邻学习）， 也可以根据不同的点的局部密度（基于半径的最近邻学习）。

距离通常可以通过任何度量来衡量： standard Euclidean distance（标准欧式距离）是最常见的选择。Neighbors-based（基于邻居的）方法被称为 非泛化 机器学习方法， 因为它们只是简单地”记住”了其所有的训练数据（可能转换为一个快速索引结构，如 Ball Tree 或 KD Tree）。

二、最近邻分类

1、KNeighborsClassifier ：

通常较大的 k 是会抑制噪声的影响，但是使得分类界限不明显。

如果数据是不均匀采样的，那么 RNC中的基于半径的近邻分类可能是更好的选择。

2、RadiusNeighborsClassifier :

用户指定一个固定半径 r ，使得稀疏邻居中的点使用较少的最近邻来分类。

对于高维参数空间，这个方法会由于所谓的 “维度灾难” 而变得不那么有效。

基本的最近邻分类使用统一的权重：分配给查询点的值是从最近邻的简单多数投票中计算出来的。 在某些环境下，最好对邻居进行加权，使得更近邻更有利于拟合。可以通过 weights 关键字来实现。

默认值 weights = 'uniform' 为每个近邻分配统一的权重。而 weights = 'distance' 分配权重与查询点的距离成反比。

或者，用户可以自定义一个距离函数用来计算权重。

三、最近邻回归

最近邻回归是用在数据标签为连续变量，而不是离散变量的情况下。分配给查询点的标签是由它的最近邻标签的均值计算而来的。

1、KNeighborsRegressor

2、RadiusNeighborsRegressor

四、最近邻算法

1、暴力计算

对于 D 维度中的 N 个样本来说, 这个方法的复杂度是 O[DN^2]。

对于小数据样本，高效的暴力近邻搜索是非常有竞争力的。 然而，随着样本数 N 的增长，暴力方法很快变得不切实际了。

2、K-D树

对于 D 维度中的 N 个样本来说, 这个方法的复杂度是 O[DNlog(N)] 或更低。

D 树的方法对于低维度 （D<20），近邻搜索非常快, 当 D 增长到很大时, 效率变低: 这就是所谓的 “维度灾难” 的一种体现。

3、Ball树

为了解决 KD 树在高维上效率低下的问题, ball树 数据结构就被研发出来了 。其中 KD 树沿卡迪尔轴（即坐标轴）分割数据, 树在沿着一系列的 超平面来分割数据。

通过这种方法构建的树要比 KD 树消耗更多的时间, 但是这种数据结构对于高结构化的数据是非常有效的, 即使在高维度上也是一样。

如上所述, 对于小样本暴力搜索是比基于数的搜索更有效的方法. 这一事实在 ball 树和 KD 树中被解释为在叶节点内部切换到蛮力搜索. 该开关的级别可以使用参数 leaf_size 来指定. 这个参数选择有很多的效果:

  • 构造时间

    更大的 leaf_size 会导致更快的树构建时间, 因为需要创建更少的节点.

  • 查询时间

    一个大或小的 leaf_size 可能会导致次优查询成本. 当 leaf_size 接近 1 时, 遍历节点所涉及的开销大大减慢了查询时间. 当 leaf_size, 接近训练集的大小，查询变得本质上是暴力的. 这些之间的一个很好的妥协是 leaf_size = 30, 这是该参数的默认值.

内存 随着leaf_size的增加，存储树结构所需的内存减少。 对于存储每个节点的D维质心的ball tree，这点至关重要。 针对 BallTree 所需的存储空间近似于 1 / leaf_size 乘以训练集的大小.

leaf_size 不被 brute force queries（暴力查询）所引用.

五、最近邻算法的选择

对于给定数据集的最优算法是一个复杂的选择, 并且取决于多个因素:

  • 样本数量 N(i.e. n_samples) 和维度 D (例如. n_features).

    1、Brute force 查询时间以 O[D N] 增长

    2、Ball tree 查询时间大约以 O[Dlog(N)] 增长

    3、KD tree 的查询时间 D 的变化是很难精确描述的.

    • 对于较小的 D (小于20) 的成本大约是 O[Dlog(N)] , 并且 KD 树更加有效.

    • 对于较大的 D 成本的增加接近 O[DN], 由于树结构引起的开销会导致查询效率比暴力还要低.

    4、对于小数据集(N小于30), logN 相当于N , 暴力算法比基于树的算法更加有效.

    KDTree 和 BallTree 通过提供一个 leaf size 参数来解决这个问题:

    这控制了查询切换到暴力计算样本数量. 使得两种算法的效率都能接近于对较小的 N 的暴力计算的效率.

  • 数据结构: 数据的 intrinsic dimensionality (本征维数) 和/或数据的 sparsity (稀疏度). 本征维数是指数据所在的流形的维数d<=D, 在参数空间可以是线性或非线性的. 稀疏度指的是数据填充参数空间的程度(这与“稀疏”矩阵中使用的概念不同, 数据矩阵可能没有零项, 但是从这个意义上来讲,它的 structure 仍然是 “稀疏” 的)。

    • Brute force (暴力查询)时间不受数据结构的影响。
    • Ball tree 和 KD tree 的数据结构对查询时间影响很大. 一般地, 小维度的 sparser (稀疏) 数据会使查询更快. 因为 KD 树的内部表现形式是与参数轴对齐的, 对于任意的结构化数据它通常不会表现的像 ball tree 那样好.

    在机器学习中往往使用的数据集是非常结构化的, 而且非常适合基于树结构的查询。

  • query point（查询点）所需的近邻数 k。

    1、Brute force 查询时间几乎不受 k 值的影响.

    2、Ball tree 和 KD tree 的查询时间会随着 k 的增加而变慢.

    这是由于两个影响: 首先 k 的值越大在参数空间中搜索的部分就越大. 其次, 使用 k>1 进行树的遍历时, 需要对内部结果进行排序.

    当 k 相比 N 变大时, 在基于树的查询中修剪树枝的能力是减弱的. 在这种情况下, 暴力查询会更加有效.

  • query points（查询点）数.

    ball tree 和 KD Tree 都需要一个构建阶段. 在许多查询中分摊时，这种结构的成本可以忽略不计。 如果只执行少量的查询, 可是构建成本却占总成本的很大一部分. 如果仅需查询很少的点, 暴力方法会比基于树的方法更好.