問題タブ [simhash]

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

Rにsimhashの実装はありますか?

(SimHash は Moses Charikaris によって作成されたハッシュ アルゴリズムであり、同様のオブジェクトに同様のハッシュを与えます)

私はしばらくの間、simhash アルゴリズムに苦労しています。クローラーでの理解に従って実装しました。しかし、私がいくつかのテストを行ったとき、それは私にはあまり信頼できないようでした.

200.000 の異なるテキスト データのフィンガープリントを計算したところ、いくつかの異なるコンテンツに同じフィンガープリントがあることがわかりました。そのため、衝突の可能性が大いにあります。

私の実装コードは以下です。

私の質問は次のとおりです。私の実装が正しい場合、このアルゴリズムには大きな衝突があります。なぜグーグルはこのアルゴリズムを使用するのですか? そうでなければ、私のアルゴリズムの問​​題は何ですか?

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

MYSQL から MongoDB に移行したいと思います。これは、必要な XOR とビット カウントを取得またはシミュレートできれば、答えが見つからない質問の 1 つです。

MYSQL では、次のようにします。

MongoDB で同様のことを行うことは可能ですか?

基本的に私は Simhashing をしたいです。

64 ビット以上の整数をサポートするには BitCount が必要です。

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

Simhash モジュール ( https://github.com/leonsim/simhash ) をチェックしていました。

Simhash("String").distance(Simhash("Another string")) は、2 つの文字列間のハミング距離だと思います。さて、( https://leons.im/posts/a-python-implementation-of-simhash-algorithm/ ) に示すように、この "get_features(string) メソッドを完全に理解しているかどうかはわかりません。

ここで、幅 2 を使用して「aaaa」と「aaas」の間の距離を計算しようとすると、距離が 0 になります。

ここで何が欠けているのかわかりません。