問題タブ [minhash]

私が知っているように、このタスクでは simhash と minhash を利用できます。しかし、これらのアルゴリズムはすべて、テキスト データベース全体を走査する必要があり、これは非常に恐ろしいことです。タスクを加速できる最適化またはその他のアルゴリズムはありますか? 私が思いついたのは、テキスト データベースをいくつかの部分にスライスし、ペアごとの類似性を並行して取得することだけです。私のテキスト データベースには、約 10 億のレコードがあります。

2 つのセットのミンハッシュ署名があり、2 つのセットの Jaccard 類似度を計算したいとします。我々は持っています：

-> S1 S2

h1 0 1

h2 1 2

h3 2 0

h4 3 3

S1 と S2 は同じ署名を異なる順序で持っています。Jaccard 類似度は 1/8 または 1(おおよそ) ですか?

私は simhash を使用していますが、minhash の方が効果的であることもわかります。
しかし、私は理解していません。
説明してください: simhash より有利な minhash は何ですか?

視覚的な言葉 (画像内の重要なポイントにラベル付けされています) に基づいて画像を一致させようとしています。シミュレートされた結果を私の理論上の結果と比較すると、かなりの偏差が得られるため、私の理論上の確率計算に間違いがあるに違いないと思います。

2 つのイメージを一連のビジュアル ワードとして想像できます (ビジュアル ワードの名前は A から Z まであります)。

いくつかのビジュアル ワードが両方のセットに含まれていることが既にわかります (例: A、Z、Y、...)。ここで、ビジュアル ワードをプライマリ ワードとセカンダリ ワードに分けます (提供された画像を参照)。各プライマリ ワードには、隣接するセカンダリ ワードがあります。主要な単語 (赤い四角形) とその二次的な単語 (楕円内の単語) を確認できます。この例では、主な単語セットは次のとおりです。

img1VAL1セット SP1 から視覚的な単語をランダムに選択し、 の近傍から 1 つの単語を選択します。img1VAL1つまりimg1VAL2=SelFromNeighborhood(img1VAL1)、ペアになりPairImage1={img1VAL1, img1VAL2}ます。2 番目の画像でも同じことを行い、 を取得しPairImage2={img2VAL1, img2VAL2}ます。

例: fromはの近くにあるため、プライマリ ビジュアル ワードおよびセカンダリ ワードとしてImage1選択します。ペアを取得しますACCA{A, C}

AImage2 から、プライマリ ビジュアル ワードおよびセカンダリ ワードとしても選択しますZ。ペアを取得します{A, Z}

{A,C} != {A,Z}したがって、一致するものはありません。しかし、ランダムに選択されたペアが等しい確率は?

ミンハッシング アルゴリズムの実装では、整数のランダム順列を多数作成する必要があります。これは、ランダム ハッシュ関数を使用して (できるだけ多く) シミュレートされます。現在、次の形式のハッシュ関数を使用しています。

ここで、a と b はランダムに生成された数値で、c は b の最大値よりも大きい素数です。とにかく、コードの実行が遅すぎて、合理的な実行時間内にそのようなハッシュ関数を 15 個以上使用することは不可能です。Python で整数にランダム ハッシュ関数を使用する他の方法を推奨できる人はいますか? 他の投稿で、ビットごとのシャッフルとXOR演算を使用するための提案に出くわしましたが、このようなものをどのように実装する必要があるかを完全には理解していませんでした (私は Python に比較的慣れていません)。