6

同様のドキュメントを検索する近隣検索アプリケーションを実装しています。これまでのところ、LSH 関連の資料のかなりの部分を読みました (LSH の背後にある理論はある種の混乱を招き、まだ 100% 理解できていません)。

私のコードは、minhash 関数を使用して署名行列を計算できます (私は終わりに近づいています)。また、署名行列にバンディング戦略を適用します。ただし、バンド内の署名ベクトル (列の) をバケットにハッシュする方法を理解できません。

最後の質問が最も重要かもしれませんが、いくつかintroduction質問する必要があります。

q1: ハッシュ関数は同じベクトルのみを同じバケットにマップしますか? (十分なバケットがあると仮定します)

q2: ハッシュ関数は類似のベクトルを同じバケットにマップする必要がありますか? はいの場合、比較を計算しているのではなく、ハッシュを行っているため、この類似性の程度/定義は何ですか。

q3: 上記の質問に応じて、どのようなハッシュ テーブル アルゴリズムを使用すればよいですか?

q4: 私の一番の弱点は、入力としてベクトルを取り、出力としてバケットを選択するハッシュ関数を生成する方法がわからないことだと思います。q1とq2に応じて自分で実装できます... LSHのハッシュ関数の生成に関する提案はありbucketingますか?

4

2 に答える 2

6

q1: ベクトル全体をハッシュするのではなく、その一部をハッシュすることになっています。各アイテムを表す長さ 100 のベクトルがあるとすると、長さ 20 の 5 つのスライスをハッシュできます。

q2: これが全体の背後にある主な考え方です。類似性は、物事の部分を比較して等しいかどうかを比較することによって測定します。テキスト内の文をベクトルと見なす場合、2 つの文がまったく同じ (同じハッシュ出力を持つ) とは考えにくいでしょう。ただし、それらを部分に分割し、部分を個別にハッシュすると、同じ位置にある一致する個々の単語のハッシュは同じハッシュ出力を返すため、文の類似性についてのアイデアを得ることができます.

スライスの数と長さは、類似性の結果の精度に影響を与える重要なパラメーターです。スライスが多すぎると誤検知が多くなり、スライスが少なすぎると最高度の類似性しか識別できなくなります。

これについての詳細は、本「大規模なデータセットのマイニング」で見つけることができます。

q3: スライス レベルごとに、すべてのベクトル スライスのハッシュの結果と、それを生成したベクトルを保持できるデータ構造が必要です。次に、Vector X の類似した近傍を見つけたい場合は、各スライスのデータ構造をチェックし、取得したハッシュ出力が別のベクトルによっても出力されたかどうかを確認できます。

q4: ここで何を言っているのかよくわかりません。オブジェクトをハッシュすると、通常、言語に応じて、ビット文字列または整数または浮動小数点数が出力として取得されます。それがバケツです。別のオブジェクトで同じハッシュ関数を使用して同じ出力が得られた場合、それはそれらが同じバケットでハッシュされたことを意味します。

于 2014-04-09T17:23:48.213 に答える