数据挖掘一个非常重要的任务就是找到相似项。不管是文本的相似度或者推荐系统，相似性都是一个重要的因素。
Jaccard Similarity 提供了一个集合之间的相似性度量方法。 定义：similarity of sets S and T is | S ∩ T | / | S ∪ T | 其实就是相同的数量占总数的比值。
但在文本方面，如果单纯使用Jaccard Similarity，并不能很好的判断文本的相似度。也很好理解，句子的语意更多的和词语的排列以及顺序有关，而不是仅仅比较里面相同的词语。在文本相似性判断中，有一种简单通用的方法，shingling
Shingling
定义：Define a k-shingle for a document to be any substring of length k found within the document. 举个例子，“nice to meet you” 在 k = 2 时，集合是 { “nice to”，“to meet”，“meet you” } 。这样就可以考虑到一些语义上的关系。 那么，问题就来了。怎么选取合适的k值。k太小，那么就不能很好的判断相似性了（k = 1 就是上面的集合比较了），而太大就可能找不到相似的子集了。从经验来看，根据文本的长度，k取5～9比较合适。
Hashing
直接比较文本的集合，用遍历+查找的方法对于大规模的数据，效率超级低。可以考虑用哈希来进行优化。将 shingle 映射到桶中，并用桶的编号来代替文本表示，可以减少数据占用的空间并且便于后续操作。
Signature
尽管经过了哈希处理，占用的空间还是过大。如果要比较的文本数量较大，计算量以及对于内存的要求都会很高，于是想到了可以用一个签名来表示一段文本。
集合的矩阵表示
| element | S1 | S2 | S3 |
|---|---|---|---|
| a | 1 | 0 | 1 |
| b | 0 | 1 | 1 |
| c | 1 | 1 | 0 |
可以用来表示 S1 = { a, c }, S2 = { b, c }, S3 = { a, b }
Minhashing
把上面的元素换一个排列方式，可以得到一个新的矩阵。
| element | S1 | S2 | S3 |
|---|---|---|---|
| b | 0 | 1 | 1 |
| a | 1 | 0 | 1 |
| c | 1 | 1 | 0 |
为了得到各集合的最小哈希值，首先对矩阵进行随机行打乱，某一列的最小哈希值就等于打乱后的这一列第一个值为1的行所在的行号。于是上述重新排列的矩阵中，h(S1) = a, h(S2) = b, h(S3) = b
- 对于一个随机的排列来说，两个集合 minhash 相等的可能性等于这两个集合的 Jaccard similarity
真实的计算过程
打乱操作对于非常大的矩阵来说计算量也是非常大的，我们可以用随机的哈希函数来模拟随机排列的过程。
| row | S1 | S2 | S3 | hash1 (x+1 mod 4) | hash2 (3x+1 mod 4) | … |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | … |
| 1 | 1 | 0 | 1 | 2 | 0 | … |
| 2 | 1 | 0 | 0 | 3 | 3 | … |
| 3 | 0 | 1 | 0 | 0 | 2 | … |
于是，对于上面的例子来说，真实的过程如下： 第一步，初始化无穷大
| hash | S1 | S2 | S3 |
|---|---|---|---|
| h1 | ∞ | ∞ | ∞ |
| h2 | ∞ | ∞ | ∞ |
第二步，按顺序遍历上面的表，第 0 行，S2 和 S3 都是 1，他们的 hash 值小于当前的初始值∞，于是表中填入他们的 hash 值。
| hash | S1 | S2 | S3 |
|---|---|---|---|
| h1 | ∞ | 1 | 1 |
| h2 | ∞ | 1 | 1 |
继续，只更新比当前小的值
| hash | S1 | S2 | S3 |
|---|---|---|---|
| h1 | 2 | 1 | 1 |
| h2 | 0 | 1 | 0 |
再继续
| hash | S1 | S2 | S3 |
|---|---|---|---|
| h1 | 2 | 0 | 1 |
| h2 | 0 | 1 | 0 |
于是就得到了一个签名矩阵。 通过比较这个签名矩阵中不同集合的Jaccard similarity，就可以估计他们的真实相似度。
Locality-Sensitive Hashing
在数据量非常大的时候，仍然不能有效的找到相似的元素。我们希望可以直接关注可能相似的元素，而不是对所有的元素（签名）进行比较。于是，我们再来一个哈希操作。 完全一样的元素在同一个哈希函数下有同样的值，相似的元素也更有可能被映射到同一个桶中，因此可以直接比较同一个桶中的元素，他们相似的可能性最大。
为了便于说明，创建一个大一点的签名矩阵。（省略行号）
| S1 | S2 | S3 | S4 |
|---|---|---|---|
| 1 | 2 | 1 | 0 |
| 2 | 0 | 2 | 1 |
| 2 | 0 | 2 | 0 |
| 2 | 2 | 1 | 3 |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | 1 |
我们把一个签名矩阵分成 b 个 band 和 r 行 b = 2 ， r = 3
band 1
| 1 | 2 | 1 | 0 |
| 2 | 0 | 2 | 1 |
| 2 | 0 | 2 | 0 |
band 2
| 2 | 2 | 1 | 3 |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | 1 |
对所有的行使用相同的哈希函数，对于每个行条使用一个独立的桶数组，为了防止不同行条中的相同列被哈希到同一个桶中。只要两个集合在某个行条中有落在相同桶的两列，这两个集合就被认为可能相似度比较高。比如 band1 中的 S1 和 S3 会被映射到同一个桶中，因此 S1 和 S3 所在的文档就被认为是可能相似的（*candidate pair*）
不难证明以下几点：
The probability that the signatures agree in all rows of one particular band is sr .
The probability that the signatures do not agree in at least one row of a particular band is 1 − sr.
The probability that the signatures do not agree in all rows of any of the bands is (1 − sr )b .
The probability that the signatures agree in all the rows of at least one band, and therefore become a candidate pair, is 1 − (1 − sr )b .