Mining of Massive Datasets 学习笔记(1) – shingling算法

Shingling 算法可以用来计算两个用字符串集合表示的文档之间的相似度,例如可以用于新闻查重等

Wiki 对 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 来说,假设一篇文档为字符串 abcdabd,选择 w=2,则文档中所有的 2-shingling组成的集合为{ab,bc,cd,da,bd},需要注意是,字串ab在文档中出现2次,但是集合只算1次。

对于基于词的 shingling,用 wiki 中的例子说明如何计算两个文档的相似度:

一篇文档的内容为 "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 的大小。

Shingling 有一种变形,将文档表示成包而不是集合,这样每个 shingle 的出现次数也被考虑在内

至于 w 的选择,则依赖于文档的一般长度以及所有字符串的大小,一般 w 应该选择足够大,以保证任意给定的 shingle 出现在任意文档的概率较低

另外,可以采用哈希函数将 w-shingling 映射为一个键值编号,把该编号看成是最终的 shingle,于是可以将文档表示成这些编号组成的整数集合,这样可以对数据进行压缩,同时将这些 shingle 映射为一个232-1之间的编号,则可以进行单字机器运算。

发表评论

电子邮件地址不会被公开。 必填项已用*标注