問題タブ [minhash]

ブルーム フィルターと Minhashing を実装して同様のアイテムを見つける必要があるアプリケーションがあります。

ブルームフィルターを実装しましたが、それを行うにはミンハッシング部分を理解していることを確認する必要があります:

• アプリケーションは、多数の k の長さの文字列を生成し、それをドキュメントに格納します。その後、それらすべてがブルームに挿入されます。
• MinHash を実装したいのは、ユーザーが文字列を挿入して比較し、ドキュメントで最も類似したものを見つけようとするオプションを提供することです。

ドキュメントのすべての文字列をシングルにする必要がありますか? 問題は、これらの中で私を助ける何かを実際に見つけることができないということです。私が見つけたのは、2 つのドキュメントに関するものであり、文字列のセットに対する 1 つの文字列に関するものではありません。

私は次のように持ってDataSetいます：

このデータセットのvector一部が「特性マトリックス」と呼ばれるもので、「どのドキュメントにどの要素が含まれているか」を表しています。目に優しい形式を使用して、特性行列を書き出しましょう。

注意深く見ると、要素とを含む にkey0マップされていることがわかります。そのため、 で与えられるベクトルがあります (ベクトルは の下の列です。特性マトリックス自体には列と最初の行が含まれていないことに注意してください。読みやすくするためだけに存在します。doc0ad(5,[0,2],[1.0,1.0])doc0element

ここでの目標は、Nハッシュ関数を使用して、この特性行列のMinhash 署名を取得することです。

たとえば、 let N = 2、つまり 2 つのハッシュ関数が使用され、これら 2 つのハッシュ関数が次のように与えられているとも言えます。

x特性行列の行番号です。これら 2 つのハッシュ関数を使用した後、「minhash 署名マトリックス」は次のようになると予想しています。

さて、Spark Java を使用して、使用したいこれら 2 つのハッシュ関数を指定するにはどうすればよいですか?次に、指定されたデータセットから上記の RDD を生成するにはどうすればよいですか? 実際のテストケースでは、おそらく約 1000 個のハッシュ関数を使用しますが、現時点では 2 個の使用方法を理解していれば十分です。

私は Spark ドキュメントを検索して読んでいますが、これに関するハンドラーを取得するのは非常に難しいようです。ヒント/ガイダンスは私にとって非常に役立ちます。

前もって感謝します！

今、私はドキュメントを見て、次のコードを持っています:

さて、結果を説明する方法がわかりません...Sparkで使用されるハッシュ関数は何ですか? これらの機能が何であるかを制御できますか? 結果を別のバケットにハッシュして、同じバケット内のドキュメントが「同じ」ドキュメントになるようにするにはどうすればよいですか? 結局のところ、ペアごとの比較はしたくありません...

かなり長くなり、申し訳ありません。

第 3 章で説明した Minhash LSH アルゴリズムを、Spark (Java) を使用して実装しようとしています。私はこのようなおもちゃの問題を使用しています:

目標は、これら 4 つのドキュメント ( doc0、doc1、doc2およびdoc3) の中で、どのドキュメントが互いに類似しているかを特定することです。そして明らかに、可能な唯一の候補ペアはdoc0とdoc3です。

Spark のサポートを使用して、次の「特性マトリックス」を生成することは、現時点で到達できる範囲です。

コードスニペットは次のとおりです。

現在、MinHashLSHModel model使用できる には 2 つの主要な呼び出しがあるようです:model.approxSimilarityJoin(...)とmodel.approxNearestNeighbors(...). これら 2 つの呼び出しの使用例は次のとおりです: https://spark.apache.org/docs/latest/ml-features.html#lsh-algorithms

一方、model.approxSimilarityJoin(...)2 つのデータセットを結合する必要があります。私は 4 つのドキュメントを持つデータセットを 1 つしか持っていません。これら 4 つのドキュメントのどれが互いに類似しているかを調べたいので、2 つ目のデータセットはありません。結合... 試してみるために、実際に唯一のデータセットをそれ自体に結合しました。結果に基づいて、model.approxSimilarityJoin(...)ペアワイズ Jaccard 計算を行ったようで、ハッシュ関数などの数を変更しても影響は見られず、minhash 署名が正確にどこで計算され、バンド/行がどこで計算されたのか疑問に思いました。分割が発生しました...

もう 1 つの呼び出し はmodel.approxNearestNeighbors(...)実際に比較ポイントを要求し、モデルはこの指定されたポイントに最も近いものを識別します... 明らかに、これも私が望んでいたものではありません。余分な基準点はありません。

アイデアが尽きたので、Spark API を使用して独自のバージョンのアルゴリズムを実装しましたが、からのサポートがあまりなくMinHashLSHModel model、本当に気分が悪くなりました。私は何かを逃したにちがいないと思っています... ??

どんな考えでも聞きたいです、本当に謎を解きたいです。

よろしくお願いします！