兩個算法用局部敏感哈希來找到最近的鄰居，哪一個？

Question

目前我正在研究如何使用局部敏感哈希來找到最近的鄰居。然而，當我正在閱讀論文並在網上搜索時，我發現了兩種算法：

1-使用L個隨機數LSH函數的哈希表，從而增加兩個文檔類似的機會得到相同的簽名。例如，如果兩份文件的相似度爲80％，則有80％的機會從一個LSH函數中獲得相同的簽名。但是，如果我們使用多個LSH函數，那麼從一個LSH函數獲得文檔的相同簽名的可能性就更大。這種方法在維基百科的解釋，我希望我的理解是正確的：

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2-其他算法使用的方法從紙（第5）呼籲：從舍入算法相似性估計技術摩西S.恰裏卡爾。它基於使用一個LSH函數生成簽名，然後對其應用P置換，然後對列表進行排序。其實我不太瞭解這個方法，我希望有人能澄清它。

我的主要問題是：爲什麼有人會使用第二種方法而不是第一種方法？我發現它更容易，更快。

我真的希望有人能幫忙!!!

編輯： 其實我不確定@ Raff.Edward在「第一」和「第二」之間混合。因爲只有第二種方法使用半徑，第一種方法使用由散列族F組成的新哈希族g。請檢查維基百科鏈接。他們只是使用許多g函數來生成不同的簽名，然後爲每個g函數都有一個相應的哈希表。爲了找到一個點的最近鄰點，你只需讓該點通過g函數並檢查相應的哈希表是否有衝突。因此，我如何把它理解爲更多的功能......更多的碰撞機會。

我沒有發現任何關於第一種方法的半徑提及。

對於第二種方法，它們只爲每個特徵向量生成一個簽名，然後對它們應用P置換。現在我們有P個排列列表，每個列表包含n個簽名。現在他們對P中的每個列表進行排序。然後給出一個查詢點q，它們爲它生成簽名，然後對其應用P置換，然後在每個排列和排序的P列表上使用二進制搜索來找到最相似的簽名查詢q。在閱讀了許多關於它的論文後，我總結了這一點，但我仍不明白爲什麼有人會使用這種方法，因爲它在尋找漢明距離方面似乎並不快。

對我來說，我會簡單地做以下操作來查找查詢點q的最近鄰居。給定簽名N的列表，我將生成查詢點q的簽名，然後掃描列表N並計算N中每個元素與q的簽名之間的漢明距離。因此，我最終會與q最近的鄰居結束。它需要O（N）！

Answer 1

你對第一個的理解有點偏離。發生碰撞的概率與相似度不成正比，但是是否小於預先定義的半徑。目標是半徑範圍內的任何事物都有很高的碰撞機會，半徑之外的任何事物*（1 + eps）的碰撞機率都很低（而且中間區域有點模糊）。

第一個算法實際上很難實現，但可以得到很好的結果。特別是，第一種算法是針對L1和L2（以及技術上更多的）指標。

第二種算法是很容易實現，但天真的實現可能會使用過多的內存根據問題的大小是有用的。在這種情況下，碰撞概率與輸入的相似性成正比。但是，它只適用於餘弦相似度（或基於相似度變換的距離度量）。

那麼您將使用哪一個主要基於您正在使用哪個距離度量最近的鄰居（或任何其他應用程序）。

第二個實際上是更容易理解和比第一個實現，本文只是很羅嗦。

簡短版本：取一個隨機向量V並給每個索引一個獨立的隨機單位正常值。根據你想要的簽名長度創建儘可能多的矢量。簽名是您製作Matrix Vector產品時每個索引的標誌。現在，任何兩個簽名之間的漢明距離與各個數據點之間的餘弦相似性有關。

因爲你可以編碼簽名成一個int數組，並使用XOR與比特數指令來獲取漢明距離非常快，你可以得到近似的餘弦相似度得分非常快。

LSH算法沒有大量的標準化，以及兩篇論文（和其他人）使用不同的定義，所以它的一切有點有時令人困惑。我最近纔在JSAT中實現了這兩種算法，並且仍在努力完全理解它們。

編輯：回覆您的編輯。維基百科的文章對LSH並不好。如果您閱讀original paper，則您所談論的第一種方法僅適用於固定半徑。然後根據該半徑創建散列函數，並將其連接以增加碰撞中靠近點的概率。然後他們通過確定他們的k的最大值，然後找到最大的合理的距離，他們將找到第k個最近的鄰居，從而構建一個用於做k-NN的系統。通過這種方式，半徑搜索很可能會返回一組k-NN。爲了加快速度，他們還創建了一些額外的小半徑，因爲密度通常不是一致的，而且使用的半徑越小，結果就越快。

您所連結的維基百科部從紙描述採取的「穩定分佈」部分，該部分提出了一個搜索半徑r = 1的哈希函數。

對於第二個文件中，「排序」你形容一點也不散列的一部分，但對於更快速地搜索海明空間一方案的一部分。正如我剛纔提到的，我最近實現了這一點，你可以看到a quick benchmark I確實使用蠻力搜索仍然比NN的天真方法快得多。同樣，如果您需要L2或L1距離上的餘弦相似度，您也可以選擇此方法。你會發現許多其他論文提出了不同的方案來搜索由簽名創建的海明空間。

如果你需要幫助，說服自己適合可以更快，即使你仍然在做蠻力 - 只要看看它的方式：可以說平均稀疏文檔與另一個文檔有40個常用詞（非常保守的數字在我的經驗）。你有n個文件要比較。蠻力餘弦相似性將涉及大約40 * n個浮點乘法（和一些額外的工作）。如果你有一個1024位的簽名，那只有32個整數。這意味着我們可以在32 * n個整數運算中進行蠻力LSH搜索，這比浮點運算快得多。

這裏還有其他一些因素。對於稀疏數據集，我們必須保留雙精度和整數索引來表示非零索引，所以稀疏點積執行大量額外的整數運算來查看它們具有哪些共同的索引。 LSH也允許我們節省內存，因爲我們不需要爲每個向量存儲所有這些整數和雙精度，而只需保留它的散列值 - 這只是幾個字節。減少內存使用可以幫助我們更好地利用CPU緩存。

你的O（n）是我在博客文章中使用過的天真的方式。而且速度很快。但是，如果您事先對比特進行排序，則可以在O（log（n））中執行二進制搜索。即使你有這些名單中的L，L < <n，所以它應該更快。唯一的問題是它讓你近似於海明NN，它們已經接近餘弦相似度，所以結果會變得更糟。這取決於你需要什麼。