Lsh( Locality Sensitive Hashing)

LSH(Locality-Sensitive Hashing) #

Date: 2015/7/25

LSH可看作是一种降维的方法，将图片映射到一组不长的hash码中，以hash码代码图片的像素特征，在上面做类似KNN的相似图片查询。

LSH的一个基础结构是满足下面两个条件的hash函数：

  • 如果$d(x, y) \le d1$, 则$h(x)=h(y)$的概率至少为$p1$;
  • 如果$d(x, y) \ge d2$, 则$h(x)=h(y)$的概率至多为$p2$;
    LSH称上述的hash函数为$(d1,d2,p1,p2)$ - sensitive

由上述基本结构，可以生成LSH family，简单的说，是可以通过一定的变化，使d1, d2, p1, p2做一些定向的改变。LSH family

  • Jaccard distance： $(d1, d2, 1-p1,1-p2)$ - sensitive

  • Hamming distance： $(d1,d2,1-d1/d,1-d2/d)$ - sensitive

  • Cosine distance： $(d1,d2,(180-d1)180,(180-d2)/180)$ - sensitive

  • normal Euclidean distance： $(a/2,2a,1/2,1/3)$ - sensitive

  • AND操作

  • OR操作

LSH在查找中的应用 #

目前就理解到一种方法：将样本扔到桶里去，比如生成L位的hash，那么就有了$2^L$个桶，将待查样本转化为hash后，直接去对应桶中遍历找出前K个相似的样本即可。桶中样本可再次使用hash或别的方式查找。
使用这种Hash方式查找最近邻，可降低查找样本数，分为了$\frac{1}{2^L}$

Categories: 图像查找