1.6. K近邻#

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

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

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

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

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

1.6.1. 无监督K近邻#

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

警告

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

1.6.1.1. 查找K近邻#

对于查找两组数据之间的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近邻矩阵。这种稀疏图在各种利用点之间空间关系进行无监督学习的情况下非常有用：特别是，请参阅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. K近邻分类#

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

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

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

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

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

classification_1

示例

1.6.3. K近邻回归#

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

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. K近邻算法#

1.6.4.1. 暴力搜索#

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

1.6.4.2. K-D Tree#

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

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

参考文献#

1.6.4.3. Ball Tree#

为了解决 KD Trees 在更高维度中的效率低下问题，开发了ball tree数据结构。KD tree沿笛卡尔轴划分数据，而 ball tree 则在一系列嵌套的超球体中划分数据。这使得树的构建成本高于 KD tree，但会产生一种数据结构，即使在非常高的维度上，对于高度结构化的数据也非常有效。

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

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

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

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

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

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

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

    • Ball tree 查询时间大约随 \(O[D \log(N)]\) 增长

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

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

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

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

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

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

  • 查询点所需的邻居数量 \(k\)。

    • 暴力搜索查询时间很大程度上不受 \(k\) 值的影响

    • Ball tree 和 KD tree 查询时间会随着 \(k\) 的增加而变慢。这归因于两种效应：首先，较大的 \(k\) 导致需要搜索更大一部分参数空间。其次，使用 \(k > 1\) 需要在遍历树时对结果进行内部排队。

    当 \(k\) 相对于 \(N\) 变大时，在基于树的查询中剪枝分支的能力会降低。在这种情况下，暴力查询可能更有效。

  • 查询点数。ball tree 和 KD Tree 都需要一个构建阶段。当分摊到许多查询上时，此构建成本可以忽略不计。但是，如果只执行少量查询，则构建可能占总成本的很大一部分。如果只需要很少的查询点，暴力方法优于基于树的方法。

目前，如果满足以下任何条件，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 的影响#

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

构建时间

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

查询时间

较大或较小的 leaf_size 都可能导致次优的查询成本。对于接近1的 leaf_size，遍历节点涉及的开销会显著减慢查询时间。对于接近训练集大小的 leaf_size，查询基本上变成了暴力搜索。在两者之间进行良好折衷的是 leaf_size = 30，这是参数的默认值。

内存

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

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

K近邻算法的有效度量#

有关可用度量列表，请参阅 DistanceMetric 类文档和 sklearn.metrics.pairwise.PAIRWISE_DISTANCE_FUNCTIONS 中列出的度量。请注意，“余弦”度量使用 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. K近邻转换器#

许多 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 分类已被证明在实践中适用于各种大小和难度的数据集。与线性判别分析等相关方法相反，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 设置。例如，下图显示了在 Digits 数据集上使用主成分分析（PCA）、线性判别分析（LinearDiscriminantAnalysis）和邻域成分分析（NeighborhoodComponentsAnalysis）进行降维的比较，该数据集的大小为 \(n_{samples} = 1797\) 和 \(n_{features} = 64\)。数据集被分成大小相等的训练集和测试集，然后进行标准化。为了进行评估，在每种方法找到的2维投影点上计算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\) 的总和，即

\[\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。操作中没有增加空间复杂度。

References