美文网首页
文本去重之MinHash算法

文本去重之MinHash算法

作者: 5f32fea06d2d | 来源:发表于2016-11-08 15:00 被阅读1262次

1.概述

跟SimHash一样,MinHash也是LSH的一种,可以用来快速估算两个集合的相似度。MinHash由Andrei Broder提出,最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。

2.Jaccard index

在介绍MinHash之前,我们先介绍下Jaccard index。

Jaccard index是用来计算相似性,也就是距离的一种度量标准。假如有集合A、B,那么,

也就是说,集合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来计算两个集合的相似度了。一般有两种方:

如果要对某一个集合做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时,计算量就降了下来。

相关文章

  • 文本去重之MinHash算法

    1.概述 跟SimHash一样,MinHash也是LSH的一种,可以用来快速估算两个集合的相似度。MinHash由...

  • 第四章 相似度分析算法——基于MinHash的相似性算法

    4.3 基于MinHash的相似性算法 MinHash也称为最小哈希式独立排列局部性敏感哈希,是一种非常快速的对两...

  • Minhash原理

    minhash是一种基于jaccard index 相似度的算法。属于LSH(Location Sensitive...

  • 文本去重

    simhash 分词,hash,加权,降维,拿到simhash;计算simhash的海明距离试用长文本去重,效率高...

  • js数组去重算法总结

    一、去重 我在前端面试过程中遇到去重算法的概率为百分之九十,这里就总结下各种去重算法及其复杂度 1. new Se...

  • 2018-12-19

    文本聚类算法之K-means算法的python实现 一、文本聚类定义 文本聚类主要是依据著名的聚类假设:同类...

  • awk文本去重

    http://www.letuknowit.com/topics/20120401/use-awk-remove-...

  • 前端笔试之去重算法

    在前端的笔试当中,算法是不必可少的一部分。它考验的是你的逻辑思维,你的编程基础。所以在这一章中,本人也就拿一个经典...

  • simhash算法原理及实现

    simhash是google用来处理海量文本去重的算法。 google出品,你懂的。 simhash最牛逼的一点就...

  • 海量文本去重simhash算法(python&scala)

    1.python(Numpy实现) 具体公式见reference中的论文。 短文本,如果文本很短,可以直接调用si...

网友评论

      本文标题:文本去重之MinHash算法

      本文链接:https://www.haomeiwen.com/subject/qeiauttx.html