LSH技术---Finding Similar Items
参考上一篇博客 k-shingles与minhash技术，我们可以采用minhash技术来缩减内容规模较大的文档集合。然而，在这些大规模的文档集合中进行任意两个文档之间的相似性计算仍然相当复杂。由于这样的两两组合对数非常大，在实际应用中往往只需要关注那些具有最相似度值的 document pairs，并不需要穷举所有的对比对数非常大的部分。因此我们可以采用 locality-sensitive hashing (LSH) 技术来实现这一目标。
LSH的基本思想
在原始数据空间中取两个相邻的数据点并施加同样的映射处理后，在新的数据空间中这两个数据点仍然保持相邻的概率较大；而若相似度较低的数据对被映射到同一个桶中，则这种概率会显著降低。换言之，在经过某种哈希映射操作后我们希望原本相邻的数据能够被分配至同一个桶内且具有相同的哈希值标识。基于此LSH算法的核心在于为特定相似度计算方法寻找一种满足上述特征的哈希函数集合如果能够寻找到这样一组具有优良特性的哈希函数那么我们就可以将原始数据空间中的近邻查找问题转化为高效的桶内匹配问题具体步骤如下：首先将查询对象进行哈希编码得到对应的桶号然后检索该桶号下所有存储的对象再从这些候选对象中逐一比对即可实现近邻匹配这一流程大大简化了高维空间中的近邻搜索过程同时有效降低了计算复杂度然而需要注意的是当相似度较低的数据对被错误地分配至同一桶时这会导致假阳性率上升反之若真正具备高相似度的数据对却被分配至不同桶则会导致假阴性率上升因此我们的目标应当是尽可能地减小这两种误差的发生概率以达到更高的搜索准确性
LSH直观解释
locality sensitive的特性：接近的数据样本会被哈希函数分配到相应的哈希桶中（在高概率下）
在图中展示了红色圆圈和黄色圆圈这两个元素群组来表示二维空间中的数据点集合。随后通过LSH方法计算这些数据点对之间的余弦相似度作为衡量标准。随后随机生成了一组垂直超平面将这些数据集进行分割处理。具体而言若某数据点位于该超平面之上区域则赋予其0值对应白色标记否则赋予1值对应黑色标记这样的二进制分类方式能够有效地区分不同类别间的差异特征进而生成一个二进制特征向量来表征原始数据的空间分布情况
基于上图所示，在编码过程中仅需6bits即可表示两个数据点。这正是原始数据经过LSH处理后的哈希值。它们的哈希签名仅有一位差异；因此其海明距离为1；基于其长度计算，则可据此计算两向量之间的夹角余弦相似度
Banding技术
通过minhash算法生成的signature矩阵被划分为b个带状块, 每个带状块包含r行数据.随后, 使用哈希函数将每个带状块中的每一列映射到一个非常大的哈希表中.只要哈希表中的桶数量足够多, 从而导致地址冲突的概率非常低.
解释banding技术：
假设存在b个bands, 每个band包含r rows, 并设定其Jaccard similarity系数为s, 则这两篇特定的文档被映射至同一个hash bucket的概率即为:
1 −(1 − sr)b
给定一个特定的band，在同一 band 的所有列上完全一致的概率是 sr；而两个文档在同一 band 上至少有一列不同的概率是 1−sr；因此，在至少存在一个 common band 的情况下两个文档被映射到同一个桶中的概率是 1−(1−sr)^b 即为目标事件发生的总的概率
假设有一百万份文件和一千个signatures（行数），这些数据集占用空间约为4GB。设置参数b设为2...r设为5后，在计算查询结果时会自动识别出与查询结果最相关的文件集合，并确保其相似度至少达到s=...的比例。
基于计算相似度SIM(C₁,C₂)=0.8，则向量C₁与C₂必然落入同一个hash bucket（即存在一个公共的带b），使得它们在该带中的相似度达到(SIM(C₁,C₂))⁵= (0.8)⁵= 0.328的概率）。因此，在所有B=2₀个带中都完全不同的概率则为(1 - ( SIM(C₁,C₂)^5 ))^B ≈ ...
假设两个向量之间的相似度SIM(C1,C2)被设定为 SIM(C_1, C_2) = 0.3 , 那么C₁和C₂应该被分配到不同的hash桶中（即每个桶都是独特的）。在这种情况下, C₁和C₂在一个特定的桶中出现相同的概率为( SIM(C_1, C_2))^5 = 0.3^5 = 0.9576? 不过实际上我们需要计算的是在每一个特定的桶中相同的可能性, 因此正确的计算应该是: 在每一个特定的桶中相同的可能性是( SIM(C_1, C_2))^5 = ( SIM(C_1, C_2))^5 = ( SIM(C_1, C_2))^5 = ( SIM(C_1, C_2))^5? 这样经过计算，在这 二十 个桶中至少存在一个重叠的概率值为 1 - (1 - ( SIM(C₁,C₂))^5)^{二十} ≈ 98\% ? 这意味着false positive的发生率非常高
参数的选择
1. minhash的个数n
2. b个bands
3. 每个band中r行
如何选择合适的n、b、r是的false negative和false positive下降？
只有1个band和1行：
LSH Family
文中提到，在寻找一些哈希函数的过程中，
经由它们实施哈希映射转换，
可以使原始空间中相邻的数据项落入同一个桶内。
这些函数必须具备什么特性才能让原本相邻的两个数据项在哈希转换后进入同一个桶呢？
这些函数必须满足以下两个条件：
首先，
对于所有的i,j属于集合S，
只要它们之间的距离满足||xi−xj||≤Δ，
就必然存在一个k属于{1,…,K}，
使得h_k(xi)=h_k(xj)；
其次，
对于所有的i,j不属于集合S，
只要它们之间的距离大于Δ（即||xi−xj||>Δ），
就必然存在一个k属于{1,…,K}，
使得h_k(xi)≠h_k(xj).
1）如果d(x,y) ≤ d1， 则h(x) = h(y)的概率至少为p1；
2）如果d(x,y) ≥ d2， 则h(x) = h(y)的概率至多为p2；
其中d(x,y)代表x与y之间的距离，并且满足d_1 < d_2。对于x与y施加哈希变换后得到h(x)与h(y)。若能满足这两个前提条件，则这些哈希函数即被称为(d_1, d_2, p_1, p_2)-敏感函数。基于上述定义的方法即为局部敏感哈希技术。
d(x,y)可被视为衡量x与y之间差距的一种指标，在计算两者的差异程度方面发挥着重要作用。然而，并非所有类型的distance metrics都能对应于具有locality-sensitive性质的hash functions。接下来将列举不同distance metrics各自对应的具有locality-sensitive特性的hash functions。
1. Jaccard距离
其距离度量可被视为与Jaccard相似性的补集。同时常用于评估两个集合间的相似程度。此外其对应的LSH方案为minhash编码，在参数空间中满足(d₁,d₂, 1−d₁, 1−d₂)敏感度要求
2. Hamming距离
Hamming测度：两个具有相同长度的向量中各对应分量之间取值不同的数量。其对应的哈希函数H(V)等于向量V第i个分量的值，并满足参数(d₁,d₂, 1−d₁/d, 1−d₂/d)下的敏感性要求。
3. Cosine距离
余弦距离通常用于衡量两个向量之间的夹角；当夹角较小时，则表明这两个向量较为接近或相似。余弦相似度对应的LSH函数定义为H(V)=\text{sign}(V\cdot R), 其中R代表一个随机向量。V\cdot R即为将V向R方向上的投影操作, 其敏感度主要取决于d_1,d_2以及(\frac{180-d_1}{180}), (\frac{180-d_2}{180})这两个因素。
4. 正规化的欧式距离
欧式距离是用来评估d维空间中任意两点之间距离的一种度量方法。其对应的局部敏感哈希函数（LSH）定义为H(V) = |V·R + b| / a，在其中R表示一个随机向量；a表示桶的宽度；b则是在区间[0,a]上均匀分布的一个随机变量；而V·R这一项则相当于将V沿着R方向进行投影操作，并且该操作具有(a/2, 2a, 1/2, 1/3)-敏感性特征。
旨在减少false negative和false positive的可能性，则应通过加强LSH的效果来实现这一目标：首先，在一个hash table中增加更多类型的LSH函数；其次，构建多个独立的哈希表。
下面给出一些常用的增强LSH的方法：
1. 使用多个独立的hash table
每一个哈希表都由k个LSH函数构成，在每次选择时，从同一个LSH函数家族中选取k个函数即可生成一个哈希表。通过反复操作，则可构建多个这样的哈希表。这些哈希表的主要优势在于显著降低了false positive率。
2. AND操作（like “rows in a band”）
从同一组LSH函数族中选择k个特定的LSH函数，在这种情况下,H(X)=H(Y)仅在满足所有k个Hi(X)=Hi(Y)的前提下才会成立；换句话说,仅当这两个数据在所有k个哈希函数下的结果完全一致时才会被映射到同一个桶中,如果有任何一个哈希不满足就不会落在同一个桶里。通过AND操作,在保持较高概率的同时降低了false negative的概率。
3. OR操作（like “many bands”）
从同一组LSH函数族中选出k个LSH函数，在这种情况下只有当至少有两个Hi(X)等于Hi(Y)，才会导致X和Y被映射到同一个桶内；而如果在这k个哈希值中没有任何两对及以上相同，则X和Y不会被映射到同一个桶内。OR运算能显著提升精确率（接近1），同时降低误报率
4. AND和OR的级联
通过连续应用AND操作和OR操作进行级联处理，能够生成更多的哈希表。这种做法的好处是可以让p₁趋近于1的同时让p₂趋近于0。
参考资料：
LSH Algorithm and Implementation (E2LSH)
A comprehensive understanding of Locality Sensitive hashing(LSH) involves exploring its theoretical foundations and practical applications. LSH: A method for efficient similarity search in high-dimensional spaces, it operates by mapping high-dimensional data points into a set of hash tables while preserving the proximity relationships between them. This technique is particularly valuable in scenarios where exact matches are computationally prohibitive, offering a probabilistic approach to approximate nearest neighbor searches. By leveraging carefully designed hash functions, LSH significantly reduces the computational complexity associated with similarity-based operations on large datasets.