估计两个或多个集合的相似度¶

概述¶

通常，Jaccard 相似度系数（或指数）用于比较两个集合之间的相似度。对于 A 和 B 这两个集合，Jaccard 指数定义为它们的交集大小与它们的并集大小之比：

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

但是，这种计算可能会消耗大量资源和时间，因此对于大型数据集来说并不理想。

相比之下，MinHash 方案的目标是快速估计 J(A,B)，而无需计算交集或并集。

SQL 函数¶

以下 聚合函数 可让您使用 MinHash 来估计近似相似度：

• MINHASH：返回 MinHash 状态，其包含一个长度为 *k*（输入实参）的 MinHash 数组。

• MINHASH_COMBINE：将两个（或多个）MinHash 输入状态合并为一个 MinHash 输出状态。

• APPROXIMATE_SIMILARITY （或 APPROXIMATE_JACCARD_INDEX）：根据输入集的 MinHash 状态返回其相似度（Jaccard 指数）的估计值。

实施细节¶

详见 MinHash (link removed) （维基百科）：

“假设 H 是一个哈希函数，它将 A 和 B 的成员映射到不同的整型值，并且对于任意集合 S，将 H_min(S) 定义为相对于 H 的 S 的最小成员，即 S 的成员 s，且最小值为 H(s)，如以下等式所示：

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

如果我们将 H_min 同时应用于 A 和 B，那么，当具有最小哈希值的并集 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_A 所示）的 MinHash 数组的条目 i 对应于应用到集合 A 每个元素的哈希函数 H_i 的最小值。

最后，对于 A 和 B 这两个集合，它们的近似相似度通过以下等式计算：

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

示例¶

在下面的示例中，我们展示了如何使用此方案和相应的函数来求出两个元素集合的近似相似度。

首先，创建两个示例表，并插入一些示例数据：

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

然后，使用这两个集合（表 mhtab1 和 mhtab2）的 MinHash 状态求出它们的近似相似度：

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

这两个表的相似度指数约为 0.79，而确切值为 0.8（即 4/5）。