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

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

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

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

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

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

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

Java で、任意の数のランダム ハッシュ関数 (私の場合は 240 個のハッシュ関数) を生成し、任意の数の整数 (現時点では 2000 個) を実行する必要があるミンハッシュ アルゴリズムをプログラミングしています。

これを行うために、240 個のハッシュ関数のそれぞれに対して乱数 a、b、c (1 ～ 2001 の範囲) を生成してきました。次に、ハッシュ関数は h = ((a*x) + b) % c を返します。ここで、h は戻り値で、x はそれを通る整数の 1 つです。

これはランダムハッシュの効率的な実装ですか、それとももっと一般的/受け入れられる方法はありますか?

この投稿は同様の質問をしていましたが、回答の文言にまだ混乱しています: Minhash implementation how to find hash functions for permutations

問題は単純です: Redis の表現に基づいて正確な HyperLogLog ユニオンを実装するための最適な戦略を見つける必要があります。これには、データ構造が他の場所で使用するためにエクスポートされる場合の疎/密表現の処理が含まれます。

2つの戦略

2 つの戦略があり、そのうちの 1 つは非常に単純に見えます。私は実際の Redis ソースを調べましたが、精度と効率の観点から、組み込みの構造/ルーチンを使用するか、独自の構造を開発する方が良いかを判断するのに少し苦労しています (C では大きくありません)。 . その価値のために、非常に大きなセットで効率を追求するために、スペースとある程度の誤差 (stdev +-2%) を喜んで犠牲にします。

1. 包含原則

2 つのうち最も単純な方法は、基本的に、ロスレス ユニオン (PFMERGE) をこの原則と組み合わせて使用​​して、オーバーラップの推定値を計算することです。テストでは、多くの場合、これが確実に実行されていることが示されているようですが、実際の効率と精度を正確に把握するのに苦労しています (場合によっては、この使用例では受け入れられない 20 ～ 40% のエラーが発生する可能性があります)。

基本的：

または、複数セットの場合は...

多くの場合、正確に動作するようですが、信頼できるかどうかはわかりません。Redis には、既知の HLL の問題を回避するために設計された低カーディナリティ修飾子が多数組み込まれていますが、(包含/除外を使用した) 非常に不正確な問題が、サイズの大きな不一致のセットで依然として存在するかどうかはわかりません...

2. Jaccard インデックス交差/MinHash

この方法はより興味深いように思えますが、Redis の既存の最適化の一部と計算上重複する可能性があると感じています (つまり、独自の HLL アルゴリズムを最初から実装していません)。

このアプローチでは、MinHash アルゴリズムを使用したビンのランダム サンプリングを使用します (LSH の実装に問題があるとは思いません)。これは別の構造になりますが、minhash を使用してセットの Jaccard インデックスを取得することにより、ユニオン カーディナリティにそのインデックスを効果的に掛けて、より正確なカウントを得ることができます。

問題は、私は HLL に精通していないことです。Google の論文を掘り下げたいのですが、すぐに実行可能な実装が必要です。おそらく、Redis の既存の最適化の基本的な考慮事項、またはかなり緩い信頼限界で計算コストの低い交差推定を可能にするアルゴリズム自体のいくつかの基本的な考慮事項を見落としている可能性があります。

したがって、私の質問：

スペースを犠牲にしても構わないと思っている場合 (そして、わずかな精度で)、redis を使用して、N 個の巨大な (数十億) セットの計算上安価な交差推定を最も効果的に取得するにはどうすればよいですか?

クラスター化したい 5 つのセットがあるとします。ここで説明されている SimHashing 手法を理解しています。

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

たとえば、結果が次の場合、3 つのクラスター ( {A}、{B,C,D}および) が生成されます。{E}

同様に、MMDS ブックの第 3 章で説明されている MinHashing 手法:

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

その結果が次の場合、同じ 3 つのクラスターを生成することもできます。

(各セットは、3 つの「バンド」で構成される MH シグネチャに対応し、シグネチャ バンドの少なくとも 1 つが一致する場合、2 つのセットがグループ化されます。バンドが多いほど、一致する可能性が高くなります。)

ただし、これらに関連するいくつかの質問があります。

(1) SHは MHのシングルバンド版と理解できますか?

(2) MH は、クラスターを構築するために Union-Find のようなデータ構造を使用することを必然的に意味しますか?

(3) クラスターは、両方の手法で、実際には「候補ペア」のセットであるという意味で、実際には「クラスター前」であると考えるのは正しいですか?

(4) (3) が真の場合、O(n^2)「実際の」クラスターにさらに分割するために、各「プレクラスター」内で検索を行う必要があることを意味しますか? (これは、小さくてかなりバランスの取れた事前クラスターが多数ある場合は合理的かもしれませんが、それ以外の場合はそれほど多くありません)

私は現在、MinHashing技術を使用したドキュメント クラスタリングに取り組んでいます。ただし、MinHash は概算でJaccard similarityあり、要件に合わないため、望ましい結果が得られません。

これは私のシナリオです:

私は膨大な数の本を持っており、単一のページがクエリとして与えられた場合、このページが取得された対応する本を見つける必要があります。制限は、本全体の機能があり、本のページごとの機能を取得することが不可能であることです。この場合、本が大きすぎると、Jaccard 類似度の結果が悪くなります。私が本当に欲しいのは、クエリ ページと書籍の間の距離です (その逆ではありません)。あれは：

2 つのセット A、B が与えられた場合: A から B までの距離が必要です。

セットAからセットBまでの距離を与える同様の距離メトリックはありますか?さらに、MinHashingこの種の類似メトリックでアルゴリズムを使用することはまだ可能ですか?

Elasticsearch で LSH を許可するプラグインはありますか? はいの場合は、その場所を示して、その使い方を少し教えていただけますか? ありがとう

編集: ES が MinHash プラグインを使用していることがわかりました。これを使用してドキュメントを相互に比較するにはどうすればよいですか? 重複を見つけるのに適した設定は何ですか?