文本去重之MinHash算法——就是多个hash函数对items计算特征值,然后取最小的计算相似度-阿里云开发者社区

开发者社区> 桃子红了呐> 正文

文本去重之MinHash算法——就是多个hash函数对items计算特征值,然后取最小的计算相似度

简介:
+关注继续查看

来源:http://my.oschina.net/pathenon/blog/65210

 

1.概述


    跟SimHash一样,MinHash也是LSH的一种,可以用来快速估算两个集合的相似度。MinHash由Andrei Broder提出,最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。
 
2.Jaccard index
 
    在介绍MinHash之前,我们先介绍下Jaccard index。
 
    也就是说,集合A,B的Jaccard系数等于A,B中共同拥有的元素数与A,B总共拥有的元素数的比例。很显然,Jaccard系数值区间为[0,1]。
 
3.MinHash
 
    先定义几个符号术语:
    h(x):  把x映射成一个整数的哈希函数。   
    hmin(S):集合S中的元素经过h(x)哈希后,具有最小哈希值的元素。

    那么对集合A、B,hmin(A) = hmin(B)成立的条件是A ∪ B 中具有最小哈希值的元素也在 ∩ B中。这里

有一个假设,h(x)是一个良好的哈希函数,它具有很好的均匀性,能够把不同元素映射成不同的整数。

    所以有,Pr[hmin(A) = hmin(B)] = J(A,B),即集合A和B的相似度为集合A、B经过hash后最小哈希值相

等的概率。

        有了上面的结论,我们便可以根据MinHash来计算两个集合的相似度了。一般有两种方法:
        
        第一种:使用多个hash函数
 
        为了计算集合A、B具有最小哈希值的概率,我们可以选择一定数量的hash函数,比如K个。然后用这K个hash函数分别对集合A、B求哈希值,对
每个集合都得到K个最小值。比如Min(A)k={a1,a2,...,ak},Min(B)k={b1,b2,...,bk}。
        那么,集合A、B的相似度为|Min(A)k ∩ Min(B)k| / |Min(A)k  ∪  Min(B)k|,及Min(A)k和Min(B)k中相同元素个数与总的元素个数的比例。
 
       第二种:使用单个hash函数
 
       第一种方法有一个很明显的缺陷,那就是计算复杂度高。使用单个hash函数是怎么解决这个问题的呢?请看:
       前面我们定义过 hmin(S)为集合S中具有最小哈希值的一个元素,那么我们也可以定义hmink(S)为集合S中具有最小哈希值的K个元素。这样一来,
我们就只需要对每个集合求一次哈希,然后取最小的K个元素。计算两个集合A、B的相似度,就是集合A中最小的K个元素与集合B中最小的K个元素
的交集个数与并集个数的比例。
        
      看完上面的,你应该大概清楚MinHash是怎么回事了。但是,MinHash的好处到底在哪里呢?计算两篇文档的相似度,就直接统计相同的词数和总的
次数,然后就Jaccard index不就可以了吗?对,如果仅仅对两篇文档计算相似度而言,MinHash没有什么优势,反而把问题复杂化了。但是如果有海量的文档需要求相似度,比如在推荐系统
中计算物品的相似度,如果两两计算相似度,计算量过于庞大。下面我们看看MinHash是怎么解决问题的。
 
      比如 元素集合{a,b,c,d,e},其中s1={a,d},s2={c},s3={b,d,e},s4={a,c,d}   那么这四个集合的矩阵表示为:  

      

    如果要对某一个集合做MinHash,则可以从上面矩阵的任意一个行排列中选取一个,然后MinHash值是排列中第一个1的行号。
    例如,对上述矩阵,我们选取排列 beadc,那么对应的矩阵为
    那么, h(S1) = a,同样可以得到h(S2) = c, h(S3) = b, h(S4) = a。
        如果只对其中一个行排列做MinHash,不用说,计算相似度当然是不可靠的。因此,我们要选择多个行排列来计算MinHash,最后根据Jaccard index公式 来计算相似度。但是求排列本身的复杂度比较高,特别是针对很大的矩阵来说。因此,我们可以设计一个随机哈希函数去模拟排列,能够把行号0~n随机映射到0~n上。比如H(0)=100,H(1)=3...。当然,冲突是不可避免的,冲突后可以二次散列。并且如果选取的随机哈希函数够均匀,并且当n较大时,冲突发生的概率还是比较低的。
 
    说到这里,只是讨论了用MinHash对海量文档求相似度的具体过程,但是它到底是怎么减少复杂度的呢?
    比如有n个文档,每个文档的维度为m,我们可以选取其中k个排列求MinHash,由于每个对每个排列而言,MinHash把一篇文档映射成一个整数,所以对k个排列计算MinHash就得到k个整数。那么所求的MinHash矩阵为n*k维,而原矩阵为n*m维。n>>m时,计算量就降了下来。
    
 
4.参考文献















本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6423334.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10099 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
11819 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13897 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11894 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4511 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7366 0
4269
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载