java - 100.000 个 vector 的高效比较

Question

我在数据库中保存了 100.000 个 vector 。每个 vector 的维度为 60。 (int vector[60])

然后我选择一个并希望按照与所选 vector 相似度递减的顺序向用户呈现 vector 。

我使用 Tanimoto Classifier比较 2 个 vector :

是否有任何方法可以避免遍历数据库中的所有条目？

还有一点!我不需要对数据库中的所有 vector 进行排序。我想获得前 20 个最相似的 vector 。所以也许我们可以粗略地确定 60% 的条目并使用其余的进行排序。你怎么看？

Answer 1

首先，预处理你的 vector 列表，使每个 vector 归一化.. 单位大小。 现在请注意，您的比较函数 T() 现在具有变为常量的量级项，并且可以简化公式以查找测试 vector 与数据库中的值之间的最大点积。

现在，考虑一个新函数 D = 60D 空间中两点之间的距离。这是经典L2 distance ，取每个分量的差值，对每个分量求平方，将所有平方相加，然后对总和开平方根。 D(A, B) = sqrt( (A-B)^2) 其中 A 和 B 均为 60 维 vector 。

不过，这可以扩展为 D(A, B) = sqrt(A * A -2*dot(A,B) + B * B)。 那么A和B是单位量级。并且函数 D 是单调的，因此如果我们删除 sqrt() 并查看平方距离，它不会更改排序顺序。这让我们只剩下 -2 * dot(A,B)。因此，最小化距离正好等同于最大化点积。

因此，原始的 T() 分类指标可以简化为寻找归一化 vector 之间的最高点积。并且该比较显示等同于在 60 维空间中找到与样本点最近的点。

所以现在您需要做的就是解决“给定 60 维空间中的归一化点，列出距离它最近的归一化样本 vector 数据库中的 20 个点”的等价问题。

这个问题是一个很好理解的问题..它是 K Nearest Neighbors. 有很多算法可以解决这个问题。最常见的就是经典KD trees .

但是有一个问题。 KD 树具有 O(e^D) 行为。高维很快就会变得痛苦。而 60 维绝对属于那个极其痛苦的范畴。甚至不要尝试。

然而，对于高 D 最近邻，有几种替代的通用技术。 This paper给出了明确的方法。

但在实践中，有一个很好的解决方案涉及另一个转换。如果你有一个度量空间(你有，或者你不会使用 Tanimoto 比较)，你可以通过 60 维旋转来降低问题的维数。这听起来既复杂又可怕，但它很常见……它是奇异值分解或特征值分解的一种形式。在统计中，它被称为 Principal Components Analysis.

基本上，这使用简单的线性计算来查找数据库真正跨越的方向。您可以将 60 个维度压缩为一个较低的数字，可能低至 3 或 4，并且仍然能够准确地确定最近的邻居。 有大量软件库可以用任何语言执行此操作，请参阅 here例如。

最后，您将在可能只有 3-10 个维度上进行经典的 K 最近邻。您可以试验最佳行为。有一个很棒的库可以做这件事，叫做 Ranger ，但您也可以使用其他库。一个很大的附带好处是您甚至不需要再存储样本数据的所有 60 个组成部分!

令人头疼的问题是，您的数据是否真的可以在不影响结果准确性的情况下降低维度。在实践中，PCA 分解可以告诉您对于您选择的任何 D 限制的最大残差，因此您可以放心它会起作用。由于比较点基于距离度量，因此它们很可能高度相关，这与哈希表值不同。

综上所述:

1. 规范化您的 vector ，将您的问题转化为 60 维的 K 最近邻问题
2. 使用主成分分析将维度降低到可管理的极限，例如 5 个维度
3. 使用 K 最近邻算法(例如 Ranger 的 KD 树库)查找附近的样本。