Min-Hash和推荐系统

标签: 未分类 | 发表时间:2012-06-22 04:56 | 作者:xlvector
出处:http://xlvector.net/blog

前几年看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大多由热门词组成。

您可能也喜欢:
各个领域著名的推荐系统
Twitter的用户推荐系统
一个现实中的推荐系统
《推荐系统实践》总结
推荐系统时效性的一条有趣的曲线
无觅

相关 [min hash 推荐系统] 推荐:

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

min(x,y)高效算法

- Rooney - C++博客-首页原创精华区
     今天偶然看到一个讲求较小值的帖子,让我突然想起一年前一次折腾逆向工程的尝试,当时用IDA进行反汇编,看到一串汇编代码,非常精妙,最终发现仅仅是为了计算两个整数的较小值. 可现在非常努力的回忆,就是想不起来是怎么做的.      真的非常想再现那串算法,于是自己开始推敲.      命题:给定整数x,y,计算较小值m.

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类:  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法( consistent hashing ).

Hash Collision DoS 问题

- mazhechao - 酷壳 - CoolShell.cn
最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 Hash Collision DoS (Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比. 这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松的让你的CPU升到100%).

局部敏感Hash

- - xiaobaoqiu Blog
之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东. LSH可以理解为一种衡量文本相似度的算法,特点是散列前的相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证. 其有坚实的理论依据(98年左右理论就提出来了,99年有第一版实现)并且在高维数据空间中表现优异.

Hash算法的使用

- khsing - Glider's home
在对语料文本进行2,3元切分时,需要借助hash表来获得切分内容在内存中的位置,以便能够记录语料库中出现的次数. 以前知道有很多hash算法,但没认真研究过,今天才知道hash算法差距还是很明显的. 首先我选择的是暴雪在魔兽里的hash算法,这个算法很高级,是time33类型的一个变种(有关time33的介绍,可以参考:http://www.cnblogs.com/napoleon_liu/articles/1911571.html),而且很巧妙的借助3次hash避免字符串比较这种费时的操作,并且不用链表来存储冲突,3次hash冲突值能相等的可能行只有1/10的23次方,应该说不可能冲突了.

一致性HASH算法

- - 企业架构 - ITeye博客
一致性 hash 算法( consistent hashing ). consistent hashing 算法早在 1997 年就在论文 . Consistent hashing and random trees 中被提出,目前在cache 系统中应用越来越广泛;. 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;.

推荐系统实战

- - 博客园_首页
推荐算法:基于特征的推荐算法. 推荐算法准确度度量公式:. 其中,R(u)表示对用户推荐的N个物品,T(u)表示用户u在测试集上喜欢的物品集合. 集合相似度度量公式(N维向量的距离度量公式):. 其中,N(u)表示用户u有过正反馈的物品集合. 其中,S(u,k)表示和用户u兴趣最接近的K个用户集合;N(i)表示对物品i有过正反馈的用户集合;w(u,v)表示用户u和用户v的兴趣相似度;r(v,i)表示用户v对物品i的兴趣.

推荐系统杂谈

- - 后端技术杂谈 | 飒然Hang
推荐系统是近些年非常火的技术,不管是电商类软件还是新闻类app,都号称有精准的推荐系统能给你推送你最感兴趣的内容. 现象级的资讯类app“今日头条”就得益于此成为了势头非常猛的一款产品. 本文就针对推荐系统讲述一些相关概念和实践经验. 首先需要明确的就是推荐系统的目标,一般来说不外乎以下几个:. 用户满意性:首当其冲的,推荐系统主要就是为了满足用户的需求,因此准确率是评判一个推荐系统好坏的最关键指标.

[翻译]最简单的无锁hash table

- - 博客园_首页
原文链接: http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table. 无锁hash table可以提高多线程下的性能表现,但是因为实现一个无锁hash table本身的复杂度不小(ps:真正的复杂在于出错之后的调试,因为多线程下的调试本身就很复杂,引入无锁数据结构之后,传统的看堆栈信息和打印log都基本上没有意义了(堆栈中的数据可能被并发访问破坏,而打印log本身可能会改变程序执行时对数据访问的时序).