Scikit Learn - K近邻算法 (KNN)

本章将帮助您理解 Sklearn 中的最近邻方法。

基于邻域的学习方法有两种类型，即监督和无监督。监督的基于邻域的学习可用于分类和回归预测问题，但在工业中主要用于分类预测问题。

基于邻域的学习方法没有专门的训练阶段，并在分类期间使用所有数据进行训练。它也不对底层数据做任何假设。这就是它们本质上是懒惰的和非参数的原因。

最近邻方法背后的主要原理是：

这里，样本数量可以是用户定义的常数，如 K 近邻学习，或者根据点的局部密度变化，如基于半径的邻域学习。

Scikit-learn 拥有sklearn.neighbors模块，该模块提供了用于无监督和监督基于邻域的学习方法的功能。作为输入，此模块中的类可以处理 NumPy 数组或scipy.sparse矩阵。

算法类型

基于邻域方法实现中可使用的不同类型的算法如下：

数据集所有点对之间距离的蛮力计算提供了最简单的邻域搜索实现。在数学上，对于 D 维中的 N 个样本，蛮力方法的规模为0[DN²]

对于小样本数据，此算法非常有用，但随着样本数量的增长，它变得不可行。蛮力邻域搜索可以通过编写关键字algorithm='brute'来启用。

为了解决蛮力方法的计算效率低下问题，人们发明了一种基于树的数据结构，即 KD 树数据结构。基本上，KD 树是一种二叉树结构，称为 K 维树。它通过将参数空间沿数据轴递归地划分成嵌套的正交区域，并将数据点填充到这些区域中，从而递归地划分参数空间。

以下是 KD 树算法的一些优点：

构建速度快 - 由于分区仅沿数据轴执行，因此 KD 树的构建速度非常快。

距离计算少 - 此算法只需要很少的距离计算即可确定查询点的最近邻。它只需要𝑶[𝐥𝐨𝐠 (𝑵)]距离计算。

仅适用于低维邻域搜索 - 对于低维 (D < 20) 邻域搜索速度非常快，但随着 D 的增长，它变得效率低下。由于分区仅沿数据轴执行，

可以通过编写关键字algorithm='kd_tree'来启用 KD 树邻域搜索。

众所周知，KD 树在高维情况下效率低下，因此为了解决 KD 树的这种效率低下问题，开发了球树数据结构。在数学上，它将数据递归地划分为由质心 C 和半径 r 定义的节点，以使节点中的每个点都位于由质心C和半径r定义的超球体内。它使用以下给出的三角不等式，这减少了邻域搜索的候选点数

$$\arrowvert X+Y\arrowvert\leq \arrowvert X\arrowvert+\arrowvert Y\arrowvert$$

以下是球树算法的一些优点：

在高度结构化的数据上高效 - 由于球树将数据划分为一系列嵌套的超球体，因此它在高度结构化的数据上效率很高。

性能优于 KD 树 - 球树在高维情况下优于 KD 树，因为它具有球树节点的球形几何形状。

代价高昂 - 将数据划分为一系列嵌套的超球体使其构建非常昂贵。

可以通过编写关键字algorithm='ball_tree'来启用球树邻域搜索。

对于给定数据集选择最佳算法取决于以下因素：

在选择最近邻算法时，这些是最重要的因素。这是因为以下原因：

蛮力算法的查询时间增长为 O[DN]。
球树算法的查询时间增长为 O[D log(N)]。
KD 树算法的查询时间以一种难以描述的奇怪方式随 D 变化。当 D < 20 时，成本为 O[D log(N)]，并且此算法非常高效。另一方面，当 D > 20 时，它效率低下，因为成本增加到接近 O[DN]。

影响这些算法性能的另一个因素是数据的内在维度或数据的稀疏性。这是因为球树和 KD 树算法的查询时间可能会受到其很大影响。而蛮力算法的查询时间不受数据结构的影响。通常，当在具有较小内在维度的更稀疏数据上实现时，球树和 KD 树算法会产生更快的查询时间。

为查询点请求的邻居数 (k) 会影响球树和 KD 树算法的查询时间。随着邻居数 (k) 的增加，它们的查询时间会变慢。而蛮力算法的查询时间不会受到 k 值的影响。

因为它们需要构建阶段，所以如果查询点数很多，KD 树和球树算法将非常有效。另一方面，如果查询点数较少，则蛮力算法的性能优于 KD 树和球树算法。

打印页面