在一組矢量中尋找最佳餘弦相似度

我有n個矢量，每個矢量都有m個元素（實數）。我想找到餘弦相似性在所有對中最大的一對。在一組矢量中尋找最佳餘弦相似度

的簡單的解決方案將需要爲O（n 2 米）時間。

有沒有更好的解決辦法？

更新

Cosine similarity/distance and triangle equation激勵着我，我可以用「弦長」，這失去精度，但增加的速度大量替換「餘弦相似性」。（有許多現有的解決方案解決最近鄰度量空間，像ANN）

來源

2012-12-01 hs3180

@ hs3180有沒有在你的向量的元素任何限制？例如。他們總是二進制（0或1）？ –

@robmayoff沒有，元素是實數（浮點） – hs3180

@robmayoff如果元素是二進制的，這個問題就等於找到了一對01串具有最相同的位。 – hs3180

餘弦相似度sim(a,b)是related to Euclidean distance|a - b|通過

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

爲單位向量a和b。

這意味着在L2範數標準化後歐幾里得距離最小時，餘弦相似性最大，問題歸結爲可以在O（n lg n）時間內求解的closest pair of points problem。

來源

2012-12-01 17:58:31

很好的回答！給出餘弦相似度與歐氏距離之間的明確關係。 – hs3180

美麗的答案！ –

可以與項目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')

來源

2014-06-12 15:10:12 Mountain

在一組矢量中尋找最佳餘弦相似度

回答

相關問題