CWYAlpha

Just another WordPress.com site

Thought this was cool: 也说MinHash

leave a comment »


之前突然想看看实时推荐系统有什么文章,看到Google文章中提到MinHash,然后看到xlvector的blog中还有网上也搜到其他一些blog中也有提到。它可以用来加速计算相似度,对于大规模数据,速度非常快。
他针对的是相似度定义为$w_{ij}=\frac{|N(i) \cap N(j)|}{|N(i) \cup N(j)|}$的情况,这里$N(i)$表示喜欢的物品i的用户列表,$N(j)$表示喜欢的物品j的用户列表。如果用通常的方法,计算一次这个结果,需要的计算量是|N(i)|+|N(j)|,所以对于数据规模较大,每个物品都被很多用户喜欢,计算量是比较大的。
一个简单的思想就是,如果随机的从$|N(i) \cup N(j)|$中抽取一个用户,那么这个用户属于$|N(i) \cap N(j)|$的概率应当刚好是$w_{ij}$。如果反复实验几次就能近似的知道$w_{ij}$的取值了。所以需要一个方法实现这个思路。
首先对所有用户赋予一个随机数,随机数范围如果足够大应当能保证基本上每个用户的随机数都是不同的。然后预处理,计算每个物品i的用户列表中$N(i)$,用户随机数的最小值。于是可以证明$N(i)$和$N(j)$的用户随机数的最小值相等的概率就是$w_{ij}$。所以这样反复多次实验就能估算出$w_{ij}$了。
假设随机实验次数为E,用户数量为U,物品数量为I,打分(喜欢)数量为R,则:
生成随机数步骤,时间复杂度为O(U*E)
预处理计算用户列表随机数最小值,时间复杂度为O(R*E)
这两步预处理的复杂度都是不高的,在预处理后,计算一次相似度的时间复杂度为O(E)
传统方法计算一次相似度的时间平均意义下会是O(R/I),所以当E很小,R/I很大的时候,提高会非常明显。E一般取几十就差不多了。
其实只要估计出了$w_{ij} = \frac{|N(i) \cap N(j)|}{|N(i) \cup N(j)|}$,由于$|N(i) \cup N(j)| + |N(i) \cap N(j)| = |N(i)| + |N(j)|$,所以有$$|N(i) \cap N(j)| = \frac{w_{ij} (|N(i)| + |N(j)|)}{1 + w_{ij}} $$
也就是近似求出了交集大小。
这样就也能算出其他一些相似度,比如
$$\frac{|N(i) \cap N(j)|}{\sqrt{|N(i)||N(j)|}}$$
$$\frac{|N(i) \cap N(j)|}{|N(i)|^\alpha|N(j)|^\beta}$$
等等和交集相关的相似度。可以根据实际情况选择效果最好的定义方式。
很多时候面临这两种情况:
大数据+低复杂度而不精确的算法 vs 小数据+高复杂度而精确的算法
虽然通常情况下,后者能做的研究工作更多,但实际情况下前者的结果经常会更好。这也就是MinHash的意义。

from Dora Blog: http://diaorui.net/?p=331

Written by cwyalpha

七月 8, 2012 在 10:23 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: