文档介绍：-
文档的局部敏感哈希算法
距离测度
局部敏感函数理论
(完整的相似项发现方法)
文档的局部敏感哈希的产生原因
最小哈希签名仍然无法高效寻找具有最大相似度的文档。
即使文档本身的数目不大,但需要比较的文档对的数目可能很大。
实际中往往需要得到那些最相似或者相似度超过某个下界的文档对,我们只需关注那些可能相似的文档对。
通过LSH我们可以只关注可能相似的文档对,而不需要研究所有文档对。
LSH(locality-sensitive hashing)
一般性做法
对目标项进行多次哈希处理,使得相似项比不相似项更可能哈希到同一桶中。
将至少有一次哈希到同一桶中的文档对看成是候选对(candidate pair),只检查这些候选对之间的相似度。
哈希到同一个桶中的非相似文档对称为伪正例(false positive),希望它们在所有对中所占比例越低越好。
我们也希望大部分真正相似的文档对会至少被一个哈希函数映射到同一桶中。
没有映射到相同桶中的真正相似的文档对称为伪反例(false negative)。
对最小哈希签名矩阵的处理
假设拥有目标项的最小哈希签名矩阵,将签名矩阵划分成b个行条(band),每个行条由r行组成。
每个行条,存在一个哈希函数能够将行条中的每r个整数组成的列向量(行条中的每一列)映射到某个大数目范围的桶中。
可以对所有行条使用相同的哈希函数,但是对每个行条都使用一个独立的桶数组,因此即使是不同行条中的相同向量列也不会被哈希到同一桶中。
12行签名矩阵,分成4个行条,每个行条由3个行组成。
计算文档(或其签名)作为候选对的概率:
假定使用b个行条,每个行条由r行组成,ard相似度为s.
不论常数b和r取值如何,上述形式的概率函数图像大致如图3-7的S-曲线。曲线中上升最陡的地方对应的相似度就是所谓阈值(threshold),是b和r的函数。阈值的一个近似估计值是
b=20,r=5,即签名个数为100,分为20个行条,每行条有5行。
当s=,1-()5=,
[1-()5]20=
1- [1-()5]20=
通过对面向最小哈希签名的LSH采用行条化策略进行处理,使得相似项会比不相似项更可能哈希到同一个桶中( )。