向量的餘弦相似度，與<爲O（n^2）複雜

說完看了看四周此網站類似的問題，我發現這一點：http://math.nist.gov/javanumerics/jama/和這樣的：http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html 向量的餘弦相似度，與<爲O（n^2）複雜

然而，似乎這些爲O運行（N^2）。我一直在做一些文檔聚類，並且發現在處理甚至是小文檔集時這種複雜性是不可行的。對於點積，我們只需要包含在兩個矢量中的矢量項就可以將矢量放入樹中，從而計算出具有n log n複雜度的點積，其中n是特徵項的最小數目2個文件中的1個。

我錯過了什麼嗎？有沒有這樣做的Java庫？

感謝

來源

2010-07-27 Ash

你不會很幸運，期望人們閱讀這兩個頁面。也許你可以更清楚地解釋你的問題 - 你爲什麼要乘以向量（你是什麼意思，O（n^2）？計算兩個n維向量的點積一般是O（n），我非常懷疑任何矢量包可能搞砸了） – 2010-07-27 19:21:22

他爲每對*文件計算點積。這使得它在二次方面變得複雜。 – Rekin 2010-07-27 19:25:16

BlueRaja - Danny Pflughoeft，這個問題是關於增大非常大但非常稀疏的向量; n不是維數而是非零元素的數量。 – 2010-07-27 19:25:21

如果存儲向量元素在哈希表中，查找僅日誌N反正，不是嗎？循環查看較小文檔中的所有鍵，看看它們是否存在於較大的文檔中。

來源

2010-07-27 18:13:05 Nicolas78

你會推薦任何課程嗎？我想，這是一個相當不錯的，如果內存是一個問題：http://www.java2s.com/Code/Java/Collections-Data-Structure/Amemoryefficienthashmap.htm – Ash 2010-07-27 18:18:17

哇不能這麼快就判斷這一點，但你可以總是以一個普通的java.util.HashMap開始。順便說一句，因爲你說這是文檔集合大小的效果：如果每個文檔比較每個文檔，你有（以文件的數量現在）另一二次項周圍的（N * log n）的長期包裹。對我而言，這部分經常比實際餘弦計算更成問題。這是否也適合你？ – Nicolas78 2010-07-27 18:32:55

我在聚類集上進行修剪以將比較歸結爲常量，但對於GAHC等完全正確的問題，您有n^2個問題，其中n是要比較的聚類數。 – Ash 2010-07-27 21:34:19

散列圖很好，但它可能需要很多內存。

如果向量存儲爲按鍵排序的鍵值對，那麼可以在O（n）中完成向量乘法：只需在兩個向量上並行迭代（相同的迭代用於例如合併排序算法）。乘法的僞代碼：

i = 0 
j = 0 
result = 0 
while i < length(vec1) && j < length(vec2): 
    if vec1[i].key == vec2[j].key: 
    result = result + vec1[i].value * vec2[j].value 
    else if vec1[i].key < vec2[j].key: 
    i = i + 1 
    else 
    j = j + 1

來源

2010-07-27 19:22:05

我喜歡這個想法，謝謝。有沒有一個使用這個原則的Java庫？ – Ash 2010-07-27 21:31:05

我不知道;但lucene（http://lucene.apache.org/java/docs/index.html）可能包含這樣的算法。 – 2010-07-28 18:09:06

感謝德米特里-vk，它似乎是一個有序的地圖可能是最好的：http://java.sun.com/j2se/1.4.2/docs/api/java/util/SortedMap.html – Ash 2010-07-29 03:56:14

如果你只是想推薦有限的物品，例如間項目，在一組具有n個大小每一個項目中，複雜不必爲n^2，但M * ñ。由於m是一個常數，因此複雜度是線性的。

你可以用項目simbase https://github.com/guokr/simbase查詢，它是一個矢量相似性的nosql數據庫。

Simbase使用以下概念：

向量設置：一組向量
基礎：用於載體的基礎上，在一個矢量集合矢量具有相同的基礎
建議：一方向二進制具有相同基礎的兩個向量組之間的關係

來源

2014-06-12 15:14:53 Mountain

如果您打算使用餘弦相似性作爲查找類似文檔簇的方式，則可能需要con sider正在研究locality-sensitive hashing，這是一個基於散列的方法，專門爲此設計的。直觀上，LSH對矢量進行散列，使得高概率將相似元素放入同一個桶和遠處元素到不同桶中。有一些LSH方案使用餘弦相似度作爲它們的基礎距離，因此要找到使用LSH將事物放入桶中的集羣，然後僅計算同一個桶中元素的成對距離。在最壞的情況下，這將是二次的（如果一切都落在同一個桶裏），但是更有可能的是你的工作會有很大的下降。

希望這會有所幫助！

來源

2014-06-12 17:21:41 templatetypedef

向量的餘弦相似度，與<爲O（n^2）複雜

回答

相關問題