3

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

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

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

A -> h01
B -> h02
C -> h02
D -> h02
E -> h03

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

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

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

A -> h01 - h02 - h03

B -> h04 - h05 - h06
      |
C -> h04 - h07 - h08
                  |
D -> h09 - h10 - h08

E -> h11 - h12 - h13

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

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

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

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

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

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

4

1 に答える 1

2

SimHash と MinHash はどちらも、セットの署名に対応する値のリストにセットをマップできるハッシュ アルゴリズムです。

SimHash の場合、値のリストは単なるビットのリストです (値は 0 または 1 です)。MinHash の場合、リスト内の値は、通常 32 ビットまたは 64 ビットの値である特定のハッシュ関数に関連するすべてのセット要素の最小ハッシュ値を表します。

両方のアルゴリズムの主な違いは、ハッシュの衝突の可能性です。SimHash の場合はコサイン類似度に等しく、MinHash の場合は Jaccard 類似度に等しくなります。セット間の類似性をどのように定義するかによって、どちらかのアルゴリズムがより適切になる可能性があります。

選択したハッシュ アルゴリズムに関係なく、計算された署名の値は一定数のバンドに均等に分割されます。任意の 2 つのセットのシグネチャが少なくとも 1 つのバンド内で同一である場合、対応するセットのペアが類似性の候補として選択されます。(これは、n セットがバンド内で同じ署名を持っている場合、このバンドだけで O(n^2) 個の候補ペアがあることを意味します。) 完全な署名 (他のバンドからの値を含む) を使用して各候補ペアの類似性を推定し、推定された類似性が特定のしきい値を超えるペアのみを保持すると、最終的に最終的なクラスタリングを定義するすべての類似したセットのペアが得られます。

于 2016-11-13T17:39:49.000 に答える