局部敏感哈希LSH(Locality Sensitive Hashing)
LSH(Locality Sensitive Hashing)
- 一、locality-sensitive hashing (LSH)
- 二、汉明距离
- 三、欧几里得距离
- 四、Jaccard系数
- 五、参考资料
在众多领域中，在海量数据库中检索与查询数据高度相似的数据是一项至关重要的任务。例如，在图像检索领域中，则需要从数据库中检索出与查询图像高度相似的图片；又比如在3D维重建和 视觉SLAM等问题中，则需要在三维点云模型（数据库）中找到与查询描述子最接近的描述子以实现特征匹配。这个问题通常被称为近似近邻搜索问题（Approximate Near Neighbor）。值得注意的是，在处理的数据量非常大（百万级别以上）时，并非线性查找是不可行的；而kd-tree算法是一种高效的方法；然而，在数据维度较高的情况下（超过30维），kd-tree算法的表现会显著下降；对于高维空间中的海量近邻搜索问题而言，则局部敏感哈希算法提供了一种非常有效的解决方案。
该局部敏感哈希方法是一种技术，在应用于不同数据的距离测量方式时会体现出显著的特性。具体而言，在评估两个数据间的相似程度时（相似性往往与两者之间的距离呈负相关关系），所需计算的衡量标准也会有所不同。因此，在这一领域中需要采用相应的算法来进行处理。接下来我会先对局部敏感哈希方法进行总体介绍，并随后深入探讨在不同距离度量空间下的具体实现情况。涵盖的内容包括Hamming距离、欧几里得距离以及Jaccard系数等指标。
如上图所示为一个图片检索案例，在应用LSH技术时可以在海量数据库中高效地实现对所查询图片的快速检索。
一、局部敏感哈希LSH
先来说说哈希Hash。在计算机科学领域中, 哈希是通过构建一个具有特定属性的哈希函数（Hash function）, 将输入的数据（通常为任意长度的信息）转换为固定长度的输出值, 这些固定长度的输出值我们称为哈希值（hash value）或者杂凑值（message digest）。这种转换过程使得我们可以利用其内部结构特点使得查找效率得以显著提升。具体而言, 哈希表（Hash Table）就是一种基于这种原理的数据存储结构, 它能够快速地根据给定的关键字找到对应的存储位置, 这一特性使得在大数据场景下实现高效的查找操作变得可能。然而, 在实际应用中, 由于各种因素的影响, 我们的算法设计往往需要权衡多方面的性能指标, 因此选择合适的哈希函数方案就显得尤为重要了。
局部敏感哈希（LSH）的基本思想是：在高维度数据的空间中存在两个接近的数据样本，在经过映射处理后会进入到一个较低维度的空间，并且这两个样本仍然会保持较高的相似度；另一方面，在该较低维度的空间中，并不会出现原本在高维度空间中并不接近的两个样本之间的相似度降低的现象。基于这一特性，在处理后的低维度表征中我们可以通过某种方式快速定位邻近的对象，并且这种定位过程相比直接在原始高维度表征中的搜索效率有着显著提升。
局部敏感哈希定义：
此哈希函数族当且仅当满足以下条件时被称为满足(R, cR, P_1, P_2)-敏感性。对于任意两个点 p,q\in\mathbb R^d：
为了让局部敏感哈希函数族起作用，需要满足 c>1，P_1>P_2.
为了更好地理解这一概念，请考虑两个二进制数据点p, q。每个比特位都有两种可能的状态：0或1。它们之间的距离可通过Hamming距离进行计算，即为不同比特位的数量。
为此我们采用一种基本的设计方案——一种哈希函数族H。每一个哈希函数都是通过随机选择一个特定位置上的值来实现映射的，并且满足对于任意d维向量x \in \{0,1\}^d有h_i(x) = x_i。
在这种情况下如果我们随机选取一个哈希函数h \in H那么h_i(p)将返回p中第i个比特的位置值。
根据这一特性我们可以推导出概率关系：
P_r[h(p)=h(q)] = \frac{\text{相同的位置数}}{d} = 1 - \frac{R}{d}
同理当比较k=2个独立选取的结果时有：
P_2 = 1 - c\frac{R}{d}（其中c > 1）
这表明所构造出的哈希族具有局部敏感性！[1]
Emdedding:
在前面阐述的例子中，由于数据本身就是二进制形式，在计算相似性时直接采用Hamming距离作为计算手段。然而，在最开始提出局部敏感哈希（LSH）方法时，在当时的方法设计中还伴随着一种必要的处理步骤——Embedding操作的存在。这一特性使得LSH方法在初期设计时就具备了相应的处理能力。
在哈希之前，LSH首先要将数据从L1准则下的欧几里得空间嵌入到Hamming空间。然而，在L2准则下的欧几里得空间无法直接嵌入到Hamming空间中。当执行此嵌入操作时，默认假设原始点在L1准则下的表现与L2准则下的表现基本一致，即欧氏距离与曼哈顿距离之间的差异可以忽略不计。
Embedding算法：
- 首先找出所有坐标值中的最大数值C；
- 对于每个点P而言,P=(x₁,x₂,…,x_d)，其中d表示数据的空间维度；
- 将每一维的数据x_i转化为长度为C的一个二进制向量，在该向量中前x_i个元素取值为1,其余元素取值为0；
- 接着将各个维度对应的二进制向量串联起来,从而得到一个新的向量。
值得指出的是，在该操作中（或称该过程中的）数据经过...变换前后任意两个点的距离均保持不变。
概率放大：
两个概率分布P₁和P₂之间的差异较小，在实际应用中通常会通过增加哈希键长度k以及构造L个不同的哈希表来提升两者的差异度。通过构建多个哈希表并进行查询操作后筛选出候选样本集合S，并对这些候选样本进行线性搜索。只要至少存在一个哈希表能够成功匹配到真实近邻，则整个系统就能可靠地找到近邻。具体而言，在映射之后这些点具有相同的指纹值；而对于那些位于cR以外区域内的点则会被映射到不同的指纹值域中。
想要的概率曲线
单个哈希的概率曲线
b个哈希表、哈希键长度为r时的概率曲线
我们选择参数k和L，在该系统中存在一个由多个哈希函数组成的族族族族族族族族族族族族族族族其中对于每个t∈{1,2,…,k}以及j∈{1,2,…,L}的值对应的单个哈希函数h_{t,j}(q)构成了该系统中的一个完整的哈希结构系统系统系统系统系统系统系统假设每个哈希函数h_i都是独立且随机选取的当这些条件满足时则使用m个双 Hash 表来提高近邻搜索的成功概率至至少 1−(1−P₁ᵏ)ᴸ
关于选择方案的说明，请可参考斯坦福课件中的相关内容[3]。为了便于理解，请通过以下表格简要说明：如表所示，在取k=4,L=4时（其中k,L分别表示...），对于不同的概率值p, 计算结果如下：当概率p取值较大时（如p=0.9），计算结果为约...；而对于概率较小的事件（如p=0.5, 1-(1-P_1^k)^L≈...), 计算结果则大幅下降至约...。这样的变化趋势表明，在实际应用中我们应选择较大的k, 以获得更为理想的结果
搜索近似最近邻：
在实施近似最近邻搜索的过程中, 通过选定的哈希函数将数据映射到相应的空间中, 针对每一个构建好的哈希表, 提取落入其对应的哈希桶内的所有样本, 并对所有构建好的哈希表均进行该操作, 最后通过线性扫描以获取候选样本集
总结一下，就是如下步骤：
二、Hamming距离
在匹配图像时通常会将图像的特征向量与数据库中的特征向量进行对比以实现匹配。实时场景中常用二进制特征指针（BIREF）、比尔士克（BRISK）和奥布罗姆（ORB）等来表示物体特征。计算两个二进制字符串之间的差异程度通常采用汉明距离。以下将详细阐述基于汉明距离的局部敏感哈希方法及其应用。
如前所述，在处理二进制描述子时
三、Euclidean距离
对于欧式距离，参考E^2LSH，基于p-stable distribution的LSH（有时间再补上）
四、Jaccard 系数
LSH也可以用于检索相关网页和文章，在这种情况下，我们采用Jaccard系数作为衡量网页和文章之间相似程度的指标。
Jaccard系数用于衡量两个集合间的相似程度；数值越大表示相似程度越高。
考虑有两个集合S_1和S_2；其Jaccard系数即被定义为：
|S_1 \cap S_2| / |S_1 \cup S_2|
举例说明：设S_1 = \{A, B, C\} 和 S_2 = \{B, C, D\}；
则s = 3/5
上图是一个总体的流程图，分为三步:
第一步就是将一个文档转换为关键词汇的集合体。
第二步就是通过MinHashing函数构建哈希表。
第三步就是采用LSH算法来查找相似文档。
这里主要对MinHashing进行介绍。更多细节还是请看斯坦福的课件[3]。
在查询文档的过程中，在先对每个待处理文本进行Shingling处理后会生成一个由词构成的集合，并将其与数据库中的所有索引项结合在一起形成一个数据结构；该结构在高维度空间中呈现极稀疏特征；由于直接处理这样一个高维度数据会导致计算资源的巨大消耗；因此为了减少计算负担需要对其进行降维处理；这一步骤采用的技术称为MinHashing；经过MinHashing处理后生成的新签名矩阵具有显著降维效果；同时确保每个签名仍然对应于原始数据库中的某个具体索引项；随后的操作流程与之前的方法完全一致；最后通过利用局部敏感哈希算法可以在较短时间内完成相似文本匹配任务
这里存在一个关键点需要注意，在进行MinHashing操作后不会改变数据间的相似度值这一特性得以保持；这是因为通过构建低维表示的空间结构能够有效保留原始数据之间的相关性信息；从而确保低维Signature矩阵中的相似列反映原始高维空间中的对应关系；这样就能使得这种哈希方法属于局部哈希函数族
那么MinHashing是怎么做的呢？
在图中用白色框标出的区域是一个输入矩阵，在这个矩阵中每个列表对应一个文档，而每一列代表一个关键词。其中哈希函数定义为h_π(C)=min{π(C)}。随后定义了一个排列操作(Permutation π)，该操作将原始矩阵中的某些行进行交换。例如第一个被标记为咖啡色的排列其序列值是{2,3,7,6,1,5,4}，这表示新的排列后的矩阵中的每一行都是从原始矩阵中的哪一行取来的。经过这样的操作后，在排列后的每一列中第一个出现1的位置所对应的行号即为该列的值。这样每次排列都会生成一个新的行向量如图所示，在本例中咖啡色排列得到的结果向量是{2,1,2,1}。如果进行N次这样的排列操作，则会得到一个N行的新矩阵，在此过程中每一步都会生成一个新的结果向量最终形成所需的签名矩阵Signature Matrix
在右下方部分中比较了原矩阵与Signature矩阵各列之间的相似度。观察结果表明这两个矩阵各列间的相似程度较为接近。实际上，在概率论框架下可以证明两者具有相同的性质。
我们可以直接定义\pi(y)为\pi(C₁∪C₂)的最小值。因此可以推断出点y必定位于集合C₁或集合C₂中的一个位置关系上。由此可知，两个集合交集的概率即为Pr(y∈C₁ ∩ C₂)。这等价于概率值等于两个集合交集元素数量除以并集元素数量。
换个角度理解，对于的行分为三种：
类X: 两个列的值都是1；
类Y: 一列是1，另一列是0；
类Z: 两个列的值都是0；
因为稀疏矩阵的性质决定了其中绝大多数元素属于类别，在经过随机重排行之后，在从上至下的顺序中，在首次遇到类别时先出现另一个类别的概率为\frac{\|\mathbf{X}\|\,}{\|\mathbf{X}+\mathbf{Y}\|\,}。这种情况下最先出现的列类型表明这两个类别在排列后的最小高度相等。进一步地可知：由于\|\mathbf{X}\,\|= \|C_{1} \cap C_{2}\,\|且\|\mathbf{X}+\mathbf{Y}\,\|= \|C_{1} \cup C_{2}\,\|因此我们能够得出结论：概率值即为两个类别的交集大小与并集大小之比即\frac{\|\mathbf{X}\,\|\,}{\|\mathbf{X}+\mathbf{Y}\,\|\,}= \frac{\|(C_{1} \cap C_{2}) \|}{( \|C_{1} \cup C_{2}) \|}同样地我们还能够得出：两个类别在排列后最先出现相同最小高度的概率即为上述计算结果即\Pr[\min(\pi (C_{1}))=\min(\pi (C_{2}))]= \frac{\|\mathbf{X}\,\|\,}{( \| X + Y ) }= \frac{( \| C_{1} \cap C_{2}) \|)}{( \| C_{1} \cup C_{2}) ) }
对于式子，右边就是的Jaccard系数！即证明了Pr[min(\pi (C_1)=min(\pi (C_2))] = sim(C_1, C_2)
到目前为止已经实现了第一步。在后续步骤中对Signature矩阵的操作与之前的讲解具有相似性。其核心机制均通过AND运算与OR运算来优化概率差异从而构建所需概率曲线。值得注意的是尽管整体思路存在相似之处但具体的实施细节稍有不同。
首先通过对大量变异操作生成一个规模充分大的Signature矩阵，并将其划分为多个部分（即Bands），其中总共有B个Bands。经过上述过程后总共进行了r \times b次变异操作，并最终生成了一个具有M行的Signature矩阵。通过MinHashing算法对每个Bands分别进行哈希处理，则可获得b个哈希表。
五、参考资料:
[1] Andoni和Indyk提出了在高维空间中实现近似最近邻搜索的最优哈希算法。
[2] Gionis、Indyk和Motwani开发了一种基于哈希技术的有效相似性搜索方法。
[3] Stanford大学CS246课程中有关于LSH章节的学习资料可参考http://cs246.stanford.edu。
[4] Datar、Immorlica、Indyk等人设计了一种基于p-稳定分布的概率分布模型来进行局部敏感哈希。
[5] E2LSH软件的手册详细介绍了相关技术参数与操作方法。
[6] Slaney和Casey教授在《Finding Nearest Neighbors》一书中系统阐述了局部敏感哈希方法及其应用实例。