2つ以上のセットの類似性の推定

Snowflakeは MinHash を使用して、2つ以上のデータセット間のおおよその類似性を推定します。MinHash スキームは、セットの交差または結合を計算せずにセットを比較するため、効率的かつ効果的な推定が可能になります。

このトピックの内容：

概要

通常、Jaccard類似性係数（またはインデックス）は、2つのセット間の類似性を比較するために使用されます。 A と B の2つのセットの場合、Jaccardインデックスは、交差のサイズと結合のサイズの比率として定義されます。

J(A,B) = (A ∩ B) / (A ∪ B)

ただし、この計算はかなりのリソースと時間を消費する可能性があるため、大規模なデータセットには適していません。

対照的に、MinHash スキームの目標は、交差または結合を計算することなく、 J(A,B) を迅速に推定することです。

SQL 関数

次の 集計関数 は、MinHash を使用しておおよその類似性を推定するために提供されています。

  • MINHASH: 長さ k （入力引数）の MinHash 配列を含む MinHash 状態を返します。

  • MINHASH_COMBINE: 2つ（またはそれ以上）の入力 MinHash 状態を単一の出力 MinHash 状態に結合します。

  • APPROXIMATE_SIMILARITY （または APPROXIMATE_JACCARD_INDEX）: MinHash 状態に基づいて、入力セットの類似性（Jaccardインデックス）の推定値を返します。

実装の詳細

詳細については、 MinHash （Wikipedia内）をご参照ください：

「H を A および B のメンバーを異なる整数値にマッピングするハッシュ関数とし、 S のセットについては、 H_min(S) を S の最小メンバーとして定義します。 H、つまり、次の式で表される H(s) の最小値を持つ S のメンバー s です。

H_min(S) = argmin_{s \in S} (H(s))

A と B の両方に H_min を適用すると、最小ハッシュ値を持つ和集合 A ∪ B の要素が交差点 A ∩ B にあるときに正確に同じ値を取得します。これが真である確率は、上記の比率です。したがって、次のようになります。

Pr[H_min(A) = H_min(B)] = J(A,B)

つまり、ランダムに選択されたセット A および B を想定すると、 H_min(A) = H_min(B) が成立する確率は J(A,B) に等しくなります。言い換えれば、 X が H_min(A) = H_min(B) の場合に1になり、それ以外では0になるランダム関数の場合、 X は J(A,B) の不偏推定量です。 X の分散は大きすぎるため、Jaccardインデックスだけでは適切な推定量にはなりません（常に0または1であるため）。

MinHash スキームは、 k 個の異なるハッシュ関数を使用して同じ方法で構築されたいくつかの変数を平均化することにより、この分散を減らします。

これを実現するために、 MINHASH 関数は最初に k 個の異なるハッシュ関数を作成し、それらを各入力セットのすべての要素に適用し、それぞれの最小値を保持して、各セットに MinHash 配列（別名： MinHash 状態）を作成します。具体的には、 i = 0 to k-1 の場合、セット A の MinHash 配列のエントリ i （MinHash_A で表示）は、セット A のすべての要素に適用されるハッシュ関数 H_i の最小値に対応します。

最後に、2つのセット A と B のおおよその類似性は次のように計算されます。

J_apprx(A,B) = (# of entries MinHash_A and MinHash_B agree on) / k

例

次の例では、2つの要素セットの類似性を近似するために、このスキームと対応する関数を使用する方法を示します。

まず、2つのサンプルテーブルを作成し、サンプルデータを挿入します。

CREATE OR REPLACE TABLE mhtab1(c1 NUMBER,c2 DOUBLE,c3 TEXT,c4 DATE);
CREATE OR REPLACE TABLE mhtab2(c1 NUMBER,c2 DOUBLE,c3 TEXT,c4 DATE);

INSERT INTO mhtab1 VALUES
    (1, 1.1, 'item 1', to_date('2016-11-30')),
    (2, 2.31, 'item 2', to_date('2016-11-30')),
    (3, 1.1, 'item 3', to_date('2016-11-29')),
    (4, 44.4, 'item 4', to_date('2016-11-30'));

INSERT INTO mhtab2 VALUES
    (1, 1.1, 'item 1', to_date('2016-11-30')),
    (2, 2.31, 'item 2', to_date('2016-11-30')),
    (3, 1.1, 'item 3', to_date('2016-11-29')),
    (4, 44.4, 'item 4', to_date('2016-11-30')),
    (6, 34.23, 'item 6', to_date('2016-11-29'));
Copy

次に、MinHash 状態を使用して2つのセット（テーブル mhtab1 および mhtab2）の類似性を近似します。

SELECT APPROXIMATE_SIMILARITY(mh) FROM
    ((SELECT MINHASH(100, *) AS mh FROM mhtab1)
    UNION ALL
    (SELECT MINHASH(100, *) AS mh FROM mhtab2));

+----------------------------+
| APPROXIMATE_SIMILARITY(MH) |
|----------------------------|
|                       0.79 |
+----------------------------+
Copy

これら2つのテーブルの類似性インデックスは、正確な値0.8（つまり、4/5）とは対照的に、0.79として近似されます。

言語: 日本語