MinHash和推荐系统
Min-Hash和推荐系统
标签：
未分类
| 发表时间：2012-06-22 12: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大多由热门词组成。