100.000 个向量的有效比较

math database java visual-studio vector

2022-09-03 09:53:51

我在数据库中保存了100.000个向量。每个向量的维度为 60。（整型向量[60]）

然后，我取一个，并希望向用户呈现向量，以降低与所选向量的相似性。

我使用谷本分类器来比较2个向量：

$alt text$

是否有任何方法可以避免对数据库中的所有条目执行操作？

还有一件事！我不需要对数据库中的所有向量进行排序。我渴望获得前20个最相似的向量。因此，也许我们可以大致阈值60%的条目，并将其余条目用于排序。你觉得怎么样？

答案 1

首先，预处理向量列表以使每个向量规范化。单位大小。现在请注意，比较函数 T（）现在具有变为常量的大小项，并且可以简化公式以查找测试向量和数据库中值之间的最大点积。

现在，考虑一个新的函数D =60D空间中两点之间的距离。这是经典的L2距离，取每个分量的差值，对每个分量求和，将所有平方相加，取和的平方根。D（A， B） = sqrt（（A-B）^2），其中 A 和 B 各是 60 维向量。

不过，这可以扩展到D（A，B） = sqrt（A * A -2 * dot（A，B） + B * B）。那么，A和B是单位大小。函数 D 是单调的，因此如果我们移除 sqrt（）并查看平方距离，它不会改变排序顺序。这给我们留下了-2 *点（A，B）。因此，最小化距离正好等价于最大化点积。

因此，原始的 T（）分类度量可以简化为查找去噪化向量之间的最高点积。这种比较相当于在60-D空间中找到最接近采样点的点。

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

这个问题是一个很好理解的问题。它是K最近邻。有许多算法可以解决这个问题。最常见的是经典的KD树。

但有一个问题。KD 树具有 O（e^D）行为。高维性很快就会变得痛苦。而60个维度绝对属于这个极其痛苦的类别。甚至不要尝试。

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

但在实践中，有一个很好的解决方案，涉及另一个转变。如果你有一个度量空间（你有，或者你不会使用谷本比较），你可以通过60维旋转来降低问题的维数。这听起来很复杂和可怕，但它很常见。它是奇异值分解或特征值分解的一种形式。在统计学中，它被称为主成分分析。

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

最后，您将做一个经典的K最近邻，可能只有3-10个维度。您可以尝试最佳行为。有一个很棒的库可以做到这一点，叫做Ranger，但你也可以使用其他库。一个很大的好处是，您甚至不再需要存储样品数据的所有60个组成部分！

令人唏嘘的问题是，您的数据是否真的可以在不影响结果准确性的情况下折叠到较低的维度。在实践中，PCA分解可以告诉您您选择的任何D限的最大残差误差，因此您可以放心它有效。由于比较点基于距离指标，因此它们很可能是高度相关的，这与哈希表值不同。

所以上面的总结：

归一化向量，将问题转换为 60 维 K 最近邻问题
使用主成分分析将维度降低到 5 个维度的可管理极限
使用 K 最近邻算法（如 Ranger 的 KD 树库）查找附近的样本。

答案 2

更新：

在你明确这是你的空间的维度，而不是向量的长度之后，下面的答案不适用于你，所以我会把它保留下来，只是为了历史。60

由于向量已归一化，因此您可以使用增量超体积来查找相邻向量。kd-treeMBH

据我所知，没有一个数据库具有的本机支持，因此，如果您正在搜索有限数量的最接近的条目，则可以尝试在中实现以下解决方案：kd-treeMySQL

存储矢量对每个可能维度空间的投影（采用列）2n * (n - 1) / 2
使用索引为其中每一列编制索引SPATIAL
在任何投影中选取给定区域的正方形。这些的乘积将给你一个有限超体积的超立方体，它将保持距离不大于给定向量的所有向量。MBRMBR
查找所有使用中的所有投影MBRMBRContains

您仍然需要在此有限的值范围内进行排序。

例如，您有一组大小为：42

(2, 0, 0, 0)
(1, 1, 1, 1)
(0, 2, 0, 0)
(-2, 0, 0, 0)

您必须按如下方式存储它们：

p12  p13  p14  p23  p24  p34
---  ---  ---  ---  ---  ---
2,0  2,0  2,0  0,0  0,0  0,0
1,1  1,1  1,1  1,1  1,1  1,1
0,2  0,0  0,0  2,0  2,0  0,0
-2,0 -2,0 -2,0 0,0  0,0  0,0

假设您希望与第一个大于的向量相似。(2, 0, 0, 0)0

这意味着在超立方体内部有向量：。(0, -2, -2, -2):(4, 2, 2, 2)

发出以下查询：

SELECT  *
FROM    vectors
WHERE   MBRContains('LineFromText(0 -2, 4 2)', p12)
        AND MBRContains('LineFromText(0 -2, 4 2)', p13)
        …

等，对于所有六列