algorithm - 在一组向量中找到最佳余弦相似度

Question

我有 n 个向量，每个向量都有 m 个元素（实数）。我想找到所有对中余弦相似度最大的对。

直接的解决方案需要 O(n ² m) 时间。

有没有更好的解决方案？

更新

余弦相似度/距离和三角方程启发我，我可以用“弦长”代替“余弦相似度”，这会降低精度但会大大提高速度。（有许多解决度量空间中最近邻的现有解决方案，如ANN）

Answer 1

余弦相似度与欧几里得sim(a,b)距离有关 |a - b|

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

对于单位向量a和b.

这意味着通过 L2 范数归一化后欧几里得距离最小时余弦相似度最大，问题归结为最近点对问题，可以在 O(n lg n) 时间内解决。

Answer 2

您可以查看项目 simbase https://github.com/guokr/simbase，它是一个向量相似度 nosql 数据库。

Simbase 使用以下概念：

• 向量集：一组向量
• 基：向量的基，一个向量集中的向量具有相同的基
• 推荐：两个具有相同基的向量集之间的单向二元关系

您可以直接使用 redis-cli 进行管理任务，也可以直接以编程方式使用不同语言的 redis 客户端绑定。这是一个 Python 示例

    import redis

    dest = redis.Redis(host='localhost', port=7654)
    schema = ['a', 'b', 'c']
    dest.execute_command('bmk', 'ba', *schema)
    dest.execute_command('vmk', 'ba', 'va')
    dest.execute_command('rmk', 'va', 'va', 'cosinesq')