15 最近邻检索（上）：如何用局部敏感哈希快速过滤相似文章？
你好，我是陈东。
在搜索引擎和推荐引擎中，往往有很多文章的内容是非常相似的，它们可能只有一些修饰词不同。如果在搜索结果或者推荐结果中，我们将这些文章不加过滤就全部展现出来，那用户可能在第一页看到的都是几乎相同的内容。这样的话，用户的使用体验就会非常糟糕。因此，在搜索引擎和推荐引擎中，对相似文章去重是一个非常重要的环节。
对相似文章去重，本质上就是把相似的文章都检索出来。今天，我们就来聊聊如何快速检索相似的文章。
如何在向量空间中进行近邻检索？
既然是要讨论相似文章的检索，那我们就得知道，一篇文章是怎么用计算机能理解的形式表示出来的，以及怎么计算两篇文章的相似性。最常见的方式就是使用向量空间模型（Vector Space Model）。所谓向量空间模型，就是将所有文档中出现过的所有关键词都提取出来。如果一共有n个关键词，那每个关键词就是一个维度，这就组成了一个n维的向量空间。
那一篇文档具体该如何表示呢？我们可以假设，一篇文章中有k（0<k<=n）个关键词，如果第k个关键词在这个文档中的权重是w，那这个文档在第k维上的值就是w。一般来说，我们会以一个关键词在这篇文档中的TF-IDF值作为w的值。而如果文章不包含第k个关键词，那它在第k维上的值就是0，那我们也可以认为这个维度的权重就是0。这样，我们就可以用一个n维的向量来表示一个文档了，也就是<w1,w2,w3,……wn>。这样一来，每一个文档就都是n维向量空间中的一个点。
那接下来，计算两个文章相似度就变成了计算两个向量的相似度。计算向量相似度实际上就是计算两个向量的距离，距离越小，它们就越相似。具体在计算的时候，我们可以使用很多种距离度量方式。比如说，我们可以采用余弦距离，或者采用欧氏距离等。一般来说，我们会采用余弦距离来计算向量相似度。
拓展到搜索引擎和推荐引擎中，因为每个文档都是n维向量中的一个点，所以查询相似文章的问题，就变成了在n维空间中，查询离一个点距离最近的k个点的问题。如果把这些“点”想象成“人”，这不就和我们在二维空间中查询附近的人的问题非常类似了吗？这就给了我们一个启发，我们是不是也能用类似的检索技术来解决它呢？下面，我们一起来看一下。
首先，在十几维量级的低维空间中，我们可以使用k-d树进行k维空间的近邻检索，它的性能还是不错的。但随着维度的增加， 如果我们还要精准找到最邻近的k个点，k-d需要不停递归来探索邻接区域，检索效率就会急剧下降，甚至接近于遍历代价。当关键词是几万乃至百万级别时，文档的向量空间可能是一个上万维甚至是百万维的超高维空间，使用k-d树就更难以完成检索工作了。因此，我们需要寻找更简单、高效的方案。
这个时候，使用非精准Top K检索代替精准Top K检索的方案就又可以派上用场了。这是为什么呢？因为高维空间本身就很抽象，在用向量空间中的一个点表示一个对象的过程中，如果我们选择了不同的权重计算方式，那得到的向量就会不同，所以这种表示方法本身就已经损失了一定的精确性。
因此，对于高维空间的近邻检索问题，我们可以使用近似最近邻检索（Approximate Nearest Neighbor）来实现。你可以先想一想查询附近的人是怎么实现的，然后再和我一起来看高维空间的近似最近邻检索是怎么做的。
什么是局部敏感哈希？
借助非精准检索的思路，我们可以将高维空间的点也进行区域划分，然后为每个区域都生成一个简单的一维编码。这样，当我们要查找一个点最邻近的k个点的时候，直接计算出区域编码就能高效检索出同一个区域的所有对象了。
也因此，我们就能得出一个结论，那就是同一个区域中的不同的点，通过统一的计算过程，都能得到相同的区域编码。这种将复杂对象映射成简单编码的过程，是不是很像哈希的思路？
所以，我们可以利用哈希的思路，将高维空间中的点映射成低维空间中的一维编码。换句话说，我们通过计算不同文章的哈希值，就能得到一维哈希编码。如果两篇文章内容100%相同，那它们的哈希值就是相同的，也就相当于编码相同。
不过，如果我们用的是普通的哈希函数，只要文档中的关键词有一些轻微的变化（如改变了一个字），哈希值就会有很大的差异。但我们又希望，整体相似度高的两篇文档，通过哈希计算以后得到的值也是相近的。因此，工业界设计了一种哈希函数，它可以让相似的数据通过哈希计算后，生成的哈希值是相近的（甚至是相等的）。这种哈希函数就叫作局部敏感哈希（Locality-Sensitive Hashing）。
其实局部敏感哈希并不神秘。让我们以熟悉的二维空间为例来进一步解释一下。
在二维空间中，我们随意划一条直线就能将它一分为二，我们把直线上方的点的哈希值定为1，把直线下方的点的哈希值定为0。这样就完成一个简单的哈希映射。通过这样的随机划分，两个很接近的点被同时划入同一边的概率，就会远大于其他节点。也就是说，这两个节点的哈希值相同的概率会远大于其他节点。
当然，这样的划分有很大的随机性，不一定可靠。但是，如果我们连续做了n次这样的随机划分，这两个点每次都在同一边，那我们就可以认为它们在很大概率上是相近的。因此，我们只要在n次随机划分的过程中，记录下每一个点在每次划分后的值是0还是1，就能得到一个n位的包含0和1的序列了。这个序列就是我们得到的哈希值，也就是区域编码。
因此，对于高维空间，我们构造局部敏感哈希函数的方案是，随机地生成n个超平面，每个超平面都将高维空间划分为两部分。位于超平面上面的点的哈希值为1，位于超平面下方的点的哈希值为0。由于有n个超平面，因此一个点会被判断n次，生成一个n位的包含0和1的序列，它就是这个点的哈希值。这就是一个基于超平面划分的局部敏感哈希构造方法。（为了方便你直观理解，我简单说成了判断一个点位于超平面的上面还是下面。在更严谨的数学表示中，其实是求一个点的向量和超平面上法向量的余弦值，通过余弦值的正负判断是1还是0。这里，你理解原理就可以了，严谨的数学分析我就不展开了。）
如果有两个点的哈希值是完全一样的，就说明它们被n个超平面都划分到了同一边，它们有很大的概率是相近的。即使哈希值不完全一样，只要它们在n个比特位中有大部分是相同的，也能说明它们有很高的相近概率。
上面我们说的判断标准都比较笼统，实际上，在利用局部敏感哈希值来判断文章相似性的时候，我们会以表示比特位差异数的海明距离（Hamming Distance）为标准。我们可以认为如果两个对象的哈希值的海明距离低于k，它们就是相近的。举个例子，如果有两个哈希值，比特位分别为00000和10000。你可以看到，它们只有第一个比特位不一样，那它们的海明距离就是1。如果我们认为海明距离在2之内的哈希值都是相似的，那它们就是相似的。
SimHash是怎么构造的？
不过，这种构造局部敏感哈希函数的方式也有一些缺陷：在原来的空间中，不同维度本来是有着不同权重的，权重代表了不同关键词的重要性，是一个很重要的信息。但是空间被n个超平面随机划分以后，权重信息在某种程度上就被丢弃了。
那为了保留维度上的权重，并且简化整个函数的生成过程，Google提出了一种简单有效的局部敏感哈希函数，叫作SimHash。它其实是使用一个普通哈希函数代替了n次随机超平面划分，并且这个普通哈希函数的作用对象也不是文档，而是文档中的每一个关键词。这样一来，我们就能在计算的时候保留下关键词的权重了。这么说有些抽象，让我们一起来看看SimHash的实现细节。
方便起见，我们就以Google官方介绍的64位的SimHash为例，来说一说它构造过程。整个过程，我们可以总结为5步。
- 选择一个能将关键词映射到64位正整数的普通哈希函数。
- 使用该哈希函数给文档中的每个关键词生成一个64位的哈希值，并将该哈希值中的0修改为-1。比如说，关键词A的哈希值编码为<1,0,1,1,0>，那我们做完转换以后，编码就变成了<1,-1,1,1,-1>。
- 将关键词的编码乘上关键词自己的权重。如果关键词编码为<1,-1,1,1,-1>，关键词的权重为2，最后我们得到的关键词编码就变成了<2,-2,2,2,-2>。
- 将所有关键词的编码按位相加，合成一个编码。如果两个关键词的编码分别为<2,-2,2,2,-2>和<3,3,-3,3,3>，那它们相加以后就会得到<5,1,-1,5,1>。
- 将最终得到的编码中大于0的值变为1，小于等于0的变为0。这样，编码<5,1,-1,5, 1>就会被转换为<1,1,0,1,1>。
通过这样巧妙的构造，SimHash将每个关键词的权重保留并且叠加，一直留到最后，从而使得高权重的关键词的影响能被保留。从上图中你可以看到，整个文档的SimHash值和权重最大的关键词word 2的哈希值是一样的。这就体现了高权重的关键词对文档的最终哈希值的影响。此外，SimHash通过一个简单的普通哈希函数就能生成64位哈希值，这替代了随机划分64个超平面的复杂工作，也让整个函数的实现更简单。
如何对局部敏感哈希值进行相似检索？
和其他局部敏感哈希函数一样，如果两个文档的SimHash值的海明距离小于k，我们就认为它们是相似的。举个例子，在Google的实现中，k的取值为3。这个时候，检索相似文章的问题变成了要找出海明距离在3之内的所有文档。如果是一个个文档比对的话，这就是一个遍历过程，效率很低。有没有更高效的检索方案呢？
一个直观的想法是，我们可以针对每一个比特位做索引。由于每个比特位只有0和1这2个值，一共有64个比特位，也就一共有2*64共128个不同的Key。因此我们可以使用倒排索引，将所有的文档根据自己每个比特位的值，加入到对应的倒排索引的posting list中。这样，当要查询和一个文档相似的其他文档的时候，我们只需要通过3步就可以实现了，具体的步骤如下：
- 计算出待查询文档的SimHash值；
- 以该SimHash值中每个比特位的值作为Key，去倒排索引中查询，将相同位置具有相同值的文档都召回；
- 合并这些文档，并一一判断它们和要查询的文档之间的海明距离是否在3之内，留下满足条件的。
我们发现，在这个过程中，只要有一个比特位的值相同，文档就会被召回。也就是说，这个方案和遍历所有文档相比，其实只能排除掉“比特位完全不同的文档”。因此，这种方法的检索效率并不高。
这又该怎么优化呢？Google利用抽屉原理设计了一个更高效的检索方法。什么是抽屉原理呢？简单来说，如果我们有3个苹果要放入4个抽屉，就至少有一个抽屉会是空的。那应用到检索上，Google会将哈希值平均切为4段，如果两个哈希值的比特位差异不超过3个，那这三个差异的比特位最多出现在3个段中，也就是说至少有一个段的比特位是完全相同的！因此，我们可以将前面的查询优化为“有一段比特位完全相同的文档会被召回”。
根据这个思路，我们可以将每一个文档都根据比特位划分为4段，以每一段的16个比特位的值作为Key，建立4个倒排索引。检索的时候，我们会把要查询文档的SimHash值也分为4段，然后分别去对应的倒排索引中，查询和自己这一段比特位完全相同的文档。最后，将返回的四个posting list合并，并一一判断它们的的海明距离是否在3之内。
通过使用SimHash函数和分段检索（抽屉原理），使得Google能在百亿级别的网页中快速完成过滤相似网页的功能，从而保证了搜索结果的质量。
重点回顾
今天，我们重点学习了使用局部敏感哈希的方法过滤相似文章。
我们可以使用向量空间模型将文章表示为高维空间中的点，从而将相似文章过滤问题转为高维空间的最近邻检索问题。对于高维空间的最近邻检索问题，我们可以使用非精准的检索思路，使用局部敏感哈希为高维空间的点生成低维的哈希值。
局部敏感哈希有许多构造方法，我们主要讲了随机超平面划分和SimHash两种方法。相比于随机超平面划分，SimHash能保留每一个关键词的权重，并且它的函数实现也更简单。
那对于局部敏感哈希的相似检索，我们可以使用海明距离定义相似度，用抽屉原理进行分段划分，从而可以建立对应的倒排索引，完成高效检索。
实际上，不仅过滤相似文章可以使用局部敏感哈希，在拍照识图和摇一摇搜歌等应用场景中，我们都可以使用它来快速检索。以图像检索为例，我们可以对图像进行特征分析，用向量来表示一张图片，这样一张图片就是高维空间中的一个点了，图像检索就也抽象成了高维空间中的近邻检索问题，也就可以使用局部敏感哈希来完成了。
当然基于局部敏感哈希的检索也有它的局限性。以相似文章检索为例，局部敏感哈希更擅长处理字面上的相似而不是语义上的相似。比如，一篇文章介绍的是随机超平面划分，另一篇文章介绍的是SimHash，两篇文章可能在字面上差距很大，但内容领域其实是相似的。好的推荐系统在用户看完随机超平面划分的文章后，还可以推荐SimHash这篇文章，但局部敏感哈希在这种语义相似的推荐系统中就不适用了。
因此，对于更灵活的相似检索问题，工业界还有许多的解决方法，我们后面再详细介绍。
课堂讨论
1.对于SimHash，如果将海明距离在4之内的文章都定义为相似的，那我们应该将哈希值分为几段进行索引和查询呢？
2.SimHash的算法能否应用到文章以外的其他对象？你能举个例子吗？
欢迎在留言区畅所欲言，说出你的思考过程和最终答案。如果有收获，也欢迎把这一讲分享给你的朋友。
- paulhaoyi 👍（11） 💬（1）
感觉局部敏感hash和深度学习中的embedding好相近啊，都是临近点的向量表示很相近。不知道应用中有没有相互替换的场景。
2020-04-30 - 那时刻 👍（10） 💬（1）
与simHash类似的还有个minHash，查了资料对比了下，貌似是minHash对于权重处理不是很好，而且处理时候因为要计算多个hash函数，占用更多CPU资源，而superminhash在处理速度上更胜一筹。不知理解是否正确？ 讨论问题： 1. 最开始想法是对于4位不同，采用5段分割，但是对于64bit，5段不能整除。可以增大分割的段数，可采用8段分割来计算。 2. 暂时没想到其它具体应用
2020-04-29 - 奕 👍（7） 💬（2）
对于思考题： 1：利用抽屉性原理，可以分为 5段保证，至少有一段是相等的，但是我看下面的老师评论说，最好分为 8段，但是这样的话相似度准确性是不是会降低很多？ 因为分为 8段 的话至少要有 4个是相等的， 还是分为8段的时候进行了特殊处理？ 2: 还可以对其他东西，比如图片，歌曲进行特征向量提取，再利用局部敏感哈希函数，这里还不用考虑语义上的相似
2020-05-03 - 明翼 👍（4） 💬（2）
这篇文章干货很多，这是很好的思路。说下我的理解，局部敏感hash关注点在于保持相似性的原文hash也相似，我一般用hash多是检验是否修改过了，或者判断是否存在比如布隆过滤器。谷歌的那个算法更是让我开了眼界，通过计算词的hash得到64bit序列，为叠加权重将0改成-1，我们如果不修改那和权重相乘的结果是0，叠加成文章权重的时候，权重很小的关键词和权重很大的关键词在这一位的影响是一样的了，然后将所有的关键词叠加保证了大权重关键词影响大，比如大关键词在一位中为-1，那最终结果很可能这一位为负数，最终为了方便比较可以说做了另外一个映射，映射成0和1这种64位比特流，因为这样和二进制对应。后面的海明距离的就更巧妙了，分割数据看成多个段，回答下问题吧： 1. 海明距离4为区分度，那分割成五段的话，至少有一段是完全相同的，不过这样分割不太好分割，分割成8段，我理解的过程为0-7为一组8-15 16-23一次类推分成8个组后，每个组都有8位，那每组就有16个不同的key因为2*8，后面postlist为哪些文章的哪些位对应这组key，查询文章过来后，找到相同的key的所有文章，这样我们得到8组文章，然后既然距离为4，我们可以每两个组求交集，每求三次仍然保留的满足条件，抽出来作为结果集，这个求的过程好好设计。 2. 这种算法可以用在推荐爱好相似的好友上，比如我们给用户打不同的标签，所有的标签组成一个文章，按照上述算法求相近的用户，推荐为好友；相似路径是不是可以，我们把一段距离之间的几个关键经过点标记出来作为词，然后比较相似性。图片音乐这种也适合；图书如果打上标签，或者用图书关键词也合适
2020-05-05 - 奕 👍（3） 💬（3）
每一个文档都根据比特位划分为 4 段，以每一段的 16 个比特位的值作为 Key，建立 4 个倒排索引 ------------------------------- 这里是怎么 以 16 个比特位的值作为 Key 建立倒排索引的呢？ 怎么把文档分配到这四个 posting list 中的？ 这里没有理解 还有下面的分段查询的图中，怎么每个倒排索引里面 还有以key建的倒排索引？ 这里的key是每一段的 位取值吗？0- 2^16-1 个倒排索引？
2020-05-03 - 范闲 👍（3） 💬（1）
1.距离相近的点比距离相远的点更容易发生Hash碰撞，这是局部敏感哈希的理论根据 2. LSH family有hyperplane和crosspoltye的，同样SimHash也是一种方法 3.文章中的例子都是关键词的，实际上现在可以做成embedding的比较吧，这样关键信息的丢失会更少 4.所有的ANN相关算法，都是建立在对全空间的不断划分上，将全空间划分为若干子空间，然后在子空间里搜索最近邻. 思考题目: 1.如果4位以内的不同，都可以认为比较相似，那么划分的时候64位应该划分成8段比较合适。 2.除了文章，其他的embedding的相似性求解也可以。
2020-04-29 - innocent 👍（2） 💬（1）
请问老师，业界主流的文本相似度计算就是采用局部哈希么
2020-05-14 - wangkx 👍（2） 💬（1）
通过学习这一讲，我联想到了虚拟内存到物理内存的页表映射方法。在映射时，虚拟内存的高位用于从映射到物理内存，低位作为偏移量，然后得到真实的物理地址。 老师，我联想的对吗？
2020-05-12 - Ignite 👍（1） 💬（1）
由于每个比特位只有 0 和 1 这 2 个值，一共有 64 个比特位，也就一共有 2*64 共 128 个不同的 Key。为啥是2*64而不是2^64
2021-10-12 - benny 👍（1） 💬（1）
分八段后，要找至少四段相同的吧？这块处理有啥特殊技巧？
2020-06-11 - 时隐时现 👍（1） 💬（1）
多谢老师的精彩分享，有2个小问题： 1、SimHash的前4步都可以理解，但是最后一步 “将最终得到的编码中大于 0 的值变为 1，小于等于 0 的变为 0。这样，编码 <5,1,-1,5, 1> 就会被转换为 <1,1,0,1,1>。” 似懂非懂，多少还是不太能理解，这样当真不会让最高权重的关键词影响受损吗？那么2和9，最后都变成1，感觉9"吃亏了",^—^... 2、还有1个小问题，SimHash表示的hash编码，在计算过程中，<3,3,-3,3,3>，会不会出现单个数值变成2位甚至是3位数的情况，如果会，在算法具体实现时，每个数值用1bit还是1byte来表示？
2020-05-09 - LDxy 👍（1） 💬（2）
当关键词是几万乃至百万级别时，文档的向量空间可能是一个上万维甚至是百万维的超高维空间，使用 k-d 树就更难以完成检索工作了。 ——这是不是就是万维网这个名称的由来？
2020-04-30 - armatrix 👍（0） 💬（1）
“由于每个比特位只有 0 和 1 这 2 个值，一共有 64 个比特位，也就一共有 2*64 共 128 个不同的 Key”这个应该是2^64个？
2021-10-11 - Bachue Zhou 👍（0） 💬（1）
我对局部敏感哈希还是抱有怀疑，这个和二分搜索不同，二分搜索每次比较都能排除掉一半的数据，但是随机划分超平面却不一定，可能一开始 n 较小的时候，每次划分都能排除近一半的可能，但随着 n 的提高，排除的概率越来越低，我无法计算当 n 要达到什么程度的时候，两点哈希相同距离确实较近的概率能高于百分之九十九。
2020-12-24 - 时隐时现 👍（0） 💬（1）
刚刚发了2个小问题，系统还没放出来，再追加第3个小问题，希望老师有空解答一下。 3、这种依靠关键词过滤查找相似文章的算法，能不能用到论文放抄袭上？但是一篇论文有太多的字和关键字，就算用SimHash和抽屉优化，也要对每个字或者关键字挨个比对一遍吗？有没有更优化的算法？
2020-05-09