1.6 最近邻¶

sklearn.neighbors提供了基于近邻的无监督和有监督的学习方法的功能。无监督最近邻是许多其他学习方法的基础，特别是流形学习(manifold learning)和光谱聚类(spectral clustering)。有监督的 neighbors-based (基于邻居的) 学习有两种方式：离散标签数据的分类和连续标签数据的回归。

最近邻方法背后的原理是找到在距离上离新样本最近的一些样本， 并且从这些样本中预测标签。最近邻的样本数可以是用户定义的常数(k-最近邻)，也可以根据不同的点的局部密度(基于半径的近邻学习)确定。一般来说，距离可以用任意来度量：标准的欧氏距离是最常见的选择。基于邻居的方法被称为非泛化机器学习方法，因为它们只是“记住”它的所有训练数据(可能转换成一个快速的索引结构，比如Ball树或KD树)。

尽管它很简单，但最近邻已经成功地解决了大量的分类和回归问题，包括手写数字和卫星图像等场景。作为一种非参数方法，在决策边界非常不规则的情况下通常是成功的。

sklearn.neighbors 中的类输入不管是numpy中的array数组， 还是scipy.sparse矩阵都可以处理。对于密集矩阵，可以支持大量的距离度量。于稀疏矩阵，支持任意的Minkowski度量进行搜索。

有许多学习规则都是依赖于它们的核心近邻。一个例子是核密度估计( kernel density estimation,)，在密度估计( density estimation)部分讨论。

1.6.1.无监督最近邻

NearestNeighbors实现了无监督的最近邻学习。它充当三个不同的最近邻算法的统一接口：BallTree和KDTree和一个基于sklearn.emeics.pair中规则的暴力算法。最近邻搜索算法的选择是通过关键字algorithm来控制的, 其选择必须是['auto', 'ball_tree', 'kd_tree', 'brute']中的一个。当传递默认值‘auto’时，该算法尝试从训练数据中自动查出最佳的方法。有关每个选项的优缺点的讨论，请参见Nearest Neighbor Algorithms。

1.6.1.1 找到最近邻

对于在两组数据之间寻找最近邻的简单任务，可以使用sklearn.neighbors中的无监督算法：

>>> from sklearn.neighbors import NearestNeighbors
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
>>> distances, indices = nbrs.kneighbors(X)
>>> indices
array([[0, 1],
       [1, 0],
       [2, 1],
       [3, 4],
       [4, 3],
       [5, 4]]...)
>>> distances
array([[0.        , 1.        ],
       [0.        , 1.        ],
       [0.        , 1.41421356],
       [0.        , 1.        ],
       [0.        , 1.        ],
       [0.        , 1.41421356]])

因为查询集与训练集匹配，所以每个点的最近邻居就是该点本身，距离为零。

还可以有效地生成表示相邻点之间的连接的稀疏图：

>>> nbrs.kneighbors_graph(X).toarray()
array([[1., 1., 0., 0., 0., 0.],
       [1., 1., 0., 0., 0., 0.],
       [0., 1., 1., 0., 0., 0.],
       [0., 0., 0., 1., 1., 0.],
       [0., 0., 0., 1., 1., 0.],
       [0., 0., 0., 0., 1., 1.]])

1.6.1.2 KDTree和BallTree类

或者，可以直接使用KDTree或BallTree类来查找最近的邻居。这是上文使用过的NearestNeighbors类包装的功能， Ball Tree和KD Tree具有相同的接口；我们将在这里展示使用KD Tree的示例：

>>> from sklearn.neighbors import KDTree
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> kdt = KDTree(X, leaf_size=30, metric='euclidean')
>>> kdt.query(X, k=2, return_distance=False)          
array([[0, 1],
 [1, 0],
 [2, 1],
 [3, 4],
 [4, 3],
 [5, 4]]...)

有关最近邻搜索可用选项的更多信息，请参阅KDTree和BallTree类文档，包括查询策略规范、距离度量等。有关可用度量的列表，请参见DistanceMetric 类的文档。

1.6.2 最近邻分类

基于近邻的分类是一种基于实例的学习或非泛化学习：它不是试图构造一个通用的内部模型，而是简单地存储训练数据的实例。分类是由每个点的最近邻的简单多数投票中计算得到的：一个查询点被标记的数据标签是由它最近邻点中最具代表性的数据标签来决定的。

scikit-learn实现了两个不同的最近邻分类器： KNeighborsClassifier 分类器根据每个查询点的k个最近邻实现学习，其中k是用户指定的整数值。 RadiusNeighborsClassifier分类器根据每个训练点的固定半径内的邻居数实现学习，其中 是用户指定的浮点值。

KNeighborsClassifier 中的K近邻分类是最常用的分类方法。k值的最佳选择是高度依赖于数据的：一般来说，较大的 会抑制噪声的影响，但使分类边界不那么清晰。

在数据不均匀采样的情况下， RadiusNeighborsClassifier中基于半径的近邻分类是更好的选择。用户指定一个固定的半径，以便在稀疏的邻居中使用更少的最近邻居来进行分类。对于高维参数空间，这种方法由于所谓的 “维度灾难” 而变得不那么有效。

基本的最近邻分类使用一样的权重：也就是说，分配给查询点的值是根据最近邻居的简单多数投票计算的。在某些情况下，最好是对邻居进行加权，这样更靠近的邻居对拟合来说贡献更大。这可以通过weights关键字来实现。默认值是weights=“uniform”，为每个邻居分配同样的权重。weights = 'distance'分配的权重与到查询点的距离成反比。或者，可以提供用户定义的距离函数来计算权重.

1.6.3 最近邻回归

如果数据标签是连续的，而不是离散的变量，则可以使用基于邻居的回归。分配给查询点的标签是根据其最近邻居的标签的平均值计算的。

scikit-learn实现了两个不同的近邻回归器：KNeighborsRegressor实现基于每个查询点的k个最近邻的学习，其中k是用户指定的整数值。 RadiusNeighborsRegressor实现了基于查询点的固定半径r内的近邻的学习，其中r是用户指定的浮点数值。

最基本的最近邻回归使用的是一样的权重：即，局部邻域中的每个点对查询点的分类都有一样的贡献。在某些情况下，它可以是有利的，即距离更近的点对回归的贡献要大于更远的点。这可以通过weights关键字来实现。默认值是weights = 'uniform'，为所有点分配一样的权重。 weights = 'distance'分配权重与到查询点的距离成反比。或者，可以提供用户定义的距离函数，该函数将用于计算权重。

在 基于多输出估计的人脸绘制中演示了多输出最近邻回归的使用。在这个示例中，输入 X 是脸上半部分像素，输出 Y 是脸下半部分像素。

1.6.4.最近邻算法

1.6.4.1 暴力计算

最近邻的快速计算是机器学习中一个活跃的研究领域。最朴素的近邻搜索的实现涉及到数据集中所有成对点之间距离的暴力计算：对于维中的个样本来说，这种方法的复杂度为。高效的暴力近邻搜索对于小数据样本来说是非常有竞争力的。然而，随着样本的增加，暴力法很快就变得不可行了。在类sklearn.neighbors中，暴力近邻搜索是使用关键字algorithm = 'brute'指定的，并使用 sklearn.metrics.pairwise中可用的程序来计算。

1.6.4.2 K-D树

为了解决暴力法计算效率低下的问题，人们发明了多种基于树的数据结构。通常，这些结构试图通过有效编码样本的聚合距离(aggregate distance)信息来减少所需的距离计算量。基本思想是，如果点离点很远，点离点很近，那么我们就知道点和是很远的，不需要显式地计算它们的距离。这样，最近邻搜索的计算成本可以降低到或更好。这是一个在大型的数据集上超越暴力法的重要实现。

利用这些聚合信息的早期方法是KD树数据结构(K-dimensional tree的缩写)，它将二维Quad-trees和三维Oct-trees推广到任意维数。KD树是一种二叉树结构，它递归地沿数据轴划分参数空间，将其划分为嵌套的正交异性区域，然后将数据点放入其中。KD树的构造非常快：因为分区只沿数据轴执行，所以不需要计算维距离。一旦构造，仅通过复杂度为的距离计算就可以确定查询点的最近邻居。虽然KD树方法对于低维()邻域搜索非常快速，但随着增大，它变得效率低下：这是所谓的“维度诅咒”的一种表现。在scikit-learn中，KD树近邻搜索使用关键字algorithm = 'kd_tree'指定，并使用 KDTree类进行计算。

参考

“Multidimensional binary search trees used for associative searching”, Bentley, J.L., Communications of the ACM (1975)

1.6.4.3 Ball树

针对KD树高维度下效率低的问题，提出了球状树的数据结构。其中KD树沿着笛卡尔轴划分数据，球树在一系列嵌套超球(hyper-spheres)中划分数据。这使得树的构建比KD树的代价更高，但是导致了一种对高度结构化非常有效的数据结构，即使在非常高的维度上也是如此。

球树递归地将数据划分为由质心和半径定义的节点，这样节点中的每个点都位于和定义的超球面内，通过使用三角不等式减少了邻居搜索的候选点数：

使用此设置，测试点和质心之间的单个距离计算就足以确定节点内所有点之间距离的上下界。由于球状树节点的球形几何特性，虽然实际性能与训练数据的结构有很大的关系，但它可以在高维上表现出一棵KD树。在scikit-learn中，基于球树的邻居搜索是使用关键字algorithm = 'ball_tree'指定的，并且是使用类 sklearn.neighbors.BallTree计算的。或者，用户可以直接使用 BallTree 类。

参考文献

“Five balltree construction algorithms”, Omohundro, S.M., International Computer Science Institute Technical Report (1989)

1.6.4.4 最近邻算法的选择

给定数据集的优化算法是一个复杂的选择，取决于以下几个因素：

• 样本数(即n_samples)和维数(即n_features)。

  • Brute force查询的时间以增长
  • Ball tree查询时间以增长
  • KD树查询时间随变化，难以精确描述。对于较小的(小于20)，代价约为​，KD树查询效率很高。对于较大的，成本增加到接近，而树结构造成的开销可能导致比暴力更慢的查询。

  对于小数据集(小于30)，可与相比较，而蛮力算法比基于树的方法更有效。 KDTree 和 BallTree都通过提供一个leaf size参数来解决这个问题：这控制了查询切换到暴力的样本数。这使得这两种算法都能接近小样本的暴力计算的效率。

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

  • Brute force (暴力查询)时间不受数据结构的影响。
  • 数据结构对球状树和KD树的查询次数有很大的影响。通常，内部维数较小的稀疏数据会导致更快的查询时间。由于KD树的内部表示是与参数轴对齐的，所以对于任意结构的数据，它通常不会像球状树那样显示出更多的改进。

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

• 查询点的邻居数。

  • 的值很大程度上不影响暴力查询的时间
  • 随着的增加，球树和KD树的查询时间会变慢。这有两个原因：首先，较大的k需要搜索参数空间的更大部分。其次，使用k>1需要在遍历树时对结果进行内部排队。

  与相比，当变得很大时，在基于树的查询中剪支的能力就降低了。在这种情况下，BruteForce查询可以更高效。

• 查询点的数量。球状树和KD树都需要一个构建阶段。当对许多查询进行摊销时，这种结构的成本可以忽略不计。但是，如果只执行少量的查询，那么构建就可以占总成本的很大一部分。如果查询点很少，暴力法比基于树的方法更好。

目前，如果，输入的数据是稀疏的，或者effective_metric_不在“kd_tree”或“ball_tree”的VALID_METRICS列表中，那么 algorithm = 'auto'选择'brute'。否则，它将从'kd_tree'和'ball_tree' 的VALID_METRICS列表中选择第一个effective_metric_。此选择基于这样的假设：查询点的数量至少与训练点数相同，而且 leaf_size接近其默认值30。

1.6.4.5 leaf_size的影响

如上所述，对于小样本大小，暴力搜索比基于树的查询更有效。在球树和KD树中，通过内部切换到叶节点内的暴力搜索来解释这一事实。此开关的级别可以使用参数leaf_size指定。这个参数的选择有许多影响：

构建时间

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

查询时间

无论是大的还是小的 leaf_size都会导致次优的查询成本。对于接近1的leaf_size，遍历节点所涉及的开销可以显著降低查询时间。对于接近训练集大小的 leaf_size，查询本质上是暴力的。两者之间的一个很好的折衷方法是leaf_size = 30，这是参数的默认值。

内存

随着 leaf_size的增加，存储树结构所需的内存减少。这在球树中尤为重要，它为每个节点存储一个D维质心。 BallTree所需的存储空间大约是训练集大小的1 / leaf_size。

对于暴力查询，不引用leaf_size。

1.6.5 最近质心分类器

NearestCentroid是一个简单的算法，它用成员的质心表示每个类。实际上，这使得它类似于 sklearn.cluster.KMeans算法的标签更新阶段。它也没有参数可供选择，因此它是一个很好的基线分类器。然而，在非凸类上，以及当类具有截然不同的方差时，当所有维度上的方差相等时，它都会受到影响。见线性判别分析。

(sklearn.discriminant_analysis.LinearDiscriminantAnalysis) 和二次判别分析

(sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis) 用于更复杂的方法，这些方法不作此假设。

默认的NearestCentroid的使用很简单：

>>> from sklearn.neighbors import NearestCentroid
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> y = np.array([1, 1, 1, 2, 2, 2])
>>> clf = NearestCentroid()
>>> clf.fit(X, y)
NearestCentroid()
>>> print(clf.predict([[-0.8, -1]]))
[1]

1.6.5.1最近收缩质心

NearestCentroid分类器有一个 shrink_threshold参数，它实现最近收缩质心分类器。实际上，每个质心的每个特征的值除以该特征的类内方差。然后，通过 shrink_threshold降低特征值。最值得注意的是，如果一个特定的特征值超过零，则它被设置为零。功能上，这将从影响分类的功能中删除。例如，这对于消除噪声特特征是有用的。

在下面的例子中，使用一个小的收缩阈值( shrink threshold)将模型的精度从0.81提高到0.82。

1.6.6 最近邻转换

许多scikit-learn的估计器依赖最近邻：几个分类器和回归器，比如KNeighborsClassifier 和KNeighborsRegressor, 还有一些聚类方法，如 DBSCAN和SpectralClustering，以及一些多种嵌入，如 TSNE和 Isomap。

所有这些估计都可以在内部计算最近邻，但大多数估计器也接受由 kneighbors_graph 和radius_neighbors_graph给出的预先计算过的最近邻稀疏图sparse graph。对于模式 mode='connectivity'，这些函数根据需要返回二分类邻居稀疏图，例如，在 SpectralClustering中。然而，如果使用mode='distance'，则会根据需要返回一个距离稀疏图，例如，在 DBSCAN中。要将这些功能包含在scikit-learn的 (pipeline)管道(pipeline)中，还可以使用相应的类KNeighborsTransformer和RadiusNeighborsTransformer。这个稀疏图API的好处是多方面的。

首先，预先计算的图可以重复使用多次，例如，在改变估计器的参数时。这可以由用户手动完成，也可以使用scikit-learn的管道的缓存属性：

>>> from sklearn.manifold import Isomap
>>> from sklearn.neighbors import KNeighborsTransformer
>>> from sklearn.pipeline import make_pipeline
>>> estimator = make_pipeline(
...     KNeighborsTransformer(n_neighbors=5, mode='distance'),
...     Isomap(neighbors_algorithm='precomputed'),
...     memory='/path/to/cache')

第二，预计算图可以对最近邻估计提供更好的控制，例如，通过参数n_jobs实现多处理，这在所有的估计器中可能都不是可用的。

最后，预计算可以由自定义估计器执行，以使用不同的实现，例如近似的最近邻方法，或使用特定数据类型的实现。预先计算过的邻居稀疏图sparse graph需要转化化为 radius_neighbors_graph 的输出：

• 一个CSR矩阵(虽然COO、CSC或LIL也会被接受)。
• 仅显式地存储每个样本相对于训练数据的最近邻。这应该包括与查询点0的距离，包括在计算训练数据与其本身之间最近的邻域时的矩阵对角线。
• 每一行的数据应按递增顺序存储距离(可选)。未排序的数据将是稳定排序的，增加了计算开销)。
• 数据中的所有值都应该是非负的。
• 在任何一行中都不应该有重复的索引indices。(看https://github.com/scipy/scipy/issues/5807)。
• 如果要传递的算法--预先计算的矩阵--使用k个最近邻(相对于半径邻域)，则必须在每一行中存储至少k个邻居(或k+1，如下注所述)。

注意：

当询问特定数量的邻居时(使用 KNeighborsTransformer)，n_neighbors的定义是不明确的，因为它可以将每个训练点作为自己的邻居，也可以将它们排除在外。这两种选择都不是完美的，因为在训练和测试中包含它们会导致不同数量的非自身邻居，而排除它们会导致fit(X).transform(X) and fit_transform(X)之间的不同，这与scikit-learn的API是背道而驰的。在KNeighborsTransformer 中，我们使用了一个定义，每个训练点作为自己的邻居被计算在n_neighbors中。但是，由于与使用另一个定义的其他估计器的兼容性原因，当 mode == 'distance'时，将计算出一个额外的邻居。为了最大化与所有估计器的兼容性，一个安全的选择是总是在自定义的最近邻估计器中包含一个额外的邻居，因为不必要的邻居将通过以下估计器进行过滤。

1.6.7 邻域成分分析

邻域成分分析(NCA，NeighborhoodComponentAnalysis)是一种距离度量学习算法，其目的是与标准欧氏距离相比，提高最近邻分类的准确性。该算法直接在训练集上使用 leave-one-out k近邻(KNN)得分的随机变量最大化。它还可以学习数据的低维线性投影，用于数据可视化和快速分类。

在上面的说明图中，我们考虑了随机生成的数据集中的一些点。重点研究了样本3的随机KNN分类。样本3和另一点之间的连接厚度与它们之间的距离成正比，可以看作是随机最近邻预测规则给这一点分配的相对权重(或概率)。在原始空间中，样本3有许多来自不同类的随机邻居，所以不太可能找到正确的类。然而，在NCA学习的投影空间中，唯一具有不可忽略权重的随机邻居来自与样本3相同的类，从而保证后者将被很好地分类。有关更多细节，请参见数学公式。

1.6.7.1 分类

与最近邻分类器(KNeighborsClassifier)相结合，NCA对分类很有吸引力，因为它可以自然地处理多类问题而不增加模型大小，并且不引入需要用户微调的额外参数。

NCA分类在不同规模和难度的数据集的实际应用中得到了很好的表现。与线性判别分析等相关方法相比，NCA对类分布不作任何假设。最近邻分类可以自然地产生高度不规则的决策边界。

要使用此模型进行分类，需要将学习最优转换的NeighborhoodComponentsAnalysis实例与在投影空间中执行分类的KNeighborsClassifier 实例相结合。下面是一个使用这两个类的示例：

>>> from sklearn.neighbors import (NeighborhoodComponentsAnalysis,
... KNeighborsClassifier)
>>> from sklearn.datasets import load_iris
>>> from sklearn.model_selection import train_test_split
>>> from sklearn.pipeline import Pipeline
>>> X, y = load_iris(return_X_y=True)
>>> X_train, X_test, y_train, y_test = train_test_split(X, y,
... stratify=y, test_size=0.7, random_state=42)
>>> nca = NeighborhoodComponentsAnalysis(random_state=42)
>>> knn = KNeighborsClassifier(n_neighbors=3)
>>> nca_pipe = Pipeline([('nca', nca), ('knn', knn)])
>>> nca_pipe.fit(X_train, y_train)
Pipeline(...)
>>> print(nca_pipe.score(X_test, y_test))
0.96190476...

图中显示了 iris数据集上最近邻分类和邻域成分分析分类的决策边界，当训练和得分仅针对两个特征时，用于可视化目的。

1.6.7.2 降维

NCA可用于有监督降维。将输入数据投影到一个线性子空间，该子空间由最小化NCA目标的方向组成。可以使用参数n_components设置所需的维数。例如，下图显示了与数字数据集上的主成分分析(sklearn.decomposition.PCA)、线性判别分析((sklearn.discriminant_analysis.LinearDiscriminantAnalysis))和邻域成分分析(NeighborhoodComponentsAnalysis)的降维效果的比较, 这个数据集有 个样本， 个特征。数据集被划分为大小相同的训练集和测试集，然后进行标准化。为了评价该方法的分类精度，对每种方法找到的二维投影点进行了3-最近邻分类精度的计算。每个数据样本属于10个类中的一个。

1.6.7.3 数学公式

NCA的目标是学习一个形状为((n_components, n_features))的最优线性变换矩阵，它使所有样本正确分类的概率的和最大，即：

其中=n_samples, 是样本在学习的嵌入空间中按照随机最近邻规则正确分类的概率：

其中是与样本相同类中的点集，是嵌入空间中欧氏距离上的归一化指数Softmax：

1.6.7.3.1 Mahalanobis距离

NCA可以看作是学习(平方)Mahalanobis距离度量：

其中，是一个对称的半正定的矩阵((n_features, n_features))。

1.6.7.4 实现

该实现遵循了最初论文[1]中的解释，对于优化方法，目前使用的是scipy的L-BFGS-B，每次迭代都进行完全梯度计算，以避免调整学习速度，提供稳定的拟合。

请参阅下面的示例和 NeighborhoodComponentsAnalysis.fit的文档以获得更多信息。

1.6.7.5 复杂度

1.6.7.5.1 训练

NCA存储一对距离矩阵，占用了n_samples ** 2的内存。时间复杂度取决于优化算法的迭代次数。但是，可以使用参数max_iter设置迭代的最大次数。对于每个迭代，时间复杂度为O(n_components x n_samples x min(n_samples, n_features))。

1.6.7.5.2 转换

这里转换操作返回值的是，因此它的时间复杂度等于n_components x n_features x n_samples_test。操作中没有增加空间复杂度。

参考

[1] “Neighbourhood Components Analysis”, J. Goldberger, S. Roweis, G. Hinton, R. Salakhutdinov, Advances in Neural Information Processing Systems, Vol. 17, May 2005, pp. 513-520.

Wikipedia entry on Neighborhood Components Analysis