局部敏感哈希算法介绍

局部敏感哈希函数的服从如下两个条件:

• 如果 d(x,y) ≤ d1， 则 h(x) = h(y) 的概率至少为 p1
• 如果 d(x,y) ≥ d2， 则 h(x) = h(y) 的概率至多为 p2
• 这两个条件正是对之前提到局部敏感哈希函数的性质的约束，意义也比较容易理解

局部敏感哈希算法的大致运行过程

• 构建索引集

  • 因为单个哈希哈数的区分能力不强（即p1与p2的差距不足够打），所以一般构造L个局部敏感哈希函数，每个局部敏感哈希函数含有K个不同的符合约束条件的哈希函数（相当于做物理实验为了减小误差，进行多次重复实验）

  • 具体实现过程：一个高维的数据点X经过一个局部敏感哈希函数 g_i 映射为 K 维的哈希码（且 K 要远小于 X 本身的维数），哈希码就是 g_i 的每一个哈希函数 h_i 将 X 映射到的那个数值组成的坐标序列，而具有相同的哈希码的数据点分布在相同的哈希桶内（即将两个数据发生哈希冲突视为两者相似同类）
    g_i(X) = (h_1(X), h_2(X), ..... , h_k(X))

  • 通过测试集的测试来决定 L 与 K 的具体数目，来达到良好的查询效果 （即训练学习）

• 实际查询过程

  • 将查询数据经过局部敏感哈希函数映射得到相应的哈希码
  • 依据哈希码，取出相应桶中的数据
  • 线性检索数据中与查询数据最接近的一个或多个数据，返回结果

• 常用的相似度计算方法介绍

  • 欧式距离（即常用的坐标差平方和开根号）d = \sqrt{(x_1-x_2)^2 +(y_1 - y_2)^2}
  • Jaccard 距离：其值为 1 - Jaccard 相似度，而 Jaccard 相似度则是被用于比较两个集合之间的相似度，Jaccard = \frac{|A\cap B|}{|A\cup B|}
  • 余弦距离：在欧式空间与离散型欧式空间中有效，视一个向量和它乘以一个常数后的向量为同一个向量，则不同的向量之间的余弦距离被定义为两个向量之间的夹角中较小的那一个（即为锐角的那一个）
  • 汉明距离：给定一个向量空间，汉明距离被定义为两个向量之间它们坐标不同的数目，汉明距离常用于二进制向量空间中（即坐标由 0，1 构成）
  • 曼哈顿距离：即 L_1 范数距离 \sum_{1}^{n} |x_i - y_i|

• 基于汉明距离的局部敏感哈希函数

  • 将给定的数据集（欧式空间下的且进行了非负化后）映射到汉明向量空间中

• 记数据集 P 中所有点的坐标中最大值为 C，则对 P 中任意一点 p=(x_1, x_2, ... ,x_n) (0 \leq x_i \leq C)

• 则 p 在汉明空间下的二进制表示为 p= Unary_C(x_1)Unary_C(x_2)..Unary_C(x_n) ，其中 Unary_C(x_i) 为二进制编码，前 x_i 位为 1，后 C - x_i 位为 0（类似于汉明码）

  • 定义如下汉明哈希函数
    h(x)= \begin{cases} 0& \text{p 的第 r 位为 0}\\ 1& \text{p 的第 r 位为 1} \end{cases}
    其中 r 服从 [0, nC] 均匀分布的随机变量，故该函数下，P(h(x)=h(y)) = \frac{nC - d}{nC} 即其敏感性为 (r_1, r_2, \frac{nC - r_1}{nC}, \frac{nC - r_2}{nC}) 其中 d 为 x 与 y 的汉明距离

• 增加 k 能够减小哈希概率
  设 h_i 为随机从哈希函数族 H 中选取的一个哈希函数，且 P(h(x)=h(y)) = p_0 ，而 g_i(x) = (h_1(x), h_2(x), .. h_k(x)) 则有：
  P(g_i(x)=g_i(y)) = P(h_1(x)=h_1(y))*..*P(h_k(x)=h_k(y)) = p_0^k
  故增大 k 可以减小哈希概率（缩小 p_1, p_2）

• 增加 L 能够增大哈希概率
  设 G(x) = (g_1(x), g_2(x), ..., g_L(x))，定义 G(x) = G(y) 条件为存在一个 g_i(x) 使得 g_i(x)=g_i(y)，那么就有如下结论
  P(G(x)=G(y))=1 - (1-P(g_1(x)=g_1(y)))*..*(1-P(g_L(x)=g_L(y))) = 1 - (1 - p_0^k)^L
  故增大 L 能够增大哈希概率

• 下面给出数学证明，增大相同的 k, p_1^k 的减小量小于 p_2^k，且增大相同的 L, 1-(1-p_1^k)^L 的增大量要大于 1- (1 - p_2^k)^L 的增加量