文档的相似度（3）--局部敏感哈希算法

59 阅读 0 评论 39 点赞

我是靠谱客的博主受伤橘子，最近开发中收集的这篇文章主要介绍文档的相似度（3）--局部敏感哈希算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

此篇博客将会接着上一篇博客继续文档相似度的分析。

在上篇博客中我们已经可以利用最小哈希签名对文档间的相似度进行分析了，但是我们应该要发现，及时可以使用最小哈希签名将大文档压缩成小的签名同时保持任意对文档之间的预期相似度，但是高效寻找具有最大相似度的问的那个对仍是不可能的。主要原因在于，即使文档本身的数目并不很大，但需要比较的文档对的数目可能很大。

例如：

假定有100万篇文档，每篇文档使用的签名的长度为250，则每篇文档需要1000个字节来表示签名。所有100万篇问的文档的签名数据占有1GB空间，这个数字小于普通台式机的内存大小。然而，有n*（n-1）/2（其中n为100万）即约5000亿个文档对需要比较。如果计算每两篇文档签名之间的相似度需要花费1微妙，那么这台计算机大约需要6天才能计算所有的相似度。

如果我们的目标是计算每对文档的相似度，那么即使采用并行机制来减少消耗时间，也没有办法减少计算量。但是，实际中往往需要得到那些最相似或者相似度超过某个下界的文档对。如果是这样的话，那么我们就只需要关注那些可能相似的文档对，而不需要研究所有的文档对。目前这类问题的处理存在着一个称为局部敏感哈希（LSH）或近邻搜索的一般性理论。此处将会介绍LSH的一个特定形式，它是面向我们所讨论的具体问题而设计的。

面向最小哈希签名的LSH

LSH的一个一般性做法就是对目标项进行多次哈希处理，使得相似项会比不相似项更可能哈希到同一个桶中。然后将至少有一次哈希到同一个桶中的玩的那个对看成候选对，我们只会检查这些候选对之间的相似度。我们希望大部分不相似的文档对将永远不会哈希到同一个桶中，这样就永远不需要检查它们的相似度。那些哈希到同一个桶中的非相似文档对称为伪正例，我们希望他们在所有对中占的比例越低越好。同时，我们也希望大部分真正相似的文档会至少被一个哈希函数映射到同一个桶中。那些没有映射到相同桶中的真正相似的文档对称为伪反例，我们希望他们在所有真正相似文档对中的比例也很小。

如果拥有目标项的最小哈希签名矩阵，那么一个有效的哈希处理方法是将签名矩阵划分成b个行条，每个行条由r行组成。对每个行条，存在一个哈希函数能够将行条中的每r个整数组成的列向量（行条中的每一列）映射到某个大数目范围的桶中。可以对所有行条使用相同的哈希函数，但是对每个行条我们都使用一个独立的桶数组，因此即使是不同行条中相同向量列，他们也不会被哈希到同一个桶中。

例如：

图1给出了一个12行签名矩阵的一部分，它被分成4个行条，每个行条由3行组成。图中显式可见的行条1中第2列和第4列均包含列向量[0,2,1]，因此它们肯定会被哈希到行条1下的相同桶中。因此，不管这两列在其他3个行条下的结果如何，它们都是一个相似候选对。图中显式给出的其它列也有可能会哈希到行条1下的同一桶中（说是可能，这是因为哈希的过程中有可能会因为冲突而造成不相同的项分配到相同的桶中）。但是，由于此时两个列向量[1,3,0]和[0,2,1]不同，加上哈西的桶数目也不少，因此偶然冲突的预期概率会非常低。通常我们假设当且仅当两个向量相等时，他们才会哈希到同一桶中。

在行条1中不相等的两个列仍然还有另外三次机会成为候选对，只要它们在剩余的3个行条中有一次相等即可。然而，我们观察到，如果签名矩阵的两列越相似，那么在多个行条中的向量相等的可能性也越大。因此，直观上看，行条化策略能够使得相似列会比不相似列更有可能成为候选对。

行条策略化的分析

假定使用b个行条，每个行条由r行组成，并假定某对具体文档之间的Jaccard相似度为s。由上篇博客中的内容可知，文档的最小哈希签名矩阵中某个具体行中的两个签名相等的概率等于s。接下来我们可以计算这些文档（或其签名）作为候选对的概率，具体计算过程如下：

（1）在某个具体行条中所有行的两个签名相等的概率为sʌr（这是表示s的r次方）；

（2）在某个具体行条中至少有一对签名不相等的概率是1-sʌr；

（3）在任何行条中的任意一行的签名对都不想等的概率为（1-sʌr）ʌb；

（4）签名至少在一个行条中全部相等的概率，也即成为候选对的概率为1-（1-sʌr）ʌb。

虽然有可能并不特别明显，但是不论常数b和r的取值如何，上述形式的概率函数图像大致为图2所给出的S-曲线。曲线中候选概率1/2对应的相似度就是所谓的阈值，它是b和r的函数。阈值对应的大概大概是上升最都陡峭的地方，对于较大的b和r，相似度在阈值之上的对很可能成为候选对，而在阈值之下的对则不太可能成为候选对，这正是我们想要的结果。阈值的一个近似估计是（1/b）ʌ(1/r)。例如，如果b=16且r=4，那么由于16的4次方跟为2，阈值的近似值为1/2.

图2 S-曲线

例如：

考虑b=20且r=5的情况，也就是说假定签名的个数为100，分成20个行条，每个行条包含5行。图3以表格形式给出了函数1-(1-s^5)^20的部分值。注意到的是，这里的阈值，也就是曲线中部上升处的s值，仅仅比0.5稍大一点。另外也注意到，该曲线并非从0到1在阈值处跳跃的最理想步进函数，但是曲线中部的斜率十分显著。例如，s从0.4变到0.6，增加的函数值大于0.6，因此中间部分的斜率大于3.

又例如，s=0.8时，1-0.8^5大约为0.672.如果再求20次方得到大约0.00035，用1减去该值以后得到0.99965.也就是说，如果认为两篇文档的相似度为80%，那么在任意行条中，5行中签名对全部相等的可能性只有约33%，因而它们会成为候选对。然而，这里有20个行条，因此有20次机会成为一个候选对。3000个对中，大致仅有1个相似度为80%的对不会成为候选对，即成为反例。

下面给出局部敏感哈希部分的python代码：

"""
在使用局部敏感哈希中，我们假设行条(也叫分组)和每个行条中行的个数的乘积刚好等于总的签名数，这样可以减少不必要的繁琐，
这就要求我们在选取相关参数时要注意
"""
def localSensitiveHash(signatureList,filesName,signatureNum,bands):
lshResult=[]
"""
此循环用于初始化这个list，构造一个下三角的模拟数组，用于存放两个文件之间行的相似个数
"""
for i in range(len(signatureList)):
temp=[]
for j in range(i):
temp.append(0)
lshResult.append(temp)
row=signatureNum/bands
#此循环是对签名的行条进行处理
for i in range(0,bands):
dicResult={}
index=i*row
#此循环是对行条中的每一列进行计算，num用于记录签名的下标
for num,signature in enumerate(signatureList):
#hashCode用于记录每个行条的hash桶号
hashCode = 0
#遍历行条中的列，此处的hash函数就暂时用累加，稍后修改
for j in range(index,index+row):
hashCode+=signature[j]
if hashCode in dicResult:
dicResult[hashCode].append(num)
else:
dicResult[hashCode]=[num]
for valueList in dicResult.values():
#print valueList
if(len(valueList)>=2):
for index1 in range(len(valueList)):
for index2 in range(index1+1,len(valueList)):
lshResult[valueList[index2]][valueList[index1]]+=1
similarityResult=[]
for i in range(1,len(lshResult)):
for j in range(len(lshResult[i])):
similarity=lshResult[i][j]/(bands*1.0)
similarityResult.append((similarity,filesName[i],filesName[j]))
return similarityResult

此篇博客到此就结束了。