研究

余弦相似度

在这种情况下,最好的算法包括 cosine similarity

def cossim(a, b): numpy.inner(a, b)/(numpy.linalg.norm(a)*numpy.linalg.norm(b))

在Python中。

线性搜索:

对这个案子最明显和简单的搜索是 linear search

def linear_search(query_text, db):  # where db is set of 512D vectors
    most_similar = ("", 0)  # placeholder
    for query in db:
        current_sim = cossim(query_text, query)  # cossim function defined above
        if current_sim > most_similar[1]:
            most_similar = (query, current_sim)
    return most_similar[0] 

如您所见,应该扫描整个数据库,如果数据库包含数十万个向量,这可能会非常低效。

拟线性搜索:(部分解析)

余弦相似性和 Euclidean distance ( explained very well in this answer )-我们可以从下面的等式中得出欧氏距离:

|a - b|² = 2(1 - cossim(a,b))

正如在回答中提到的,随着两个向量之间的余弦变大,欧氏距离会变小,因此我们可以将其转化为 closest pairs of points quasilinear O(n log n) 时间使用递归 divide and conquer algorithm .

但是 遗憾的是,由于向量的高维性,这个问题无法直接解决。经典的分治算法只适用于二维。

二进制搜索索引(未解析):

据我所知,就速度而言,优化余弦相似性搜索的最佳方法是索引,然后执行二进制搜索。

这里的主要问题是,索引512维向量是相当困难的,我还不知道什么,除了 locality sensitive hashing 这对于索引我的数据库可能有用,也可能不有用(主要关注的是维数减少,这可能会导致准确度的相应降低)。

有一个新的 Angular Multi-index Hashing 方法,不幸的是它只适用于基于二进制的向量和维数 independent similarity computation 如果向量是稀疏的,但它们不是。

最后,还有 An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions ,乍一看可能是最好的解决方案,但文件中指出:

算法不适用于大的d值 远小于定理1中给出的许多 与暴力搜索相比,在高维上有了显著的改进 平均误差相对较小。

20 * 25.6 = 512

也有类似的情况 question 这包含了类似的问题,但不幸的是,还没有找到索引的解决方案。

问题

最接近的解决方案

我相信我已经找到了一个可能的解决方案,它包括用于索引几百维向量数据库的随机分区树,我相信这正是我所需要的。( see here

谢谢您!