100.000向量的有效比较

Question

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

然后我拿一个并希望当前向量按照与所选择的相似度递减的顺序给用户.

我使用Tanimoto分类器来比较2个向量:

$替代文字$

有没有办法避免通过数据库中的所有条目？

还有一件事!我不需要对数据库中的所有向量进行排序.我想获得前20名最相似的矢量.所以也许我们可以粗略地控制60%的条目,并使用其余的进行排序.你怎么看？

Answer 1

首先,预处理矢量列表,使每个矢量标准化.单位幅度.现在请注意,您的比较函数T()现在具有变为常量的幅度项,并且公式可以简化为查找测试向量与数据库中的值之间的最大点积.

现在,想想一个新函数D = 60D空间中两点之间的距离.这是经典的L2距离,取每个组件的差异,每个方块的正方形,加上所有的正方形,并取总和的平方根.D(A,B)= sqrt((AB)^ 2)其中A和B各自是60维向量.

但是,这可以扩展到D(A,B)= sqrt(A*A -2*点(A,B)+ B*B).那么A和B是单位幅度.并且函数D是单调的,因此如果我们删除sqrt()并查看平方距离,它将不会更改排序顺序.这使我们只有-2*点(A,B).因此,最小化距离恰好等于最大化点积.

因此,可以将原始T()分类度量简化为在找到的矢量之间找到最高点积.并且该比较显示相当于在60-D空间中找到与样本点最接近的点.

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

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

但是有一个问题.KD树具有O(e ^ D)行为.高维度很快变得痛苦.60个维度绝对是非常痛苦的类别.甚至不尝试.

然而,对于高D最近邻居,存在若干替代的一般技术. 本文给出了一个明确的方法.

但在实践中,有一个很好的解决方案涉及另一个转换.如果您有度量空间(您可以使用,或者您不使用Tanimoto比较),则可以通过60维旋转来减少问题的维数.这听起来很复杂和可怕,但它很常见..它是奇异值分解或特征值分解的一种形式.在统计学中,它被称为主成分分析.

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

最后,你将做一个经典的K最近邻居,可能只有3-10维.你可以尝试最好的行为.有一个很棒的库,可以做这个叫Ranger,但你也可以使用其他库.一个很好的附带好处是您甚至不需要再存储样本数据的所有60个组件!

唠叨的问题是您的数据是否真的可以折叠到较低维度而不影响结果的准确性.在实践中,PCA分解可以告诉您选择的任何D限制的最大残留误差,因此可以确保它有效.由于比较点基于距离度量,因此与哈希表值不同,它们很可能是强烈相关的.

所以上面的总结: