【文本去重】通俗易懂理解Minhash算法

大家好，欢迎来到IT知识分享网。

Minhash算法直观理解

作者： @凌漪_ @板烧鱼仔 @Yuxn.

背景

1. Jaccard相似度
   两个集合 A 和 B，我们关心它们的Jaccard相似度
   $$J(A,B)=\frac{\mid A\cup B\mid }{\mid A\cap B\mid }$$
   Jaccard相似度描述了两个集合之间的相似程度。
   使用场景1：两个文档之间的相似度。注意: jaccard相似度并没有提取文档的任何语义，只是在查看它们是否包含相同的单词。因此，“大王八”和“八大王”的jaccard相似度为1。在计算文档之间的相似度时，通常不会基于词级别，而是n-gram（n个连续单词），再计算交集和并集的元素的个数，得到jaccard相似度。
   使用场景2：你的歌单和我的歌单之间的相似度
   
   
   
   
   
2. 计算Jaccard效率低下
   当拥有一个大型的文档集合时（比如里面有N篇文档），我们需要找出其中相似度高的文档对。此时就需要对文档进行来两两比较，计算Jaccard，得到一个$N\ast N$的矩阵。（当然，为了避免重复进行2次计算：文档A与文档B，文档B与文档A，其中有一半上三角的值为0），所需要的比较次数为 ($N^2)/2$,计算复杂度为$O(N^2)$。而在每次进行jaccard比较时，需要交集和并集，计算复杂度取决于文档的大小，假设所有文档的长度相等，都包含M个单词，则计算复杂度为$O(N^2\cdot M)$。就会耗费很长时间，计算和内存消耗变得不可承受
   
3. Jaccard的计算替代方式：Minhash算法
   Minhash的好处：Minhash可以实现把一篇文章用一个较短的signature表示，这个signature有个很好的性质： 两个minhash signature的Jaccard相似度和原始文本的Jaccard相似度在概率上是一致的。 比较一次的所耗费的时间为numHash，总的计算复杂度为$O(N^2\cdot numHash)$。而numHash是可以自己设置的大小，这就远小于M。
   

minhash如何工作？

1. 假设我们拥有2个集合

# 设置2个集合A和B A = { 
   1, 2, 3, 4, 5} B = { 
   3, 4, 5, 6, 7} 

2. 其jaccard相似度为：

print('Jaccard相似度：', len(A & B) / len(A | B)) Jaccard相似度： 0.4285 

基于hash函数的算法

#设置某个哈希函数 def hash(x, a=1, b=1, p=11): return (a * x + b) % p #对集合里的元素进行哈希，并计算最小哈希值 def minhash(s, hash): return min(hash(x) for x in s) 

我们将某个文档A经过hash函数之后（Hash(A))，记录所得到的最小哈希值(minHash(A))。minHash(A)相当于此集合在某种观测视角下得到的结果。我们对文档B也进行计算，得到

Hash(A) = [5, 8, 0, 3, 6] minHash(A) = 0 Hash(B) = [0, 3, 6, 9, 1] minHash(B) = 0 

最后，minHash(A) = minHash(B）的概率就是Jaccard相似度。这一步我们在之后会进行解释。

实际上，单次比较 minHash(A) 和 minHash(B），查看取值是否相等，这个事件的取值只有True or False。（就和抛硬币一样）只有我们经过多次hash函数操作（相当于经过了多次抛硬币），该事件发生的概率值理论上趋近于（A ∩ B）/ （ A ∪ B）。

5. 接下来我们进行多个不同的hash函数的实验，并观察其变化趋势：
   如果哈希函数产生的结果高度相关（甚至相同），则这些哈希函数提供的不同视角就减少了。这意味着我们实际上并没有从多个独立的角度去观察集合的相似性，从而可能导致估计的Jaccard相似度不够准确
   生成k个不相同的随机数：
   
   

import random def pickRandomCoeffs(k): randList = [] while k > 0: randIndex = random.randint(0, 99999) while randIndex in randList: randIndex = random.randint(0, 99999) randList.append(randIndex) k = k - 1 return randList 

基于不相同的随机数，作为a和b，生成不同hash函数

#生成n个不同的hash函数，确保每个hash函数的a系数和b系数不同： num_hash_funcs = 10000 hash_funcs = [] a = pickRandomCoeffs(num_hash_funcs) b = pickRandomCoeffs(num_hash_funcs) for i in range(num_hash_funcs): #增加不同的hash函数，确保每次生成的hash函数不同 hash_funcs.append(lambda x, a=a[i], b=b[i]: hash(x, a, b)) count = 0 for a, b in zip(minhash_values_A, minhash_values_B): #如果hash函数得到的minhash相同 if a == b: count += 1 print('进行比较的哈希函数个数：', len(hash_funcs)) print('Minhash相似度：', count/ len(hash_funcs)) 

进行比较的哈希函数个数： 5 Minhash相似度： 0.6 进行比较的哈希函数个数： 100 Minhash相似度： 0.38 进行比较的哈希函数个数： 1000 Minhash相似度： 0.411 进行比较的哈希函数个数： 5000 Minhash相似度： 0.4242 

Jaccard相似度的理论值为： 0.4285。随着hash函数的个数增加，实验值逐渐逼近 0.4285

基于打乱排序的做法

我们可以使用基于打乱排序的算法。

观测视角是：进行行变换，打乱排序，查找两个文档第一个为1的下标，判断它们是否相等

打乱行的排序：

具体代码如下：

import random # 设置2个集合A和B A = [0,0,1,1,1] B = [1,0,1,1,0] idx = [0,1,2,3,4] cnt = 0 # 计算Jaccard相似度 print("Jaccard相似度理论值",sum([A[i] & B[i] for i in range(5)]) / sum([A[i] | B[i] for i in range(5)])) for i in range(1000): random.shuffle(idx) newA = [A[i] for i in idx] newB = [B[i] for i in idx] # 第一个为1的位置 idxA = newA.index(1) idxB = newB.index(1) if idxA == idxB: cnt += 1 print("Jaccard相似度实验值",cnt / 1000) 

Jaccard相似度理论值 0.5 Jaccard相似度实验值 0.497 

为什么minhash有效?

case1:

”横看成岭侧成峰，远近高低各不同“ ——苏轼《题西林壁》

minhash相当于在不同视角（投影角度）下观察两个集合的特征点是否相同，如果他们在多次观察下都具有相同的特征点，那么他们很有可能是分布相似的集合。

我们想象现在存在两座山，如果A山和B山从东西南北四个角度观察，他们的最高点高度相同，次高点、次次高点的高度都相同，那么这两座山很可能就是形状一样的山。

minhash在实际操作上很容易，但为什么minHash(A) = minHash(B）的概率就是Jaccard相似度呢？

为了方便理解，我们这里还是举一个直观的例子：

有一个班级，里面有30个小朋友，里面的小朋友不是会唱歌，就是会跳舞，还有的既会唱歌也会跳舞。

此时集合 A = { 会唱歌的小朋友 } A = \{会唱歌的小朋友\} A={
会唱歌的小朋友}， B = { 会跳舞的小朋友 } B = \{会跳舞的小朋友\} B={
会跳舞的小朋友}，$A\cup B$ 构成了全集 $D$

我们寻找一种相同的投影维度（一种哈希函数）将小朋友们排序，并选出顺序第一的人。例如各自选出集合A和B中身高最高的小朋友，他们是同一个小朋友的概率，等价于在全班所有小朋友中都选出最高的小朋友，他既会唱歌也会跳舞的概率。

在这个例子中，身高就是一种将小朋友们向一个方向投影的哈希函数，同理还可以使用体重、力气、吃零食速度、谁哭得最响等等多个维度，最终我们多次投影得到计算的概率值就可以用来近似 $\frac{A\cap B}{A\cup B}$。

转化成数学公式，就是:$Pr(某一种投影(A)=某一种投影(B))=\frac{A\cap B}{A\cup B}$

当多次投影都能得到相同的值时，我们就可以认为这两个集合很相似啦！

参考文献