CWYAlpha

Just another WordPress.com site

Thought this was cool: Min-Hash和推荐系统

leave a comment »


前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼。不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处。

其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数。比如Google用来进行去重的SimHash算法。不过在深入了解了LSH之后,我发现这个算法对于降低时空复杂度,处理大数据集有很大的优势。

在推荐系统里经常要算相似度。比如假设购买过物品A的用户集合是 N(A),购买过物品B的用户集合是N(B),那么A和B的相似度就定义为他们的Jaccard Index。但是,直接对两两物品算Jaccard Index复杂度是很高的。于是我在《推荐系统实践》中提出了一种方法,就是扫描所有的用户,然后将用户看过的物品两两加1,这样我们就可以算出任意两个物品的共现次数。而Jaccard Index最大的计算量就来自于算共现次数。这个算法可以避免计算大量的相似度为0的物品对,所以时间复杂度大大降低了。不过这个算法有个缺点,就是有比较高的空间复杂度。因为她要将所有相似度不为0的物品对都存在内存里,这在物品数很多的时候往往会带来内存的问题。

那么现在的问题就是,还有没有更好的方法来计算Jaccard Index?答案是有,如果我们不需要特别准确的Jaccard Index,那么Min-Hash就是一种方法。

Min-Hash的基本思想是,它将一个集合Hash成1个数,而这两个集合Hash出来的数相等的概率是这两个集合的Jaccard Index。那么,我们如果Hash多次,看有多少次两个集合的Hash数相同,就可以估计出集合的Jaccard Index。

因此,问题的重点就是怎么Hash出这个数了。方法很简单,假设X是所有集合中所能出现的所有元素的集合。我们可以给每个元素赋予一个随机数作为权重,然后对于一个集合,找出他所有的元素中权重最低的那个元素,就是这个集合的Hash值。

这个算法看上去很简单,但却可以发扬光大。

比如在推荐系统中,我们可以根据MinHash生成一个用户的一串Hash数,其实每个hash代表了一种很小的topic。这里的topic和LDA的topic不太一样,他的粒度很细。比如我在Delicious的数据集上用MinHash的方法就计算出了下面这些topic

英国的地方 teignmouth bideford newton-abbot cullompton paignton budleigh-salterton
人体器官 pancreas mouth orchitis gonorrhoea homeopathic croup dysentery
装修房子 screed spraying plastering utiform shotcrete

上面这些topic里的词都是词频不大的词,这些词在LDA中基本上看不到,因为LDA的topic大多由热门词组成。

您可能也喜欢:

Aardvark 专家推荐式的问答系统

从推荐的角度看搜索和社会网络

各个领域著名的推荐系统

推荐系统和协同过滤面临的主要问题

《推荐系统实践》总结

无觅

from xlvector – Recommender System: http://xlvector.net/blog/?p=848

Written by cwyalpha

六月 22, 2012 在 8:08 上午

发表在 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 博主赞过: