用于拟合 scikit 邻居/半径分类的预计算矩阵

Question

我使用预先计算的指标使用 Scikit-Learn 的最近邻/半径分类。这意味着，我将成对距离的 n_samples_train x n_samples_train 矩阵传递给分类器的拟合方法。

现在我想知道为什么必须这样做。使用 knn 学习只是意味着“存储样本”，但距离的计算应该只在稍后的泛化过程中进行（在该步骤中，我当然会计算训练样本和测试样本之间的距离矩阵，因此大小为 n_samples_train x n_samples_test 的矩阵）。

例如，在 SVM 的情况下，我将一个预先计算的矩阵（Gramian，一个相似性矩阵）传递给 smv.SVC 对象的 fit 方法。然后进行优化，找到支持向量等等。在那里，该矩阵在训练期间是绝对必要的。

但是我看不出为什么需要一个预先计算的矩阵来拟合邻居/半径分类。

有人可以给我一个相关的提示吗？

我很想跳过使用 scikit learn 计算 knn 的训练矩阵。

最好的问候和谢谢。:-)

Answer 1

这是旧的，但我在搜索相关问题时偶然发现了它。

本质上，这是一个性能问题。以您对 k 个邻居/半径分类器进行一次拟合，然后使用它对多个不同的测试点集进行分类的情况为例。如果内核矩阵没有预先计算，那么每次调用 fit() 时都必须计算内核矩阵。这些分类器的实现方式利用了您正在使用正（半）定函数的事实，并且可以使用它来加速使用 kd 树或球树的最近邻居/半径搜索新点，它构建了一个结构，该结构对到每个子树外部的点的距离设置了界限。对于 n 个样本和 k 个邻居（至少对于球树），这种结构的构造可以在 iirc O(k*log(n)) 时间内完成。因此，通过提前做一些工作，可以大大加快新点的分类速度。

要使用实用的解决方案回答您的问题，如果您想使用自定义指标，则无需传递预先计算的距离矩阵。如果您传递可调用作为度量，距离矩阵仍将在一定程度上预先计算 - 但它会在拟合过程中透明地发生，并且实际上应该比暴力计算所有样本对之间的距离更有效你自己（注意，如果你有稀疏输入，分类器仍然会使用暴力。它仍然会使用多个核心，因此可能比你自己做更好，但它的行为会有所不同。）

总结一下：预先计算的距离矩阵对于拟合一般的 k 最近邻分类器并不是严格必要的，这是完全正确的。然而，通过预先计算——无论你这样做还是传递一个可调用的——后续的分类会更加有效。Sklearn 显然选择预先计算自定义指标 - 可能是因为使用 python 函数 n*(n-1)/2 次的开销使得该路线比使用高度优化的内置指标慢得多，其中许多指标是部分或完全在 cython 中实现。但您不需要在拟合之前将其计算为显式步骤。