专栏首页Spark学习技巧面试|海量文本去重~minhash

面试|海量文本去重~minhash

在实际应用的过程中。相似性度量和计算是很经常使用的一个方法。比如网页去重、推断帖子是否相似、推荐系统衡量物品或者用户的相似度等等。当数据量大的时候,计算的时间和空间复杂度就会是一个很重要的问题,比如在推断相似发帖的时候。我们能够用kmeans来进行聚类。可是资源的消耗是巨大的。所以本文推荐一种方法,minhash+lsh(局部敏感hash),用minhash来降维。用lsh来做近似查询,本文主要介绍一下minhash。

在介绍minhash之前,先给出相似性的度量方法。

1. 相似性的度量

相似性度量有非常多方法,欧氏距离是比較经常使用的。这里我们用一下Jaccard相似性系数,公式例如以下

计算方法非常easy。文档A和文档B共同拥有的单词数除以A和B单词的集合。比如A={a,b,c,d},B={c,d,e,f},那么相似性系数就是2/6=0.33。

2. minhash

刚才我们知道在求相似度的时候我们用到了文档和单词。通常情况下,我们都会将文档和单词表示成doc-term矩阵的形式,能够看到term详细的是什么对最后的结果没有不论什么影响。所以我索性用行号来代表term,行号跟term是一一相应的。比如

第一行中的S1,、S2、S3表示文档,第一列的01234表示行号。也即单词。其它部分1表示文档S中有这个单词,0表示没有这个单词,有了这个集合,我们看一下minhash是怎么做的

随机确定一个顺序。比如上面的顺序是01234。随机确定一个顺序,比如12340。注意这里是随机。目的就是不让最后的结果受人为的干扰。结果例如以下

我们看到,行号是不变的,行号还是那个行号,变化的是矩阵的内容。找到排在最前面的1代表这个文档,比如S1排在最前面的1行号为2,那么就用2代表文档S1,同理,用1代表S2,那么能够计算S1和S2的相似性系数了,1交2除以1并2等于0。

后面会给出为什么用这样的方法是合理的证明。我们临时先跳过。能够想象一下,用一个单词来代表一个文档偶然性会比較大,那么这个时候我们的想法可能是,能够随机的产生多次变换,取出多个单词来进行比較。这个时候问题就来了,在实际应用的过程中,文档可能有几百万,单词也会有几万,对如此庞大的矩阵做变换时间和空间的代价都会比較大。是不是有别的方法呢,答案是肯定的,我们知道运动是相对的。之前是变换矩阵内容不变行号。我们如今不变矩阵,仅仅变换行号,是不是计算量少了许多。

所以问题转换为怎样产生随机的行号,我们能够用hash函数来产生行号的顺序,两个函数能够自定义。最好保证hash后的值均匀。比如x+1mod5,3x+1mod5。我们选用这两个hash函数来产生行号的顺序。看一下我们如今的情况

我们用h1、h2两个hash函数产生了两个行号顺序,那么接下来就是关键步骤了

比如求文档s1的值。遍历s1相应的单词

从第0行到第四行

1. 第0行为1,看一下h1计算出来的行号为1。赋值h1为1(就是行号)。继续遍历

2. 第1行为0,不关心,跳过

3. 第2行为0,不关心。跳过

4. 第3行为1, 看一下h1计算出来的行号为4。4大于此时h1的值,h1的值不变。假设小于h1此时的值,将值付给h1

5. 第4行为0。不关心,跳过

遍历完了之后此时h1的值就是1,能够看到。我们事实上在做的就是遍历矩阵中的值,对0的不关心。跳过。对1的。看一下hash函数产生的行号,找到行号最小的值作为h1输出的值。同理,h2也一样,最后得到例如以下的矩阵

这个时候就能够计算s1、s2的相似度了,J=0/3=0

3. 为什么minhash的方法是合理的

问题:两个集合的随机的一个行排列的minhash值相等的概率和两个集合的Jaccard相似度相等

证明例如以下:

两个集合。A、B。对一行来说。他们的状态有三种

X:A、B都为1,即表示A、B集合中都有这个单词

Y:A、B当中一个为1,当中一个不为1,即一个有这个单词,一个没有

Z:A、B都为0,即表示A、B中都没有这个单词。

如果有x行为X,y行为Y,z行为z。这是jaccard系数为x/(x+y)。再看minhash,由于排列是随机的,在遇到Y之前遇到X的概率是x/(x+y)。是不是正好等于jaccard系数的值。

4. 怎样进行相似查询比較

通过前面的方法。我们将文档进行了压缩,比如使用了30个hash函数。那么就将一篇文档压缩成了30位表示。接下来的问题是怎样进行查询。

一种思路是:建立倒排,term是一个单词,doclist就是拥有这个单词的其它文档。

还有一种思路是:不是建立单个单词的倒排,而是建立多个单词的联合倒排,比如

一篇文档:通过前面的方式用30位进行了表示,将这30为进行分成m个桶,每桶r个单词,即m*r=30,这个倒排建立的是:term是r个单词(或者将这r个单词求hashcode),doclist就是拥有这r个单词的文档。

那么这里的问题就是。m、r怎样求解,m等于几好。r等于几好。

假设两个文档相似度为p,那么相应位数相似的概率也是p,那么一个桶里全然同样的概率是p^r,不同样的概率是1-p^r,那么m个桶都不同样的概率是(1-p^r)^m。所以至少有一个桶同样的概率是1-(1-p^r)^m,我们能够依据我们想要的概率p去分配m和r。

最后建立倒排是这种。

桶1——>doc1,doc2,doc3,doc4

桶2——>doc2,doc5,doc9,doc10

索引建立完毕了之后,下一步就是检索,一篇新的文档。也要经过全面的步骤,得到对应的桶。比如桶1,桶3,那么接下来就是用桶1查询,得到跟这篇文档相似的文档。为了保证确实相似。还能够对候选文档计算一下跟本片文档的相似度

本文分享自微信公众号 - Spark学习技巧(bigdatatip)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 读懂Word2Vec之Skip-Gram

    本教程将介绍Word2Vec的skip gram神经网络体系结构。我这篇文章的目的是跳过对Word2Vec的一般的介绍和抽象见解,并深入了解其细节。具体来说,我...

    Spark学习技巧
  • HBase在滴滴出行的应用场景和最佳实践

    本文主要介绍HBase在滴滴内部的一些典型使用场景,如何设计整个业务数据流,让平台开发者与用户建立清晰、明确、良好的合作关系 背景 对接业务类型 HBase是建...

    Spark学习技巧
  • flink sql使用中的一个问题

    最近有人问了浪尖一个flink共享datastream或者临时表会否重复计算的问题。

    Spark学习技巧
  • 算法教程:能够体现文本语义关系的关键词提取算法

    关键词提取能让我们快速地了解一篇文章。在信息爆炸的时代,能够有效提取文本的关键词,对于快速、及时、高效地获取信息是非常有帮助的。本文介绍一种能够体现文本语义关系...

    人工智能的秘密
  • JS 刷新页面

    如果该方法没有规定参数,或者参数是 false,它就会用 HTTP 头 If-Modified-Since 来检测服务器上的文档是否已改变。如果文档已改变,re...

    week
  • 足迹地图刷屏朋友圈,国人的隐私看起来如此廉价

    “如果你告诉我你的一个秘密,我就给你一颗糖”,面对这样的交易,你竟然欣然同意,或者你根本没意识到这是一场交易。西瓜足迹一夜之间刷便朋友圈,差不多也是类似的道理。

    FB客服
  • [From Nand to Tetris] 第8章 虚拟机项目 python 实现

    为防闲逛至此的看官不知所云: From Nand to Tetris 是一个在线课程,目标是指导学生从 Nand 逻辑门开始从头到尾完成一整套计算机系统。

    Alan Zhang
  • 倒排索引(一)

    毕业以后在网页搜索组,所以抽空就看看了《这就是搜索引擎--核心技术详解》,书比较白话文,对于我这样的入门小白再合适不过了,还有一本《信息检索导论》比较系统和专业...

    张凝可
  • 人工智能也能玩音乐?这个小程序要做你手上的「初音未来」| 晓组织 #27

    大家好,我们是成都涂鸦科技团队,一个扎根人工智能音乐行业的初创公司,由一群有梦想、爱音乐、懂人工智能的年轻人组成。

    知晓君
  • 后端技术杂谈1:搜索引擎基础倒排索引

    本文转载自 https://www.cnblogs.com/zlslch/p/6440114.html

    Java技术江湖

扫码关注云+社区

领取腾讯云代金券