局部敏感哈希算法介绍

1. 应用：从海量高维数据中查询与某个数据最相似的一个数据或数据集（用于人脸检索）
2. 基本思想：基于原始数据空间中相邻的数据经过同一个映射变换之后，处于相邻区域的概率仍然较大的理念；人为的选取一些具有上述性质的函数来作为哈希函数，使得相邻的数据映射后处在哈希表的同一个位置，这样就可以轻松的找到与该数据相似的数据集了。即，通过选取的哈希函数的映射变换能够将原始的数据集划分为若干较小的子集，且每个子集中的元素个数较小且相邻。

3. 局部敏感哈希函数的服从如下两个条件:
   • 如果 d(x,y) ≤ d1， 则 h(x) = h(y) 的概率至少为 p1
   • 如果 d(x,y) ≥ d2， 则 h(x) = h(y) 的概率至多为 p2
   • 这两个条件正是对之前提到局部敏感哈希函数的性质的约束，意义也比较容易理解
4. 局部敏感哈希算法的大致运行过程
   • 构建索引集
     • 因为单个哈希哈数的区分能力不强（即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 的具体数目，来达到良好的查询效果 （即训练学习）
   • 实际查询过程
     • 将查询数据经过局部敏感哈希函数映射得到相应的哈希码
     • 依据哈希码，取出相应桶中的数据
     • 线性检索数据中与查询数据最接近的一个或多个数据，返回结果

5. 常用局部敏感哈希哈数族
   • 常用的相似度计算方法介绍
     • 欧式距离（即常用的坐标差平方和开根号）$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\le x_i\le C)$
       • 则 p 在汉明空间下的二进制表示为 $p=Unar{y}_C(x_1)Unar{y}_C(x_2)..Unar{y}_C(x_n)$ ，其中 $Unar{y}_C(x_i)$ 为二进制编码，前 $x_i$ 位为 1，后 $C-x_i$ 位为 0（类似于汉明码）
     • 定义如下汉明哈希函数
       $$h(x)=\{\begin{array}{ll}0& \text{p 的第 r 位为 0}\\ 1& \text{p 的第 r 位为 1}\end{array}$$
       其中 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 的汉明距离

6. 关于通过改变 L 与 K 参数放大与缩小相关的哈希概率的分析
   • 增加 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))\ast ..\ast 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)))\ast ..\ast (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$ 的增加量
     

最后

以上就是忧心鱼为你收集整理的局部敏感哈希算法介绍的全部内容，希望文章能够帮你解决局部敏感哈希算法介绍所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。