寻找最好的余弦相似性在一组向量(Finding the best cosine similarity

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

该简单的解决方案将需要O（N ²米）的时间。

有没有更好的解决办法？

更新

余弦相似性/距离和三角公式激励着我，我可以用“弦长”，它失去精度，但增加速度的大量替换“余弦相似性”。 （有解决度量空间近邻许多现有的解决方案，如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使用以下概念：

• 矢量集：一组向量
• 基础：用于载体的基础上，在一个矢量集合矢量具有相同的基础
• 建议：它们具有相同的基础2个矢量集之间的一个方向的二进制关系

您可以直接使用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')

文章来源: Finding the best cosine similarity in a set of vectors