冗余文档发现
具体步骤
第一步：Shingling
目的：将文档转化为集合
一个文档的一个k-Shingle是出现在该文当中的k个tokens构成的序列
为了对长的shingles压缩，可以对它们进行哈希，哈希成一个整数（4字节）
用一个文档的所有k-shingles的哈希值构成集合来表示该文档
Shingles的压缩
例子：k=2；文档D=abcab
2-shingles的集合：S(D)={ab,bc,ca}
对shingles做哈希：h(D)={1,5,7}
在实际中k常常是8,9或10
shingle的好处：
相似为文档往往有很多共同的shingles
改变一个单词往往只会影响和这个单词距离不超过k-1的k-shingles
文档 D 1 D_1 D1的k-shingles集合是 C 1 = S （ D 1 ） C_1=S（D_1） C1=S（D1）
Jaccard相似度：
s
i
m
(
D
1
,
D
2
)
=
∣
C
1
∩
C
2
∣
/
∣
C
1
∪
C
2
∣
sim(D_1,D_2)=|C_1∩C_2|/|C_1∪C_2|
sim(D1,D2)=∣C1∩C2∣/∣C1∪C2∣
Jaccard距离：
d ( D 1 , D 2 ) = 1 − ∣ C 1 ∩ C 2 ∣ / ∣ C 1 ∪ C 2 ∣ d(D_1,D_2)=1-|C_1∩C_2|/|C_1∪C_2| d(D1,D2)=1−∣C1∩C2∣/∣C1∪C2∣
第二步：最小哈希（针对Jaccard相似度）
最小哈希：将大集合转化为小的签名同时保留其相似度。
签名：表示集合的较短的整数向量，能表示集合间的相似度。
思想是：将每一列C“哈希”成一个小的签名h©，使得sim(C1,C2)等于签名的h(C1)和h(C2)的“相似度”。
目标是：找到一个哈希函数h(·)，使得：
如
果
s
i
m
(
C
1
,
C
2
)
大
，
则
h
(
C
1
)
＝
h
(
C
2
)
的
概
率
大
如果sim(C1,C2)大，则h(C1)＝h(C2)的概率大
如果sim(C1,C2)大，则h(C1)＝h(C2)的概率大
如
果
s
i
m
(
C
1
,
C
2
)
小
，
则
h
(
C
1
)
≠
h
(
C
2
)
的
概
率
大
如果sim(C1,C2)小，则h(C1) ≠ h(C2)的概率大
如果sim(C1,C2)小，则h(C1)=h(C2)的概率大
想法：将文档哈希到桶里。期望“绝大多数”近似冗余的文档被哈希到同一个桶里。π为随机选择策略
对所有列进行应用几个随机挑选的排列，从而对每一个列构建一个签名。
输出结果是一个签名矩阵：列＝集合（文档），行＝该列的若干最小哈希值
第三步：局部敏感哈希（LSH：Local Sensitive Hash）
目标：发现Jaccard相似度至少为s的文档对（给定相似度阈值，例如，s=0.8）
LSH的基本思想：用一个函数 f ( x , y ) f(x,y) f(x,y)来判断 x x x和 y y y是否是一个候选对：其相似度需要进行计算的元素对。
对于最小哈希矩阵：
将签名矩阵
M
M
M的列哈希到多个桶里
被哈希到同一个桶里的文档是一个候选对
步骤：
- 将签名矩阵 M M M划分成b个行条，每个行条有r行
- 对于每个行条，将它对应每一列的内容哈希到包含k个桶的哈希表中（让k尽可能大）
- 候选对是≥1和行条被哈希到同一个桶的列队
- 通过调整r和b，可以捕捉绝大多数相似对，且包含很少不相似对
通过挑选：
最小哈希的个数（ M M M的行数），行条个数b和每个行条的行数r来平衡：假阳性/假阴性