問題タブ [minhash]

FindSimilarminHash を使用して 2 つのセット間の類似性を見つけるというクラスがあります (この目標では、うまく機能します)。私の問題は、2 つ以上のセットを比較する必要があることです。より具体的には、特定のset1量の他のセットと比較する必要があります。クラスは次のとおりです。

similarityこのメソッドを 2 つ以上のセットで使用する必要があります。問題は、それらすべてを調べる方法が見つからないことです。を作成した場合、 と を比較しforたいとは言えません。私が意味を成しているかどうかはわかりませんが、少し混乱していることを認めなければなりません。set1seti

このプログラムの目的は、ユーザーを比較することです。ユーザーには連絡先 (他のユーザー) のリストがあり、同様のユーザーには同様の連絡先があります。各セットはユーザーであり、セットの内容は連絡先になります。

次の 2 つのテキストがあります。

text0 = "AAAAAAAAAAAA";

text1 = "AAAAABAAAAAA";

4枚刃を使用しています。したがって、text0 = {AAAA}、text1 = {AAAA、AAAB、AABA、ABAA、BAAA} です。

この場合、Jaccard 類似度は sim = 1/5 = 0.2 です。

私はこの結果を望んでいません。2 つのテキストの類似性が高いように思われるためです。

次のようにバッグの類似性を使用したい：

text0 = {AAAA、AAAA、AAAA、AAAA、AAAA、AAAA、AAAA、AAAA、AAAA}、

text1 = {AAAA、AAAA、AAAB、AABA、ABAA、BAAA、AAAA、AAAA、AAAA}。

この 2 つのバッグを使用する場合、その類似は sim = 5/9 です。これは 0.2 をはるかに超えています。

MinHash はこれを行うことができますか?

.approxSimilarityJoinSpark MLlib LSH: MinHash for Jaccard Distanceを使用しようとしています。

numHashTables が高いほど、システムがより正確になり、計算がより複雑/遅くなることを理解しています。パラメータについて 2 つの質問があります。

• numHashTables と MinHash 指紋サイズの関係は?
• 値を正しく設定するにはどうすればよいですか?

注: このアルゴリズムは Uber によって MLlib に追加されていると思います: https://eng.uber.com/lsh/

ドキュメント A と B の間のジャカードの類似性を推定する必要があり、これらのセット/ドキュメントの和集合の k 個のランダム順列を使用して、ドキュメントの署名を決定するとします。

k 値はどのように設定すればよいですか? 非常に高い値に設定すると計算時間が大幅に増加するため、適切な jaccard インデックス推定値を得ることができる k の最小値は何でしょうか?

許容誤差 e>0 とデルタが与えられた場合、ジャカード インデックスが (1-e)jaccard_estimate と (1+e)jaccard_estimate の間にあり、(1-delta) 以上の確率で k の最小値を決定するにはどうすればよいですか? ?

これは、チャーノフの不等式境界を使用して導出できると思いますが、どうすればよいかわかりません。どんな助けでも大歓迎です。前もって感謝します！