minHash（最⼩哈希）和LSH（局部敏感哈希）
在数据挖掘中，有⼀个⽐较基本的问题，就是⽐较两个集合的相似度。关于这个问题，最笨的⽅法就是⽤⼀个两重循环来遍历这两个集合中的所有元素，进⽽统计这两个集合中相同元素的个数。但是，当这两个集合⾥的元素数量⾮常庞⼤时，同时⼜有很多个集合需要判断两两之间的相似度时，这种⽅法就呵呵了，对内存和时间的消耗都⾮常⼤。因此，为了解决这个问题，数据挖掘中有另⼀个⽅法。 Jaccard相似度
在介绍具体算法之前，我们⾸先来了解⼀个概念：Jaccard相似度。
Jaccard相似度是⽤来描述两个集合间的相似度的，其计算⽅法如下（假设有两个集合A，B）：，也就是A与B交集的元素个数除以A与B并集的元素个数；为了书写⽅便，下⾯的讨论中我们将集合A和B的Jaccard相似度记为SIM(A,B)；
阿凡达 阿凡提
例如：上图中有两个集合A，B；A中有4个元素，B中有5个元素；A，B的交集元素个数为2，并集元素个数为7，所以SIM(A,B) = 2 / 7；
k-Shingle
假如我们把⼀整篇⽂章看成⼀个长的字符串，那么k-shingle就是这篇⽂档中长度为k的任意字符⼦串。所以，⼀篇⽂章就是很多个不同的k-shingle的集合。
例如：现在我们有⼀篇很短的⽂章，⽂章内容为abcdabd，令k=2，那么这篇⽂章中所有的2-shingle组成的集合为
卢新{ab,bc,cd,da,bd}，需要注意的是，ab在⽂章中出现了两次，但是在集合中只出现⼀次，这是因为集合中不能有相同的元素。
尽管⽤k-shingle的⽅式来表⽰每篇⽂章，然后再通过判断每篇⽂章中shingle集合的相同元素的数量，就可以得出⽂章的相似度；但是，⼀篇⽂章得到的shingle集合的元素个数是很多的。假定k=4，那么每个shingle中就会有4个字符，存在内存中就⾄少需要4个字节；那么要以这种⽅式存下⼀篇⽂章的所有shingle，需要的内存空间⼤概是原⽂档⼤⼩的4倍（假设原⽂档⼤⼩为100K，那么存下这篇⽂档的所有shingle则需要400K），这是因为原⽂档中的每个字符串都会出现在4个shingle中（除了开头和结尾那⼏个字符）。因此，以shingle 的⽅式来存⽂章会消耗⼤量的内存。
接下来，我们需要把上⾯的shingle集合替换成规模⼩很多的“签名”集合。这样，就可以通过⽐较两篇⽂章的签名集合的相似度，就能够估计shingle的相似度了。这样得到的相似度只是原来相似度的近似值。 solver
在介绍签名集合之前，我们先来看下如何将集合表⽰成其特征矩阵。 特征矩阵
特征矩阵的⼀列就对应⼀个集合，所有的⾏加起来就是所有集合元素的全集，如果集合中有那个元素，则矩阵中的对应位置为1，否则为
0（好吧，讲的不是很清楚，还是直接上例⼦吧）：
假设现在有4个集合，分别为S1，S2，S3，S4；其中，S1={a,d}, S2={c}, S3={b,d,e}, S4={a,c,d}，所以全集U={a,b,c,d,e}
那么这4个集合的特征矩阵为：
其中第⼀⾏和第⼀列不是特征矩阵的⼀部分，只是为了便于理解⽽写上的。
最⼩哈希
构建集合的特征矩阵是为了计算集合的最⼩哈希。
为了计算最⼩哈希，⾸先对特征矩阵的⾏进⾏打乱（也即随机调换⾏与⾏之间的位置），这个打乱是随机的。然后某⼀列的最⼩哈希值就等于打乱后的这⼀列第⼀个值为1的⾏所在的⾏号（不明⽩的直接看例⼦），⾏号从0开始。
例如，定义⼀个最⼩哈希函数h，然后对上⾯的特征矩阵进⾏⾏打乱，原来第⼀列的顺序为abcde，打乱后为beadc，则新的特征矩阵为：
对于列S1，从这⼀列的第⼀⾏往下⾛，直到遇到第⼀个1，所在的⾏号则为这⼀列的最⼩哈希值。所以这4列的最⼩哈希值依次为h(S1) = 2, h(S2) = 4, h(S3) = 0, h(S4) = 2.
最⼩哈希与Jaccard相似度
在经过⾏打乱后的两个集合计算得到的最⼩哈希值相等的概率等于这两个集合的Jaccard相似度。简单推导如下：
假设只考虑集合S1和S2，那么这两列所在的⾏有下⾯三种类型：
产值利润率1. 这⼀⾏的S1和S2的值都为1（即两列值都为1），记为X类；
2. 这⼀⾏只有⼀个值为1，另⼀个值为0，记为Y类；
3. 这⼀⾏两列的值都为0，记为Z类。
假设属于X类的⾏有x个，属于Y类的⾏有y个，所以S1和S2交集的元素个数为x，并集的元素个数为x+y，所以SIM(S1,S2) = x / (x+y)。注：SIM(S1,S2)就是集合S1和S2的Jaccard相似度。
接下来计算最⼩哈希h(S1) = h(S2)的概率。经过⾏打乱之后，对特征矩阵从上往下扫描，在碰到Y类⾏之前碰到X类⾏的概率是x /
(x+y)；⼜因为X类⾏中h(S1)=h(S2)，所以h(S1)=h(S2)的概率为x/(x+y)，也就是这两个集合Jaccard相似度。
最⼩哈希签名
上⾯是⽤⼀个⾏打乱来处理特征矩阵，然后就可以得到每个集合最⼩哈希值，这样多个集合就会有多个最⼩哈希值，这些值就可以组成⼀列。当我们⽤多个随机⾏打乱（假设为n个，分别为h1,h2…hn）来处理特征矩阵时，然后分别计算打乱后的这n个矩阵的最⼩哈希值；这样，对于集合S，就会有n个最⼩哈希值，这n个哈希值就可以组成⼀个列向量，为[h1(S), h2(S)…hn(S)]；因此对于⼀个集合，经过上⾯的处理后，就能得到⼀个列向量；如果有m个集合，就会有m个列向量，每个列向量中有n个元素。把这m个列向量组成⼀个矩阵，这个矩阵就是特征矩阵的签名矩阵；这个签名矩阵的列数与特征矩阵相同，但⾏数为n，也即哈希函数的个数。通常来说，n都会⽐特征矩阵的⾏数要⼩很多，所以签名矩阵就会⽐特征矩阵⼩很多。
最⼩签名的计算
中国医疗设备网
其实得到上⾯的签名矩阵之后，我们就可以⽤签名矩阵中列与列之间的相似度来计算集合间的Jaccard相似度了；但是这样会带来⼀个问题，就是当⼀个特征矩阵很⼤时（假设有上亿⾏），那么对其进⾏⾏打乱是⾮常耗时，更要命的是还要进⾏多次⾏打乱。 为了解决这个问题，可以通过⼀些随机哈希函数来模拟⾏打乱的效果。具体做法如下:
假设我们要进⾏n次⾏打乱，则为了模拟这个效果，我们选⽤n个随机哈希函数h1,h2,h3…hn（注意，这⾥的h跟上⾯的h不是同⼀个哈希函数，只是为了⽅便，就不⽤其他字母了）。处理过程如下：
令SIG(i,c)表⽰签名矩阵中第i个哈希函数在第c列上的元素。开始时，将所有的SIG(i,c)初始化为Inf(⽆穷⼤)，然后对第r⾏进⾏如下处理：
1. 计算h1(r), h2(r)…hn(r)；
2. 对于每⼀列c:
a) 如果c所在的第r⾏为0，则什么都不做；
b) 如果c所在的第r⾏为1，则对于每个i=1,2…n，将SIG(i,c)置为原来的SIG(i,c)和hi(r)之间的最⼩值。
（看不懂的直接看例⼦吧，这⾥讲的⽐较晦涩）
例如，考虑上⾯的特征矩阵，将abcde换成对应的⾏号，在后⾯加上两个哈希函数，其中h1(x)=(x+1) mod 5，h2(x) = (3*x+1) mod 5，注意这⾥x指的是⾏号：
接下来计算签名矩阵。⼀开始时，全部初始化为Inf:
接着看特征矩阵中的第0⾏；这时S2和S3的值为0，所以⽆需改动；S1和S4的值为1，需改动。h1= 1，h2= 1。1⽐Inf⼩，所以需把S1和S4这两个位置对应的值替换掉，替换后效果如下：
接着看第1⾏；只有S3的值为1；此时h1= 2，h2= 4；对S3那⼀列进⾏替换，得到：
接着看第2⾏；S2和S4的值为1；h1=3，h2=2；因为签名矩阵S4那⼀列的两个值都为1，⽐3和2⼩，所以只需替换S2那⼀列：
接着看第3⾏；S1，S3和S4的值都为1，h1=4, h2= 0；替换后效果如下：
接着看第4⾏；S3值为1，h1=0, h2= 3，最终效果如下：
这样，所有的⾏都被遍历⼀次了，最终得到的签名矩阵如下：
基于这个签名矩阵，我们就可以估计原始集合之间的Jaccard相似度了。由于S1和S4对应的列向量完全⼀样，所以可以估计括约肌
SIM(S1，S4)=1；同理可得SIM(S1，S3) = 0.5;
局部敏感哈希算法（LSH）
通过上⾯的⽅法处理过后，⼀篇⽂档可以⽤⼀个很⼩的签名矩阵来表⽰，节省下很多内存空间；但是，还有⼀个问题没有解决，那就是如果有很多篇⽂档，那么如果要出相似度很⾼的⽂档，其中⼀种办法就是先计算出所有⽂档的签名矩阵，然后依次两两⽐较签名矩阵的相似度；这样做的缺点是当⽂档数量很多时，要⽐较的次数会⾮常⼤。那么我们可不可以只⽐较那些相似度可能会很⾼的⽂档，⽽直接忽略过那些相似度很低的⽂档。接下来我们就讨论这个问题的解决⽅法。
⾸先，我们可以通过上⾯的⽅法得到⼀个签名矩阵，然后把这个矩阵划分成b个⾏条(band)，每个⾏条
由r⾏组成。对于每个⾏条，存在⼀个哈希函数能够将⾏条中的每r个整数组成的列向量（⾏条中的每⼀列）映射到某个桶中。可以对所有⾏条使⽤相同的哈希函数，但是对于每个⾏条我们都使⽤⼀个独⽴的桶数组，因此即便是不同⾏条中的相同列向量，也不会被哈希到同⼀个桶中。这样，只要两个集合在某个⾏条中有落在相同桶的两列，这两个集合就被认为可能相似度⽐较⾼，作为后续计算的候选对；⽽那些在所有⾏条中都不落在同⼀个桶中的两列，就会被认为相似度不会很⾼，⽽被直接忽略。下⾯直接看⼀个例⼦：
例如，现在有⼀个12⾏签名矩阵，把这个矩阵分为4个⾏条，每个⾏条有3⾏；为了⽅便，这⾥只写出⾏条1的内容。
可以看出，⾏条1中第2列和第4列的内容都为[0,2,1]，所以这两列会落在⾏条1下的相同桶中，因此⽆论在剩下的3个⾏条中这两列是否有落在相同桶中，这两个集合都会成为候选对。在⾏条1中不相等的两列还有另外的3次机会成为候选对，因为他们只需在剩下的3个⾏条中有⼀次相等即可。
经过上⾯的处理后，我们就出了相似度可能会很⾼的⼀些候选对，接下来我们只需对这些候选队进⾏⽐较就可以了，⽽直接忽略那些不是候选对的集合。这个⽅法适合⽤来计算相似度超过某个值的⽂档的相似度，⽽不适⽤于计算所有⽂档的相似度，因为那些相似度可能很低的⽂档已经被直接忽略了。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议