注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

王小二的博客

勤俭以修身,淡泊以明志

 
 
 

日志

 
 

基于MinHash的集合相似度计算原理  

2012-07-09 19:55:21|  分类: 专业相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
from: http://www.sunmingming.name/2011/12/基于minhash的集合相似度计算原理/

首先,MinHash 是用于快速检测两个集合的相似性的方法。该方法由 Andrei Broder (1997) 发明,并最初用于AltaVista搜索引擎中来检测重复的网页。它同样可以用于大规模文档聚类中。

MinHash基于Jaccard相似性度量。对于两个集合A与B,Jaccard相似性系数可以定义为:

 J(A,B) = {{|A \cap B|}\over{|A \cup B|}}.

容易知道,该系数是0-1之间的值。当两个集合越接近,那么该值越接近1;反之,更接近0。

假设h是一个哈希函数,将A与B的元素个数映射为一个整数。定义: hmin(S) 是集合S集合中具有最小哈希值的元素。那么,一个重要的结论是:仅当 ∪ 中具有最小哈希值的元素位于A ∩ B中时,hmin(A) = hmin(B) 。而将哈希函数看成一个随机变量,那么任何 ∪ 中的元素都有可能具有最小哈希值。因此,就有:

Pr[hmin(A) = hmin(B)] = J(A,B).

若令r 为一个随机变量(或者随机变量h的函数),当hmin(A) = hmin(B) 时取1,否则取0。那么r 就是J(A,B)的一个无偏估计。

于是,自然而然地,计算两个集合的相似度J(A,B),我们便可以取n个哈希函数(n = 80或400等),计算对每个哈希函数,r 的取值。然后求平均即可。


  评论这张
 
阅读(1882)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017