相似项发现(3.4-3.6)

1、相似项发现3.4-3.6文档的局部敏感哈希算法文档的局部敏感哈希算法距离测度距离测度局部敏感函数理论局部敏感函数理论3.4文档的局部敏感哈希算法 3.4.1面向最小哈希签名的LSH 3.4.2行条化策略的分析 3.4.3上述技术的综合（完整的相似项发现方法）文档的局部敏感哈希的产生原因 最小哈希签名仍然无法高效寻找具有最大相似度的文档。 即使文档本身的数目不大，但需要比较的文档对的数目可能很大。 实际中往往需要得到那些最相似或者相似度超过某个下界的文档对，我们只需关注那些可能相似的文档对。 通过LSH我们可以只关注可能相似的文档对，而不需要研究所有文档对。4.3.1面向最小哈希签名的LSH L

2、SH(locality-sensitive hashing) 一般性做法一般性做法 对目标项进行多次哈希处理，使得相似项比不相似项更可能哈希到同一桶中。 将至少有一次哈希到同一桶中的文档对看成是候选对（candidate pair）,只检查这些候选对之间的相似度。 哈希到同一个桶中的非相似文档对称为伪正例（false positive）,希望它们在所有对中所占比例越低越好。 我们也希望大部分真正相似的文档对会至少被一个哈希函数映射到同一桶中。 没有映射到相同桶中的真正相似的文档对称为伪反例（false negative）。对最小哈希签名矩阵的处理 假设拥有目标项的最小哈希签名矩阵，将签名矩阵划

3、分成b个行条（band），每个行条由r行组成。 每个行条，存在一个哈希函数能够将行条中的每r个整数组成的列向量（行条中的每一列）映射到某个大数目范围的桶中。 可以对所有行条使用相同的哈希函数，但是对每个行条都使用一个独立的桶数组，因此即使是不同行条中的相同向量列也不会被哈希到同一桶中。例3.10 12行签名矩阵，分成4个行条，每个行条由3个行组成。3.4.2行条化策略分析 计算文档（或其签名）作为候选对的概率：计算文档（或其签名）作为候选对的概率： 假定使用b个行条，每个行条由r行组成，假定某对具体文档间的Jaccard相似度为s. 不论常数b和r取值如何，上述形式的概率函数图像大致如图3-7

4、的S-曲线。曲线中上升最陡的地方对应的相似度就是所谓阈值（threshold）,是b和r的函数。阈值的一个近似估计值是 b=20,r=5,即签名个数为100，分为20个行条，每行条有5行。 当s=0.8时，1-(0.8)5=0.328， 1-(0.8)520=0.00035 1- 1-(0.8)520=0.99965 通过对面向最小哈希签名的LSH采用行条化策略进行处理，使得相似项会比不相似项更可能哈希到同一个桶中(0.00035 远小于0.99965)。3.4.3上述技术的综合 一个完整的相似项发现的方法：一个完整的相似项发现的方法：（1）找出可能的候选对相似文档集合（2）基于该集合发现真正

5、的相似文档 选择某个k,并对每篇文档构建其k-shingle集合。将这些k-shingle映射成更短的桶编号（后一步可选）； 将文档-shingle对按照shingle排序； 选择最小哈希签名的长度n。对中排好序的表进行最小哈希签名的计算； 选择阈值t来定义应该达到的相似度使之被看做是预期的“相似对”。选择行条数b和每个行条中的行数r，使得br=n，而阈值t近似等于(1/b)1/r 。 如果避免伪反例的产生很重要，那么选择合适的b和r以产生小于t的阈值。 如果速度相当重要并且希望限制伪正例的数目，那么选择合适的b和r来获得更高的阈值。 应用面向最小哈希签名的LSH技术来构建候选对； 检查每个候

6、选对的签名，确定他们一致性的比例是否大于t； （该步可选）如果签名足够相似，则直接检查文档本身看他们是否真正相似。不相似的文档有时碰巧会具有相似的签名。 该方法存在的缺陷：该方法存在的缺陷： （1）可能会产生伪反例，即某些相似文档对由于没有进入候选对所以最终没有被识别出来。 （2）可能会产生伪正例，即在评估了某些候选对后发现其相似度不足。3.5距离测度（similarity measure） 3.5.1 距离测度的定义 3.5.2 欧氏距离 3.5.3 Jaccard距离 3.5.4 余弦距离 3.5.5 编辑距离 3.5.6海明距离3.5.1距离测度的定义 假定有一些点组成的集合，称为空间（

7、space）。该空间下的距离测度是一个函数d(x , y)，以空间中的两个点作为参数，输出是一个实数值。该函数必须满足下列准则：该函数必须满足下列准则： d(x , y)0（距离非负） d(x , y)=0当且仅当x=y（只有点到自身的距离为0，其他距离都大于0） d(x , y)=d(y , x)（距离具有对称性） d(x , y)d(x , z)+d(z , y)（三角不等式） 如果从x点行进到y点，那么一定要求经过某个特定的第三点z则不会有任何好处。 使得所有的距离测度表现的如同是从一个点到另一个点的最短路径的长度。3.5.2欧氏距离 L2范式： Lr范式： L1范式距离（曼哈顿距离）：

8、 两个点的距离是每维距离的绝对值之和。 L范式： 当r趋向于无穷大时Lr范式的极限值。 当r增大时只有那个具有最大距离的维度才真正起作用。 正式定义：在所有维度i下|xi-yi|中的最大值。例3.12 二维欧氏空间（平面）上有两个点(2,7),(6,4)。 L2范式距离： L1范式距离： L范式距离：3.5.3 Jaccard距离 Jaccard距离： d(x , y)=1-SIM(x , y) 即1减去x、y的交集与并集的比率。 验证验证Jaccard距离是否为距离测度：距离是否为距离测度： （1）交集的大小不可能大于并集的大小，因此d(x , y)不可能为负值； （2）若x=y则d(x ,

9、 y)=0，这是因为xx=xx=x。 然而如果xy，那么xy的大小严格小于xy的大小，因此d(x , y)严格为正； （3）由于交集和并集运算都是对称的，即xy=yx，xy=yx，因此d(x , y)=d(y , x); （4）三角不等式的验证 SIM(x , y)是一个随机最小哈希函数将x和y映射为相同值的概率。 Jaccard距离则为一个随机最小哈希函数将x和y映射为不同值的概率。 如果h是一个随机的最小哈希函数，那么h(x)h(y) 的概率不高于h(x)h(z)的概率与h(z)h(y)的概率之和。 因为只要有h(x)h(y)，那么至少h(x)和h(y)中的一个一定与h(z)不同，即h(x

10、)和h(y)不可能都是h(z),否则二者肯定相等。3.5.4 余弦距离（cosine distance） 在有维度的空间下余弦距离才有意义，这些空间包括欧氏空间和离散欧式空间（包括坐标只采用整数值或布尔值来表示的空间）。 在上述空间下，点可以代表方向。在这里不区分一个向量及其多倍向量（向量的每一维都放大相同的倍数得到的向量）。 两个点的余弦距离实际上是点所代表的向量之间的夹角，不管空间有多少维，该夹角的范围是0到180度。 首先计算夹角的余弦，然后应用反余弦函数将结果转化为0到180度之间的角度，从而最终得到余弦距离。 给定向量x和y，其余弦距离如下： 验证余弦距离是否为距离测度：验证余弦距离

11、是否为距离测度： （1）余弦定义为0到180度之间，因此余弦距离非负； （2）当且仅当两个向量表示同一方向时向量的夹角为0； （3）余弦距离 的对称性：x和y的夹角显然与y和x的夹角相等； （4）通过物理含义诠释三角不等式。如要将向量x旋转到y，可以先从x旋转到z，再从z旋转到y。两次旋转经过的夹角之和不会小于直接旋转所得到的夹角。3.5.5 编辑距离 只适用于字符比较串。 两个字符串x=x1x2xn 及y=y1 y2 ym 的编辑距离等于将x转换为y所需要的单字符插入及删除操作的最小数目。例3.14 两个字符串x=abcde, y=acfdeg的编辑距离为3. 删除字符b; 在字符c之后插入

12、字符f; 在字符e之后插入字符g。 可以验证不存在少于3步的插入或删除操作序列能把x转换为y。最长公共子序列(LCS)（longest common subsequence） 通过在x和y的某些位置上进行删除操作能够得到某个字符串，基于上述方法构造出的x和y的最长公共字符串就是x和y的LCS。 其编辑距离等于x和y的长度之和减去它们的LCS长度的两倍。例3.15 字符串x=abcde和y=acfdeg存在一个唯一的LCS即acde，包含了所有同时在x和y中出现的字符，且次序相同。 x的长度为5，y的长度为6，LCS的长度为4。 编辑距离=5+62*4=3 验证编辑距离是否为距离测度：验证编辑距

13、离是否为距离测度： （1）编辑距离非负。只有两个相等的字符串的编辑距离才会为0； （2）编辑距离是对称的。x到y的插入、删除的操作序列完全可以颠倒次序应用与y转换为x的过程中去。 （3）编辑距离满足三角不等式。将x转换为y的一种方法是先将x转换为z，再将z转换为y。x到z再到y的最少编辑操作数一定不小于从x到y的最小编辑操作数。3.5.6 海明距离（Hamming distance） 海明距离：两个向量中不同分量的个数。 海明距离往往应用与布尔向量。 例3.16 向量10101和11110的海明距离为3。 两个向量第2、4、5位元素不同，而其他元素均相同。 验证海明距离是否为距离测度：验证海明

14、距离是否为距离测度： （1）海明距离非负，当且仅当两个向量相等时，海明距离为0； （2）海明距离在计算时与向量的先后顺序无关； （3）满足三角不等式：如果x和z有m个分量不同，z和y有n个分量不同，那么x和y中不同的分量个数不可能超过m+n个。3.6 局部敏感函数理论 3.6.1 局部敏感函数 3.6.2 面向Jaccard距离的局部敏感函数族 3.6.3 局部敏感函数族的放大处理 可高效产生候选对的函数族要满足的三个条件：可高效产生候选对的函数族要满足的三个条件： （1）它们必须更可能选择近距离而不是远距离作为候选对。 （2）函数之间必须在统计上相互独立，在这个意义上，两个或者多个函数的联合

15、概率等于每个函数上独立事件的概率乘积。 （3）必须在以下两个方面具有很高的效率： 必须能够在很短的时间内识别候选对，该时间远低于扫描所有对所花费的时间。 它们必须可以组合在一起以更好地避免伪正例和伪反例，组合后函数所花费的时间也必须远低于对的数目3.6.1 局部敏感函数 函数族（family of functions） f(x , y) f(x)=f(y)：x和y是一个候选对 f(x)f(y)：x和y不是一个候选对 （d1 , d2 , p 1 , p 2）-敏感的函数族： 令d1 d2 是定义在某个距离测度d下的两个距离值。 函数族F中的每个函数f都满足以下条件： 如果d(x , y) d1

16、， 那么f(x)=f(y)的概率至少是p 1 如果d(x , y) d2, 那么 f(x)=f(y)的概率最大是p23.6.2面向Jaccard距离的局部敏感函数族 目前只有一种找到局部敏感函数族的方法：采用最小哈希函数族并假设距离测度采用Jaccard距离。 一个最小哈希函数h:当且仅当h(x)=h(y)时，x和y是一对候选对。 对任意d1 ，d2， 0 d1 d2 1，最小哈希函数族是（ d1 ， d2 ， 1-d1 ，1- d2 ）-敏感的。3.6.3局部敏感函数族的放大处理 与构造（与构造（AND-construction） 假设给定一个（d1 , d2 , p 1 , p 2）-敏感

17、的函数族F 构造的新的函数族F： F的每个成员函数由r个F成员函数组成，r是一个固定常数。 若f在F中，f从F的成员函数集合f1 ,f2 ,，fn中构造，i=1,2r，当且仅当对所有i都有fi (x)=fi (y)时，才有f(x)=f(y) 由于F的成员函数都是从F的成员函数中独立选出来的，因此可以断言F是一个（d1 , d2 , (p1 ) r, (p2 )r )-敏感函数族。 即对任意p,如果F的一个成员函数判定(x , y)是候选对的概率为p，那么F的一个成员函数做相同判定的概率是pr . 与构造实际上反映了单个行条中所有r行的每一行的效果： 如果一个行条中r行的每一行的x , y值都相

18、等，那么基于整个行条就可以认为x和y是候选对。 或构造（或构造（OR-construction） 可以将一个（d1 , d2 , p 1 , p 2）-敏感的函数族F转换为（d1 , d2 , 1-(1-p1 ) b, 1-(1-p2 )b )-敏感函数族F。 F的每一个成员函数f由b个F中的成员函数f1 ,f2 ,，fb构成。当且仅当存在一个或者多个i使得fi (x)=fi (y)时，才有f(x)=f(y) 或构造实际上反映了将多个行条组合的效果： 如果某个行条使得x和y可以成为候选对，那么x和y就成为候选对。 与构造过程降低了所有的概率(pr )。若谨慎选择F和r，可使小概率p 2 非常接近0，