推荐系统map（MinHash和推荐系统）
Min-Hash和推荐系统
出处：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的用户推荐系统
一个现实中的推荐系统
《推荐系统实践》总结
推荐系统时效性的一条有趣的曲线
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！