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