ミンハッシュ

コンピュータサイエンスとデータマイニングにおいて、MinHash（または最小値独立順列 局所性敏感ハッシュ方式）は、2つのセットがどれだけ類似しているかを素早く推定する技術です。この方式は、1997年の会議でAndrei Broderによって発表され、 ^[1]当初はAltaVista検索エンジンで重複したWebページを検出し、検索結果から削除するために使用されました。^[2]また、単語セットの類似性によってドキュメントをクラスタリングするなど、大規模なクラスタリング問題にも適用されています。 ^[1]

ジャカード類似度係数は、 2 つの集合間の類似性を示す一般的な指標です。Uを集合とし、AとB をUのサブセットとすると、ジャカード指数は、それらの共通集合の要素数とそれらの和集合の要素数の比として定義されます。

${\displaystyle J(A,B)={{|A\cap B|} \over {|A\cup B|}}.}$

この値は、2 つのセットが互いに素である場合は 0、等しい場合は 1、それ以外の場合は厳密に 0 と 1 の間になります。Jaccard インデックスが 1 に近いほど、2 つのセットは類似しています (つまり、共通のメンバーが比較的多くあります)。MinHash の目的は、交差と和集合を明示的に計算せずに、 J ( A、B ) を迅速に推定することです。

h をUのメンバーを異なる整数にマッピングするハッシュ関数とし、 perm を集合Uの要素のランダムな順列とし、 Uの任意の部分集合Sについて、 h _min ( S )をh ∘ permに関するSの最小のメンバー、つまりh ( perm ( x ))の最小値を持つSのメンバーxと定義します。(使用するハッシュ関数が疑似ランダム特性を持つと想定される場合、ランダムな順列は使用されません。)

ここで、h _{min を}AとB の両方に適用し、ハッシュ衝突がないと仮定すると、のすべての要素の中でハッシュ値が最小の要素が交差点 にある場合にのみ、値が等しい ( h _min ( A ) = h _min ( B ) ) ことがわかります。これが真である確率は、ジャカード指数とまったく同じであるため、次のようになります。 ${\displaystyle A\cup B}$${\displaystyle A\cap B}$

Pr[ h _min ( A ) = h _min ( B )] = J ( A , B )、

つまり、h _min ( A ) = h _min ( B )が真である確率は、一様分布からパームを抽出した場合の類似度J ( A、B )に等しいということです。言い換えると、 rがh _min ( A ) = h _min ( B )のときに 1 、それ以外のときに 0 となるランダム変数である場合、 r はJ ( A、B )の不偏推定量です。 r は分散が大きすぎるため、それ自体では Jaccard 類似度の有用な推定量にはなりません。これは、 r が常に 0 か 1 であるためです。MinHashスキームの考え方は、同じ方法で構築された複数の変数を平均化することで、この分散を減らすというものです。 ${\displaystyle r}$

minhash 方式の最も単純なバージョンでは、 k 個の異なるハッシュ関数を使用します。ここで、kは固定の整数パラメータであり、各セットS をこれらのk個の関数のh _min ( S )のk個の値で表します。

このバージョンの方式を使用してJ ( A , B )を推定するには、 y をh _min ( A ) = h _min ( B )となるハッシュ関数の数とし、y / k を推定値として使用します。この推定値は、 k 個の異なる 0-1 ランダム変数の平均です。各変数は、h _min ( A ) = h _min ( B )の場合は 1 、それ以外の場合は 0 となり、 J ( A , B )の不偏推定値となります。したがって、それらの平均も不偏推定値となり、 0-1 ランダム変数の合計の標準偏差により、その期待誤差はO(1/ √ k )となります。^[3]

したがって、任意の定数ε > 0に対して、推定値の期待誤差が最大でも εとなる定数k = O(1/ε ² )が存在します。たとえば、期待誤差が .05 以下となるようにJ ( A , B )を推定するには、400 回のハッシュが必要になります。

複数のハッシュ関数を計算するのは計算コストがかかる場合があります。しかし、 MinHash スキームの関連バージョンでは、ハッシュ関数を 1 つだけ使用し、ハッシュ関数ごとに 1 つの最小値のみを選択するのではなく、各セットから複数の値を選択するためにハッシュ関数を使用することでこのペナルティを回避します。 hをハッシュ関数、kを固定整数とします。S がhの定義域内のk以上の値の任意のセットである場合、 h _{( k )} ( S )を、 hの最小値を持つSのkメンバーのサブセットとして定義します。このサブセットh _{( k )} ( S )はセットSの署名として使用され、任意の 2 つのセットの類似性は署名を比較することで推定されます。

具体的には、AとB を任意の 2 つの集合とします。すると、X = h _{( k )} ( h _{( k )} ( A ) ∪ h _{( k )} ( B )) = h _{( k )} ( A ∪ B )はA ∪ Bのk個の要素の集合となり、h がランダム関数であれば、k個の要素の任意のサブセットが選択される可能性は等しくなります。つまり、X はA ∪ Bの単純ランダムサンプルです。サブセットY = X ∩ h _{( k )} ( A ) ∩ h _{( k )} ( B )は、交差点A ∩ Bに属するXのメンバーの集合です。したがって、 | Y |/ k はJ ( A , B )の不偏推定値です。この推定値と複数のハッシュ関数によって生成される推定値の違いは、X には常にk個のメンバーがあるのに対し、複数のハッシュ関数では、2 つの異なるハッシュ関数が同じ最小値を持つ可能性があるため、サンプル要素の数が少なくなる可能性があることです。ただし、kがセットのサイズに比べて小さい場合、この違いは無視できます。

非復元サンプリングの標準的なチェルノフ境界によれば、この推定量はO(1/ √k )の誤差が予想され、多重ハッシュ関数方式のパフォーマンスと一致します。

推定量| Y |/ k は、どちらの方式でも、与えられたセットの 2 つの署名からO( k )の時間で計算できます。したがって、 εとkが定数の場合、署名から推定類似度を計算する時間も一定です。各セットの署名はセットのサイズに対して線形時間で計算できるため、多数のペアワイズ類似度を推定する必要がある場合、この方法を使用すると、各セットのメンバーを完全に比較する場合に比べて実行時間を大幅に節約できます。具体的には、セット サイズがn の場合、多数のハッシュのバリアントではO( n k ) の時間がかかります。単一のハッシュのバリアントは一般に高速で、n >> kと仮定すると、最小ハッシュ値のキューを維持するためにO( n ) の時間が必要です。^[1]

MinHashesの計算に重みを導入するさまざまな手法が開発されています。最も単純な手法は、それを整数の重みに拡張するものです。^[4] ハッシュ関数hを拡張して、セットメンバーと整数の両方を受け入れ、各アイテムの重みに応じて複数のハッシュを生成します。アイテムiがn回出現する場合は、ハッシュを生成します。この拡張されたハッシュセットに対して元のアルゴリズムを実行します。これにより、衝突確率として 重み付きJaccard指数が得られます。${\displaystyle h(i,1),h(i,2),\ldots ,h(i,n)}$

${\displaystyle J_{\mathcal {W}}(x,y)={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}}$

より短い実行時間で実重みに対する衝突確率を実現するさらなる拡張が開発されており、1つは密なデータ用、^[5]、もう1つは疎なデータ用である。^[6]

別の拡張機能ファミリーでは、指数分布ハッシュを使用します。0 から 1 の間の均一ランダム ハッシュは、CDF 反転によって指数分布に従うように変換できます。この方法は、指数変数の集合の最小値の多くの優れた特性を活用します。

${\displaystyle H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}}$

これにより、衝突確率として確率ジャカード指数^{[7]が得られる。}

${\displaystyle J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0 \atop y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}}$

上で説明したように MinHash 方式を実装するには、ハッシュ関数h でn個の要素のランダムな順列を定義する必要があります。ここでn は、比較するすべてのセットの和集合に含まれる異なる要素の総数です。しかし、n個の異なる順列があるため、真にランダムな順列を指定するだけでΩ( n log n )ビットが必要になります。これは、 nが中程度の値であっても実現不可能なほど大きな数です。この事実から、ユニバーサル ハッシュの理論に倣って、「最小値独立」な順列の族を見つけるための重要な研究が行われてきました。これは、ドメインの任意のサブセットについて、任意の要素が最小値になる可能性が等しいことを意味します。最小値独立な順列の族には、少なくとも次の要素が含まれている必要があることが確立されています。

${\displaystyle \operatorname {lcm} (1,2,\cdots ,n)\geq e^{no(n)}}$

異なる順列が存在するため、単一の順列を指定するのにΩ( n )ビットが必要となり、それでも実行不可能なほど大きい。 ^[2]

上記の非実用性のため、最小単位独立性の2つの変形概念が導入されました。制限付き最小単位独立順列族と近似最小単位独立族です。制限付き最小単位独立性は、最大kの特定の基数集合に制限された最小単位独立性特性です。^[8]近似最小単位独立性は、完全独立性から変化する 確率が最大で固定の確率εです。 ^[9]

1999年にピオトル・インディクは、ハッシュ関数のk-wise独立な族は、十分大きい場合には近似的にmin-wise独立でもあることを証明した^[10]。特に、ならばと なる定数が存在する。${\displaystyle k}$${\displaystyle c,c'>0}$${\displaystyle k\geq c\log {\tfrac {1}{\epsilon }}}$

${\displaystyle \Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),}$

すべての集合およびについて。(注意: ここでは、確率が最大で 1 倍大きくなり、最大で倍小さくなることを意味します。) ${\displaystyle |X|\leq \epsilon nc'}$${\displaystyle x\not \in X}$${\displaystyle (1\pm \epsilon )}$${\displaystyle 1+\epsilon }$${\displaystyle 1-\epsilon }$

この保証は、とりわけ、MinHashアルゴリズムに必要なJaccard境界を与えるのに十分である。つまり、とが集合である場合、 ${\displaystyle A}$${\displaystyle B}$

${\displaystyle \Pr _{h\in {\mathcal {H}}}[\min h(A)=\min h(B)]={\frac {|A\cap B|}{|A\cup B|}}\pm \epsilon .}$

k 単位の独立ハッシュ関数はビットのみを使用して指定できるため、このアプローチは完全に min 単位の独立順列を使用するよりもはるかに実用的です。 ${\displaystyle k\log n}$

近似的に最小値ごとの独立性を与えるハッシュ関数のもう 1 つの実用的なファミリは、タブレーション ハッシュです。

MinHashの元々の用途は、Web文書内の単語の集合として表現されるクラスタリングとほぼ重複の除去でした。^{[1] [2] [11]}同様の技術は、画像などの他の種類のデータのクラスタリングとほぼ重複の除去にも使用されています。画像データの場合、画像は、そこから切り取られた小さなサブイメージの集合として、またはより複雑な画像特徴記述の集合として表現できます。^[12]

データマイニングにおいて、Cohen et al. (2001) はMinHashを相関ルール学習のツールとして使用しています。各エントリが複数の属性を持つデータベース（データベースエントリごとに行、属性ごとに列を持つ0–1行列として表示）が与えられた場合、彼らはJaccardインデックスのMinHashベースの近似値を使用して、頻繁に共起する属性の候補ペアを識別し、それらのペアのみのインデックスの正確な値を計算して、共起頻度が特定の厳密なしきい値を下回るペアを決定します。^[13]

MinHash アルゴリズムはバイオインフォマティクスに応用されており、ゲノム配列の比較の問題は、Web 上の文書の比較の問題と理論的根拠が似ています。MinHash ベースのツール^{[14] [15]を使用すると、ゲノム全体の配列データと参照ゲノムを迅速に比較できます (1 つのゲノムを}RefSeq の 90000 の参照ゲノムと比較するのに約 3 分かかります)。また、種の分類や、ある程度の微生物のサブタイピングに適しています。メタゲノミクス^[14]への応用や、ゲノムアライメントやゲノムアセンブリのための MinHash 派生アルゴリズムの使用もあります。^[16] MinHash ベースのアルゴリズムを使用すると、正確な平均ヌクレオチド同一性 (ANI) 値を非常に効率的に生成できます。^[17]

MinHash 方式は、ハッシュ関数を使用して、2 つのオブジェクト間の距離が短い場合にハッシュ値が同じになる可能性が高いように、オブジェクトの大きなセットをより小さなハッシュ値にマッピングする一連の手法である局所性に敏感なハッシュの一例と見なすことができます。この例では、セットの署名がそのハッシュ値と見なすことができます。他の局所性に敏感なハッシュ手法には、セット間のハミング距離やベクトル間のコサイン距離などがあります。局所性に敏感なハッシュは、最近傍検索アルゴリズムで重要なアプリケーションを持っています。 ^[18]大規模な分散システム、特にMapReduceでは、ポイント次元に依存せずに類似性を計算するのに役立つ MinHash の修正バージョンが存在します。^[19]

2006年にGoogleはMinhashとSimHash ^[21]アルゴリズム の性能を比較する大規模な評価を実施しました^{[20] 。2007年にGoogleはWebクロールの重複検出にSimhashを使用し[22] 、} GoogleニュースのパーソナライゼーションにMinhashとLSHを使用していると報告しました^[23]。

• ブルームフィルタ – 近似集合メンバーシップのデータ構造
• カウント・ミニマムスケッチ – コンピュータサイエンスにおける確率的データ構造
• W-シングル