(完整)LocalitySensitiveHashing总结,推荐文档

1、Locality Sensitive Hashing 总结最近邻搜索问题(Nearest Neighbor Search Problem , NNS)是： 给定距离空间 X 中的 点集 P = p1,p2pn ，以及 q X，如何高效的找到 P 中距离近 q 最近的那个点。这里 的距离空间 X，我们一般只关注 Rd 空间。当 d 较小的时候，文献 H. Edelsbrunner. Algorithms in Combinatorial Geometry. 1987提出了一个有效的解决办法。但是，当空间的维度 d 较大的时候，无论是理论上还是实践中，还没有令人满意的解决方法，线性查找方法的效率也

2、非常低。这种由于维度 d 太大，而带来的求解困难的问题称为维度灾难” 。除了最近邻问题之外，研究人员对近似最近邻问题也比较感兴趣，即，在 P 中找到点 p,使得对所有的 p都满足。 此时， 可以直观理解为， p 是 P 中距离 q 的差不多最小的点。 但 是即使是& -NNS问题，情况也不比 NNS 好到哪里去。为了解决维度灾难问题，Indyk 提出了局部敏感哈希算法，专门用于处理高维海量数据， 尤其是用于数据间的相似度计算。在实际应用中，如果是低维少量数据，可以直接采用线性查找的方法。当数据量大，并且维度高时，LSH 是一个不错的选择。LSH 从 1998 年开始，经历了多个版本。比

3、较经典的是汉明空间上的 LSH、p-stable LSH。P-stableLSH 是汉明空间 LSH 的改进版本，它使得数据无需转化为 01 串，可以直接在欧氏 空间上处理。下文分别介绍这两种 LSH 方案。LSH 算法的思想是，利用 hash 函数，将原始数据点映射到一个新的空间中，并且使得，在原空间中距离相近的点，会以很大的概率产生hash 碰撞。当进行最近邻查找时，只需要计算查询点的 hash 值，然后提取所有与查询点产生hash 碰撞的数据点。这些数据点可以在一个较大的概率下保证是与查询点相似的。这样一来，我们只需要在这些相似的点中寻找那个最近邻，无需遍历整个数据库。因此，LSH 算法

4、能够帮助我们从整个数据库中找到一个子 集，这个子集种的数据点会以很大的概率与查询点相接近。LSH 算法中采用的 hash 函数并不同于传统的用于密码学中的hash 函数。在密码学中，我们期望尽量避免hash 碰撞。而在LSH 算法中的 hash 函数，我们却希望最大化碰撞概率。那么什么样的函数才算是局部敏感哈希函数呢？从上述描述来看，可以看出LSH 函数有如下性质：距离较远的点，产生哈希碰撞的概率较小概述原始LSH距离较近的点，产生哈希碰撞的概率较高。从 LSH 函数的性质，我们可以这么定义LSH 函数：在距离空间 X( d)中，d 为距离，函数簇 H 是从 X 到 U 到映射，对任意 X 中

5、的点 p,q， f 都满足：1)如果 d(x,y) d2,贝 U h(x) = h(y)的概率至多为 p2;满足上述条件的函数称之为是(di, d2 , pi , p2-sensitive 的。Mining of Massive Datasets一书中，给出了寻找这样的函数的方法。一般来说，我们只需要几个常用的：下面我们介绍一些满足不同距离度量方式下的locality-sensitive 的 hash functions :1. Jaccard dista neeJaccard dista nee：(1 - Jaccard similarity)，而 Jaccard similarity =

6、(A in tersect ion B) / (Aunion B) , Jaccard similarity 通常用来判断两个集合的相似性。Jaccard dista nce 对应的 LSH hash fun ctio n 为：min hash，其是(d1,d2,1-d1,1-d2)-se nsitive 的。2. Hammi ng dista nceHamming distance :两个具有相同长度的向量中对应位置处值不同的次数。Hamming distance 对应的 LSH hash function 为：H(V)= 向量 V 的第 i 位上的值，其是(d1,d2,1-d1/d,1-d

7、2/d)-sensitive 的。3. Cos ine dista nceCosine distance: cos(theta) = A B /，常用来判断两个向量之间的夹角，夹角越小，表示它们越相似。Cosine distance 对应的 LSH hash function 为：H(V) = sign(V R), R 是一个随机向量。V R 可以看做是将 V 向 R 上进行投影操作。其是(d1,d2,(180-d1)180,(180-d2)/180)-sensitive的。理解：利用随机的超平面(ran dom hyperpla ne)将原始数据空间进行划分，每一个数据 被投影后会落入超平面

8、的某一侧，经过多个随机的超平面划分后，原始空间被划分为了很多cell，而位于每个cell 内的数据被认为具有很大可能是相邻的(即原始数据之间的cosinedistanee 很小)。4. no rmal Euclidea n dista neeEuclidean distanee 是衡量 D 维空间中两个点之间的距离的一种距离度量方式。Euclidean distanee 对应的 LSH hash function 为：H(V) = |V R + b| / a , R 是一个随机向 量，a 是桶宽，b 是一个在0,a之间均匀分布的随机变量。 V R 可以看做是将 V 向 R 上进 行投影操作。其

9、是(a/2,2a,1/2,1/3)-sensitive 的。本章介绍的是原始 LSH 算法，该算法采用的是汉明距离。其LSH 函数的构造方法是：给定函数簇 H = h | hi(v) = vi。即，取出向量 V 第 i 位上的值。这个 H 仅仅是 hash 函数， 但不能算作是局部敏感哈希函数。因此，下一步就是构造具有sensitive 性质的 hash 函数簇G。构造方法是，从 H 中随机的取 k 个 h，将这 k 个 h 串联起来形成一个新的函数g。g = h1, h2,hk 这个 g 是 sensitive 的。因为 g 是随机的取 k 个 h，而 h 又是去向量 V 上的第 i 位。函

10、数 g 的实际效果就是，随机的从向量 V 中取 k 位。由于 V 是经过汉明化的，因 此，函数 g 的函数值，也即 hash 值，的排列组合就有 2k个。我们把函数 g 产生的 hash 值称 为 hash 桶。这样，每个函数g 都能够生成 2k个 hash 桶，这 2k个 hash 桶摆成一行，就会形成一个表， 称为 hash tab每个 hash 桶对应的都是产生碰撞的向量。 当数据量特别大的时 候， 每个 hash桶中都会对应了大量向量，这些向量会以很大概率在原空间X 中距离接近。依然提到了概率，就会有例外。也有可能本身距离较远的点，经过哈希之后落入了同一个 hash 桶，这种错误称之为

11、 false positive;反之，也有可能本身距离相近的点，落入了不同的 hash 桶中，这种错误称之为false n egative。在实际应用中，我们希望尽量减小这两类错误。因此，采用的一搬方法就是把g 函数进行级联。因为，我们仅仅是从H 中选出了一个 g,如果我们选出大量的g,够成一个簇 G。把这些 g 函数进行级联，就能使得错误概率大大减小。级联方法有 AND、OR 方法。通过选取多个 g 函数，可以形成多个hash table。当有了 sensitive 哈希函数时，就可以把数据库中所有的点映射到这多张hash table 中的桶中。距离相近的点，会议较大的概率落入同一个hash

12、 table 中的同一个桶里，即同一个g函数输出相等的 hash 值。当我们进行查询的时候，将查询点也计算hash 值。因为我们选择了多个 g 函数的级联，假设是 L 个 g 函数。因此我们有 L 个 hash table。查询点也会计算出 L 个 hash值，对应了 L 个 hash 桶。将这 L 个 hash 桶对应的数据库中的点都搜集起来，构 成一个集合。这个集合就是查询点最接近的点。我们只需要在这个子集中进行线性查找，就能找到查询点的最近邻，而无需搜索整个数据库。三、P-stable LSH四、E2LSHE2LSH 与 p-stable LSH 相比，有少许的改动，但主要部分不变。E2

13、LSH 可以看做是 p-stable LSH 的概率版本，也就是说。P-stable LSH 能够 100%的返回所有满足要求的近邻。而E2LSH 只能以一个概率值返回满足要求的近邻。R-NN 问题的定义是。给定集合 P,和半径 R。来回答下面的问题：给定查询点 q,和所有的点p P,返回满足|p-q| 0,con struct a data structure that an swers the followi ng queries: for a query point q, find all points pPsuch that |q - p|2R, where |q - p|2is th

14、e Euclidea n dista nee betwee n q and p. E2LSHsolves a ran domized vers ion of this problem, which we call a ( R, 1 -3)-n ear n eighborproblem .In this case, each point psatisfying |q- p|2er vcif ritctH.从 running time 的角度去考虑，我们希望扩大0, RR,之间的碰撞概率 P1 与 P2 的间隔。处于这种考虑，我们采用串联k 个 h 函数，并定义 G 函数，使得每个 g 都是 k

15、个 h的串联。然后，再构造L 个具有这种形式的 g 函数。在预处理阶段，我们把 P 中的每一个点 v 放进哈希桶 gi(v)中。由于哈希桶的数量很大，所以不可能在内存中存储所有的哈希桶，一搬的做法是只选择那些非空的哈希桶。当我们处理一个查询点q 的时候，会搜索所有的哈希桶g1(q), . . . , gL(q).。对于在哈希桶中发现的每一个与q 碰撞的点 v，都计算一个 q 与 v 之间的距离。然后返回所有那些满足|q - v| w 时，Ph(v1) = h (v2) = 0 。当 c w 时，他们投影在同一个线段内的概率是w- (a*v1-a*v2)/ w 。这个不难理解，可以想象成把一个火

16、柴棍放在一个线段内，两端点同在一条线段内的概率是多少。此时，我们只需要考虑一侧端点即可。这样一来，我们就成功的把一个普通的hash 函数，转化成了一个具有高冲突率的 hash函数。并且冲突率可以通过两个向量之间的距离来量化。这时，我们需要得知，这个 hash 函数冲突率有多高，即有多敏感，也就是算出，敏感性的4 个参数：r1,r2,p1,p2，前面说过， 只有当 a*v1-a*v2 w 的时候， 才有可能投影到同一个线段。概率是w- (a*v1- a*v2)/ w。但是，a*v1-a*v2 并不总是小于 w，所以这是一个乘法原理。我们得先算，a*v1-a*v2 有多大的概率会小于 w。也即是算

17、 P(a*v1-a*v2w)=? 根据 P-stable 分布的定义，a*v1-a*v2 与|v1-v2|X 同分布。 所以，也就是等价于计算 P( |v1-v2|X w)= ?也即，P(X w/|v1-v2|)= ?其中 X 符合 p-stable 分布。设 X 的分布函数时 f(x)。我们通过分布函数 f(x)可以得到|v1-v2|X 有多大的可能性小于w。注意，仅仅这一步是不能算作v1 与 v2 产生 hash 冲突的概率的。因为 v1 与 v2 要产生hash 冲突，应该分为两步。第一步是 a*v1-a*v2w 的概率，这一步的直观理解是对v1 与 v2 投影距离的伸缩。第二步是，在第

18、一步的基础上，投影在同一个线段内的概率是w- (a*v1-a*v2)/ w不妨设 a*v1-a*v2 =Y。故，产生 hash 冲突的概率是 Yw 并且 其中一个投影点落在一个线段内的 0 到(w-Y)/w 范围内的概率。而根据p-stable 的定义，Y 与 IX 同分布。因此，上述条件转化为：量投影在同一个线段内的时候，就认为他们输出相同的hash 值。可以取线段上的端点的坐标作为这个 hash 值。例如，有一条线段在坐标轴上横跨3-4 之间，同时有两个向量落在了3.6 和 3.7 上，那么我们就取线段的一个端点坐标作为hash 值，例如 3 或 4。具体形式见下图:1 1 0I. 111 !卩1* 11的分布函数时已知的，设为f(x)。因此，下面采用微分的思想算整体概率。产生 hash 冲突的概率是 IXW，并且投影点落在线段内的0 到(w-lX