Scikit Learn K-最近邻(KNN)
本章将帮助你理解 Sklearn 中的最近邻方法。
基于邻居的学习方法有两种类型，即监督和无监督。基于监督的邻居学习可用于分类和回归预测问题，但它主要用于工业中的分类预测问题。
基于邻居的学习方法没有专门的训练阶段，在分类时使用所有数据进行训练。它还不对基础数据做任何假设。这就是它们本质上懒惰和非参数化的原因。
最近邻方法的主要原理是：
查找距离新数据点最近的预定义数量的训练样本
从这些数量的训练样本中预测标签。
在这里，样本数量可以是用户定义的常数，如 K-最近邻学习中，或者根据点的局部密度而变化，如基于半径的邻居学习。
sklearn.neighbors 模块
Scikit-learn 有sklearn.neighbors为无监督和有监督的基于邻居的学习方法提供功能的模块。作为输入，此模块中的类可以处理 NumPy 数组或scipy.sparse矩阵。
算法类型
可用于基于邻居的方法实现的不同类型的算法如下：
蛮力
数据集中所有点对之间距离的蛮力计算提供了最简单的邻居搜索实现。在数学上，对于 D 维中的 N 个样本，蛮力方法缩放为0[DN2]
对于小数据样本，该算法非常有用，但随着样本数量的增加，它变得不可行。可以通过写入关键字来启用暴力邻居搜索算法='brute'.
K-D Tree
为解决蛮力方法的计算效率低下而发明的一种基于树的数据结构是 KD 树数据结构。基本上，KD树是一种二叉树结构，称为K维树。它通过将参数空间划分为填充数据点的嵌套正交区域，沿数据轴递归地划分参数空间。
优点
以下是K-D树算法的一些优点：
施工速度快： 由于仅沿数据轴进行分区，因此K-D树的构建速度非常快。
更少的距离计算： 该算法需要非常少的距离计算来确定查询点的最近邻居。只需要?[???(?)]距离计算。
缺点
仅适用于低维邻居搜索的快速： 对于低维(D < 20)邻居搜索非常快，但随着 D 的增长，它变得效率低下。由于分区仅沿数据轴执行，
K-D树邻居搜索可以通过写关键字来启用algorithm='kd_tree'.
球树
众所周知，KD Tree 在更高维度上效率低下，因此，为了解决 KD Tree 的这种低效率，开发了 Ball tree 数据结构。在数学上，它递归地将数据划分为由质心 C 和半径 r 定义的节点，这样节点中的每个点都位于由质心定义的超球面内C和半径r.它使用三角不等式，如下所示，减少了邻域搜索的候选点数
$$\arrowvert X+Y\arrowvert\leq \arrowvert X\arrowvert+\arrowvert Y\arrowvert$$
优点
以下是球树算法的一些优点：
高效处理高度结构化的数据： 由于球树将数据划分为一系列嵌套的超球体，因此在高度结构化的数据上是高效的。
优于 KD 树： 球树在高维度上优于 KD 树，因为它具有球树节点的球形几何形状。
缺点
Costly： 将数据划分为一系列嵌套的超球体，其构建成本非常高。
可以通过编写关键字来启用球树邻居搜索algorithm='ball_tree'.
选择最近邻算法
为给定数据集选择最佳算法取决于以下因素：
样本数(N)和维数(D)
这些是选择最近邻算法时要考虑的最重要因素。原因如下：
Brute Force 算法的查询时间随着 O[DN] 增长。
球树算法的查询时间随着 O[D log(N)] 增长。
KD树算法的查询时间随D以一种很难表征的奇怪方式变化。当 D < 20 时，代价为 O[D log(N)]，该算法非常有效。另一方面，在 D > 20 的情况下效率低下，因为成本增加到接近 O[DN]。
数据结构
影响这些算法性能的另一个因素是数据的内在维度或数据的稀疏性。这是因为球树和KD树算法的查询次数会受到很大的影响。而 Brute Force 算法的查询时间不受数据结构的影响。通常，球树和 KD 树算法在植入具有较小内在维数的稀疏数据时会产生更快的查询时间。
邻居数(k)
一个查询点请求的邻居数(k)会影响Ball树和KD树算法的查询时间。随着邻居数量 (k) 的增加，它们的查询时间变慢。而 Brute Force 的查询时间将不受 k 值的影响。
查询点数
因为，它们需要构建阶段，如果有大量查询点，KD树和球树算法都会有效。另一方面，如果查询点数较少，Brute Force 算法的性能要优于 KD 树和 Ball 树算法。