MinHash原理与应用



MinHash首先它是一种基于 Jaccard Index 相似度的算法,也是一种LSH的降维的方法,应用于大数据集的相似度检索、推荐系统。下边按我的理解介绍下MinHash。

举例A,B 两个集合:

A = {s1, s3, s6, s8, s9}

B = {s3, s4, s7, s8, s10}

根据Jaccard Index公式,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其实是一种降维技术

在Mahout中用MinHash作聚类,则是将每个minhash相同的向量聚集为一个簇,哈希函数个数为10的情况下,有一个hash相同就表示至少有20%的相似度了。

你可能注意到,这个相似度其实没有说元素的权重,另一个问题是哈希函数个数,理论上次数越多,会越准确,但是计算复杂度也越高,实际应用需要找一个平衡点。

我在一个推荐人的场景——将几十万优质用户按相似度推荐给几千万的普通用户,就是先用MinHash筛选一次,为每个普通用户推荐一个按MinHash相同个数作排序的、至少跟用户交集的优质用户备选集,再计算用户跟备选集的余弦相似度,找出最相似的TOPN作为推荐。这种方法虽然不是最优解(计算量仍然很大),但是在一个可接受的时间范围内,效果跟两两计算余弦相似取TOPN相比比较接近(通过取样测试,取用户权重最重的TOPN个属性作MinHash计算,这样的结果往在做TOPN的推荐容易接近于基于COS的最优解)。另外因为涉及到两个量级差异比较大的集合的推荐,简单用聚类推荐效果很难达到使用MinHash的方法。

企业级互联网架构Aliware,让您的业务能力云化:https://www.aliyun.com/aliware