文档局部敏感哈希算法

本文介绍文档局部敏感哈希算法。

最小哈希(min hashing)

最小哈希的目的是为特征生成特征签名。为什么需要特征签名呢？举个例子，对于一篇千字文章，如果我想比较和另一篇文章的相似度，那么用直观的方法进行比较是很困难的。所以，需要对文章进行特征提取，提取的特征集合通常被称作签名，也有指纹的叫法。

先给出最小哈希的计算方法： 考虑集合与特征

S1有特征{a,d} S2有特征{c} S3有特征{b,d,e} S4有特征{a,c,d}

首先对行进行随机排(洗牌，shuffle)(稍后介绍这么做的意义)。任意一列的最小哈希值是元素Si拥有的第一个特征。

以上是矩阵的一个行排列转换结果 我们有h(S1) = a, h(S2) = c, h(S3) = b, h(S4) = a

那么，如果两个元素，他们的特征相似（拥有若干个相同的特征），那么，他们的最小哈希值更有可能相同。

这个“更有可能”的概率是多大呢？ 我们以集合S1和S2所对应的列为例，它们每个元素所在的行按照所有可能的结果分成如下三类：

(1)x类 同一行的两个元素都是1。比如S3,S4的d特征。

(2)y类 同一行的两个元素不一样（一个为0，一个为1）。

(3)z类 同一行的两个元素值都为0。也就是两个元素都不具有这个特征。

对S1和S2对应的每行就是这3种类型。h(S1) = h(S2)的概率多大呢？

z类的情况不会对h(S1)和h(S2)产生影响，因为这时候，最小哈希会跳过这些0值。所以，h(S1) = h(S2)的概率可以用x / (x+y)来表示。这个就是S1与S2的Jaccard相似度。

Jaccard相似度是两个集合的交集与并集的比值。S1有特征{a,d}，S3有特征{b,d,e}，那么S1与S3的Jaccard相似度是 ||S1 ∩ S3|| / ||S1 ∪ S3||，也就是||{d}|| / ||{a,b,d,e}|| = 1/4

##最小哈希签名 还是上面介绍的矩阵，我们知道了，如果只进行一次最小哈希计算，那么两个元素的最小哈希值相同的概率是x / (x + y)。为了降低这个概率，我们可以进行多次的最小哈希值计算，那么，两个元素的最小哈希值相同的概率会变成 (x / (x+y)) ^ n。n是我们计算最小哈希值的次数。 （这种现象在计算系统的可靠性中尤为显著，一个串行系统的可靠性是所有部件可靠性的乘积。在一个5000台机器的集群，如果每个机器是99.99%的可靠性的，那么，这个集群没有机器出问题的可靠性是60.65%）

下面继续回到最小哈希签名，我们对上面的矩阵M做n次洗牌，然后每次使用一个哈希函数h1 ~ hn，则可以构建S(S是S1~Sn的集合)的最小哈希签名向量[h1(S), h2(S), ···, hn(S)]，该向量通常写成列向量方式。因此，基于矩阵M可以构建一个签名矩阵。

签名矩阵和M的列数相同，但是行数只有n。对于行很多（上万量级）的矩阵来说，n是很小的值。达到了实现签名的目的（可以用签名矩阵来表征实际上的矩阵M）。

###最小哈希签名的计算 上述对最小哈希签名的产生还有一个实现的问题：洗牌(shuffle)。对大规模特征矩阵进行显式排列转换是不可行的。即使对于上百万甚至数十亿的行选择一个随机排列转换也极其消耗时间，而对行进行必要的排序则需要花更多地时间，因此，对矩阵进行洗牌操作，看似不错，但缺乏可操作性。

最小哈希签名是寻求一种方式，把过多的属性(每行都对应一个属性)以牺牲准确度的方式，用哈希函数来代替

怎么办呢？

幸运的是，我们可以通过一个随机哈希函数来模拟随机排列转换的效果，该函数将行号映射到与行数目大致相当的桶中。哈希函数总是会有碰撞的(collision)，碰撞系数是1/m(m是桶的数量)(也就是说，任何两个记录都会有1/m的概率“碰撞”，如果有n条记录，那么碰撞的概率是(n-1)/m)。

虽然可能出现两个行号被映射到同一个哈希位置，但只要m足够大，并且哈希结果冲突不太频繁的话，差异就不是很重要。

于是，对大规模特征矩阵进行显式的行排列转换就可以被转换成行的哈希计算问题。

选择n个哈希函数,h1,h2,…hn作用于行。根据每一行在哈希之后的位置来构建签名矩阵。令SIG(i,c)为签名矩阵中，第i个哈希函数在第c列上的元素。一开始，对于所有的i和c，将SIG(i, c)都初始化为∞。然后，对行号(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)和h(r)之中的较小值。

挂一段计算最小哈希签名的代码，计算过程实在是太别扭了。

# R langurage
hash1 <- function(x, mod) {
  return ((x+1) %% mod);
}

hash2 <- function(x, mod) {
  return ((3*x + 1) %% mod);
}

om <- c(1,0,0,1,
        0,0,1,0,
        0,1,0,1,
        1,0,1,1,
        0,0,1,0)

originmatrix <- matrix(om, ncol=4, byrow=T)

rownames(originmatrix) <- c(1:nrow(originmatrix))
colnumber <- c(1:ncol(originmatrix) - 1)
colnames(originmatrix) <- paste('S', colnumber, sep = "")

# build hash signature
sigMatrix <- matrix(rep(Inf, 2*ncol(originmatrix)), nrow=2);
rownames(sigMatrix) <- c("h1", "h2");
colnames(sigMatrix) <- paste('S', colnumber, sep = "");

for (row_idx in c(1: nrow(originmatrix))) {
  h1r <- hash1(row_idx - 1, nrow(originmatrix))
  h2r <- hash2(row_idx - 1, nrow(originmatrix))
  
  row <- originmatrix[row_idx,]
  col_not_0 <- which(row == 1) # get 1 idx
  
  for (col in col_not_0) {
    oh1r <-sigMatrix[1, col]
    oh2r <-sigMatrix[2, col]
    sigMatrix[1, col_not_0] <- min(c(oh1r, h1r))
    sigMatrix[2, col_not_0] <- min(c(oh2r, h2r))
  }
}

print(sigMatrix)

可以看到下面的输出:

S0 S1 S2 S3
h1  1  3  0  1
h2  0  2  0  0

LSH(Locallity Sensitive Hashing)

即使可以使用最小哈希将大文档压缩成小的签名并同时保持任意对文档之间的预期相似度，但是高效寻找具有最大相似度的文档对依然是不可能的。主要原因在于，即使文档本身的数目并不是很大，但需要比较的文档对的数目可能太大。

假定有100万篇文章，每篇文章使用的签名长度为250，则每篇文章需要1000(250 * 4(每个整形占4个字节))个字节来表示签名。所有100万篇文档的签名数据占用1GB空间，这个数字小于普通台式机的内存大小。然后，需要比较的次数约10000K ^ 2 / 2。如果计算每两篇文档签名之间的相似度需要花费1微秒，那么这台计算机大约需要6天才能计算所有的相似度。

事实上，我们只关心那些可能相似的文档，而不需要研究所有的文档对。目前对这类问题处理存在着一个成为局部敏感哈希(locallity-sensitive hashing, 简称LSH)或近邻搜索(near-neighbor search)的一般性理论。

考虑有100 000文档(每个文档都是1列)，选取100个hash函数(每个都是integer)。

将这100个哈希函数分成20组(band)，每个组都有5个数。

如果C1和C2拥有80%的相似度: * 他们在一个特定组完全一样的概率是 (0.8)^5=0.328 * 他们在20组中都不同的概率是:(1-0.328)^20=.00035 误判(false negtive)为不相同的概率要低于1/3000。

如果C1和C2拥有40%的相似度: * 他们在一个特定组完全一样的概率是 (0.1)^5=0.01 * 他们至少在其中一个组中一样的概率<= 20 * 0.01 = 0.2 * 但是误判« 40%

1 - (1-s^r)^b