[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

时间:2022-05-13 07:19:57

简介

局部敏感哈希(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}\),此时数据在随机向量的两侧。反之,数据肯定会在随机向量的同侧。
[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

加载*数据集

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

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

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

提取文档特征TF-IDF

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

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

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

训练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)

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

现在就可以生成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

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

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

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

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

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

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)

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

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

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

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

到此为止,我们就可以实现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']

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

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

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

可以看到,top1是奥巴马自己,top2是美国副总统拜登,有点意思!
[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索

模型评估

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索
当我们增加搜索半径,会检索更多的文档。

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索
随着搜索半径的增加,检索时间也会增加,当搜索半径足够大的时候,接近暴力解法。

[机器学习] 在茫茫人海中发现相似的你:实现局部敏感哈希(LSH)并应用于文档检索
当我们增加搜索半径的时候,越来越多相似的文档会被检索到。