k-NN输出的距离度量

Question

假设有人已经训练了一个基于未知度量的最近邻算法。我有一个大型的N观测数据集和P特性。对于每个观察结果，我都会得到对应于(相同)数据集中的K“最近”点的D3索引。

学习这个指标的一般策略是什么？这类问题有标准名称吗？有这样一个任务的卡格勒式的比赛，或者这是不寻常的？

Answer 1

有趣的问题。如果您假设距离度量是一些常见的度量，那么当然您可以尝试所有常见的度量，看看它返回的最近的邻居是一致的。

我想不出一种可靠的学习方法，因为你没有任何关于实际距离的信息。也许把所有的近邻配对看作是“小”距离，而其余“大”，并训练一个深的模型，试图学习预测它的对对点。无论它作为一个度量得到什么，都会近似于它。

Answer 2

这被称为“距离度量学习”或“学习距离度量”。你可以在文献中找到许多关于这个主题的论文。

学习距离度量有很多算法。它们中的一些允许您指定四胞胎(x_1,x_2,x_3,x_4)，在这里我们得到了d(x_1,x_2) < d(x_3,x_4)的承诺，任务是学习一个与这个训练集一致的距离矩阵d。然后，您可以在您的任务中使用这样的算法，方法是从您的训练集中随机抽样x_1，从K最近的x_1邻居中抽取x_2，设置x_3=x_1，以及从其他N-K-1非邻居中的一个采样x_4。

一种方法是学习Mahalanobis距离，即表单d(x,x') = \|Lx-Lx'\|_2的距离度量。这可以等效地表示为d(x,x') = \sqrt{(x-x')^\top M(x-x')}其中的M=L^\top L。您可以将学习任务描述为优化问题，然后使用标准的优化方法来学习矩阵L (或M)。这学习了一个线性距离度量。

还有其他方法试图使用神经网络学习更复杂的非线性距离度量，例如d(x,x') = \|N(x)-N(x')\|_2，其中N是一个神经网络(因此，使用暹罗网络测量距离)。关于训练神经网络以测量图像相似性的标准文献描述了学习这种网络的许多方法，它也可以通过适当地抽样三胞胎来应用于您的情况。

您可能对Python的公制学习包感兴趣。