您的位置: 首页  >  文章  >  LSH局部敏感哈希的知识入门（概念、方法）

LSH局部敏感哈希的知识入门（概念、方法）

分类: 文章 • 2024-05-13 17:24:16

LSH局部敏感哈希的相关知识

LSH的知识入门

LSH（Local Sensitive Hash）的基本思想是
将原始数据空间中的两个相邻数据点通过相同的映射或投影变换（projection）后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。
我们希望原先相邻的两个数据能够被hash到相同的桶内，具有相同的桶号。对原始数据集合中所有的数据都进行hash映射后，我们就得到了一个hash table，这些原始数据集被分散到了hash table的桶内，每个桶会落入一些原始数据，属于同一个桶内的数据就有很大可能是相邻的，当然也存在不相邻的数据被hash到了同一个桶之中（false positive）。

我们需要 hash functions，使得经过 hash functions的哈希映射变换后，原始空间中相邻的数据落入相同的桶内的话，那么我们在该数据集合中进行近邻查找就变得容易了，我们只需对查询数据（就引出query的概念）进行哈希映射得到其桶号，再取出该桶号对应桶内的所有数据，然后进行线性匹配即可查找到与查询数据相邻的数据。

LSH的hash functions与一般哈希函数不同的是位置敏感性，也就是散列前的相似点经过哈希之后，也能够在一定程度上相似，并且具有一定的概率保证。

LSH能用来作什么

LSH局部敏感哈希，用于解决在高维空间中查找相似节点的问题。如果直接在高维空间中进行线性查找，将面临维度灾难，效率低下，LSH的作用就是把原来高维空间上的点都映射到一个或多个hashtable的不同的位置上，这个位置术语上称作桶(buckets)。它映射的原则是：原来在高维空间中就很接近的点，会以很大的概率被映射到同一个桶中。

简单来说，可以这么理解，你建立了L个hash table ,每个哈希表肯定是由K个哈希函数来对数据进行映射至桶buckets内的，如下图，出自论文Fast and Accurate Stochastic Gradient Estimation

LSH局部敏感哈希的知识入门（概念、方法）
图7显示了哈希表的可视化。直观地说，元哈希函数(meta hash)使bucket稀疏，并减少误报次数（false positives），因为只有有效的最近邻项才可能匹配给定查询（query）的所有K个哈希值。L个桶（bucket）的并集通过增加可能包含有效近邻项的潜在的桶（bucket）的数量来减少假否定（false negatives）的数量。

补充知识：如果相邻的数据被投影到了不同的桶内，我们称为false negtive；
如果不相邻的数据被投影到了相同的桶内，我们称为false positive。因此，我们在使用LSH中，我们希望能够尽量降低false negtive rate和false positive rate。

part1：常用的增强LSH的方法(我目前接触了才是前两个)

  1. 使用多个独立的hash table
    每个hash table由K个LSH hash function创建，每次选用K个LSH hash function（同属于一个LSH function family）就得到了一个hash table，重复多次，即可创建多个hash table。多个hash table的好处在于能够降低false positive rate。
  2. AND 与操作
    从同一个LSH function family中挑选出K个LSH function，H(X) = H(Y)有且仅当这k个Hi(X) = Hi(Y)都满足。也就是说只有当两个数据的这K个hash值都对应相同时，才会被投影到相同的桶内，只要有一个不满足就不会被投影到同一个桶内。
    AND与操作能够使得找到近邻数据的p1概率保持高概率的同时降低p2概率，即降低了false negtive rate。
  3. OR 或操作
    从同一个LSH function family中挑选出k个LSH function，H(X) = H(Y)有且仅当存在一个以上的Hi(X) = Hi(Y)。也就是说只要两个数据的这K个hash值中有一对以上相同时，就会被投影到相同的桶内，只有当这k个hash值都不相同时才不被投影到同一个桶内。
    OR或操作能够使得找到近邻数据的p1概率变的更大（越接近1）的同时保持p2概率较小，即降低了false positive rate。
  4. AND和OR的级联
    将与操作和或操作级联在一起，产生更多的hahs table，这样的好处在于能够使得p1更接近1，而p2更接近0。

part2：
除了上面介绍的增强LSH的方法外，有时候我们希望将多个LSH hash function得到的hash值组合起来，在此基础上得到新的hash值，这样做的好处在于减少了存储hash table的空间。

  1. 求模运算
    new hash value = old hash value % N
    2. 随机投影
    假设通过k个LSH hash function得到了k个hash值：h1, h2…, hk。那么新的hash值采用如下公式求得：
    new hash value = h1r1 + h2r2 + … + hk*rk，其中r1, r2, …, rk是一些随机数。
    3. XOR异或
    假设通过k个LSH hash function得到了k个hash值：h1, h2…, hk。那么新的hash值采用如下公式求得：
    new hash value = h1 XOR h2 XOR h3 … XOR hk

ps:以我学习上述提到的那篇论文，作者的源程序是在用随机投影法（SRP）进行哈希数据表的数据插入的。

通过建立Hash Table的方式我们能够得到O(1)的查找时间性能，其中关键在于选取一个hash function，将原始数据映射到相对应的桶内（bucket, hash bin），例如对数据求模：h = x mod w，w通常为一个素数（这也可以看成在对初始化后的哈希表进行数据插入）。
在对数据集进行hash（通俗想成在数据插入） 的过程中，会发生不同的数据被映射到了同一个桶中（即发生了冲突collision），这一般通过再次哈希将数据映射到其他空桶内来解决。这是普通Hash方法或者叫传统Hash方法。

但LSH与传统哈希的思想有些不同之处，他是希望原来高位相邻的点在哈希后仍然相邻（体现在被映射到了一个桶中）。注意L个哈希表是想降低false positive rate。

如有问题，欢迎大家指正。

相关推荐