增强LSH

　　通过LSH hash functions我们能够得到一个或多个hash table，每个桶内的数据之间是近邻的可能性很大。我们希望原本相邻的数据经过LSH hash后，都能够落入到相同的桶内，而不相邻的数据经过LSH hash后，都能够落入到不同的桶中。如果相邻的数据被投影到了不同的桶内，我们称为false negtive；如果不相邻的数据被投影到了相同的桶内，我们称为false positive。因此，我们在使用LSH中，我们希望能够尽量降低false negtive rate和false positive rate。

　　通常，为了能够增强LSH，即使得false negtive rate和/或false positive rate降低，我们有两个途径来实现：1）在一个hash table内使用更多的LSH hash function；2）建立多个hash table。
　　下面介绍一些常用的增强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概率，即降低了falsenegtiverate。

　　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。
　　除了上面介绍的增强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 = h1*r1 + h2*r2 + ... + 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

巴特西

增强LSH

最新文章

热门文章