简介

局部敏感哈希(Locality Sensitive Hasing)是一种近邻搜索模型，由斯坦福大学的Mose Charikar提出。我们用一种随机投影(Random Projection)的方式来创建LSH model。随机投影要求我们首先选择一个(这里考虑最简单的情况)超平面（由一个向量\(r\)定义），然后用这个超平面去散列输入的向量。给定一个输入向量\(v\)和一个超平面\(r\)，我们令\(h(v)=sgn(v \cdot r)\)，\(h(v)=\pm 1\)取决于输入向量在超平面的哪一侧。对于任意两个向量\(u, v\)，他们在随机向量同一侧的概率为\(Pr[h(u)=h(v)]=1-\frac{\theta (u,v)}{\pi}\)（夹角比较小时近似等于\(cos(\theta (u,v))\)），其中\(\theta (u,v)\)是向量\(u\)和向量\(v\)的夹角。我们简单地证明一下这个公式。如下图，随机向量落在了两个向量\(u\)和\(v\)之间的概率是\(\frac{\theta (u,v)}{\pi}\)，此时数据在随机向量的两侧。反之，数据肯定会在随机向量的同侧。

加载*数据集

首先我们将数据加载到SFrame，在打印之前，我们首先给每篇文档添加个引用id。

wiki = graphlab.SFrame('people_wiki.gl/')
wiki = wiki.add_row_number()
wiki

提取文档特征TF-IDF

接下来，我们可以利用graphlab的内置函数提取每篇文档的特征。

wiki['tf_idf'] = graphlab.text_analytics.tf_idf(wiki['text'])
wiki

训练LSH模型

首先我们要生成一组服从标准正态分布的随机向量，可以把这个功能封装成一个函数。num_vertor表示随机向量的数目，dim表是随机向量的维度。

def generate_random_vectors(num_vector, dim):
    return np.random.randn(dim, num_vector)

参考：numpy.random.randn

接下来，我们用这个函数生成3个维度为5的随机向量，为了每次运行结果都能重现，我们将随机数的种子设置为0。

np.random.seed(0)
generate_random_vectors(num_vector=3, dim=5)

现在就可以生成16个维度为547979（与词典大小相同）的随机向量。每一个随机向量，可以确定一位编码（1或者0）。

np.random.seed(0)
random_vectors = generate_random_vectors(num_vector=16, dim=547979)
random_vectors.shape

我们现在要考虑把数据划分到某个桶里，对于第0篇文档，我们首先取出它的特征向量（TF-IDF），然后去点乘第0个随机向量。结果是正数就将第0位置1，否则置0。

doc = corpus[0, :]
doc.dot(random_vectors[:, 0]) >= 0

我们可以可以用一个矩阵乘法计算出桶的所有下标位。

doc.dot(random_vectors) >= 0

当然还需要把布尔值转换为整型，下面的代码可以完成这项工作。注意：如果某些文档最终计算得到了同一个向量，那么将会分配到同一个桶里。下面是对应关系。

np.array(doc.dot(random_vectors) >= 0, dtype=int)

为了表示方便，我们将桶的索引转换为十进制。

Bin index integer
[0,0,0,0,0,0,0,0,0,0,0,0] => 0
[0,0,0,0,0,0,0,0,0,0,0,1] => 1
[0,0,0,0,0,0,0,0,0,0,1,0] => 2
[0,0,0,0,0,0,0,0,0,0,1,1] => 3
...
[1,1,1,1,1,1,1,1,1,1,0,0] => 65532
[1,1,1,1,1,1,1,1,1,1,0,1] => 65533
[1,1,1,1,1,1,1,1,1,1,1,0] => 65534
[1,1,1,1,1,1,1,1,1,1,1,1] => 65535 (= 2^16-1)

举例说明：只要将powers_of_two和index_bits这两个向量点乘即可。

doc = corpus[0, :]
index_bits = (doc.dot(random_vectors) >= 0)
powers_of_two = (1 << np.arange(15, -1, -1))
print index_bits
print powers_of_two
print index_bits.dot(powers_of_two)

理解了上面的代码，我们就可以计算每一篇文档的的散列值。

index_bits = corpus.dot(random_vectors) >= 0
index_bits.dot(powers_of_two)

到此为止，我们就可以实现train_lsh这个函数了。

def train_lsh(data, num_vector=16, seed=None):

    dim = corpus.shape[1]
    if seed is not None:
        np.random.seed(seed)
    random_vectors = generate_random_vectors(num_vector, dim)

    powers_of_two = 1 << np.arange(num_vector-1, -1, -1)

    table = {}

    # 将数据散列到相应的桶里。
    bin_index_bits = (data.dot(random_vectors) >= 0)

    # 将二进制索引转换为数组下标。
    bin_indices = bin_index_bits.dot(powers_of_two)

    # 更新table，table[i]存储了属于第i个桶的所有的文档id
    for data_index, bin_index in enumerate(bin_indices):
        if bin_index not in table:
            # 如果这个桶里还没有文档，就首先初始化一个空列表。
            table[bin_index] = []
        # 将文档的id，保存到相应的桶里。
        table[bin_index].append(data_index) 

    model = {'data': data,
             'bin_index_bits': bin_index_bits,
             'bin_indices': bin_indices,
             'table': table,
             'random_vectors': random_vectors,
             'num_vector': num_vector}

    return model

LSH模型用于文档检索

为了能够在茫茫的百科中找到相似文档，我们考虑一下几点：
1.假设编号为L的桶包括了我们要检索的文章。
2.我们考虑编号为L的桶中所有的文章。
3.我们考虑编号与L相差1位的所有桶中的所有文章。
4.我们考虑编号与L相差2位的所有桶中的所有文章。
...
相对于要检索文章所在的桶，我们要找到相邻的桶。可以使用itertools.combinations函数，示例如下：

num_vector = 16
search_radius = 3 # 搜索半径

for diff in combinations(range(num_vector), search_radius):
    print diff

对于其中一个输出结果(0, 1, 3)，表示新桶的位置与要检索的文章所在桶的位置，在第0位，第1位，和第3位不同。

def search_nearby_bins(query_bin_bits, table, search_radius=2, initial_candidates=set()):
    """
    对于给定的某篇文档和LSH模型，返回所有搜索半径内的文档编号。

    使用方式
    -------------
    >>> model = train_lsh(corpus, num_vector=16, seed=143)
    >>> q = model['bin_index_bits'][0]  # 第一篇文档的TF-IDF特征。

    >>> candidates = search_nearby_bins(q, model['table'])
    """
    num_vector = len(query_bin_bits)
    powers_of_two = 1 << np.arange(num_vector-1, -1, -1)

    # 允许用户提供一些候选的文档。
    candidate_set = copy(initial_candidates)

    for different_bits in combinations(range(num_vector), search_radius):
        # 反转要检索文档所在桶的对应位(n_1,n_2,...,n_r)，用于生成新桶的索引。
        alternate_bits = copy(query_bin_bits)
        for i in different_bits:
            alternate_bits[i] = not alternate_bits[i]

        # 将二进制索引转换为数组下标。
        nearby_bin = alternate_bits.dot(powers_of_two)

        # 将所有相似的文档编号添加到候选集合中
        if nearby_bin in table:
            candidate_set.update(table[nearby_bin]) 

    return candidate_set

接下来我们通过一个函数返回k个候选文档，然后计算他们的真实距离

def query(vec, model, k, max_search_radius):

    data = model['data']
    table = model['table']
    random_vectors = model['random_vectors']
    num_vector = random_vectors.shape[1]

    # 计算要检索文档所在的下标
    bin_index_bits = (vec.dot(random_vectors) >= 0).flatten()

    # 搜索邻近的桶找到相似的文档
    candidate_set = set()
    for search_radius in xrange(max_search_radius+1):
        candidate_set = search_nearby_bins(bin_index_bits, table, search_radius, initial_candidates=candidate_set)

    # 按照与query的距离由小到大排序
    nearest_neighbors = graphlab.SFrame({'id':candidate_set})
    candidates = data[np.array(list(candidate_set)),:]
    nearest_neighbors['distance'] = pairwise_distances(candidates, vec, metric='cosine').flatten()

    return nearest_neighbors.topk('distance', k, reverse=True), len(candidate_set)

我们先查看一下奥巴马的文档id是多少

wiki[wiki['name']=='Barack Obama']

我们现在找到与奥巴马最相似的10篇文档

query(corpus[35817,:], model, k=10, max_search_radius=3)

可以看到，top1是奥巴马自己，top2是美国副总统拜登，有点意思！

模型评估

当我们增加搜索半径，会检索更多的文档。

随着搜索半径的增加，检索时间也会增加，当搜索半径足够大的时候，接近暴力解法。

当我们增加搜索半径的时候，越来越多相似的文档会被检索到。