局部敏感哈希（Locality Sensitive Hashing）和MinHash

by 夏泽民 Apr 18, 2020

我们所面对的数据是海量的，并且有着很高的维度。在对数据的各种操作中，查询操作是最常见的一种，这里的查询是指输入一个数据，查找与其相似的数据，那么怎样快速地从海量高维数据中，找到与某个数据最相似的数据，成为了一个难点和问题。

低维的小数据集，可通过线性查找来解决，但如果是对一个海量的高维数据集采用线性查找的话，时间代价非常大，因此，为了解决该问题，我们需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找或近似最近邻查找。局部敏感哈希就可以视为一种“近似最近邻查找”。

在介绍局部敏感哈希之前，需要先介绍传统的哈希算法。

传统哈希算法通过哈希函数建立哈希表，由哈希表我们能够得到O(1)的查找时间性能，传统哈希算法的关键在于，找到合适的哈希函数，将原始数据映射到相对应的桶内，如果不同的数据，映射到了同一个位置，就是发生了冲突，这是传统哈希算法所要避免的。

而局部敏感哈希的思路恰恰想法，LSH渴望冲突，但是，不是没有限制的胡乱冲突，而是希望原先相邻的两个数据能够被映射到相同的桶内，具有相同的桶号，也就是说，将相似的数据聚到一起。

LSH算法基于一个假设，如果两个数据在原有的数据空间中是相似的，那么分别经过哈希函数映射以后的它们也具有很高的相似度；相反，如果它们本身是不相似的，那么经过映射后它们仍不具有相似性。

也就是说，将原始数据空间中的两个相邻数据点通过相同的映射后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。

那么在实际使用中，我们只需要将查询数据进行哈希映射得到其桶号，然后取出该桶号对应桶内的所有数据，再进行线性匹配即可查找到与查询数据相邻的数据，极大的减少了时间代价。

局部敏感哈希的最大特点就在于保持数据的相似性。

我们可以看一个反例：

假设一个哈希函数为Hash(x) = x%9，那么我们现在有三个数据分别为356、359和814，我们将上述的三个数据通过Hash函数转换为：

Hash(356) = 356%9 =5 ;

Hash(359) = 359%9= 8;

Hash(814) = 814%9 = 4;

在未经过映射前，数据356和359比较接近，和814相差较远，但是在经过哈希映射之后，814的哈希值和356的哈希值接近，359的哈希值和356的哈希值相差较远，也就是说，经过这种哈希计算后，数据之间原有的相似度消失，所以他不是一个局部敏感哈希。

那么，局部敏感哈希的哈希函数需要遵循什么样的原则呢？

局部敏感哈希函数需要满足以下两个条件：

1）如果d(x,y) ≤ d1，则h(x) = h(y)的概率至少为p1；

2）如果d(x,y) ≥ d2，则h(x) = h(y)的概率至多为p2；

其中d(x,y)表示x和y之间的距离，d1 < d2， h(x)和h(y)分别表示对x和y进行hash变换。

满足以上两个条件的hash functions称为(d1,d2,p1,p2)-sensitive。而通过一个或多个(d1,d2,p1,p2)-sensitive的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing 局部敏感哈希。

下面我们通过一个具体的实例，来介绍一下LSH的具体用法，“使用LSH实现文档相似度计算”。

假设现在有4个网页，我们将它们分别进行Shingling（将待查询的字符串集进行映射，映射到一个集合里。）得到如下的特征矩阵，每一列代表一个网页(文档)，每一行可以视为一个字符，例如a,b,c,d,e,f,g。

其中“1”代表对应位置的Shingles在文档中出现过，“0”则代表没有出现过。

运用Jaccard相似度来衡量文档之间的相似性。接下来我们就要去找一种哈希函数，使得在hash后尽量还能保持这些文档之间的Jaccard相似度，也就是说，这种哈希可以保持数据之间的相似性，那就可以视为局部敏感哈希。

顺道提一下Jaccard(杰卡德)相似度。

Jaccard相似指数用来度量两个集合之间的相似性，它被定义为两个集合交集的元素个数除以并集的元素个数。

Jaccard距离用来度量两个集合之间的差异性，它是Jaccard的相似系数的补集，被定义为1减去Jaccard相似系数。

接下里，我们就要选择一个适当的哈希函数，令其满足局部敏感哈希的条件，在此处我们选用的哈希函数是MinHash，也就是最小哈希。

MinHash 是用于快速检测两个集合相似性的方法。该方法由 Andrei Broder (1997) 发明，最初用于AltaVista搜索引擎中来检测重复的网页。

MinHash定义为：特征矩阵按行进行一个随机的排列后，第一个列值为1的行的行号。

比如我们原先有一个特征矩阵如下：S1，S2，S3为三个文档，A,B,C,D为四个字符。

接下来，我们按行做一个随机排列：

哈希值：排列转换后的行排列次序下第一个列值为1的行的行号，例如h(S1)=D，h(S2)=B。当然，你也可以记为h(S1）=2，h(S2)=1,h(s3)=2，两种表示方法应该都可行。

事实上，两个集合经随机排列之后得到的两个最小哈希值相等的概率等于这两个集合的Jaccard相似度。即P(h(Si)=h(Sj)) = sim(Si,Sj)。

MinHash的基本原理:在A∪B这个大的随机域里，选中的元素落在A∩B这个区域的概率，这个概率就等于Jaccard的相似度

P(h(Si)=h(Sj)) 为什么会等于sim(Si,Sj)?

我们考虑Si和Sj这两列，它们所在行的所有可能结果可以分成如下三类：

（1）A类：两列的值都为1；

（2）B类：其中一列的值为0，另一列的值为1；

（3）C类：两列的值都为0.

特征矩阵相当稀疏，导致大部分的行都属于C类，但只有A、B类行决定sim( Si , Sj )，假定A类行有a个，B类行有b个，那么sim( si,sj )=a/(a+b)。

如果我们把C类行都删掉，那么第一行不是A类行就是B类行，如果第一行是A类行那么h(Si)=h(Sj)，因此P( h(Si)=h(Sj) )=P(删掉C类行后，第一行为A类)=A类行的数目/所有行的数目=a/(a+b)

所以，P(h(Si)=h(Sj)) = sim(Si,Sj)。

介绍完了jaccard相似度和MinHash，我们回到我们最初的工作，对原始特征矩阵做随机排序，计算每一个排序后每列的哈希值，一共做三次。

比如，第一次随机排序后，特征矩阵变成如下所示，可以求得该次随机排序后的最小哈希值。

那么，三次之后，我们得到如下一个矩阵，我们可以把它视为原始特征矩阵的一个压缩，或者说是降维。

最后我们需要验证的是，哈希过后的特征矩阵，是否保持了数据的相似性。相似度的计算结果如下表，所示，可以看出，极好的保留了相似性。

注：在原始数据相似度的计算中，去掉了C类数据，也就是都为0的数据。

这就是一个局部敏感哈希的例子，进行了数据的降维，之后查找所消耗的代价就大大减少了
怎么发现“相似”的集合或者项在一个非常大的集合里而不需要一个一个的比较（两两对比）。因为这样的比较是一个二次方的时间复杂度，所以我们的LSH就这样应运而生啦
Locality Sensitive Hashing(LSH) 一般的思想就是hash items （项）到一个桶里（bins）很多次，并且留意在同一个bin 里的items
仅仅只有那些高相似度的items 有更多的可能在同一个桶里。
相似的文档是由相似的集合组成的。
许多的数据挖掘问题都可以表示为发现相似的集合的问题：

网页有很多的相似的词汇，可以用来根据主题来分类
电影的推荐系统
根据某个电影找到喜欢同类电影的人
相似的文档例子

镜像网站（mirror sites）
剽窃问题包括大量的引用
相似的新闻在很多的不同的网站
Big pitcture
##基本概念

shingling: 表示的是对一个文档的转换，可以理解为对一个文档进行切割
minhashing: 将一个大的集合中的元素转换为很多短小的签名，但是保持了这些集合中的元素的相似性
Locality-sensitive hashing: 关注的是签名对可能的相似性
整体架构
一下这个图揭示了Locality Sensitive Hashing 的一个整体结构图。

当接受到文档，或者输入文档之后，我们开始shingling 他们，就是将这个文档切割成一个一个的元素，这些元素是由很多的字符串组成的（由k个字符串组成）
用Minhashing 得到我们集合元素的签名
产生可能的候选对

Shingles

K-shingle
又叫做是k-gram 。一个文档可以看成是K个字符组成的一个集合。

这个概念该什么NLP的同学应该很熟悉了，在我之前的文章中也有提到了，怎么得到我们的shingles. 还有代码的呢。
例如; k=2; doc=adcab 这个集合的2-shingles={ab,ba,ca}
我们对这个字符串进行划分，得到的是ad dc ca ab 由于集合是唯一性的所以不可能有重复的元素
k=2 其实是一个比较糟糕的选择，我们一般选择K在实际情况中一般会选择9或者10，我们要求这个k一般要大于我们文章中出现的单词的长度。这样的选择会比较合理一些

Shingles 和相似性

文档如果是相似的，那么他们理论上（intuitively）应该有很多的shingles 是相同的。这里的相似其实是指的是在文本上的相似 text similarity 不涉及到我们说的其他的主题相似等另外一些情况。
交换文档的两个段落只会影响 2k 的shingles 在段落的边界处
e.g.
k=3, “The dog which chased the cat” 转换成 “The dog that chased the cat”.

这个时候被替换的3-shingles 就是g_w, wh, whi, hic, ich, ch, and h_c

#MinHashing
在介绍MinHashing 之前我们有必要来介绍一些重要的基本概念。在这里最重要的就是我们的Jaccard Similarity

Jaccard Similarity

Jaccard similarity 指的就是两个集合交集的个数除以两个几何并集的个数

看下面这个例子我们也可以理解：

在这里有两个集合，交集中元素的个数是3，而并集中元素的个数是8

这个时候我们的Jaccard Similarity 相似度就是3/8

我们来看下面的这个例子来说明我们的列的相似性

这个很好理解，我们看列的相似性，我们只看含有1 的那些行，所以我们的并集个数就是5，而我们的交集个数就是2 所以相似性就是 0.4

这里需要注意的是，我们的并集不是 0 1,1 0,11，00，我们的交集也不是11,00

这里我们一行一行的看，每一行表示的其实是一个属性值，你这个数据集或者是单个的个体有没有我这个属性，每一行是不同的，而且我们不考虑我们要比较的这两个元素都没有这个特征值

看上面这个图我们也可以很清楚的看到。

但是我们也可以用另一种眼观来看，就是假设只有两列，我们的数据集，也就是说有两个元素，那么行的类型也就是说是有4种就是 A 有B没有或者是A没有B有或者是两个都有或者是两个都没有的情况。

如下图所示：

在这里我们a 看做是两个元素都具有的属性的个数。
b 就是C1 元素有而C2元素没有的情况的个数。
c 就是C2有而C1元素没有的情况下的个数。
d 就是两个元素都没有的情况下的个数。

所以我们的Jaccard Sim = a/(a+b+c)

定义
minhash 函数 h© = 表示的是在某一列中的第一个出现1的那一行的行号,我们用这个行号中第一次出现1的那个行来做我们这个矩阵的那一列的特征值。

如下图所示，这里有一个矩阵

我们对这个矩阵的每一行标注一个号码，就是紫色的这个部分

从这里我们可以看出我们的输入的这个布尔矩阵的可以得到一个特征矩阵

这个时候我们的到的一个签名矩阵就是这个输入矩阵的第一个出现1的行数特征值是3，1，1，2

接下来我们对我们的这个输入矩阵进行重拍，得到一个新的矩阵。

我们在对这个输入矩阵进行第三次的重排，这个时候我们又可以得到一个新的特征值
我们对这个矩阵重拍之后得到一个新的矩阵，绿色的那个表示重排之后这个时候它表示的第一排是最后一排，最后一排是第一排的意思。

得到的特征值就是 2,2,1,3

为什么这么做，因为我们可以用这个singnature matrix 的相似性（Jaccard similarity）来表示我们的这个input matrix 的相似性

我们来看我们的这个例子

我们来看我们的第1列和第2列，这个时候我们需要观察的就是我们的input matrix 这个矩阵。

这两个样本的相似性我们可以看出来是 1/4 根据我们刚才介绍的公式 sim=a/(a+b+c)

我们要比较第一列和第二列我们拿出这两列来看
0 1
0 0
1 0
0 1
0 0
1 1
0 0

我们只关注有1 的列

0 1
1 0
0 1
1 1

a 的个数是1
并集的个数是4 所以我们得到的是1/4

我们看我们的签名矩阵signature matrix
第一列和第二列拿出来看
3 1
2 2
1 5
签名的相似性 1/3
以此类推我们可以得到我们所求的图中要求的相似性
我们看图中第2 列和第3列 Jaccard similarity 就是 1/5
我们签名的相似性就是1/3

根据上面我们计算分析的例子发现其实我们可以用signature matrix 中hash 值的相似性来表示我们的样本的相似性

这就推理出了我们重要的属性

Surprising Property
这个标题觉得就叫surprising property 比较好，翻译过来我都想不到比较好的词汇，惊奇的属性

我们用MinHash 计算我们的样本我们的minhash 函数h(C1)=h(C2) 当我们的函数值相等的话，这个时候这个值有很大的可能性等于我们这两列的相似性 sim(C1,C2)
而且他们都等于 a/(b+c+a)

这个结论和我们刚才实验自己计算的结果是一致的！！！

这个也是我们LSH 的原理，在一开始的时候我们也提到了，如果对一些元素进行hash ,他们如果这些元素是相似的或者是相同的，那么他们就有可能被映射到我们的同一个桶里。

更重要的是我们想一想我们的算法

我们是从上往下看找到我们列举的C1 和C2 中出现的第一个1
只有是类型a 的行的时候我们才有 h(C1)=h(C2).如果是类型b 或者是类型c这样是不可能相等的，他们的minhash 的值。
这个其实比较容易能够想明白的，必须同一行都是1才可能出现他们的minhash 是相同的情况。

##签名的相似性

签名的相似行就是minhash 函数中值相同的分数的分子
这句话要怎么理解呢，我们可以看下面这个图

比如说我们要比较的是这个签名矩阵（Signature Matrix ）的相似性，我们比较我们的第1列和第二列的相似性，那么我们的签名的相似性就是我们要比较这两列中行里面的数字相同的个数

我们根据我们的相似性矩阵我们来看；这个矩阵第一列和第二列的相似性就是1/3 ；在第二行相同。

因此，我们比较希望的是两个签名的相似性和我们原先两个样本也就是两个原始的列，在没有计算MinHash 的原始的两个列的它们两个的Jaccard similarity 要一致，或者说是要接近。
我说的比较啰嗦，也就是签名的相似性和原先矩阵的相似性要是比较接近的或者说是一样的。

这里说的就是我们上面这张图片上显示的在最左边的这个列的Jaccard Similarity 必须和我们的签名的相似性保持比较接近。怎么能做到保持比较接近呢，当然就是我们的签名的矩阵越长越好了。

我们可以看看下面的这个例子

充分的说明了上面我们说的问题。

好的这里解释完了，我想在这里放上standford 的课件给大家参考一下，尤其是理解一下中文的翻译和理解和英文在表述上的差距，我希望我的讲解能够让各位豁然开朗。

Minhashing 的执行

虽然刚才讲了一堆废话，介绍了我们Minhash 算法以及对应的函数的映射规则，但是一般来说基本上上面等于废话，白说。创造LSH的时候就是为了能够处理大数据，上面的那个只能针对数据集比较小的情况才考虑。

如果情况变了呢？

假设如下的情况

如果我们有 10亿行这么多的数据，这个时候我们按照上面的方式来玩，显然是行不通的。把10亿行数据放到内存中排序，这样显然是不科学的。有的人写代码不仅是把行考虑进去了，还考虑了矩阵，这就更尴尬了，你不仅考虑了这么多属性，你还要考虑样本？

按照刚才上面说的这些方法来执行的话，容易出现下面的这些问题：

很难对10亿个数据进行排序。
没有这么大的内存空间
容易造成系统奔溃
所以，我们就要换种玩法。我们刚刚说了，要看两个列的相似性我们可以从签名矩阵上来看，签名矩阵的长度越长的话，这样出错的机会或者说相似的机会就比较小。我们没有必要挑选比较所有的行，我们只要保证我们的签名矩阵的长度合理就可以了。

###执行对策

所以我们想了下面的这个执行对策：

我们不用对所有的行进行一个随机的排序，我们只需要挑选，我们用100个不同的哈希函数来对我们的行号进行计算就可以得到新的数据，这个数据就代表我们原先的行号变更出来的行号，可以看成是对我们整个矩阵的行进行洗牌。
其实这样的Hash 函数很难找到，因为可能是会存在hash 值的碰撞，但是这个不影响我们这个算法的执行。
这个想法就是把我们选择hash 行数对行号做计算，得出来的数字就是相应的排序行号，哈哈，我是不是搞得有点啰嗦啊
在这里我们引入一个Slot 的值我们把这个值叫做M，M的初始值是无穷大。我们有100个hash 函数我们这么来表示我们的hash 函数 hih_{i}h
i

, i 的取值是从1 到100 的，我们用hash 函数 hih_{i}h
i

计算得到一个Hash值，如果我们的样本，也就是某一列的某一行是1我们将这个计算出来的Hash值如果比我们的M值要小，那么M就保存着我们计算出来的较小的hash 值，实际上就是我们默认排列出来较小的行号。
这个算法的思想实在是太帅了，有没有！如果你脑子好使，一定已经发现它迷人的规律和为什么这么想的方式了。

下面我们来看算法的具体描述

MinHashing 算法（MinHashing algorithm）

for each hash function hi  do

   compute hi (r);

for each column c 

	if c has 1 in row r 

	   for each hash function hi do

 	         if hi (r) is smaller than M(i, c) then

	  M(i, c) := hi (r); end; 1 2 3 4 5 6 7 8 我们来描述一下我们的算法

1.首先我们先把我们的M slot 值设置为无穷大

就假设我们有100 个hash 函数
我们从每一个hash 函数开始对我们的行号进行计算，当然，你想要你的签名矩阵（signature matrix ）长度有多长你最外围的循环就来几次

每一个hash 函数 hih_{i}h
i

对我们的行 r 做计算，我们把行号表示为r hih_{i}h
i

作用在上面就是 hi（r）h_{i}（r）h
i

（r）

这个时候查看我们的每一列，我们只考虑我们的列中只含有1的元素，为个毛呢，这是因为我们的minhash 函数本来就是要找的就是随机排序之后的某一列中出现1 的行号的第一个

如果我们的hash 函数值比我们的M值小这个时候我们就替换我们M 值

其实就是不断让M保持我们的搜索到1的最小的行号，这个就是这个算法的精髓所在。

下面我们来看一个例子

这个是我们的行，以及我们的两列样本的对应属性的情况

我们设置了两个hash 函数来计算我们的signature 的签名应该要哪个
h(x)=xmod5h(x) = x mod 5h(x)=xmod5
g(x)=(2x+1)mod5g(x) = (2x+1) mod 5g(x)=(2x+1)mod5

如果我们按照常规方法来计算的话，我们要对这个行号进行一个排序，然后找到行号第一个为1 的来做我们的特征值，现在换了计算特征值的方法，我们对行号进行hash 不断的替换我们的最小行号达到我们原始的目的

我们设置两个签名的M值都为无限大，这个时候我们计算行号对应的hash 值

这个时候我们看到两个hash 值分别为1 和 3
这个时候我们查看他们的对应的原始行也就是第一行的每一列，我们看到只有第一列有元素为1所以我们要替换的只能是第一列的M值如上图所示。这个时候我们在依次计算我们的以下几行的hash 值

计算到第二行的时候得到两个hash 值分别是2,0 但是我们检查列只有第2列有1，所以比较大小之后替换得到上面的这个结果

接下来我们来查看我们第三行的Hash 值，我们发现计算的是3,2 并且我们两列的值都是为1 的这个时候我们就要来看看替换谁，只能替换的结果是越来越小的。
3 比sig1 和sig2 的值都要大，所以我们保留不替换，我们看2 比sig1 大，所以被替换的就是它。以此类推，我们得到了下面的结果

其次，这样做的目的是因为我们的数据常常是按照我们的列来给出的，而不是按照行来给出的，如果按照行来给出，我们只需要对矩阵进行一次排列即可。

我们一般会得到很多的文档，以及文档被划分出来的shingles

候选签名

我们用上述的这些算法得到的签名其实是一些候选的相似对，对于这些相似的对我们必须要对他们进行一个评估。对于我们的signature matrix 我们必须对这个hash 得到的列在进行Hash ,这个时候要让这些元素映射到不同的bucket中。（注意，这里的hash 函数可以用一些比较传统的hash 函数）这样我们认为这些列映射到我们相同的buckets 中的就是我们的候选的相似的对，或者说是我们候选可能相似的样本。

我们要得到我们的候选签名，这个时候我们就要设置一个阈值threshold，这个阈值必须是小于1的当我们的相似度超过了这个阈值的时候我们就认为这些候选的签名是相似的
我们来看一下怎么对我们得到的这个Matrix M 进行处理又或者说是怎么对我们的这个signature M进行处理

我们看下面的这个图，以上的图都来自与这个PPT
http://i.stanford.edu/~ullman/cs246slides/LSH-1.pdf

上面的这个图黄色的部分就是我们的Matrix M，或者说是我们的signature matirx

每一列我们可以看成是一个样本的签名，就是我们图中的粉红色的条形的部分，就是一列，这一列就是我们样本中的一个签名或者说是样本的特征值，指纹，你都可以这么理解。

然后把这个矩阵划分成了b 个bands 也就是b 个条状。每一条含有r 行。

接下来我们要做的就是

对每一个signature 分段之后的每一个band 计算一个Hash值然后让它映射到一个长度为K的bucket 里面。我们的k 要设置的尽量的大一些。这样子是为了减少碰撞的发生。
我们候选的candidate就是我们认为可能相似的样本就是那些列的hash 值被映射到同一个bucket 里面的，一般有 band 的投射个数>=1
我们通过调节我们的 b 以及 r 能够捕捉到大多数的相似的pair ,但是很难捕捉到不相似的pair
我们看下面的这个图

我们发现第二列和第6 列经过计算一个Hash值之后被映射到了同一个桶里面，这个时候我们可以认为这两个band 很有可能是相同的。当然也有极小的概率是发生了碰撞。

是这样的吗？

我们来计算一个概率看一看:

假设我们 C1 和C2 有80% 的相似度，在这里我们设置一个Matrix M 它有100 行，我们把这个矩阵分成了20 个bands 每一个band 里面都有5 行（r）

这个时候我们来计算一下C1 以及C2 在某个特定的band 里面相似的概率，记住我们有5行，每一行相同的情况是 0.8 的概率:

(0.8)5=0.328(0.8)^5 = 0.328(0.8)
5
=0.328

那么我们是不是可以计算出C1 ，C2 在任何一个band 都不相似的概率就是:
$ (1-0.328)^{20} = 0.00035$

这个时候我们可以得到如果我们设置相似度的阈值是80% 那么它的false nagatives 的概率约为1/3000

我们在看另外的一个例子：
假设我们认为C1，C2的相似度只有40%

C1 和C2在同一个band 里面相同的概率：
注意我们还是认为我们有100行，也就是我们的签名矩阵（signature matrix 或者说是我们的matrix M）有100 行，同样是被分成了20个band,每一个band还是有5行

这样，如果C1 和C2 在某个特定的band 里面是相同的概率：

(0.4)5=0.01(0.4)^5 = 0.01(0.4)
5
=0.01

那么在20 个band 里面都不相同的概率就是
(1−0.01)20=0.9920=0.82(1-0.01)^{20}=0.99^{20} = 0.82(1−0.01)
20
=0.99
20
=0.82

我们计算一下如果C1，C2在1个band 或者2,3,4，…20 个band里面都相同的概率
1-0.82<0.2

我们的false positive 是远小于40% 的

所以当我们设定一个阈值，相似度大于阈值的时候，如果列的相似度非常的大，他们在同一个bucket的概率是非常大的

我们看下面的例子，s 表示的是相似度

所以实际的情况就是下面的这个样子

这个就说明了我们的LSH 如果其中有两个band 被映射到同一个 bucket 我们可以认为这两列就是相似的。说了这么多意思就是尽管我们的文档很大，产生的最后的Matrix M 也很多。但是我们只需要计算一个band .我们就可以大概的预测出我们样本的相似性了。

看完，学完这个LSH是不是想拍着大腿直呼 66666666了呢，反正我是被震撼到了。

OK,当处理大数据的时候，方法也就是这个原理了，你们学会了没有呢。
之后还是会有更加详细的介绍，主要是觉得有个时候是不是篇幅太长的原因，为什么有个时候写的太长了好像速度会有点影响，感觉CSDN的编辑器的有时候就是容易卡

#写在后面的话

喜欢本小姐的博客的各位帅哥美女们，有兴趣的话打赏一个呗，哈哈，有帮助就更要打赏好么，我都帮助到你了。被黑被捅刀子更是要打赏我，毕竟这样才能进步，啊哈哈哈。给你们一个超大的超大的么么哒，超大的好么！
还有人不喜欢我在文章后面放我自己喜欢的图片，哼，本宝宝就是不喜欢这种死板的做科研的风格，我的博客我做主，好吗！就是这么的任性！

References
i.stanford.edu/~ullman/cs246slides/LSH-2.pptx
https://web.stanford.edu/class/cs345a/slides/05-LSH.pdf
https://www.youtube.com/watch?v=bQAYY8INBxg
https://www.youtube.com/watch?v=MaqNlNSY4gc&t=2010s
https://www.youtube.com/watch?v=_rWpSC-s4vU
https://www.youtube.com/watch?v=c6xK9WgRFhI 3 1 Finding Similar Sets 13 37
3 2 Minhashing https://www.youtube.com/watch?v=96WOGPUgMfw
Locality Sensitive Hashing https://www.youtube.com/watch?v=_1D35bN95Go
http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

在实际应用中，我们所面对的数据是海量的，并且有着很高的维度。在对数据的各种操作中，查询操作是最常见的一种，这里的查询是指输入一个数据，查找与其相似的数据，那么怎样快速地从海量高维数据中，找到与某个数据最相似的数据，成为了一个难点和问题。