LSH（局部敏感度哈希）

一、局部敏感哈希LSH

在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维度，怎样快速地从海量的高维数据集合中找到与某个数据最相似（距离最近）的一个数据或多个数据成为了一个难点和问题。如果是低维的小数据集，我们通过线性查找（Linear Search）就可以容易解决，但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常耗时，因此，为了解决该问题，我们需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest Neighbor,AN），例如K-d tree；或近似最近邻查找（Approximate Nearest Neighbor, ANN），例如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH是ANN中的一类方法。

通过建立Hash Table的方式我们能够得到O(1)的查找时间性能，其中关键在于选取一个hash function，将原始数据映射到相对应的桶内（bucket, hash bin）

传统的哈希是希望数据通过哈希后尽量使数据不冲突（collision），如用户ID经过UUID得到全局唯一
而LSH却是依赖冲突，希望相似的文档经过哈希后冲突在一起。

LSH的基本思想是：将原始数据空间中的两个相邻数据点通过相同的映射或投影变换（projection）后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。也就是说，如果我们对原始数据进行一些hash映射后，我们希望原先相邻的两个数据能够被hash到相同的桶内，具有相同的桶号。对原始数据集合中所有的数据都进行hash映射后，我们就得到了一个hash table，这些原始数据集被分散到了hash table的桶内，每个桶会落入一些原始数据，属于同一个桶内的数据就有很大可能是相邻的，当然也存在不相邻的数据被hash到了同一个桶内。因此，如果我们能够找到这样一些hash functions，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入相同的桶内的话，那么我们在该数据集合中进行近邻查找就变得容易了，我们只需要将查询数据进行哈希映射得到其桶号，然后取出该桶号对应桶内的所有数据，再进行线性匹配即可查找到与查询数据相邻的数据。换句话说，我们通过hash function映射变换操作，将原始数据集合分成了多个子集合，而每个子集合中的数据间是相邻的且该子集合中的元素个数较小，因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题，显然计算量下降了很多。

mini哈希：
1.对所有文档，对应不同的词进行文档标记

过程
2.对所有词的顺序做一个随机打乱，然后文章进行重新标记
minhash定义：特征矩阵按行进行随机的排列后，第一列值为1的行的行号

得到 1 1 2 (第一列W2在D3中第2行才为1，所以行号为2) 1
3.重复第2 个步骤
重复N次，若有M个文档, 则得到N×M的标记矩阵

4.对标记矩阵行进行分割，分割成若干个brand(一个brand若干行），假设进行N次，有N行，分割成B个brand,则
每个brand有N/B行。

对每一组brand进行哈希（如md5,sha1等），一组brand是N/B行 M列。
哈希为事先设定好的hash桶的tag中，把每组brand丢进桶内

这样得到M个文档在每个brand中的哈希结果