问100.000个向量的有效比较

EN

首先，对向量列表进行预处理，使每个向量归一化。单位大小。请注意，现在您的比较函数T()中的幅度项已变为常量，并且公式可以简化为找到测试向量和数据库中的值之间的最大点积。

现在，考虑一个新函数D= 60D空间中两点之间的距离。这是经典的L2 distance，取每个分量的差，每个分量的平方，将所有平方相加，然后取和的平方根。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维空间中找到与采样点最接近的点。

因此，现在您需要做的就是解决等价问题“给定60D空间中的一个归一化点，列出数据库中最接近它的归一化样本向量的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限制的最大残差，因此您可以确信它是有效的。因为比较点是基于距离度量的，所以它们很可能是紧密相关的，不像散列表值那样。

所以总结一下上面的内容：

在60 dimensions

• Use主成分分析中，

1. 标准化您的向量，将您的问题转换为K最近邻问题，以将维度降低到可管理的限制，例如5 dimensions
2. Use K最近邻算法，如Ranger的KD树库，以查找附近的样本。

更新：

在您明确60是空间的维度，而不是向量的长度之后，下面的答案不适用于您，因此我将其保留为历史。

由于您的向量是标准化的，因此您可以使用kd-tree在增量超级卷的MBH中查找邻居。

据我所知，没有数据库具有对kd-tree的本地支持，所以如果您正在搜索有限数量的最近条目，可以尝试在MySQL中实现以下解决方案：

将向量的投影存储到每个可能的正方形空间(takes columns)

• Index a n * (n - 1) / 2 SPATIAL

• n * (n - 1) / 2aSPATIAL

• MBR of aSPATIAL area to any projections )。这些MBR的乘积将给你一个有限超体积的超立方体，它将容纳距离不大于给定一的所有向量。

• 使用MBR找出所有投影

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

例如，您有一组幅值为2的4-dimensional向量

(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)
        …

，等等，用于所有六列

因此，可以缓存以下信息：

所选向量的范数

• 点积A.B，在给定的T(A，B)计算中将其同时用于分子和分母。

如果您只需要N个最近的向量，或者如果您多次执行相同的排序过程，则可能会有更多的技巧可用。(像T(A，B)=T(B，A)这样的观察值，缓存所有向量的向量范数，也许还有某种阈值/空间排序)。