局部敏感哈希算法(Locality Sensitive Hashing)初探

前言:

其实有了前文simhash算法的基础,局部敏感hash算法已经不存在理解上的问题了吧。。。毕竟simhash算法应该是局部敏感哈希算法的一种。。所以我就直接转载几篇我认为比较好的文档结合一下好了。。。会把比较重要的概念或者定义标记重点。

局部敏感哈希(Locality Sensitive Hashing,LSH)算法是我在前一段时间找工作时接触到的一种衡量文本相似度的算法。局部敏感哈希是近似最近邻搜索算法中最流行的一种,它有坚实的理论依据并且在高维数据空间中表现优异。它的主要作用就是从海量的数据中挖掘出相似的数据,可以具体应用到文本相似度检测、网页搜索等领域。

1. 基本思想

局部敏感哈希的基本思想类似于一种空间域转换思想,LSH算法基于一个假设,如果两个文本在原有的数据空间是相似的,那么分别经过哈希函数转换以后的它们也具有很高的相似度;相反,如果它们本身是不相似的,那么经过转换后它们应仍不具有相似性。

哈希函数,大家一定都很熟悉,那么什么样的哈希函数可以具有上述的功能呢,可以保持数据转化前后的相似性?当然,答案就是局部敏感哈希。

2. 局部敏感哈希LSH

局部敏感哈希的最大特点就在于保持数据的相似性,我们通过一个反例来具体介绍一下。

假设一个哈希函数为Hash(x) = x%8,那么我们现在有三个数据分别为255、257和1023,我们知道255和257本身在数值上具有很小的差距,也就是说它们在三者中比较相似。我们将上述的三个数据通过Hash函数转换:

Hash(255) = 255%8 = 7;

Hash(257) = 257%8 = 1;

Hash(1023) = 1023%8 = 7;

我们通过上述的转换结果可以看出,本身很相似的255和257在转换以后变得差距很大,而在数值上差很多的255和1023却对应相同的转换结果。从这个例子我们可以看出,上述的Hash函数从数值相似度角度来看,它不是一个局部敏感哈希,因为经过它转换后的数据的相似性丧失了。

我们说局部敏感哈希要求能够保持数据的相似性,那么很多人怀疑这样的哈希函数是否真的存在。我们这样去思考这样一个极端的条件,假设一个局部敏感哈希函数具有10个不同的输出值,而现在我们具有11个完全没有相似度的数据,那么它们经过这个哈希函数必然至少存在两个不相似的数据变为了相似数据。从这个假设中,我们应该意识到局部敏感哈希是相对的,而且我们所说的保持数据的相似度不是说保持100%的相似度,而是保持最大可能的相似度

对于局部敏感哈希“保持最大可能的相似度”的这一点,我们也可以从数据降维的角度去考虑。数据对应的维度越高,信息量也就越大,相反,如果数据进行了降维,那么毫无疑问数据所反映的信息必然会有损失。哈希函数从本质上来看就是一直在扮演数据降维的角色。

 3. 文档相似度计算

我们通过利用LSH来实现文档的相似度计算这个实例来介绍一下LSH的具体用法。

  3.1 Shingling

假设现在有4个网页,我们将它们分别进行Shingling(将待查询的字符串集进行映射,映射到一个集合里,如字符串“abcdeeee”, 映射到集合”(a,b,c,d,e)”, 注意集合中元素是无重复的,这一步骤就叫做Shingling, 意即构建文档中的短字符串集合,即shingle集合。),得到如下的特征矩阵:

其中“1”代表对应位置的Shingles在文档中出现过,“0”则代表没有出现过。

在衡量文档的相似度中,我们有很多的方法去完成,比如利用欧式距离、编辑距离、余弦距离、Jaccard距离等来进行相似度的度量。在这里我们运用Jaccard相似度。接下来我们就要去找一种哈希函数,使得在hash后尽量还能保持这些文档之间的Jaccard相似度,即:

我们的目标就是找到这样一种哈希函数,如果原来文档的Jaccard相似度高,那么它们的hash值相同的概率高,如果原来文档的Jaccard相似度低,那么它们的hash值不相同的概率高,我们称之为Min-hashing(最小哈希)。

  3.2 Min-hashing

Min-hashing定义为:特征矩阵按行进行一个随机的排列后,第一个列值为1的行的行号。举例说明如下,假设之前的特征矩阵按行进行的一个随机排列如下:

元素 S1 S2 S3 S4
0 0 1 0
成功 0 0 1 1
1 0 0 0
减肥 1 0 1 1
0 1 0 1

最小哈希值:h(S1)=3,h(S2)=5,h(S3)=1,h(S4)=2.

为什么定义最小hash?事实上,两列的最小hash值就是这两列的Jaccard相似度的一个估计,换句话说,两列最小hash值同等的概率与其相似度相等,即P(h(Si)=h(Sj)) = sim(Si,Sj)。为什么会相等?我们考虑Si和Sj这两列,它们所在的行的所有可能结果可以分成如下三类:

(1)A类:两列的值都为1;

(2)B类:其中一列的值为0,另一列的值为1;

(3)C类:两列的值都为0.

特征矩阵相当稀疏,导致大部分的行都属于C类,但只有A、B类行的决定sim(Si,Sj),假定A类行有a个,B类行有b个,那么sim(si,sj)=a/(a+b)。现在我们只需要证明对矩阵行进行随机排列,两个的最小hash值相等的概率P(h(Si)=h(Sj))=a/(a+b),如果我们把C类行都删掉,那么第一行不是A类行就是B类行,如果第一行是A类行那么h(Si)=h(Sj),因此P(h(Si)=h(Sj))=P(删掉C类行后,第一行为A类)=A类行的数目/所有行的数目=a/(a+b),这就是最小hash的神奇之处。

Min-hashing的具体做法可以根据如下进行表述:

返回到我们的实例,我们首先生成一堆随机置换,把特征矩阵的每一行进行置换,然后hash function就定义为把一个列C hash成一个这样的值:就是在置换后的列C上,第一个值为1的行的行号。如下图所示:

  图中展示了三个置换,就是彩色的那三个,我现在解释其中的一个,另外两个同理。比如现在看蓝色的那个置换,置换后的Signature Matrix为:
  然后看第一列的第一个是1的行是第几行,是第2行,同理再看二三四列,分别是1,2,1,因此这四列(四个document)在这个置换下,被哈希成了2,1,2,1,就是右图中的蓝色部分,也就相当于每个document现在是1维。再通过另外两个置换然后再hash,又得到右边的另外两行,于是最终结果是每个document从7维降到了3维。我们来看看降维后的相似度情况,就是右下角那个表,给出了降维后的document两两之间的相似性。可以看出,还是挺准确的,回想一下刚刚说的:希望原来documents的Jaccard相似度高,那么它们的hash值相同的概率高,如果原来documents的Jaccard相似度低,那么它们的hash值不相同的概率高,如何进行概率上的保证?Min-Hashing有个惊人的性质:
  就是说,对于两个document,在Min-Hashing方法中,它们hash值相等的概率等于它们降维前的Jaccard相似度。
  注:在上述例子中,我们还可以采取欧氏距离等相似度量来替代Jaccard相似度,这时候LSH相应的策略也需要进行改变,从而使得最后的hash值等于降为前的相似度。

局部敏感hash的一般定义

局部敏感hash实质上是满足一定条件的函数簇,上面介绍只是一个基于Jaccard的例子,实际上还有面向其他距离的LSH。

令d1<d2是定义在距离测定d下得两个距离值,如果一个函数族的每一个函数f满足:

(1)如果d(x,y)<=d1,则f(x)=f(y)的概率至少为p1,即P(f(x)=f(y)) >= p1;

(2)如果d(x,y)>=d2,则f(x)=f(y)的概率至多为p2,即p(f(x)=f(y)) <= p2.

那么称F为(d1,d2,p1,p2)-敏感的函数族。实际上我们之前的最小hash函数族是(d1,d2,1-d1,1-d2)-敏感的。

局部敏感hash族还可以进行放大处理,已获得更高的准确率和召回率,当然也有面向其他距离的LSH。本文的东西全部源自参考文献的课本,有兴趣可以好好读一下这本书。

 

 

 

文本相似度判断-simhash算法学习笔记

先放原始论文。。。以此表达对这个算法的敬意orz

论文链接

 

问题引出:

那天百度一面,frog学姐问了我如何判断两篇新闻稿的相似度的问题….我满篇口胡…也只是回答了一些诸如从图片上考虑。。或者去掉stop word之后得到特征向量然后计算余弦值之类得到传统想法。。。

今天看到了google在用的网页去重的算法(?。。。感觉好神奇。。。准备面试到现在,第一个让我感到惊异而不是套路的算法orz

对于处理大规模文本(500字以上吧)的时候效果很好。。。但是算法思想却又非常简单。

这才是算法的美丽之处吧。。。。leetcode上的那些纱布技巧也好意思叫算法。。。?

网页去重,其实本质还是网页相似度的计算….首先是两篇,之后还可以推广到海量数据。

算法初探:

simhash算法。。。字面上也可以看出。。是一种hash算法。。。那么它和一般的hash有什么不同呢?

最大的问题在于。。。传统hash的设计目的之一是使得映射后的值的分布尽可能均匀…对于同样的key会有同样的value,但是每当key有轻微的变化的时候,value就会千差万别。

举个例子:

“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

也就是说。。。没办法通过hash之后得到的值的差异,去分析key的相似程度。

而simhash就是通过某种方法进行hash,使得hash之后得到的value可以反应key的相似度。

流程

simhash算法分为5个步骤:分词、hash、加权、合并、降维,具体过程如下所述:

  • 分词
    • 给定一段语句,进行分词,得到有效的特征向量,然后为每一个特征向量设置1-5等5个级别的权重(如果是给定一个文本,那么特征向量可以是文本中的词,其权重可以是这个词出现的次数)。例如给定一段语句:“CSDN博客结构之法算法之道的作者July”,分词后为:“CSDN 博客 结构 之 法 算法 之 道 的 作者 July”,然后为每个特征向量赋予权值:CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5),其中括号里的数字代表这个单词在整条语句中的重要程度,数字越大代表越重要。
  • hash
    • 通过hash函数计算各个特征向量的hash值,hash值为二进制数01组成的n-bit签名。比如“CSDN”的hash值Hash(CSDN)为100101,“博客”的hash值Hash(博客)为“101011”。就这样,字符串就变成了一系列数字。
  • 加权
    • 在hash值的基础上,给所有特征向量进行加权,即W = Hash * weight,且遇到1则hash值和权值正相乘,遇到0则hash值和权值负相乘。例如给“CSDN”的hash值“100101”加权得到:W(CSDN) = 100101 4 = 4 -4 -4 4 -4 4,给“博客”的hash值“101011”加权得到:W(博客)=101011 5 = 5 -5 5 -5 5 5,其余特征向量类似此般操作。
  • 合并
    • 将上述各个特征向量的加权结果累加,变成只有一个序列串。拿前两个特征向量举例,例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加,得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”,得到“9 -9 1 -1 1”。
  • 降维
    • 对于n-bit签名的累加结果,如果大于0则置1,否则置0,从而得到该语句的simhash值,最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维(某位大于0记为1,小于0记为0),得到的01串为:“1 0 1 0 1 1”,从而形成它们的simhash签名。

每篇文档得到SimHash签名值后,接着计算两个签名的海明距离即可。根据经验值,对64位的 SimHash值,海明距离在3以内的可认为相似度比较高。

  • 海明距离的求法:异或时,只有在两个比较的位不同时其结果是1 ,否则结果为0,两个二进制“异或”后得到1的个数即为海明距离的大小。

 

推广到海量数据:

关键是,如何将其扩展到海量数据呢?譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢?

  • 一种方案是查找待查询文本的64位simhash code的所有3位以内变化的组合
    • 大约需要四万多次的查询。
  • 另一种方案是预生成库中所有样本simhash code的3位变化以内的组合
    • 大约需要占据4万多倍的原始空间。

这两种方案,要么时间复杂度高,要么空间复杂度复杂,能否有一种方案可以达到时空复杂度的绝佳平衡呢?答案是肯定的:

  • 我们可以把 64 位的二进制simhash签名均分成4块,每块16位。根据鸽巢原理(也称抽屉原理),如果两个签名的海明距离在 3 以内,它们必有一块完全相同。如下图所示:
  • 然后把分成的4 块中的每一个块分别作为前16位来进行查找,建倒排索引。

具体如下图所示:

如此,如果样本库中存有2^34(差不多10亿)的simhash签名,则每个table返回2^(34-16)=262144个候选结果,大大减少了海明距离的计算成本。

  • 假设数据是均匀分布,16位的数据,产生的像限为2^16个,则平均每个像限分布的文档数则为2^34/2^16 = 2^(34-16)) ,四个块返回的总结果数为 4* 262144 (大概 100 万)。
    • 这样,原本需要比较10亿次,经过索引后,大概只需要处理100万次。

 

 

参考资料:

 

simhash算法具体流程

海量数据相似度计算之simhash和海明距离

simhash算法

基于局部敏感哈希的协同过滤算法之simHash算法