文档介绍：第三章 相似项发现
整理课件
近邻搜索的应用
相似度：通过计算交集的相对大小来获得集合之间的相似度，也称为Jaccard相似度
Sim (C1, C2) = |C1C2|/|C1C2|.
整理课件
3
E shingle 集合也是原始文件的4倍
想办法计算文件的签名（一个较小的文件），通过计算签名的相似性来推断文件之间的相似性。
整理课件
集合的矩阵表示
矩阵的列表示各个集合，行表示所有可能的元素
S1={a,d},s2={c},s3={b,d,e},s4={a,c,d}
元素
s1
s2
s3
s4
A
1
0
0
1
B
0
0
1
0
C
0
1
0
1
D
1
0
1
1
e
0
0
1
0
整理课件
最小哈希
首先选择行的一个排列变换。
任意一列的最小哈希值是在该行排列顺序下第一个列值为1的行的行号。
H(S1)=a,H(s2)=c,H(s3)=b,H(s4)=a
元素
S1
S2
s3
s4
B
0
0
1
0
E
0
0
1
0
A
1
0
0
1
D
1
0
1
1
c
0
1
0
1
整理课件
最小哈希及jaccard相似度
两个集合经随机排列转换之后得到的两个最小哈希值相等的概率等于这两个集合的jaccard相似度
假设只考虑s1和s2两个集合对应的列
。
整理课件
四种类型
Given columns C1 and C2, rows may be classified as:
C1 C2
a 1 1
b 1 0
c 0 1
d 0 0
两列同时为0的行对于这两列的相似性没有贡献。
.设x是两列都为1的行的数目
y是其中一行为1的数目
Note Sim (C1, C2) = x /(x +y ).
整理课件
最小哈希
对行进行随机转换后，从上往下扫描。遇到两行均为1的概率是x/(x+y)
总共有x+y行，两行均为1的个数有x个。
两行均为1，也就是H(s1)=H(s1)
整理课件
最小哈希签名
对于每一个行排列方式，每一个集合都有一个最小哈希值
如果有n个行排列方式（n一般是1百到数百），每个集合就能产生n个最小哈希值，把这些哈希值写成一个列向量。也称为哈希签名。
每个集合的列向量组合在一起，写成一个矩阵，称为签名矩阵。
文档的相似性就等于最小哈希值相等的概率
整理课件
最小哈希签名的计算
操作矩阵较为困难，操作较小的签名矩阵是可以的
用签名矩阵记录行变换的结果，每一个位置只记录当前变换的最小的位置
整理课件
整理课件
整理课件
文档的局部敏感哈希算法
即使可以使用最小哈希将大文档压缩成小的签名并同时保存任意文档对之间的相似度，寻找相似文档对仍然是不可能的
文档的数目太大
实际上，只需要寻找那些相似性大于某个门限的文档对，而不是全部文档对。这就是局部敏感哈希
整理课件
文档的局部敏感哈希算法
假设
文档先表示为shingle集合，通过哈希处理，变为短签名集合
基本想法：
把签名矩阵分成子矩阵，使用多次哈希函数。
具有相同部分的列将被哈希到同一个桶中
只考察那些哈希到同一个桶里面的列的相似性
整理课件
26
Partition Into Bands
Matrix M
r rows
per band
b bands
One
signature
整理课件
27
Matrix M
r rows
b bands
Buckets
Columns 2 and 6
are probably identical.
Columns 6 and 7 are
surely different.
整理课件
28
What b Bands of r Rows Gives You
Similarity s of two sets
Probability
of sharing
a bucket
t
s r
All rows
of a band
are equal
1 -
Some row
of a band
unequal
(
)b
No bands
identical
1 -
At least
one band
ident