159

LSHは、高次元のプロパティを持つ同様のアイテムを見つけるための良い方法のように思われることに気づきました。

論文ht​​tp://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdfを読んだ後、私はまだそれらの公式と混同しています。

誰かがその簡単な方法を説明するブログや記事を知っていますか？

4

6 に答える 6

256

LSHについて私が見た中で最高のチュートリアルは、「大量のデータセットのマイニング」という本にあります。第3章を確認してください-同様のアイテムを見つける http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

また、以下のスライドをお勧めします： http ://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf 。スライドの例は、コサイン類似性のハッシュを理解するのに大いに役立ちます。

ACL2010のBenjaminVanDurme＆Ashwin Lallから2枚のスライドを借りて、コサイン距離に関するLSHファミリーの直感を少し説明しようとしています。 ここに画像の説明を入力してください

  • この図では、 2つの2次元データポイントを表す、赤と黄色の2つの円があります。LSHを使用してそれらの余弦の類似性を見つけようとしています。
  • 灰色の線は、均一にランダムに選択された平面です。
  • データポイントが灰色の線の上にあるか下にあるかに応じて、この関係を0/1としてマークします。
  • 左上隅には、2つのデータポイントの署名をそれぞれ表す白/黒の正方形の2つの行があります。各正方形はビット0（白）または1（黒）に対応しています。
  • したがって、平面のプールができたら、平面に対応する位置でデータポイントをエンコードできます。プール内の平面が増えると、署名にエンコードされた角度の差が実際の差に近くなると想像してください。2つのポイントの間にある平面だけが、2つのデータに異なるビット値を与えるためです。

ここに画像の説明を入力してください

  • 次に、2つのデータポイントの署名を確認します。例のように、各データを表すために6ビット（正方形）のみを使用します。これは、元のデータのLSHハッシュです。
  • 2つのハッシュ値間のハミング距離は1です。これは、それらの署名が1ビットだけ異なるためです。
  • シグニチャの長さを考慮して、グラフに示すように角度の類似性を計算できます。

ここに、コサイン類似性を使用しているPythonのサンプルコード（わずか50行）があります。 https://gist.github.com/94a3d425009be0f94751

于 2012-10-19T04:45:20.427 に答える
35

ベクトル空間でのツイートは、高次元データの優れた例です。

ツイートに局所性鋭敏型ハッシュを適用することに関する私のブログ投稿をチェックして、類似したものを見つけてください。

http://micvog.com/2013/09/08/storm-first-story-detection/

そして、1つの写真は千の言葉なので、下の写真を確認してください。

ここに画像の説明を入力してください http://micvog.files.wordpress.com/2013/08/lsh1.png

それが役に立てば幸い。@mvogiatzis

于 2013-09-18T21:52:06.267 に答える
21

これがそれを説明するスタンフォードからのプレゼンテーションです。それは私にとって大きな違いをもたらしました。パート2ではLSHについて詳しく説明しますが、パート1でもLSHについて説明します。

概要の写真（スライドにはもっとたくさんあります）：

ここに画像の説明を入力してください

高次元データでの近隣検索-パート1：http: //www.stanford.edu/class/cs345a/slides/04-highdim.pdf

高次元データでの近隣検索-パート2：http： //www.stanford.edu/class/cs345a/slides/05-LSH.pdf

于 2014-03-24T09:14:59.970 に答える
10
  • LSHは、ドキュメント/画像/オブジェクトのセットを入力として受け取り、一種のハッシュテーブルを出力するプロシージャです。
  • このテーブルのインデックスには、同じインデックスにあるドキュメントは類似していると見なされ、異なるインデックスにあるドキュメントは「異なる」と見なされるようなドキュメントが含まれています。
  • 類似する場合は、メートル法と、LSHのグローバルパラメータのように機能 するしきい値の類似性に依存します。
  • 問題に対する適切なしきい値を定義するのはあなた次第です。

ここに画像の説明を入力してください

異なる類似性測度にはLSHの異なる実装があることを強調することが重要です。

私のブログでは、minHashing（ジャッカード類似度測定）とsimHashing（余弦距離測定）の場合のLSHを徹底的に説明しようとしました。お役に立てば幸いです： https ：//aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

于 2018-01-27T19:18:25.150 に答える
2

私は視覚的な人です。これが私にとって直感として機能するものです。

おおよそ検索したいもののそれぞれが、リンゴ、立方体、椅子などの物理的なオブジェクトであると言います。

LSHに対する私の直感は、これらのオブジェクトの影をとることに似ているということです。たとえば、3D立方体の影をとると、1枚の紙に2Dの正方形のようになり、3D球体の場合は、1枚の紙に円のような影ができます。

最終的に、検索問題には3つ以上の次元があります（テキスト内の各単語が1つの次元になる可能性があります）が、シャドウのアナロジーは依然として私にとって非常に役立ちます。

これで、ソフトウェアのビット文字列を効率的に比較できます。固定長のビット文字列は、多かれ少なかれ、一次元の線のようなものです。

したがって、LSHを使用して、オブジェクトのシャドウを最終的に単一の固定長のライン/ビット文字列上のポイント（0または1）として投影します。

全体の秘訣は、低次元でも意味をなすように影をとることです。たとえば、認識できる十分な方法で元のオブジェクトに似ています。

遠近法での立方体の2D描画は、これが立方体であることを示しています。しかし、遠近法なしでは2Dの正方形と3Dの立方体の影を簡単に区別することはできません。どちらも私には正方形のように見えます。

オブジェクトを光にどのように提示するかによって、認識しやすい影が得られるかどうかが決まります。したがって、「優れた」LSHは、オブジェクトをライトの前に向けて、オブジェクトの影がオブジェクトを表すものとして最もよく認識されるようにするものと考えています。

要約すると、LSHを使用してインデックスを作成するものを、立方体、テーブル、椅子などの物理オブジェクトと考え、それらの影を2Dで投影し、最終的には線（ビット文字列）に沿って投影します。そして、「優れた」LSH「機能」とは、ライトの前にオブジェクトを表示して、2Dフラットランドと後でビットストリングでほぼ識別可能な形状を取得する方法です。

最後に、私が持っているオブジェクトがインデックスを付けたいくつかのオブジェクトに類似しているかどうかを検索したい場合、同じ方法を使用してこの「クエリ」オブジェクトの影を取り、ライトの前にオブジェクトを表示します（最終的には少しで終わります）文字列も）。そして今、私はそのビット文字列が他のすべてのインデックス付きビット文字列とどれほど似ているかを比較できます。これは、オブジェクトを光に提示するための適切で認識可能な方法を見つけた場合に、オブジェクト全体を検索するためのプロキシです。

于 2017-12-18T17:42:21.083 に答える
0

非常に短い、tldrの答えとして：

局所性鋭敏型ハッシュの例としては、最初にハッシュへの入力の空間に平面をランダムに（回転とオフセットを使用して）設定し、次に空間内のハッシュにポイントをドロップし、平面ごとにポイントがその上または下（例：0または1）で、答えはハッシュです。したがって、空間内で類似しているポイントは、前後のコサイン距離で測定された場合、同様のハッシュを持ちます。

scikit-learnを使用してこの例を読むことができます：https ：//github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer

于 2019-06-22T07:29:07.580 に答える