1.6. 最近邻#

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

最近邻方法背后的原理是找到与新点距离最近的预定义数量的训练样本，并根据这些样本预测标签。样本数量可以是用户定义的常数（k-最近邻学习），或者根据点的局部密度变化（基于半径的邻居学习）。一般来说，距离可以是任何度量指标：标准欧几里得距离是最常见的选择。基于邻居的方法被称为非泛化机器学习方法，因为它们只是“记住”所有训练数据（可能被转换为快速索引结构，例如球树或 KD 树）。

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

中的类 sklearn.neighbors 可以处理 NumPy 数组或 scipy.sparse 矩阵作为输入。对于密集矩阵，支持大量可能的距离度量。对于稀疏矩阵，支持任意闵可夫斯基度量进行搜索。

许多学习例程的核心都依赖于最近邻。一个例子是核密度估计，在密度估计部分进行了讨论。

1.6.1. 无监督最近邻#

NearestNeighbors实现了无监督最近邻学习。它作为三种不同的最近邻算法的统一接口：BallTree、KDTree，以及基于sklearn.metrics.pairwise中的例程的暴力算法。邻居搜索算法的选择通过关键字'algorithm'控制，它必须是['auto', 'ball_tree', 'kd_tree', 'brute']之一。当传递默认值'auto'时，算法尝试从训练数据中确定最佳方法。有关每个选项的优缺点的讨论，请参见最近邻算法。

警告

关于最近邻算法，如果两个邻居\(k+1\)和\(k\)具有相同的距离但不同的标签，则结果将取决于训练数据的排序。

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.]])

数据集的结构使得索引顺序中附近的点在参数空间中也比较接近，从而导致一个近似块对角的 K 最近邻矩阵。这种稀疏图在各种情况下很有用，这些情况利用点之间的空间关系进行无监督学习：特别是，请参见Isomap、LocallyLinearEmbedding和SpectralClustering。

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类文档。有关有效度量的列表，请使用KDTree.valid_metrics和BallTree.valid_metrics

>>> from sklearn.neighbors import KDTree, BallTree
>>> KDTree.valid_metrics
['euclidean', 'l2', 'minkowski', 'p', 'manhattan', 'cityblock', 'l1', 'chebyshev', 'infinity']
>>> BallTree.valid_metrics
['euclidean', 'l2', 'minkowski', 'p', 'manhattan', 'cityblock', 'l1', 'chebyshev', 'infinity', 'seuclidean', 'mahalanobis', 'hamming', 'canberra', 'braycurtis', 'jaccard', 'dice', 'rogerstanimoto', 'russellrao', 'sokalmichener', 'sokalsneath', 'haversine', 'pyfunc']

1.6.2. 最近邻分类#

基于邻居的分类是一种基于实例的学习或非泛化学习：它不试图构建一个通用的内部模型，而只是存储训练数据的实例。分类是从每个点的最近邻的简单多数投票计算出来的：查询点被分配给在该点的最近邻中具有最多代表的数据类。

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

KNeighborsClassifier中的\(k\)近邻分类是最常用的技术。值\(k\)的最佳选择高度依赖于数据：通常，较大的\(k\)会抑制噪声的影响，但会使分类边界不太明显。

在数据采样不均匀的情况下，RadiusNeighborsClassifier中的基于半径的邻居分类可能是更好的选择。用户指定一个固定半径\(r\)，使得稀疏邻域中的点使用更少的最近邻进行分类。对于高维参数空间，由于所谓的“维数灾难”，这种方法的效果会降低。

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

示例

最近邻分类：使用最近邻进行分类的示例。

1.6.3. 最近邻回归#

基于邻居的回归可用于数据标签是连续变量而不是离散变量的情况。分配给查询点的标签是根据其最近邻的标签的平均值计算出来的。

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

基本的最近邻回归使用统一权重：也就是说，局部邻域中的每个点对查询点的分类贡献相同。在某些情况下，对点进行加权，使附近的点对回归的贡献大于远处的点，可能是有利的。这可以通过 weights 关键字来实现。默认值，weights = 'uniform'，为所有点分配相同的权重。 weights = 'distance' 为点分配与查询点距离的倒数成比例的权重。或者，可以提供距离的自定义函数，该函数将用于计算权重。

../_images/sphx_glr_plot_regression_001.png

在使用多输出估计器完成人脸中演示了使用多输出最近邻进行回归。在这个例子中，输入 X 是人脸的上半部分的像素，输出 Y 是这些人脸的下半部分的像素。

../_images/sphx_glr_plot_multioutput_face_completion_001.png

示例

最近邻回归：使用最近邻进行回归的示例。
使用多输出估计器完成人脸：使用最近邻进行多输出回归的示例。

1.6.4. 最近邻算法#

1.6.4.1. 暴力搜索#

快速计算最近邻是机器学习领域的一个活跃研究领域。最简单的最近邻搜索实现涉及对数据集中的所有点对进行暴力计算距离：对于 \(N\) 个样本在 \(D\) 维中，这种方法的规模为 \(O[D N^2]\)。对于小型数据样本，高效的暴力搜索可以非常有竞争力。但是，随着样本数量 \(N\) 的增长，暴力搜索方法很快变得不可行。在 sklearn.neighbors 中的类中，暴力搜索使用关键字 algorithm = 'brute' 指定，并使用 sklearn.metrics.pairwise 中提供的例程计算。

1.6.4.2. KD 树#

为了解决暴力搜索方法的计算效率低下问题，人们发明了各种基于树的数据结构。一般来说，这些结构试图通过有效地编码样本的聚合距离信息来减少所需的距离计算次数。基本思想是，如果点 \(A\) 与点 \(B\) 相距很远，而点 \(B\) 与点 \(C\) 相距很近，那么我们就知道点 \(A\) 和点 \(C\) 相距很远，而无需显式计算它们的距离。这样，最近邻搜索的计算成本可以降低到 \(O[D N \log(N)]\) 或更低。对于大型 \(N\)，这比暴力搜索有了显著的改进。

利用这种聚合信息的早期方法是KD 树数据结构（K 维树的简称），它将二维四叉树和三维八叉树推广到任意维数。KD 树是一种二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌套的正交区域，并将数据点归档到这些区域中。KD 树的构建非常快：因为划分只沿着数据轴进行，所以不需要计算任何 \(D\) 维距离。构建完成后，查询点的最近邻可以通过仅 \(O[\log(N)]\) 次距离计算来确定。虽然 KD 树方法对于低维（\(D < 20\)）最近邻搜索非常快，但随着 \(D\) 变得非常大，它会变得效率低下：这是所谓的“维数灾难”的一种表现形式。在 scikit-learn 中，KD 树最近邻搜索使用关键字 algorithm = 'kd_tree' 指定，并使用类 KDTree 计算。

1.6.4.3. 球树#

为了解决 KD 树在更高维数上的效率低下问题，人们开发了球树数据结构。KD 树沿着笛卡尔轴划分数据，而球树则在一系列嵌套的超球体中划分数据。这使得树的构建比 KD 树更昂贵，但它会产生一个数据结构，即使在非常高的维数下，它也能在高度结构化的数据上非常有效。

球树递归地将数据划分为由质心 \(C\) 和半径 \(r\) 定义的节点，使得节点中的每个点都位于由 \(r\) 和 \(C\) 定义的超球体中。通过使用三角不等式，可以减少最近邻搜索的候选点数

\[|x+y| \leq |x| + |y|\]

有了这种设置，测试点与质心之间的单个距离计算就足以确定节点内所有点距离的下限和上限。由于球树节点的球形几何形状，它可以在高维中胜过KD 树，尽管实际性能高度依赖于训练数据的结构。在 scikit-learn 中，基于球树的最近邻搜索使用关键字 algorithm = 'ball_tree' 指定，并使用类 BallTree 计算。或者，用户可以直接使用 BallTree 类。

Choice of Nearest Neighbors Algorithm#

The optimal algorithm for a given dataset is a complicated choice, and depends on a number of factors:

number of samples \(N\) (i.e. n_samples) and dimensionality \(D\) (i.e. n_features).
- Brute force query time grows as \(O[D N]\)
- Ball tree query time grows as approximately \(O[D \log(N)]\)
- KD tree query time changes with \(D\) in a way that is difficult to precisely characterise. For small \(D\) (less than 20 or so) the cost is approximately \(O[D\log(N)]\), and the KD tree query can be very efficient. For larger \(D\), the cost increases to nearly \(O[DN]\), and the overhead due to the tree structure can lead to queries which are slower than brute force.
For small data sets (\(N\) less than 30 or so), \(\log(N)\) is comparable to \(N\), and brute force algorithms can be more efficient than a tree-based approach. Both KDTree and BallTree address this through providing a leaf size parameter: this controls the number of samples at which a query switches to brute-force. This allows both algorithms to approach the efficiency of a brute-force computation for small \(N\).
data structure: intrinsic dimensionality of the data and/or sparsity of the data. Intrinsic dimensionality refers to the dimension \(d \le D\) of a manifold on which the data lies, which can be linearly or non-linearly embedded in the parameter space. Sparsity refers to the degree to which the data fills the parameter space (this is to be distinguished from the concept as used in “sparse” matrices. The data matrix may have no zero entries, but the structure can still be “sparse” in this sense).
- Brute force query time is unchanged by data structure.
- Ball tree and KD tree query times can be greatly influenced by data structure. In general, sparser data with a smaller intrinsic dimensionality leads to faster query times. Because the KD tree internal representation is aligned with the parameter axes, it will not generally show as much improvement as ball tree for arbitrarily structured data.
Datasets used in machine learning tend to be very structured, and are very well-suited for tree-based queries.
number of neighbors \(k\) requested for a query point.
- Brute force query time is largely unaffected by the value of \(k\)
- Ball tree and KD tree query time will become slower as \(k\) increases. This is due to two effects: first, a larger \(k\) leads to the necessity to search a larger portion of the parameter space. Second, using \(k > 1\) requires internal queueing of results as the tree is traversed.
As \(k\) becomes large compared to \(N\), the ability to prune branches in a tree-based query is reduced. In this situation, Brute force queries can be more efficient.
number of query points. Both the ball tree and the KD Tree require a construction phase. The cost of this construction becomes negligible when amortized over many queries. If only a small number of queries will be performed, however, the construction can make up a significant fraction of the total cost. If very few query points will be required, brute force is better than a tree-based method.

Currently, algorithm = 'auto' selects 'brute' if any of the following conditions are verified:

input data is sparse
metric = 'precomputed'
\(D > 15\)
\(k >= N/2\)
effective_metric_ isn’t in the VALID_METRICS list for either 'kd_tree' or 'ball_tree'

Otherwise, it selects the first out of 'kd_tree' and 'ball_tree' that has effective_metric_ in its VALID_METRICS list. This heuristic is based on the following assumptions:

the number of query points is at least the same order as the number of training points
leaf_size is close to its default value of 30
when \(D > 15\), the intrinsic dimensionality of the data is generally too high for tree-based methods

1.6.5. 最近质心分类器#

NearestCentroid 分类器是一种简单的算法，它用每个类成员的质心来表示每个类。实际上，这使其类似于 KMeans 算法的标签更新阶段。它也没有参数可供选择，使其成为一个良好的基线分类器。但是，它在非凸类以及类具有极大差异的方差时会受到影响，因为它假设所有维度的方差相等。有关不作此假设的更复杂方法，请参见线性判别分析（LinearDiscriminantAnalysis）和二次判别分析（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。最值得注意的是，如果某个特定特征值越过零，则将其设置为零。实际上，这会消除该特征对分类的影响。例如，这对于去除噪声特征很有用。

在下面的示例中，使用小的收缩阈值将模型的准确率从 0.81 提高到 0.82。

示例

最近质心分类：使用具有不同收缩阈值的最近质心进行分类的示例。

1.6.6. 最近邻转换器#

许多 scikit-learn 估计器依赖于最近邻：一些分类器和回归器，例如 KNeighborsClassifier 和 KNeighborsRegressor，但还有一些聚类方法，例如 DBSCAN 和 SpectralClustering，以及一些流形嵌入，例如 TSNE 和 Isomap。

所有这些估计器都可以在内部计算最近邻，但大多数估计器也接受由稀疏图给出的预先计算的最近邻，如 kneighbors_graph 和 radius_neighbors_graph 所提供。使用 mode='connectivity' 模式，这些函数将返回二进制邻接稀疏图，例如，在 SpectralClustering 中需要。而使用 mode='distance' 模式，它们将返回距离稀疏图，例如，在 DBSCAN 中需要。为了将这些函数包含在 scikit-learn 管道中，还可以使用相应的类 KNeighborsTransformer 和 RadiusNeighborsTransformer。这种稀疏图 API 的优势有很多。

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

>>> import tempfile
>>> from sklearn.manifold import Isomap
>>> from sklearn.neighbors import KNeighborsTransformer
>>> from sklearn.pipeline import make_pipeline
>>> from sklearn.datasets import make_regression
>>> cache_path = tempfile.gettempdir()  # we use a temporary folder here
>>> X, _ = make_regression(n_samples=50, n_features=25, random_state=0)
>>> estimator = make_pipeline(
...     KNeighborsTransformer(mode='distance'),
...     Isomap(n_components=3, metric='precomputed'),
...     memory=cache_path)
>>> X_embedded = estimator.fit_transform(X)
>>> X_embedded.shape
(50, 3)

其次，预先计算图可以对最近邻估计进行更精细的控制，例如，通过参数 n_jobs 启用多处理，而这可能并非所有估计器都可用。

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

CSR 矩阵（虽然 COO、CSC 或 LIL 会被接受）。
仅显式存储每个样本相对于训练数据的最近邻。这应该包括与查询点距离为 0 的那些点，包括在计算训练数据本身之间的最近邻时矩阵对角线。
每行的 data 应该按升序存储距离（可选。未排序的数据将被稳定排序，增加计算开销）。
数据中的所有值都应该是非负的。
任何行中都不应该有重复的 indices（参见 scipy/scipy#5807）。
如果传递给预先计算矩阵的算法使用 k 个最近邻（而不是半径邻域），那么每行中必须至少存储 k 个邻近（或 k+1，如以下说明）。

注意

当查询特定数量的邻近时（使用 KNeighborsTransformer），n_neighbors 的定义是模棱两可的，因为它可以包含每个训练点作为其自身的邻近，也可以排除它们。两种选择都不完美，因为包含它们会导致训练和测试期间非自身邻近的数量不同，而排除它们会导致 fit(X).transform(X) 和 fit_transform(X) 之间的差异，这违反了 scikit-learn API。在 KNeighborsTransformer 中，我们使用将每个训练点作为其自身邻近包含在 n_neighbors 计数中的定义。但是，出于与其他使用其他定义的估计器的兼容性，当 mode == 'distance' 时，将计算一个额外的邻近。为了最大限度地与所有估计器兼容，一个安全的做法是在自定义最近邻估计器中始终包含一个额外的邻近，因为不必要的邻近将被后续估计器过滤掉。

示例

TSNE 中的近似最近邻：一个将 KNeighborsTransformer 和 TSNE 连接到一起的示例。还提出了两个基于外部包的自定义最近邻估计器。
缓存最近邻：一个将 KNeighborsTransformer 和 KNeighborsClassifier 连接到一起的示例，以在超参数网格搜索期间启用邻近图的缓存。

1.6.7. 邻域成分分析#

邻域成分分析（NCA，NeighborhoodComponentsAnalysis）是一种距离度量学习算法，旨在提高与标准欧几里得距离相比的最近邻分类的准确性。该算法直接最大化训练集上留一法 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...

该图显示了在仅训练和评分两个特征（用于可视化目的）时，虹膜数据集上的最近邻分类和邻域成分分析分类的决策边界。

1.6.7.2. 降维#

NCA 可用于执行监督降维。输入数据被投影到一个线性子空间上，该子空间由最小化 NCA 目标的方向组成。可以使用参数 n_components 设置所需的维数。例如，下图显示了使用主成分分析 (PCA)、线性判别分析 (LinearDiscriminantAnalysis) 和邻域成分分析 (NeighborhoodComponentsAnalysis) 对 Digits 数据集进行降维的比较，该数据集的大小为 \(n_{samples} = 1797\) 和 \(n_{features} = 64\)。数据集被分成大小相等的训练集和测试集，然后进行标准化。为了评估，在每个方法找到的二维投影点上计算 3-最近邻分类精度。每个数据样本属于 10 个类别中的一个。

示例

1.6.7.3. 数学公式#

NCA 的目标是学习一个大小为 (n_components, n_features) 的最佳线性变换矩阵，该矩阵最大化所有样本 \(i\) 的概率 \(p_i\) 的总和，即 \(i\) 被正确分类的概率，即

\[\underset{L}{\arg\max} \sum\limits_{i=0}^{N - 1} p_{i}\]

其中 \(N\) = n_samples，\(p_i\) 是样本 \(i\) 在学习到的嵌入空间中根据随机最近邻规则被正确分类的概率

\[p_{i}=\sum\limits_{j \in C_i}{p_{i j}}\]

其中 \(C_i\) 是与样本 \(i\) 同类别的点的集合，\(p_{i j}\) 是嵌入空间中欧几里得距离的 softmax

\[p_{i j} = \frac{\exp(-||L x_i - L x_j||^2)}{\sum\limits_{k \ne i} {\exp{-(||L x_i - L x_k||^2)}}} , \quad p_{i i} = 0\]

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. 转换#

这里 transform 操作返回 \(LX^T\)，因此它的时间复杂度等于 n_components * n_features * n_samples_test。操作中没有额外的空间复杂度。

参考文献

维基百科关于邻域成分分析的条目