1.6. 最近邻#

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

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

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

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

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

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'分配与查询点距离的倒数成比例的权重。或者，可以提供距离的用户定义函数来计算权重。

classification_1

示例

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类。

参考文献#
最近邻算法的选择#

对于给定数据集，最佳算法的选择非常复杂，取决于许多因素。

  • 样本数量\(N\)（即n_samples）和维度\(D\)（即n_features）。

    • 暴力搜索查询时间增长为\(O[D N]\)

    • 球树查询时间增长近似为\(O[D \log(N)]\)

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

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

  • 数据结构：数据的内在维度和/或数据的稀疏性。内在维度指的是数据所在的流形的维度\(d \le D\)，它可以线性或非线性地嵌入到参数空间中。稀疏性指的是数据填充参数空间的程度（这与“稀疏”矩阵中使用的概念不同。数据矩阵可能没有零条目，但在这个意义上，**结构**仍然可以是“稀疏”的）。

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

    • 球树和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都可能导致次优的查询成本。对于接近1的leaf_size，遍历节点的开销会显著降低查询速度。对于接近训练集大小的leaf_size，查询本质上变成了暴力搜索。一个很好的折衷方案是leaf_size = 30，这是参数的默认值。

内存

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

暴力搜索查询不引用leaf_size。

最近邻算法的有效度量#

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

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

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

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。

nearest_centroid_1 nearest_centroid_2

示例

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

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 应按升序存储距离（可选。未排序的数据将被稳定排序，增加计算开销）。

  • 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' 时，将计算一个额外的邻居。为了最大限度地与所有估计器兼容，安全的选择是在自定义最近邻估计器中始终包含一个额外的邻居，因为不必要的邻居将被后续估计器过滤。

示例

1.6.7. 邻域成分分析#

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

nca_illustration_1 nca_illustration_2

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

1.6.7.1. 分类#

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

NCA 分类已被证明在实践中适用于不同大小和难度的dataset。与线性判别分析等相关方法相比，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_classification_1 nca_classification_2

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

1.6.7.2. 降维#

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

nca_dim_reduction_1 nca_dim_reduction_2 nca_dim_reduction_3

示例

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\]
马氏距离#

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

\[|| L(x_i - x_j)||^2 = (x_i - x_j)^TM(x_i - x_j),\]

其中 \(M = L^T L\) 是一个大小为 (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. 转换#

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

参考文献