局部敏感哈希笔记（Locality-Sensitive Hashing）_局部敏感哈希 哈希键计数

局部敏感哈希（Locality-Sensitive Hashing）

ps:在隐私保护的文献中看到了使用局部敏感哈希算法的内容，于是看了一下Stanford的CS246课程关于LSH的部分，整理了些csdn上大佬的内容。

---

传统哈希：通过O(1)的时间复杂度将数据映射为另一个数据。

如$Hash(Key)=key\%11$，那么对于129、132、140这三个关键字， 129%11=8，133%11=0，140%11=8
本来很接近的129和132经过映射后距离变远了，本来远一些的129和140反而映射到了同一位置，也就是说传统哈希不能保留原有数据的相似性。

局部敏感哈希：哈希的同时保留原有数据的相似性

最大特点就是保留数据原有的相似性。为了保留相似性，设计哈希函数的时候要满足以下两个条件：
1）如果$d(x,y)\le d1$， 则$h(x)=h(y)$的概率至少为p1；
2）如果$d(x,y)\ge d2$， 则$h(x)=h(y)$的概率至多为p2；
若哈希函数满足以上条件，则称其为$(d1,d2,p1,p2)-sensitive$。而通过一个或多个$(d1,d2,p1,p2)-sensitive$的哈希函数对原始数据集合进行哈希操作生成一个或多个哈希表的过程叫做局部敏感哈希。

---

LSH流程（Stanford CS246）

Step1. 将文件转化为集合

文件中出现的k个字符/文字称为k-shingles，用集合的0/1表示
矩阵的行表示shinglings，列表示文件，当文件s中包括shingle e时，第e行第s列的值为1，否则为0。

【每一列表示一个文件，每一行表示一个关键字/字符。比如a,b,c,d,e,f,g，第一列表示文件1中包含a,b,e,f,g，没有c,d】

Step2. Min-Hash算法构建哈希表

目标：挑选一个哈希函数H，在大多情况下
当sim(C1,C2)高时，H(C1)=H(C2)；当sim(C1,C2)小时，H(C1)≠H(C2)
算法：特征矩阵按行进行一个随机的排列后，第一个列值为1的行的行号。

【左边三列表示三种排列的方式，第一列的第一个2表示原本的第一列在新的排列中是第二行，3表示原第二行在新的排列中是第三行，下面同理。根据一个排列找到每个文件中，第一次出现值为1是第几行，行号即文件得到的哈希值。根据不同的排列方式，即可得到一个签名矩阵M】

Step3 使用LSH寻找相似文档

目标：找到Jaccard相似度至少为s的文件们（s自行设定，eg.s=0.8）
LSH的主要思想：使用哈希函数来判断x和y是不是候选对（是否需要评估相似度）
对min-hash生成的巨大的签名矩阵M再进行Hash，Hash到不同的busket里，若文档位于同一个busket，则认为他们为候选对。
【签名矩阵会包括很多行（eg.100行），如果直接做哈希的话，在我们将s设置为0.8时，100行里要有80行的值相同我们才会判定为相似，要求十分严格。但是我们把签名矩阵分成十份（b=10，即图中10个band）时，对每个band进行哈希生成一个哈希表，在一个band中有8行值相同就可判定为相似。】

对每个band，将它的每一列hash到有k个busket的哈希表中（k越大越好），若文档在一个及以上的哈希表中位于一个busket，则可以称为候选对。

---

准确性计算

假设签名矩阵M有100000列，100行，设置s=0.8，b=20，r=5；假定只要在一个band里面判定两个文件相似就认为二者相似。

设C1,C2两个文件相似度为0.8，在一个band中五个值都相等的概率为$(0.8{)}^5=0.328$，则在20个band中都没发现C1,C2相似的概率为$(1-0.328{)}^{2}0=0.00035$，所以假阴性的概率为0.00035。

设C1,C2两个文件度相似度为0.3，在一个band中五个值都相等的概率为$(0.3{)}^5=0.00243$，则存在一个band判定二者相似的概率为$1-{(1-0.00243)}^{20}=0.0474$，即假阳性的概率为0.0474。

---

调参

LSH过程中需要挑选参数，

1. 选取Min-Hash的次数（决定M的行数）；
2. 挑选b和r ->平衡假阴性和假阳性
   【假阳性可以通过再传输数据来过滤，假阴性会永远失去有用信息，所以调参过程中更注重降低假阴性。】

理想情况：希望相似度大于s的都被判定为1，小于s的都被判定为0

现实很骨感：相似度是多少就会判定多少
b=1,r=100时（即没划分band时）

调参的目标：调整b和r尽可能达到理想

---

相似度计算方法【不同的计算方法对于不同的hash函数？】

• Jaccard相似度（对应minhash）：并集/交集
  
  minhash是$(d1,d2,1-d1,1-d2)-sensitive$
• 海明距离（simhash使用）：两个具有相同长度的向量中对应位置处值不同的次数。两个二进制串对应的位有几个不一样，海明距离就是几。
  1011和1010的距离是1。对应的LSH 哈希函数为：H(V) = 向量V的第i位上的值，是$(d1,d2,1-d1/d,1-d2/d)-sensitive$。
• Cosine distance:
  $cos\theta =(A\ast B)/(|A||B|)$
  两个向量的夹角越小越相似，对应的LSH 哈希函数为：$H(V)=sign(V\cdot R)$，R是一个随机向量。V·R可以看做是将V向R上进行投影操作。其是$(d1,d2,(180-d1)180,(180-d2)/180)-sensitive$的。
• Normal Euclidean distance
  Euclidean distance是衡量D维空间中两个点之间的距离的一种距离度量方式。Euclidean distance对应的LSH 哈希函数为：
  $H(V)=|V\cdot R+b|/a$
  R是一个随机向量，a是桶宽，b是一个在[0,a]之间均匀分布的随机变量。V·R可以看做是将V向R上进行投影操作。其是$(a/2,2a,1/2,1/3)-sensitive$的。

---

增强LSH

通常，为了能够增强LSH，即使得假阳性和/或假阴性降低，我们有两个途径来实现：1）在一个哈希表内使用更多的LSH 哈希函数；2）建立多个哈希表。
常用的增强LSH的方法：

1. 使用多个独立的哈希表
   每个哈希表由k个LSH 哈希函数创建，每次选用k个LSH 哈希函数（同属于一个LSH function family）就得到了一个哈希表，重复多次，即可创建多个哈希表。多个哈希表的好处在于能够降低假阳性。
2. AND与操作
   所有哈希表都判定相似才认为相似。
   AND与操作能够使得找到近邻数据的p1概率保持高概率的同时降低p2概率，即降低了假阴性。
3. OR 或操作
   和上面步骤的假设一样，只要有一个hash表可以判断相似即认为相似。
   OR或操作能够使得找到近邻数据的p1概率变的更大（越接近1）的同时保持p2概率较小，即降低了假阳性。
4. AND和OR的级联
   将与操作和或操作级联在一起，产生更多的哈希表，这样的好处在于能够使得p1更接近1，而p2更接近0。