你能推荐一个好的minhash实现吗？

Question

我正在寻找一个开源的minhash实现，想用在我的工作中。

我需要的功能很简单，就是给定一个集合作为输入，这个实现应该能返回它的minhash。

如果有Python或C语言的实现就更好了，这样我可以根据需要进行修改。

如果有人能提供一些线索，那就太感谢了。

祝好。

Answer 1

看看这个 datasketch库。它支持数据的序列化和合并。这个库是用纯Python写的，不需要其他的外部库。它的 Go版本 也有完全相同的功能。

Answer 2

你可以看看以下这些开源库，按照顺序来。这些库都是用Python写的，展示了如何使用LSH（局部敏感哈希）和MinHash来计算文档之间的相似度：

lsh
LSHHDC : 基于局部敏感哈希的高维聚类
MinHash

Answer 3

如果你对学习minhash算法感兴趣，这里有一个非常简单的实现和一些讨论。

为了生成一个集合的MinHash签名，我们首先创建一个长度为$N$的向量，所有的值都设置为正无穷大。接着，我们还创建$N$个函数，这些函数会接收一个整数输入并对这个值进行排列。第$i^{th}$个函数将专门负责更新向量中的第$i^{th}$个值。根据这些值，我们可以通过将集合中的每个值传递给这$N$个排列函数来计算集合的minhash签名。如果第$i^{th}$个排列函数的输出值小于向量中第$i^{th}$个值，我们就用排列函数的输出替换向量中的这个值（这就是为什么这个哈希叫做"min-hash"的原因）。下面是用Python实现的代码：

from scipy.spatial.distance import cosine
from random import randint
import numpy as np

# specify the length of each minhash vector
N = 128
max_val = (2**32)-1

# create N tuples that will serve as permutation functions
# these permutation values are used to hash all input sets
perms = [ (randint(0,max_val), randint(0,max_val)) for i in range(N)]

# initialize a sample minhash vector of length N
# each record will be represented by its own vec
vec = [float('inf') for i in range(N)]

def minhash(s, prime=4294967311):
  '''
  Given a set `s`, pass each member of the set through all permutation
  functions, and set the `ith` position of `vec` to the `ith` permutation
  function's output if that output is smaller than `vec[i]`.
  '''
  # initialize a minhash of length N with positive infinity values
  vec = [float('inf') for i in range(N)]

  for val in s:

    # ensure s is composed of integers
    if not isinstance(val, int): val = hash(val)

    # loop over each "permutation function"
    for perm_idx, perm_vals in enumerate(perms):
      a, b = perm_vals

      # pass `val` through the `ith` permutation function
      output = (a * val + b) % prime

      # conditionally update the `ith` value of vec
      if vec[perm_idx] > output:
        vec[perm_idx] = output

  # the returned vector represents the minimum hash of the set s
  return vec

就这么简单！为了演示我们如何使用这个实现，下面是一个简单的例子：

import numpy as np

# specify some input sets
data1 = set(['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',
        'estimating', 'the', 'similarity', 'between', 'datasets'])
data2 = set(['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',
        'estimating', 'the', 'similarity', 'between', 'documents'])

# get the minhash vectors for each input set
vec1 = minhash(data1)
vec2 = minhash(data2)

# divide both vectors by their max values to scale values {0:1}
vec1 = np.array(vec1) / max(vec1)
vec2 = np.array(vec2) / max(vec2)

# measure the similarity between the vectors using cosine similarity
print( ' * similarity:', 1 - cosine(vec1, vec2) )

这会返回大约0.9，作为这两个向量之间相似度的测量。

虽然我们上面只比较了两个minhash向量，但我们可以通过使用“局部敏感哈希”来更简单地进行比较。为此，我们可以建立一个字典，将每个$W$个MinHash向量组件的序列映射到一个唯一的标识符，这个标识符代表了生成该MinHash向量的集合。例如，如果W = 4，并且我们有一个集合S1，从中我们得到了一个MinHash向量[111,512,736,927,817...]，我们会将S1的标识符添加到该向量中每四个MinHash值的序列中：

d[111-512-736-927].append('S1')
d[512-736-927-817].append('S1')
...

一旦我们对所有集合都这样做了，我们就可以检查字典中的每个键，如果某个键有多个不同的集合ID，我们就有理由相信这些集合是相似的。实际上，在字典中的单个值中，集合ID的配对出现次数越多，两个集合之间的相似度就越高。通过这种方式处理数据，我们可以将识别所有相似集合的复杂度降低到大约线性时间！