minhash算法-Seo优化-塔城地区网站建设公司

MinHash（最小哈希）算法是一种在计算机科学中用于快速估计两个集合之间相似度的算法。它由 Andrei Broder 在1997年提出，最初用于搜索引擎中网页去重和聚类。

在大数据环境下，如果直接比对两个海量集合的交集和并集，计算量会呈爆炸式增长。MinHash 的核心思想是：将庞大的集合“压缩”为一个短小的特征向量（签名），通过比对签名来估算原始集合的相似度。

1. 核心数学基础：Jaccard 相似度

在了解 MinHash 之前，需要先知道它所估计的指标——Jaccard 相似度（Jaccard Similarity）。

对于两个集合A AA和B BB，它们的 Jaccard 相似度定义为：两个集合的交集大小除以并集大小。

J ( A , B ) = ∣ A ∩ B ∣ ∣ A ∪ B ∣ J(A, B) = \frac{|A \cap B|}{|A \cup B|}J(A,B)=∣A∪B∣∣A∩B∣

结果在0 00到1 11之间。1 11表示集合完全相同，0 00表示完全没有交集。

2. MinHash 的工作原理

MinHash 的巧妙之处在于：利用哈希函数的随机性，将 Jaccard 相似度的计算转化为概率问题。

核心定理

假设有一个随机的哈希函数h hh，它将集合中的元素映射为一个整数。对于集合A AA和B BB，它们的所有元素在经过h hh哈希后，最小哈希值相等的概率，正好等于它们的 Jaccard 相似度。

P ( min ⁡ ( h ( A ) ) = min ⁡ ( h ( B ) ) ) = J ( A , B ) P(\min(h(A)) = \min(h(B))) = J(A, B)P(min(h(A))=min(h(B)))=J(A,B)

为什么？
想象把A ∪ B A \cup BA∪B的所有元素随机排列。在这个排列中，第一个出现的元素要么属于A AA（且不属于B BB），要么属于B BB（且不属于A AA），要么属于A ∩ B A \cap BA∩B（交集）。
只有当第一个出现的元素同时属于A AA和B BB（即属于交集）时，min ⁡ ( h ( A ) ) \min(h(A))min(h(A))才会等于min ⁡ ( h ( B ) ) \min(h(B))min(h(B))。因此，相等的概率就是∣ A ∩ B ∣ ∣ A ∪ B ∣ \frac{|A \cap B|}{|A \cup B|}∣A∪B∣∣A∩B∣。

3. 算法实现步骤（MinHash Signature）

单个哈希函数只能给出0 00（不相等）或1 11（相等）的结果。为了准确估计相似度，我们需要使用k kk个不同的随机哈希函数（通常k = 100 ∼ 500 k = 100 \sim 500k=100∼500），为每个集合生成一个长度为k kk的签名（Signature）。

步骤拆解：

行特征矩阵化：将所有文档/集合中的元素（比如文本去重中的单词或 Shingle）作为行，文档作为列，构建一个0 / 1 0/10/1矩阵（1 11表示文档包含该元素）。
应用k kk个哈希函数：创建k kk个独立的哈希函数h 1 , h 2 , . . . , h k h_1, h_2, ..., h_kh1,h2,...,hk。
计算签名向量：对于每一个文档（列），计算其所有包含的元素（行为1）在各个哈希函数下的最小值。

文档A AA的签名向量 =[ min ⁡ ( h 1 ( A ) ) , min ⁡ ( h 2 ( A ) ) , . . . , min ⁡ ( h k ( A ) ) ] [\min(h_1(A)), \min(h_2(A)), ..., \min(h_k(A))][min(h1(A)),min(h2(A)),...,min(hk(A))]