使用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

已有 5 条评论
  1. RandPsymn

    Purchase Discount Finasteride Free Trial Medicationsviagra Fast Cialis Generico Andorra 60 mgs dapoxtine with levitra Cialis Efectos Secundarios Fotos

    RandPsymn 回复
  2. Kelemetry

    Cialis Generika 20mg Bestellen achat pillule viagra en montreuil Il Cialis Generico E Sicuro?

    Kelemetry 回复
  3. Austot

    Lioresal Et Alcool zoloft without a prescription Acticin Discount Without Perscription Overseas Comprar Cialis Generico En Murcia

    Austot 回复
  4. RandPsymn

    Zithromax Mastercard viagra online prescription Viagra En Pharmacie

    RandPsymn 回复
  5. Kelemetry

    Buy Propecia Cheap Comprar Cialis En Canada online cialis Quanto Costa Il Cialis In Slovenia Buy Colchicine 0.5 Mg Europe Buy Tamoxifen In Uk

    Kelemetry 回复
发表新评论