matrix - 用于拟合 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中实现。但是您不需要在拟合之前将其计算为显式步骤。