shingling算法——提取特征,m个hash函数做指纹计算,针对特征hash后变成m维向量,最后利用union-find算法计算相似性

  1. 云栖社区>
  2. 博客>
  3. 正文

shingling算法——提取特征,m个hash函数做指纹计算,针对特征hash后变成m维向量,最后利用union-find算法计算相似性

桃子红了呐 2017-11-16 19:15:00 浏览885
展开阅读全文

shingling算法用于计算两个文档的相似度,例如,用于网页去重。维基百科对w-shingling的定义如下:

In natural language processing a w-shingling is a set of unique "shingles"—contiguous subsequences of tokens in a document —that can be used to gauge the similarity of two documents. The w denotes the number of tokens in each shingle in the set.

维基百科用一个浅显的例子讲解了shingling算法的原理。比如,一个文档

   "a rose is a rose is a rose"

分词后的词汇(token,语汇单元)集合是

   (a,rose,is,a,rose,is, a, rose)

那么w=4的4-shingling就是集合:

   { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) }

去掉重复的子集合:

   { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }

给定shingle的大小,两个文档A和B的相似度 r 定义为:

   r(A,B)=|S(A)∩S(B)| / |S(A)∪S(B)|

其中|A|表示集合A的大小。

因此,相似度是介于0和1之间的一个数值,且r(A,A)=1,即一个文档和它自身 100%相似。 

 

shingling算法是最常见的文档分割算法,说白了就是将一个文档分解成由短字符构成的字符串集合。分割后的文档就可以通过Jaccard相似度等简单的度量标准进行相似度检测了。

 

Shingling算法二大步骤:

1、从文档中抽取能代表文档内容的特征

2、通过二个文档对应特征集合的重叠程度来判断是否近似重复。

Shingling算法将文档转换成特征集合示意图

Shingling算法实例:

假想有一个固定大小的移动窗口从第一个单字开始依次移动,每次向后移动一个单字,直到文档结尾。

在同时对汉字串做哈希计算,随着窗口的移动,会出现一系列的shingles值,这样就构成了文档对应的特征集合。

后面再进行jaccard相似性计算,计算二个集合相似部分所占总元素个数的比例。

算法缺点:

计算效率不高,当网页数量比较大时,运行时间会比较长,并不实用。

算法改进:

Shingling算法改进示意图

前面的计算过程和原始的Shingling算法是一致的,构成一个文档转换成shingles的特征集合,但是为了将特征集合映射成固定大小,会引 入m个不同的哈希函数,形成哈希函数簇,对于某个特定的哈希函数F,对于每个shingles都会计算出一个哈希数值,取其中最小的值作为代表,这样m个 哈希函数就会获得m个哈希数值,文档特征也就转换为固定大小m,最后再进行相似度的计算,得出相似重复页面。

 

转自:http://www.wuhenseo.com/course/cjcourse/424.html

 

然后利用union-find算法进行相似度计算Jaccard相似性。







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



网友评论

登录后评论
0/500
评论
桃子红了呐
+ 关注