简介
局部敏感哈希(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)
接下来,我们用这个函数生成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是美国副总统拜登,有点意思!
模型评估
当我们增加搜索半径,会检索更多的文档。
随着搜索半径的增加,检索时间也会增加,当搜索半径足够大的时候,接近暴力解法。
当我们增加搜索半径的时候,越来越多相似的文档会被检索到。