海量数据相似度计算之simhash和海明距离

标签: 数据 相似 计算 | 发表时间:2013-08-25 17:19 | 作者:lance_yan
出处:http://blog.csdn.net

通过  采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
             String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
             String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

            long t1 =  System.currentTimeMillis();

            for (int i = 0; i < 1000000; i++) {
                   int dis = StringUtils .getLevenshteinDistance(s1, s2);
            }

            long t2 =  System.currentTimeMillis();

             System. out .println(" 耗费时间: " + (t2 - t1) + "  ms ");

耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考  《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:

  • 1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

  • 2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

  • 3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

  • 4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

  • 5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。

整个过程图为:
simhash计算过程图

大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101 111111100000101011010001001111100001 00101 1001011

1000010010101101 011111100000101011010001001111100001 10101 0001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明, “量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下:  101 01 和  001 10 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?

simhash_hammingdistance

参考:
Detecting near-duplicates for web crawling.

Similarity estimation techniques from rounding algorithms.

http://en.wikipedia.org/wiki/Locality_sensitive_hashing

http://en.wikipedia.org/wiki/Hamming_distance

simHash 简介以及 java 实现

simhash原理推导

原创文章,转载请注明: 转载自 LANCEYAN.COM

本文链接地址:  海量数据相似度计算之simhash和海明距离

作者:lance_yan 发表于2013-8-25 17:19:36 原文链接
阅读:86 评论:0 查看评论

相关 [数据 相似 计算] 推荐:

海量数据相似度计算之simhash短文本查找

- - ITeye博客
在前一篇文章 《 海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力. 但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了. 我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s.

海量数据相似度计算之simhash和海明距离

- - CSDN博客架构设计推荐文章
通过  采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析. 分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法. 常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等. 这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重.

URL相似度计算的思考

- - IT技术博客大学习
在做一些web相关的工作的时候,我们往往可能需要做一些对url的处理,其中包括对相似的url的识别和处理. 这就需要计算两个url的相似度. 那么怎么进行url相似度的计算的. 我首先想到的是把一个url看作是一个字符串,这样就简化成两个字符串相似度的计算. 字符串相似度计算有很多已经比较成熟的算法,比如“ 编辑距离算法”,该算法描述了两个字符串之间转换需要的最小的编辑次数;还有一些其他的比如“ 最长公共字串”等方法.

相似度计算常用方法综述

- - 搜索研发部官方博客
       相似度计算用于衡量对象之间的相似程度,在数据挖掘、自然语言处理中是一个基础性计算. 其中的关键技术主要是两个部分,对象的特征表示,特征集合之间的相似关系. 在信息检索、网页判重、推荐系统等,都涉及到对象之间或者对象和对象集合的相似性的计算. 而针对不同的应用场景,受限于数据规模、时空开销等的限制,相似度计算方法的选择又会有所区别和不同.

如何计算两个文档的相似度(一)

- - 我爱自然语言处理
前几天,我发布了一个和在线教育相关的网站: 课程图谱,这个网站的目的通过对公开课的导航、推荐和点评等功能方便大家找到感兴趣的公开课,特别是目前最火的Coursera,Udacity等公开课平台上的课程. 在发布之前,遇到的一个问题是如何找到两个相关的公开课,最早的计划是通过用户对课程的关注和用户对用户的关注来做推荐,譬如“你关注的朋友也关注这些课程”,但是问题是网站发布之前,我还没有积累用户关注的数据.

如何计算两个文档的相似度(三)

- - 我爱自然语言处理
上一节我们用了一个简单的例子过了一遍 gensim的用法,这一节我们将用 课程图谱的实际数据来做一些验证和改进,同时会用到 NLTK来对课程的英文数据做预处理. 为了方便大家一起来做验证,这里准备了一份Coursera的课程数据,可以在这里下载: coursera_corpus,总共379个课程,每行包括3部分内容:课程名\t课程简介\t课程详情, 已经清除了其中的html tag, 下面所示的例子仅仅是其中的课程名:.

如何计算两个文档的相似度(二)

- - 我爱自然语言处理
上一节我们介绍了一些背景知识以及 gensim , 相信很多同学已经尝试过了. 这一节将从gensim最基本的安装讲起,然后举一个非常简单的例子用以说明如何使用gensim,下一节再介绍其在 课程图谱上的应用. 二、gensim的安装和使用. gensim依赖 NumPy和 SciPy这两大Python科学计算工具包,一种简单的安装方法是pip install,但是国内因为网络的缘故常常失败.

文本相似度计算-google的simHash汉明距离

- - 行业应用 - ITeye博客
       针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Model). 使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角、欧式距离、Jaccard相似系数等. 这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理.

相似度计算常用方法综述

- - 互联网实践
相似度计算用于衡量对象之间的相似程度,在数据挖掘、自然语言处理中是一个基础性计算. 其中的关键技术主要是两个部分,对象的特征表示,特征集合之间的相似关系. 在信息检索、网页判重、推荐系统等,都涉及到对象之间或者对象和对象集合的相似性的计算. 而针对不同的应用场景,受限于数据规模、时空开销等的限制,相似度计算方法的选择又会有所区别和不同.

IKAnalyzer中文分词,计算句子相似度

- - 两只蜗牛 - 关注生活,关注旅游
IKAnalyzer中文分词,计算句子相似度.     IKAnalyzer是一个开源的,基于java语言开发的轻量级的中文分词工具包. 以开源项目Luence为应用主体的,结合词典分词和文法分析算法的中文分词组件. 独立于Lucene项目,同时提供了对Lucene的默认优化实现. (简介来源: 百度百科).