《算法图解》11.8读书笔记
机械相似性代表着，两个文本内容上的相关程度，比如“你好吗”和“你好”的相似性，纯粹代表着内容上字符是否完全共现，应用场景在：文章去重；
语义相似性代表着，两个文本语义上的相似程度，比如“苹果”和“公司”的相似性；
把LSH局部敏感哈希算法讲明白的一篇博客：Locality Sensitive Hashing ( LSH，局部敏感哈希 ) 详解
常规的敏感hash可以将文本降维成简单数字串，但是计算相似时候只能两两比较，计算量巨大。
局部敏感哈希算法一般用在常规Hash之后，相比两两比较，LSH可以实现再降维+局部寻找匹配对。
一、基本概念界定上的区别
1、Hash叫哈希，也叫散列，可以叫散列算法，也可以叫哈希算法；
2、hash与其他诸如simhash/minhash的区别：
一般的hash可能两个文档本来相似，但是hash之后的值反而不相似了；simhash/minhash可以做到两个文档相似，hash之后仍然相似；
3、simhash与Minhash的区别：
simhash和minhash可以做到两个文档Hash之后仍然相似，但是simhash计算相似的方法是海明距离；而minhash计算距离的方式是Jaccard距离。
4、局部敏感哈希与simhash、minhash的区别。
局部敏感哈希可以在这两者基础上更快的找到相似、可匹配的对象，而且继承了simhash/minhash的优点，相似文档LSH计算之后还是保持相似的。
二、hash函数拓展simhash、minhash算法
1、海明距离
Hamming Distance可以用来度量两个串（通常是二进制串）的距离，其定义为这两个二进制串对应的位有几个不一样，那么海明距离就是几，值越小越相似。例如x=1010，y=1011，那么x和y的海明距离就是1。又如x=1000，y=1111，那么x和y的海明距离就是3。
2、simhash与minhash
simhash和minhash由于hash之后的算法构造不同，所以需要不同的距离去测度，一般simhash用的是海明距离，而minhash用的是Jaccard距离。
Min-hashing定义为：特征矩阵按行进行一个随机的排列后，第一个列值为1的行的行号。举例说明如下，假设之前的特征矩阵按行进行的一个随机排列如下：
元素
S1
S2
S3
S4
他
0
0
1
0
成功
0
0
1
1
我
1
0
0
0
减肥
1
0
1
1
要
0
1
0
1
最小哈希值：h(S1)=3，h(S2)=5，h(S3)=1，h(S4)=2.
三、局部敏感哈希(Locality Sensitive Hashing，LSH)算法
1、LSH算法流程介绍
1、一般的步骤是先把数据点（可以是原始数据，或者提取到的特征向量）组成矩阵；
2、第一次hash functions（有多个哈希函数，是从某个哈希函数族中选出来的）哈希成一个叫“签名矩阵（Signature Matrix）”的东西，这个矩阵可以直接理解为是降维后的数据，此时用simhash、minhash来做，第一步的hash过程可以使用不同的functions来做；
3、第二次LSH把Signature Matrix哈希一下，就得到了每个数据点最终被hash到了哪个bucket里，如果新来一个数据点，假如是一个网页的特征向量，我想找和这个网页相似的网页，那么把这个网页对应的特征向量hash一下，看看它到哪个桶里了。
于是bucket里的网页就是和它相似的一些候选网页，这样就大大减少了要比对的网页数，极大的提高了效率。注意上句为什么说是“候选网页”，也就是说，在那个bucket里，也有可能存在和被hash到这个bucket的那个网页不相似的网页，原因请回忆前面讲的“降维”问题。
但LSH的巧妙之处在于可以控制这种情况发生的概率，这一点实在是太牛了，下面会介绍。
2、LSH实质解读
那么可以看出LSH的实质其实就是把hash之上的数据再一次降维。相比两两比较，LSH可以实现再降维+局部寻找匹配对。
降维会对相似性度量造成什么影响？
数据的维数在某种程度上能反映其信息量，一般来说维数越多，其反映的信息量就越大，比如说对于一个人，假设有一个一维数据：（姓名）,有一个三维数据（姓名，身高，体重），那么这个三维数据反映的信息是不是要比一维的多？如果我们知道的信息越多，是不是就能越准确地判定两个东西的相似性？
所以，降维就在某种程度上造成的信息的丢失，在降维后的低维空间中就很难100%保持原始数据空间中的相似性，所以刚才是说“保持一定的相似性”。
一方面想把数据降维，一方面又希望降维后不丢失信息。
那么LSH就要做一个妥协了，双方都让一步，那么就可以实现在损失一点相似性度量准确性的基础上，把数据降维
3、LSH局部敏感哈希算法
LSH流程中有两个流程，第一个hash是用simhash,minhash来做，在第一部分里面有，第二个hash才是局部敏感哈希的内容。
LSH的具体流程：
1、将Signature Matrix分成一些bands，每个bands包含一些rows（就像把每一个文档ID变成4个（band）部分，4个（band）颜色）。
2、然后把每个band哈希到一些bucket中，注意bucket的数量要足够多（筛选：设定bucket个篮子，然后比对，相同的颜色部分扔到相应的篮子里面）。
3、计算相似性。使得两个不一样的bands被哈希到不同的bucket中，这样一来就有：如果两个document的bands中，至少有一个share了同一个bucket，那这两个document就是candidate pair，也就是很有可能是相似的。（找相似：同一个篮子里面的就是有可能相似的样本框；如果两个篮子都有同样的颜色和同样的ID，说明这几个同样的ID相似性较高）
4、相似性分析案例
下面来看看一个例子，来算一下概率，假设有两个document，它们的相似性是80%，它们对应的Signature Matrix矩阵的列分别为C1,C2，又假设把Signature Matrix分成20个bands，每个bands有5行，那么C1中的一个band与C2中的一个band完全一样的概率就是0.8^5=0.328，那么C1与C2在20个bands上都没有相同的band的概率是(1-0.328)^20=0.00035，这个0.00035概率表示什么？它表示，如果这两个document是80%相似的话，LSH中判定它们不相似的概率是0.00035，多么小的概率啊！
再看先一个例子，假设有两个document，它们的相似性是30%，它们对应的Signature Matrix矩阵的列分别为C1,C2，Signature Matrix还是分成20个bands，每个bands有5行，那么C1中的一个band与C2中的一个band完全一样的概率就是0.3^5=0.00243，那么C1与C2在20个bands至少C1的一个band和C2的一个band一样的概率是1-（1-0.00243）^20=0.0474，换句话说就是，如果这两个document是30%相似的话，LSH中判定它们相似的概率是0.0474，也就是几乎不会认为它们相似，多么神奇。
这里涉及到的参数有点多：
第一个参数：buckets，LSH会预先设定一些篮子，作为相似性匹对的粒度，Buckets越多越好，粒度越细，当然越吃计算量；
第二个参数：维度h，就是第一步hash成多长的维度，simhash可以指定划分的维度；
第三个参数：bands（b），签名矩阵分块，分为不同的部分；
第四个参数：行数row（r），r=h/b，签名矩阵每一块有r行（r个文本）；
第五个参数：相似性S,代表两个文档的相似性。
第六个参数：相似性J,代表buckets共现相似性（J）。
从操作的流程可以得到，LSH第二步是先根据 buckets共现相似性（J） 找出潜在的候选匹配对，然后在这些匹配对之上计算文档相似性（S）。两者相互关系为：
J=1-（1-S^r）^b (1)
文本的相似性才是我们最后要求得的。
更为神奇的是，LSH这些概率是可以通过选取不同的band数量以及每个band中的row的数量来控制的：
纵轴代表buckets共现相似性（J），横轴代表文档相似性（S）。看懂这个图就可以大致了解实战过程中，如何设置参数啦。
看图可知在文本相似性S达到某一个临界值的时候，临界值之下LSH会智能得判定 buckets共现相似性（J）极小，而大于某一个临界值的时候，LSH会判定buckets相似性J极高。
LSH会将相似性高的认为是候选匹配对留下，而相似性低的则不考虑。所以大大简化了计算量。
