【搜索引擎(五)】局部敏感哈希

1.介绍

    哈希是一种常用的数据摘要方法，可以把大段的数据映射成固定长度的字符串。在查找某个文档的时候，我们不希望每一次都比较大段的数据，以此来确定文档的位置，这样太过浪费生命了。只要实现计算好文档的哈希值，就可以只通过比较两个文档的哈希，查出匹配的文档，从而大大减少检索的时间。

    传统的hash方法，比如md5，其设计的目的是为了让整个分布尽可能地均匀，输入内容哪怕只有轻微变化，hash值就会发生很大的变化，这跟它本来是为了跟哈希表配合有关的。但是由于搜索引擎的发展，我们很容易遇到这种情景，即我们为了加快搜索的效率会利用索引，但是索引本身如果直接使用哈希，可无法找到内容相近的，而只能找到完全匹配的，这在现实中是很难满足的。

    现实中很多查找问题都是寻找相似集，而非完美匹配集。

    这种问题最后是在高维空间里查找，例如：1.两篇有相似单词的文章；2. 两个消费了相似物品的顾客；3.两张有相似特征的图片。

2. LSH的作用

    我们需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest Neighbor,AN），例如K-d tree；或近似最近邻查找（Approximate Nearest Neighbor, ANN），例如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH是ANN中的一类方法。

    LSH的基本思想是：将原始数据空间中的两个相邻数据点通过相同的映射或投影变换（projection）后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。

3. 实现

    实现Locality Sensitive Hashing的重要工具只有三个。

    Jaccard距离、Min-Hashing函数、桶映射

    算法流程是：Documents -> Shingle -> Min-hashing产生签名（摘要）->检索.其中Shingle解释如下：

　　Shingling

　　shingling是一种文本的预处理方式。对文档分别进行Shingling（将待查询的字符串集进行映射，映射到一个集合里，如字符串"abcdeeee", 映射到集合"(a,b,c,d,e)", 注意集合中元素是无重复的，这一步骤就叫做Shingling, 意即构建文档中的短字符串集合，即shingle集合。类比倒排索引，我们可以得到类似的矩阵：

    3.2 度量和函数

　　A. C1和C2的Jaccard 距离：

    B. 重要的哈希函数     Min-Hashing

    输入值是一个矩阵：shingle（文本单元）x文档矩阵，值(i,j)表示词si在文档dj中出现与否。

    这样文档的哈希值长度是我们设定的置换个数。在下面的例子中，文档1,2,3,4的哈希值分别是221,112,241,112

    找到一个哈希函数，如果sim(C1,C2) 很高, 那么很高概率h(C1) = h(C2)

    如果sim(C1,C2)低，那么很高概率h(C1) ≠h(C2)。

    Min-hashing函数：    hπ(C), 表示在经过π置换的C列中为1的方格的第一个下标。   注：π置换(a1,a2,…)会将向量X中的xi置换到位置ai(i=1,2,3…)

　根据这种定义，有如下性质：选择一个随机π，则Pr[h_π(C₁) = h_π(C₂)] = sim(C₁,C₂)

    证明： 设y∈X, 因为Pr[π(y) = min(π(X)) ] = 1/|X|,(这个性质下面没有用到)

         若 π(y) = min(π(C₁∪C₂)), (即y在置换后是新向量里的最小为1下标)，

         则 要么π(y) = min(π(C₁) 且 y∈C₁, 要么π(y) = min(π(C₁) 且y∈ C₂。

         这两种情况同时成立的概率为

                Pr[min(π(C₁) = min(π(C₂)] = |C₁ ∩C₂| / |C₁∪C₂| = sim(C₁, C₂)

         这个概率反映的是随机置换的结果。

    

    Min-Hash Signature

用sig(C)表示文档编码C的签名, 则sig(C)[i] = min(π_i(C)), 如100个随机置换得到的签名需要100 个byte。

   

C. LSH算法

　　　　　　1. 先看产生签名的实现方法:

for each column C and hash-func ki keep a slot of the min-hash value
	sig(C)[i] = ∞
	Scan rows looking for 1
		Suppose row j has 1 in column C  即: C[j][i] = 1
		Then for each ki:
		    if ki(j) < sig(C)[i], then sig(C)[i] <- ki(j)  // 用每个置换的下

　　上面是签名算法，而LSH 算法是检索的算法，给定一个相似度值s和文档，找出相似文档。

        由于检索的方法是很naïve的，下面我们只需要验证LSH的性质，并且给出实现方法即可。

问题：

给定s和n x m矩阵M, 先在矩阵M (shingle * document)中找出候选对

        n = |shingle|, m = |document|

        

        把矩阵分割成b个band(条带)，每个带有整数个数 r = M / b

样例：

假设有100,000个文档, 每个签名是100个整数(100 bytes)

        签名占了40 Mb。

        b = 20, a = 5, s=0.8.

        相似度s >= 0.8的时候, 验算至少有一个band是相同的概率：

sim(C1, C2) = 0.8, (0.8)^5 = 0.328,

    1 – (0.328)^20 = 0.00035, 即sim(C1, C2) = 0.8 的时候至少有一个band相同的概率是99.965%。

        同样地, 计算sim(C1，C2) = 0.3的时候可以验算得到其概率很低。

    

4. 参考：

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets,http://www.mmds.org/mmds/v2.1/ch03-lsh.pdf