LSH局部敏感哈希
问题场景：
快速的从海量高维数据集合中找到与某个数据最相似（距离最近）的一个数据或多个数据
局部敏感： 指样本越相似，经过哈希后的值越可能一样。
通过建立Hash Table的方式，我们期望能够获得O(1)的查找时间性能，其中的关键在于选取一个hash function，将原始数据映射到对应的桶内（bucket）。以下以jacarrd距离为度量（对应的哈希函数为minhash）。简要介绍LSH。
MinHash算法
-
对A、B的n个维度，做一个随机排列（即对索引 [图片上传失败...(image-1dabad-1599725828667)]
随机打乱）
分别取向量A、B的第一个非0行的索引值（index），即为MinHash值
得到AB的MinHash值后，可以有以下一个重要结论：
通过计算Sig(A) 与Sig(B)相等的比例，我们就可以估计AB的jaccard相似度了（近似相似，但是不会完全相等，除非全排列）。
数学证明：
两个集合。A、B。对一行来说。他们的状态有三种
A、B都为1，即表示A、B集合中都有这个单词
A、B当中一个为1，当中一个不为1，即一个有这个单词，一个没有
A、B都为0，即表示A、B中都没有这个单词。
令第一种状态有x次，第二种状态y次，第三种状态z次
jaccard = x/(x+y)
再看minhash，由于排列是随机的，在出现第二种状态之前出现第一种状态的概率为x/(x+y)
代码模拟：
import random
import numpy as np
A = set(['a', 'b', 'c', 'd'])
B = set(['a', 'c', 'e', 'f'])
sigA = []
sigB = []
U = list(A.union(B))
I = A.intersection(B)
# minhash
for x in range(0, 1000000):
# step1 对A、B的n个维度，做一个随机排列（即对索引随机打乱）
r_u = random.shuffle(U)
# step2 分别取向量A、B的第一个非0行的索引值（index），即为MinHash值
for index in range(0, len(U)):
if U[index] in A:
sigA.append(index)
break
for index in range(0, len(U)):
if U[index] in B:
sigB.append(index)
break
print('jacarrd distance: ', np.sum(np.array(sigA) == np.array(sigB)) / len(sigA))
LSH
上面的集合摘要采用了12个不同的hash函数计算出来，然后分成了B = 4个区间。前面已经分析过，任意两个集合（S1，S2）对应的Minhash值相等的概率r = Jac(S1，S2)。先分析区间1，在这个区间内，P(集合S1等于集合S2) = r3。所以只要S1和S2的Jaccard相似度越高，在区间1内越有可能完成全一致，反过来也一样。那么P(集合S1不等于集合S2) = 1 - r3。现在有4个区间，其他区间与第一个相同，所以P(4个区间上，集合S1都不等于集合S2) = (1 – r3)4。P(4个区间上，至少有一个区间，集合S1等于集合S2) = 1 - (1 – r3)4。这里的概率是一个r的函数，形状犹如一个S型，如下：
如果令区间个数为B，每个区间内的行数为C，那么上面的公式可以形式的表示为：
P(B个区间中至少有一个区间中两个结合相等) = 1 - (1 - rC)B
令r = 0.4，C=3，B = 100。上述公式计算的概率为0.9986585。这表明两个Jaccard相似度为0.4的集合在至少一个区间内冲撞的概率达到了99.9%。根据这一事实，我们只需要选取合适的B和C，和一个冲撞率很低的hash函数，就可以将相似的集合至少在一个区间内冲撞，这样也就达成了本节最开始的目的：将相似的集合放到一起。具体的方法是为B个区间，准备B个hash表，和区间编号一一对应，然后用hash函数将每个区间的部分集合映射到对应hash表里。最后遍历所有的hash表，将冲撞的集合作为候选对象进行比较，找出相识的集合对。整个过程是采用O(n)的时间复杂度，因为B和C均是常量。由于聚到一起的集合相比于整体比较少，所以在这小范围内互相比较的时间开销也可以计算为常量，那么总体的计算时间也是O(n)。
以s1为例，遍历4个hash table取出所有hash table中冲撞的集合( s2, s4 )进行进一步的计算，从而得到距离最近的元素。
参考：
https://blog.csdn.net/weixin_43098787/article/details/82838929
https://blog.csdn.net/weixin_43461341/article/details/105603825
