杰克·范德普拉斯 < vanderplas@astro.washington.edu>

sklearn.neighbors

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

最近邻方法的原理是找到与新点距离最近的预定义数量的训练样本，并根据这些样本预测标签。样本数量可以是用户定义的常数（k最近邻学习），也可以根据点的局部密度变化（基于半径的最近邻学习）。距离通常可以是任何度量标准：标准的欧氏距离是最常见的选择。基于最近邻的方法被称为非泛化机器学习方法，因为它们只是“记住”所有的训练数据（可能转换为快速索引结构，如Ball Tree <ball_tree>或KD Tree <kd_tree>）。

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

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

许多学习例程都依赖于最近邻算法。一个例子是kernel density estimation <kernel_density>，在density estimation <density_estimation>部分讨论。

无监督最近邻

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

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

查找最近邻

对于在两组数据之间查找最近邻的简单任务，可以使用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最近邻。这样的稀疏图在许多情况下都很有用，这些情况利用了点之间的空间关系进行无监督学习：特别是，请参见~sklearn.manifold.Isomap，~sklearn.manifold.LocallyLinearEmbedding和~sklearn.cluster.SpectralClustering。

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']

最近邻分类

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

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

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

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

示例：

• sphx_glr_auto_examples_neighbors_plot_classification.py：使用最近邻进行分类的示例。

最近邻回归

当数据标签是连续变量而不是离散变量时，可以使用基于最近邻的回归。对于查询点，分配的标签是基于其最近邻的标签的均值计算得出的。

scikit-learn 实现了两种不同的最近邻回归器：KNeighborsRegressor 根据用户指定的整数值 $k$ 学习每个查询点的 $k$ 个最近邻。RadiusNeighborsRegressor 根据用户指定的浮点值 $r$ 学习查询点附近半径为 $r$ 的邻居。

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

在 sphx_glr_auto_examples_miscellaneous_plot_multioutput_face_completion.py 中演示了使用多输出最近邻进行回归的示例。在此示例中，输入 X 是脸部上半部分的像素，输出 Y 是这些脸部下半部分的像素。

示例：

• sphx_glr_auto_examples_neighbors_plot_regression.py：使用最近邻进行回归的示例。
• sphx_glr_auto_examples_miscellaneous_plot_multioutput_face_completion.py：使用最近邻进行多输出回归的示例。

最近邻算法

暴力搜索

快速计算最近邻是机器学习中的一个活跃研究领域。最简单的最近邻搜索实现涉及计算数据集中所有点对之间的距离：对于 $D$ 维度中的 $N$ 个样本，此方法的计算复杂度为 $O[D{N}^2]$。对于小数据样本，高效的暴力搜索方法可能非常有竞争力。然而，随着样本数 $N$ 的增长，暴力方法很快变得不可行。在 sklearn.neighbors 中的类中，使用关键字 algorithm = 'brute' 指定暴力最近邻搜索，并使用 sklearn.metrics.pairwise 中的例程进行计算。

K-D 树

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

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

参考文献：

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

Ball 树

为了解决高维度中 KD 树的效率问题，开发了 ball 树 数据结构。Ball 树将数据递归地划分为由质心 $C$ 和半径 $r$ 定义的节点，使得节点中的每个点都位于由 $r$ 和 $C$ 定义的超球内。通过使用 三角不等式，可以减少邻居搜索的候选点数：

$$|x+y|\le |x|+|y|$$

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

参考文献：

• “Five Balltree Construction Algorithms”，Omohundro, S.M., International Computer Science Institute Technical Report (1989)

最近邻算法的选择

对于给定的数据集，选择最佳算法是一个复杂的选择，取决于多个因素：

• 样本数 $N$（即 n_samples）和维度 $D$（即 n_features）。

  • 暴力搜索 的查询时间随 $D$ 增长为 $O[DN]$
  • Ball 树 的查询时间约为 $O[D\log (N)]$
  • KD 树 的查询时间随 $D$ 变化，很难精确描述。对于小的 $D$（小于 20 左右），成本约为 $O[D\log (N)]$，KD 树查询可以非常高效。对于较大的 $D$，成本增加到接近 $O[DN]$，由于树结构的开销，查询可能比暴力搜索更慢。

  对于小数据集（$N$ 小于 30 左右），$\log (N)$ 与 $N$ 相当，暴力算法可能比基于树的方法更高效。KDTree 和 BallTree 都通过提供 叶子大小 参数来解决这个问题：这控制了查询何时切换到暴力计算。这使得两种算法都可以在小 $N$ 的情况下接近暴力计算的效率。

• 暴力搜索的查询时间不受数据结构的影响。

• 球树和KD树的查询时间可以受到数据结构的很大影响。一般来说，稀疏数据和较小的内在维度会导致更快的查询时间。由于KD树的内部表示与参数轴对齐，它通常不会像球树那样在任意结构化数据上显示出更多的改进。

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

• 查询点请求的邻居数$k$。

  • 暴力搜索的查询时间基本不受$k$值的影响。
  • 球树和KD树的查询时间随着$k$的增加而变慢。这是由于两个效应造成的：首先，较大的$k$会导致需要搜索更大的参数空间。其次，使用$k>1$需要在遍历树时对结果进行内部排队。

  当$k$相对于$N$变大时，基于树的查询的修剪分支能力减弱。在这种情况下，暴力搜索可能比基于树的方法更高效。

• 查询点的数量。球树和KD树都需要一个构建阶段。当在许多查询上摊销时，构建的成本变得可以忽略不计。然而，如果只需要进行少量查询，构建过程可能占据总成本的相当大一部分。如果只需要很少的查询点，暴力搜索比基于树的方法更好。

目前，algorithm = 'auto'在满足以下任何条件时选择'brute'：

• 输入数据是稀疏的
• metric = 'precomputed'
• $D>15$
• $k>=N/2$
• effective_metric_不在'kd_tree'或'ball_tree'的VALID_METRICS列表中

否则，它选择'kd_tree'和'ball_tree'中的第一个具有effective_metric_的VALID_METRICS列表。这个启发式方法基于以下假设：

• 查询点的数量至少与训练点的数量相同
• leaf_size接近其默认值30
• 当$D>15$时，数据的内在维度通常对于基于树的方法来说太高了

leaf_size的影响

如上所述，对于小样本大小，暴力搜索可能比基于树的查询更高效。球树和KD树通过在叶节点内部切换到暴力搜索来解决这个问题。leaf_size参数可以指定此切换的级别。这个参数选择有很多影响：

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

查询时间
较大或较小的leaf_size都可能导致子优化的查询成本。当leaf_size接近1时，遍历节点所涉及的开销可能会显著减慢查询时间。当leaf_size接近训练集的大小时，查询实际上变成了暴力搜索。在这两者之间取得一个很好的折衷是使用leaf_size = 30，这是参数的默认值。

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

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

最近邻算法的有效度量

有关可用度量的列表，请参阅~sklearn.metrics.DistanceMetric类的文档以及sklearn.metrics.pairwise.PAIRWISE_DISTANCE_FUNCTIONS中列出的度量。请注意，"cosine"度量使用~sklearn.metrics.pairwise.cosine_distances。

可以使用上述任何算法的valid_metric属性获取有效度量的列表。例如，可以通过以下方式生成KDTree的有效度量：

>>> from sklearn.neighbors import KDTree >>> print(sorted(KDTree.valid_metrics)) [‘chebyshev’, ‘cityblock’, ‘euclidean’, ‘infinity’, ‘l1’, ‘l2’, ‘manhattan’, ‘minkowski’, ‘p’]

最近质心分类器

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]

最近缩小质心

NearestCentroid分类器有一个shrink_threshold参数，它实现了最近缩小质心分类器。实际上，对于每个质心的每个特征，特征值都被该特征的类内方差除以。然后，特征值通过shrink_threshold进行缩小。特别需要注意的是，如果某个特征值越过零点，它将被设置为零。实际上，这将使该特征不会影响分类。这对于去除噪声特征非常有用。

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

示例：

• sphx_glr_auto_examples_neighbors_plot_nearest_centroid.py：使用不同的缩小阈值进行最近质心分类的示例。

最近邻转换器

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

所有这些估计器都可以在内部计算最近邻，但大多数也接受预计算的最近邻sparse graph，如~sklearn.neighbors.kneighbors_graph和~sklearn.neighbors.radius_neighbors_graph所示。使用mode mode=‘connectivity’，这些函数返回一个二进制邻接稀疏图，如~sklearn.cluster.SpectralClustering所需。而使用mode=‘distance’，它们返回一个距离稀疏图，如~sklearn.cluster.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 启用多进程，而这在某些估计器中可能不可用。

最后，预计算可以由自定义估计器执行，以使用不同的实现，例如近似最近邻方法或具有特殊数据类型的实现。预计算的邻居 稀疏图 需要格式化为与 ~sklearn.neighbors.radius_neighbors_graph 输出相同的格式：

• CSR 矩阵（尽管 COO、CSC 或 LIL 也将被接受）。
• 仅显式存储每个样本相对于训练数据的最近邻。这应该包括与查询点之间的距离为 0 的邻居，包括计算训练数据与自身之间的最近邻时的矩阵对角线。
• 每行的数据应按升序存储距离（可选。未排序的数据将被稳定排序，增加计算开销）。
• 数据中的所有值应为非负数。
• 任何行中都不应有重复的索引（参见 https://github.com/scipy/scipy/issues/5807）。
• 如果传递给预计算矩阵的算法使用 k 最近邻（而不是半径邻域），则每行必须存储至少 k 个邻居（或 k+1，如下面的注释所解释的那样）。

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

示例：

• sphx_glr_auto_examples_neighbors_approximate_nearest_neighbors.py：展示了如何使用 KNeighborsTransformer 和 ~sklearn.manifold.TSNE 进行流水线处理。还提供了两个基于外部包的自定义最近邻估计器。
• sphx_glr_auto_examples_neighbors_plot_caching_nearest_neighbors.py：展示了如何使用 KNeighborsTransformer 和 KNeighborsClassifier 进行流水线处理，以在超参数网格搜索期间启用邻居图的缓存。

邻域成分分析

William de Vazelhes <william.de-vazelhes@inria.fr>

邻域成分分析（NCA，NeighborhoodComponentsAnalysis）是一种距离度量学习算法，旨在改善与标准欧氏距离相比的最近邻分类的准确性。该算法直接在训练集上最大化了一种随机变体的留一法 k 最近邻（KNN）得分。它还可以学习用于数据可视化和快速分类的低维线性投影。

在上面的示例图中，我们考虑了一些来自随机生成数据集的点。我们关注点 3 的随机 KNN 分类。样本 3 与另一个点之间的链接粗细与它们的距离成比例，并且可以看作是随机最近邻预测规则分配给该点的相对权重（或概率）。在原始空间中，样本 3 有许多来自不同类别的随机邻居，因此正确的类别不太可能。然而，在 NCA 学习的投影空间中，具有非零权重的唯一随机邻居来自与样本 3 相同的类别，确保后者将被正确分类。有关更多详细信息，请参见 数学公式 <nca_mathematical_formulation>。

分类

与最近邻分类器（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...

该图显示了在仅使用两个特征进行训练和评分时，最近邻分类和邻域成分分析分类在鸢尾花数据集上的决策边界，以便进行可视化。

降维

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

示例：

• sphx_glr_auto_examples_neighbors_plot_nca_classification.py
• sphx_glr_auto_examples_neighbors_plot_nca_dim_reduction.py
• sphx_glr_auto_examples_manifold_plot_lle_digits.py

数学公式

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

$$\underset{L}{\mathrm{argmax}}\sum _{i=0}^{N-1}{p}_i$$
$$p_i=\sum _{j\in C_i}{p}_{ij}$$

其中 $C_i$ 是与样本 $i$ 属于同一类的点的集合，$p_{ij}$ 是嵌入空间中欧氏距离的 softmax：

$$p_{ij}=\frac{\exp (-||L{x}_i-L{x}_j|{|}^2)}{\sum _{k\ne i}\exp -(||L{x}_i-L{x}_k|{|}^2)},p_{ii}=0$$

马氏距离

NCA 可以看作是学习一个（平方的）马氏距离度量：

$$||L(x_i-x_j)|{|}^2=(x_i-x_j{)}^{T}M(x_i-x_j),$$

其中 $M=L^{T}L$ 是一个大小为 (n_features, n_features) 的对称正半定矩阵。

实现

这个实现遵循原始论文中的解释。对于优化方法，它目前使用 scipy 的 L-BFGS-B 方法，在每次迭代时进行完整的梯度计算，以避免调整学习率并提供稳定的学习。

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

复杂度

训练

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

转换

这里的 transform 操作返回 $L{X}^T$，因此其时间复杂度为 n_components * n_features * n_samples_test。操作中没有额外的空间复杂度。

参考文献：

维基百科关于邻域成分分析（Neighborhood Components Analysis）的条目