1.高效相似度计算：局部敏感哈希算法Locality Sensitive Hashing (LSH)
高效相似度计算：局部敏感哈希算法Locality Sensitive Hashing (LSH)
前言：最近工作接触文本相似度匹配的一些任务，对于使用的一些算法补下基础知识。
一、摘要
局部敏感哈希(LSH)是一种广泛应用于近似最近邻搜索(ANN)的技术。高效相似度搜索的解决方案是有利可图的，像谷歌、档案管理系统源码Netflix、亚马逊、Spotify、优步等大公司的许多核心功能都依赖于相似度搜索。例如亚马逊使用相似度搜索来比较用户，以相似度最高的DKBY公式源码用户，根据其历史购买记录来寻找新产品推荐。
二、背景
想象一个包含数百万甚至数十亿个样本的数据集，我们如何有效地比较所有这些样本?
即使在最好的硬件上，采用穷举法比较所有数据对是不可能的，这最多产生O(n²)的搜索复杂度。即使将单个查询与数十亿个样本进行比较，我们仍然产生最多为O(n)的搜索复杂度。此外还需要考虑单个相似性计算背后的复杂度。
怎样才能避免这种情况呢？
解决方案是近似搜索 ，不采用穷举搜索，源码申请版权而是 限制搜索范围，只搜索最相关的部分。
LSH是一种为我们提供亚线性搜索时间的算法。
三、算法简介
当我们考虑寻找相似向量对的复杂性时，我们发现即使在相当小的数据集上，比较所有东西所需的计算数量也是难以想象得大。这里引入 向量索引，如果我们想要将所有这些向量相互进行比较，最佳排序方法是对数线性时间复杂度。所以我们需要一种 减少比较次数 的9牛源码方法。理想情况下，我们只想比较我们认为是潜在匹配的向量（候选对），局部敏感散(LSH)允许我们这样做。
LSH由多种不同的方法组成。在本文中，我们将介绍由多个步骤组成的传统方法——shingling、MinHashing和band的LSH函数。核心是允许对同一个样本进行分段和多次哈希，当一对向量至少被哈希到一次相同的值时，我们把它们标记为候选对（即潜在匹配的向量）。
典型的积分源码系统哈希函数旨在将不同的值放入不同的桶中，尽量减少多个键值被映射到同一个桶的可能性（即尽量减少哈希碰撞），LSH的哈希函数与其正好相反，希望将相似的值放入相同的桶中，实现最大化哈希碰撞（理想情况下只针对相似的输入，但不可避免地存在不相似的向量被标记为候选对进行minhash）。
在LSH中没有单一的哈希方法。事实上，它们都共享相同的“通过哈希函数的桶相似样本”逻辑，但它们可以有很大的不同。
四、三个步骤：Shingling, MinHashing, Band and LSH
本文探索LSH的方法包括三个步骤。首先，我们使用k-shingling(和one-hot编码)将文本转换为稀疏向量，然后使用minhashing创建“签名”，最后将签名向量传递给LSH环节以淘汰候选对。
4.1 k-Shingling
定义：k-Shingling（简称shingling）将一串文本转换为一组“shingles”的过程。这个过程类似于在我们的文本字符串中移动一个长度为k的窗口，并将每一步移动获取的k个字符 整理成去重的“shingle set”。
4.2 Minhashing
定义：在保持相相似度的情况下，Minhashing通过哈希函数将稀疏的one-hot编码向量映射到密集向量（minhash签名向量）。有了稀疏向量，我们所做的是为我们密集向量中的每个签名位置分配不同的minhash函数将稀疏向量映射到signature。
Min Hashing算法解决了前面所说的计算复杂度：它通过将向量A、B映射到低维空间中的两个签名向量，并且近似保持A、B之间的相似度，降低了用户相似度在高维下的计算复杂度。
4.3 Band 和 Hash
我们将对LSH采用banding方法——它将获取我们的签名，对每个签名的片段进行哈希，并查找哈希冲突，将具有一些相似性的签名哈希到同一桶中，从而将其标识为候选对。
定义：banding方法通过将密集向量分成b个子向量，通过相同的哈希函数处理每个子向量并映射到一个哈希桶中，两个向量的子向量匹配，我们将各自的完整向量视为候选对。
例如，想象一下，我们把一个维的向量分成个片段，这给了我们次机会来识别两个向量之间匹配的子向量。但这也增加了误报的数量(我们标记为候选对的样本，它们实际并不相似)，但是我们会尽量减少这些问题。
五、优化Bands
假设我们将signature向量分为[公式] 个band，每个band的大小为 [公式] ，两个用户向量之间的Jaccard相似度为 [公式] ：
这个概率在[公式] 和 [公式] 取不同值时总是一个S形的曲线（这个S形曲线的特点在于，当 [公式] 超过一个阈值之后，两个用户成为candidate的概率会迅速增加并接近于1。这个阈值就是概率变化最陡的地方，近似为[公式] ）；
上面的例子中[公式] ， [公式] ，可视化当前的概率值 [公式] -是否候选集 [公式] 之间的关系，我们注意到一个模式：虽然这种对齐并不完美，但我们可以看到理论计算的概率 [公式] 与真正的候选配对结果之间的相关性。
现在，我们可以通过修改[公式] 来推测具有不同相似性分数的候选对的返回概率，通过优化 [公式] 值来移动LSH函数的相似性阈值。
增加[公式] 值提供更多的子向量部分哈希碰撞的可能性更大，返回更多的候选对，将导致更多的误报（FP），也会减少一些漏网之鱼（FN）.
六、源码
Github源码： github.com/topics/local...
Scala中基于Jaccard 距离的LSH相似度计算代码： spark.apache.org/docs/3...
七、参考
参考： Locality Sensitive Hashing (LSH): The Illustrated Guide | Pinecone
参考： hunter7z：大规模数据的相似度计算：LSH算法
参考： allen：一文纵览KNN（ANN）向量检索
