Scikit Learn 简明教程
Scikit Learn - K-Nearest Neighbors (KNN)
本章将帮助您理解 Sklearn 中的最近邻方法。
基于邻居的学习方法有两种类型，即 supervised 和 unsupervised. 。基于受监督邻居的学习既能用于分类，也能用于回归预测问题，但主要用于工业中的分类预测问题。
基于邻居的学习方法没有专门的训练阶段，会在分类时使用所有数据进行训练。它也不会对基础数据做出任何假设。这就是为什么它们本质上是惰性和非参数化的原因。
最近邻方法背后的主要原则是 −
-
找到与新数据点距离最近的一组预定义训练样本
-
根据这些训练样本预测标签。
此处，样本数量可以是用户定义的常数，如 K-最近邻学习，或根据点局部密度而变化，如基于半径的邻近学习。
sklearn.neighbors Module
Scikit-learn 拥有 sklearn.neighbors 模块，可为无监督和有监督的基于邻居的学习方法提供功能。对于输入，该模块中的类可以处理 NumPy 数组或 scipy.sparse 矩阵。
Types of algorithms
可在基于邻居方法的实现中使用的不同类型的算法如下 −
Brute Force
对数据集中所有点对之间的距离进行蛮力计算提供了一种最简单的邻近搜索实现。在数学上，对于 D 维中的 N 个样本，蛮力方法的规模是 0[DN2]
对于小数据样本，此算法可能非常有用，但随着样本数量的增长，它将变得不可行。可以使用关键字 algorithm=’brute’ 来启用蛮力邻近搜索。
K-D Tree
为了解决蛮力方法的计算效率低的问题而发明的一棵基于树的数据结构是 KD 树数据结构。基本上，KD 树是一种称为 K 维树的二叉树结构。它通过将参数空间沿数据轴递归地划分为嵌套正交区域，并填充数据点来划分数据轴。
Advantages
以下是一些 K-D 树算法的优点 −
Construction is fast − 由于划分仅沿着数据轴执行，因此 K-D 树的构建非常快。
Less distance computations − 该算法只需要很少的距离计算即可确定查询点的最近邻。它只需要 𝑶[𝐥𝐨𝐠 (𝑵)] 距离计算。
Disadvantages
Fast for only low-dimensional neighbor searches − 它对于低维（D < 20）邻域搜索非常快，但随着 D 的增长，它变得效率低下。由于划分仅沿着数据轴执行，因此
可以通过编写关键字 algorithm=’kd_tree’ 启用 K-D 树邻近搜索。
Ball Tree
众所周知，KD 树在高维度中效率低下，因此，为了解决 KD 树的这种低效性，开发了 Ball 树数据结构。在数学上，它以一种递归的方式将数据划分为由质心 C 和半径 r 定义的节点，使得节点中的每个点都位于由质心 C 和半径 r 定义的超球体中。它使用三角不等式（如下所示），该不等式减少了邻近搜索的候选点数量
Choosing Nearest Neighbors Algorithm
选择给定数据集的最佳算法取决于以下因素 −
Number of samples (N) and Dimensionality (D)
在选择最近邻算法时，这些是最重要的因素。这是因为以下原因 −
-
蛮力算法的查询时间以 O[DN] 速度增长。
-
球树算法的查询时间以 O[D log(N)] 速度增长。
-
KD 树算法的查询时间随 D 的变化方式非常奇怪，很难描述。当 D < 20 时，开销为 O[D log(N)]，并且此算法非常高效。另一方面，当 D > 20 时效率不高，因为开销增加到接近 O[DN]。
Data Structure
另一个影响这些算法性能的因素是数据的内在维度或稀疏性。这是因为球树和 KD 树算法的查询时间会受到它的极大影响。而蛮力算法的查询时间不受数据结构改变的影响。通常，球树和 KD 树算法在稀疏数据和较小的内在维度上实施时会产生更快的查询时间。