使用MinHash算法计算两个集合的相似度

集合相似度计算是一个常见的问题。例如,已知看过芈月传的人都有哪些,还知道看过琅琊榜的人都有哪些,那么想知道同时看过两者的人群占至少看过一部的人群的占比,就是求这两个集合的相似度:

集合A = 看过芈月传的人群
集合B = 看过琅琊榜的人群
相似度 = |A∩B| / |A∪B| = 既看过芈月传又看过琅琊榜的人数 / 看过芈月传或琅琊榜的人数

当集合的元素较少时,我们可以采用逐一比较的方式来找出既在集合A出现也在集合B出现的人,统计其人数,再除以至少在集合A或集合B出现的人数,得到相似度。

然而当集合的元素较多时,比如每个集合都有上百万或上千万个元素,采用复杂度为O(n)的逐一比较方式就比较捉急了,无法胜任要求即时得到计算结果的场景。

而使用MinHash算法,可以将复杂度降为常数。

让我通过一个例子解释MinHash算法。假设你是野生动物园的管理员,负责管理一座猴山,猴山没有栅栏,所以虽然猴子大多习惯呆在一座山上,但它们也可以跑到你的管辖范围外,外面的猴子也可以到你的山头拜访。

如果你突然想知道这个月月初的猴群和月末的猴群有多少重叠,即常住“猴口”的占比是多少,就是在面对一个相似度问题。按照上文提供的逐一比较的思路,你可以在月初抓到所有的猴子,统计数量为C1,并给它们戴上号码牌后释放。到了月末,你再次上山统计所有的猴子,有号牌的猴子的数量为C2a,没号牌的猴子的数量为C2b,则你的答案就是C2a / (C1 + C2b),大功告成。

然而这种方法太劳猴伤财了,你决定换一个简单但粗略的方法。你上山观察,找到最小的猴子,抓来给它戴上号码牌后释放,并记录下它的号码,然后再找到最大的猴子,做同样的事,再找到最瘦的猴子,做同样的事,然后是最胖的猴子,尾巴最长的猴子,尾巴最短的猴子,屁股最红的猴子,以及各种最XX的猴子,得到记录如下:

特征 | 号码
最小 | 1
最大 | 2
最瘦 | 3
...
最精 | 19
最傻 | 20

到了月末,你带着记录本再次上山,找到最小的猴子,如果它有号牌且号码是1,就意味着这只猴子就是月初那一只,你就在本子上画一个圈,如果它不是月初那只,就画一个叉。然后再找到最大的猴子,做同样的事,然后再继续,直到找完所有最XX的猴子。你低头看记录本,有15个圈,5个叉,那么相似度就是15 / (15 + 5) = 75%。

为什么?

简单来说,你每次带着目的去寻找某种视角下最XX的猴子时,实际都是在为猴群建立一个索引。而当排在两个集合的索引第一位的元素相同时,就意味着这两个集合有了一定的相似度,因为它们不仅同时包含这个元素,而且它们的所有元素在某种视角下都大于等于该元素。由于每次索引的视角都不同,所以当我们比较了20次不同的索引的第一位,其中有15次都遇到了相同的元素,就可以说这两个集合相当、相当的相似了。

让我们换成数学语言。已知集合X,设每次用来索引的函数为H(X),索引中第一个元素为Hmin(X),则对任意H(X),满足Himin(A) = Himin(B)的充要条件就是A和B中都存在一个相同的元素,所以有如下公式:

Pr[Hmin(A) = Hmin(B)] = |A∩B| / |A∪B|
注:Pr表示概率。

公式左侧的概率,我们可以通过选取有限个数的H(X)来趋近理论值,即:

满足Hmin(A) = Hmin(B)的H(X)的个数 / H(X)的个数 ≈ Pr[Hmin(A) = Hmin(B)] = |A∩B| / |A∪B|

以上就是MinHash算法的讲解。在实际应用中,当一个集合A的元素确定后,就可以调用一系列预先定义好的H(X)进行计算,得到一个数组[ H1min(A), H2min(A) ... Himin(A) ... Hnmin(A) ],将该数组作为中间数据进行存储,在每次需要即时计算任意两个集合A和B的相似度时读取每个集合对应的数组,通过定义如下随机变量r:

r = 1 if Hmin(A) = Hmin(B) else 0

得到相似度为:

∑r / n

在我这边的应用里,n = 2048。所以不管每个集合里有几百几千万个元素,都会被预先降维成包含2048个元素的数组(一律2048,通通2048,算起来不吃亏,算起来不上当^_^),后续的相似度计算的复杂度自然也成了一个常数。

参考:
https://en.wikipedia.org/wiki/MinHash

仅有 1 条评论
  1. Austot

    Cialis Efectos Viagra Levoxyl Pharm Side Effects Of Misoprostol levitra on sale Cialis Professional Review Cialis Professional

    Austot 回复
发表新评论