如果您有兴趣研究 minhash 算法,这里有一个非常简单的实现和一些讨论。
为了生成集合的 MinHash 签名,我们创建一个长度向量$N$
其中所有值都设置为正无穷大。我们还创造$N$
接受输入整数并排列该值的函数。这$i^{th}$
功能将全权负责更新$i^{th}$
向量中的值。给定这些值,我们可以通过将集合中的每个值传递给每个集合来计算集合的 minhash 签名$N$
排列函数。如果输出的$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) )
这将返回 ~.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 在字典中的单个值中出现的次数越多,两个集合之间的相似性就越大。以这种方式处理我们的数据,我们可以将识别所有成对的相似集合的复杂性降低到大致线性时间!