LSH（局部敏感度哈希）
LSH（局部敏感度哈希）
1 intuition
在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维度 ，怎样快速地从海量的高维数据集合中找到与某个数据最相似 （距离最近）的一个数据或多个数据成为了一个难点。
例如推荐系统的用户协同过滤 中，我们拥有4亿活跃用户，每个用户可以用一个高维向量表示，如果计算用户的两两相似度，需要花费很长的时间；在商品协同过滤 中，单JD泰国就拥有超过2500万个商品，每个商品可以用一个高维向量表示(商品名称的embedding+一些数值型属性)，如果要计算所有商品的两两相似度，复杂度也是O(n^2)。
在之前的文章讲KNN算法的时候，计算每个点的两两相似度太过耗时，我们也用kd-tree来降低这个时间。<>
所以，需要类似索引的技术来加快查找过程。
传统的哈希是希望数据通过哈希后尽量使数据不冲突（collision），而LSH却是依赖冲突 ，希望相似的文档经过哈希后冲突在一起。
我们希望原先相似的两个数据能够被hash到相同的桶内，这样我们在该数据集合中进行近邻查找就变得容易了：我们只需要将查询数据进行哈希映射得到其桶号，然后取出该桶号对应桶内的所有数据，再进行两两匹配即可查找到与查询数据相邻的数据。
2 定义
h为哈希函数，
表示两个具有多维属性的数据对象，
表示对象
之间的距离(余弦相似度，Jaccard距离，Minkovski距离...).
h需要满足如下两个条件：
- 如果
, 则
(对于相似的对象，它们有大概率落在同一个桶内) - 如果
, 则
(对于不相似的对象，它们有小概率落在同一个桶内)
LSH的作用就是将高维数据降维到低维数据，同时还能在一定程度上保持原始数据的相似度不变。LSH不是确定性的，而是概率性的，也就是说有一定的概率导致原本很相似的数据映射成两个不同的hash值，或者原本不相似的数据映射成同一hash值。这是高维数据降维过程中所不能避免的（因为降维势必会造成某种程度上数据的失真），不过好在LSH的设计能够通过相应的参数控制出现这种错误的概率，这也是LSH被广泛应用的原因。
3 min-hash
3.1 hash函数选择
首先我们定义一下变量的记号：假设有四个用户，用A、B、C、D来表示。 
表示商品。如果用户A购买过商品
, 相应的格点就应该为1.
问题：可能有非常多的商品，也有上亿的用户，如何快速计算和某个用户相似的用户群体呢？
现在做这样一件事：对这个矩阵按行进行多次置换，每次置换之后，统计每一列（用户）第一个不为0的行号，这样每次统计的结果能构成一个与用户数等大的向量，这个向量，我们称之为签名向量。
图中：4个用户，做了3次置换（用红、黄、蓝向量表示置换顺序），得到了一个3 x 4的签名矩阵。
置换input matrix的行，取每列第一个非0元行号的做法，就是一个hash函数。这个hash函数成功地将多维数据映射成了一维数据。而从这个定理我们发现，这样的映射没有改变数据相似度。
需要注意的一点是，这里的hash函数只能对Jaccard系数定义数据相似度的情况起作用。不同的相似度模型，LSH是不同的，目前，还不存在一种通用的LSH。
3.2 构造LSH函数族
现在，我们有了一个signature matrix。为了控制相似度与映射概率之间的关系（满足 2.定义），我们需要按下面的操作进行，一共三步。
step 1. 将signature matrix水平分割成一些区块（记为band），每个band包含了signature matrix中的r行。
step 2. 对每个band计算hash值，这里的hash算法没有特殊要求，MD5，SHA1等等均可。一般情况下，我们需要将这些hash值做处理，使之成为事先设定好的hash桶的脚标，然后把这些band“扔”进hash桶中。如下图所示。
用户2和用户6在这一层的band落到了同一个桶中，说明他们可能相似；用户6和用户7在这一层的band落在了不同的桶中，说明他们在这个部分不甚相同。
step 3. 如果某两个用户在某个同一水平方向上的band，映射成了同一hash值（如果你选的hash函数比较安全，抗碰撞性好，那这基本说明这两个band是一样的），我们就将这两个文档映射到同一个hash bucket中，也就是认为这两个文档是足够相近的。
下面计算两个用户被映射到同一个桶中的概率：
- 对于两个用户的任意一个band来说，这两个band值相同的概率是：
，其中s∈[0,1]是这两个文档的相似度。 - 也就是说，这两个band不相同的概率是
- 这两个文档一共存在b个band，这b个band都不相同的概率是
- 所以说，这b个band至少有一个相同的概率是
概率 
就是最终两个文档被映射到同一个桶中的概率。这样可以通过控制参数r,b的值来控制两个文档被映射到同一个哈希桶的概率。而且效果非常好。比如，令b=20,r=5
当相似度s=0.8时，两个文档被映射到同一个哈希桶的概率是：
当相似度s=0.2时，两个文档被映射到同一个哈希桶的概率是：
不难看出，这样的设计通过调节参数值，达到了“越相似，越容易在一个哈希桶；越不相似，越不容易在一个哈希桶”的效果。这也就能实现我们上边说的LSH的两个性质。
当相似度高于某个值的时候，概率会变得非常大，并且快速靠近1，而当相似度低于某个值的时候，概率会变得非常小，并且快速靠近0.