前言

在数据挖掘中，一个最基本的问题就是比较两个集合的相似度。

通常通过遍历这两个集合中的所有元素，统计这两个集合中相同元素的个数，来表示集合的相似度；这一步也可以看成特征向量间相似度的计算（欧氏距离，余弦相似度）。

当这两个集合里的元素数量异常大（特征空间维数很大），同时又有很多个集合需要判断两两间的相似度时，传统方法会变得十分耗时，最小哈希（minHash）可以用来解决该问题。

Jaccard 相似度

在本例中，我们仅探讨集合的相似度，先来看 Jaccard 相似度。假设有两个集合A，B，则

Jaccard(A, B)= |A ∩ B| / |A ∪ B|

我们举一个例子：

集合相似度

在上述例子中，sim(A, B) = 2/7。

minHash最小哈希

举例 A，B 两个集合：

A = {s1, s3, s6, s8, s9}
B = {s3, s4, s7, s8, s10}

根据 Jaccard 公式，A, B 的相似度 S(A,B) = |A ∩ B| / |A ∪ B| = 2 / 8 = 0.25

当然直接计算两个集合的交集与并集，是很耗计算资源的，特别是在海量数据场景下不可行。

假如，我们随机从两个集合中各挑选一个元素 s(A)、s(B)，刚好这两个元素相同的概率是多少呢？
这个概率其实等同于，在 A ∪ B 这个大的随机域里，选中的元素落在 A ∩ B 这个区域的概率，这个概率就等于 Jaccard 的相似度！这就是 MinHash 的基本原理。

基于这一原理，我们找一个随机的哈希函数 h，对集合的每一个元素作哈希运算。
比如集合 A，可以算出 5 个 hash 值，因为是随机的，这 5 个 hash 值里值最小的那个元素，对于 A 集合中所有元素概率都是均等的。同样方法从 B 中取最小 hash 值，2 个 minHash 相等的概率就是集合的相似度了。

我们只需要找到 N 个哈希函数，对集合生成一组 minHash，算两个集合的相似度，也就是这 2 组 minHash中，交集/并集了。
这个计算相对容易了，因为每个集合的元素数变成了常数 N，也就是说，minHash 其实是一种降维技术。

MinHash 其实是一种降维技术。

代码演示

1. 添加 Maven 依赖：

<dependency>
  <groupId>org.codelibs</groupId>
  <artifactId>minhash</artifactId>
  <version>0.2.0</version>
</dependency>

2. 计算 minHash

import org.apache.commons.lang3.StringUtils;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.Tokenizer;
import org.apache.lucene.analysis.core.WhitespaceTokenizer;
import org.codelibs.minhash.MinHash;

import java.io.IOException;

public class MinHashDemo {
    public static void main(String[] args) throws IOException {
        // Lucene's tokenizer parses a text.
        Tokenizer tokenizer = new WhitespaceTokenizer();
        // The number of bits for each hash value.
        int hashBit = 1;
        // A base seed for hash functions.
        int seed = 0;
        // The number of hash functions.
        int num = 128;
        // Analyzer for 1-bit 32 hash with custom Tokenizer.
        Analyzer analyzer = MinHash.createAnalyzer(tokenizer, hashBit, seed, num);

        String text = "Fess is very powerful and easily deployable Enterprise Search Server.";

        // Calculate a minhash value. The size is hashBit*num.
        byte[] minhash = MinHash.calculate(analyzer, text);

        System.out.println(minhash.length); // 128 / 8 = 16
        System.out.println(StringUtils.join(minhash, ','));
    }
}

tips：1 byte = 8 bits

3. 比较文本相似度

compare 方法返回文本之间的相似性。值从 0 到 1，但是值小于 0.5 表示不同的文本。

import lombok.SneakyThrows;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.Tokenizer;
import org.apache.lucene.analysis.core.WhitespaceTokenizer;
import org.codelibs.minhash.MinHash;

import java.io.IOException;

public class MinHashDemo {
    public static void main(String[] args) throws IOException {
        String text = "Fess is very powerful and easily deployable Enterprise Search Server.";
        byte[] minhash = calculateMinHash(text);

        String text1 = "Fess is very powerful and easily deployable Search Server.";
        byte[] minhash1 = calculateMinHash(text1);
        float score1 = MinHash.compare(minhash, minhash1);
        System.out.println(score1); // 0.953125

        // Compare a different text.
        String text2 = "Solr is the popular, blazing fast open source enterprise search platform";
        byte[] minhash2 = calculateMinHash(text2);
        float score2 = MinHash.compare(minhash, minhash2);
        System.out.println(score2); // 0.453125
    }
    
    @SneakyThrows
    private static byte[] calculateMinHash(String text) {
        // Lucene's tokenizer parses a text.
        Tokenizer tokenizer = new WhitespaceTokenizer();
        // The number of bits for each hash value.
        int hashBit = 1;
        // A base seed for hash functions.
        int seed = 0;
        // The number of hash functions.
        int num = 128;
        // Analyzer for 1-bit 32 hash with custom Tokenizer.
        Analyzer analyzer = MinHash.createAnalyzer(tokenizer, hashBit, seed, num);

        // Calculate a minhash value. The size is hashBit*num.
        return MinHash.calculate(analyzer, text);
    }
}

Lucene 分词器（拓展）

WhitespaceAnalyzer 演示代码：

import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.core.WhitespaceAnalyzer;
import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;

import java.io.IOException;

public class AnalyzerDemo {
    public static void main(String[] args) throws IOException {
        WhitespaceAnalyzer analyzer = new WhitespaceAnalyzer();

        String text = "The Lucene PMC is pleased to announce the release of the Apache Solr Reference Guide for Solr 4.4.";

        TokenStream tokenStream = analyzer.tokenStream("field", text);
        CharTermAttribute charTermAttribute = tokenStream.addAttribute(CharTermAttribute.class);
        tokenStream.reset();
        while (tokenStream.incrementToken()) {
            System.out.println(charTermAttribute.toString());
        }
        tokenStream.end();
        tokenStream.close();
    }
}

输出：

The
Lucene
PMC
is
pleased
to
announce
the
release
of
the
Apache
Solr
Reference
Guide
for
Solr
4.4.

参考

• minHash最小哈希原理
• https://github.com/codelibs/minhash
• Lucene 4.4.0中常用的几个分词器
• 文本查重-SimHash和MinHash算法
• 海量数据相似数据查找方法
• MinHash原理与应用