赵桂兰
局部敏感哈希（Localitynsitivehash）[3]——代码篇
我们在之前的⽂章中Locality Sensitive Hashing(局部敏感哈希)中已经详细的说了这个算法的基本核⼼思想，现在我们就来⼀点⼀点的把这个算法的每⼀步都来实现了。
⾸先我们⾄少得构建出我们能够⽐较的样本的特征值，设计出我们的布尔矩阵（Boolean Matrix）。局部敏感哈希的⼀个优点就是避免两两⽐较（pairwi comparison），主要的⽅法就是看最后的band 被映射 同⼀个bucket的话我们就⼀般认为这两个特征值其实是相似的，或者说在某个概率下是相同的。
⾸先我们先构建⼀个数据集，⽐如说把它叫做dataSet，这个⾥⾯有⼀些特征向量，我们就⽤之前我们说的下图这个例⼦来写我们的代码吧。
我们可以设计我们的dataSet 为⼀个⼆维的数组，设计我们需要查询的（或者说找到我们的这个待查询的这个数组为它找到和它相似的数据集）数组为⼀维数组。我们可以给这个查询的数据叫做query. 我们把这个查询的数组设置为⼀维数组。
我们可以这么来构建我们的数据结构：
dataSet = [[1,1,0,0,0,1,1],[0,0,1,1,1,0,0],[1,0,0,0,0,1,1]]
query = [0,1,1,1,1,0,0]
dataSet.append(query)
#把这个查询的数组加⼊到我们的整个数据集当中，并且将它转换成矩阵的形式
matrix = np.array(dataSet).T
信息的载体如果要写成代码，我们可以像下⾯这样操作。把我们的这些要操作的数据集设置为我们的输⼊参数来做：
def get_data(dataSet,query):
dataSet.append(query)
matrix = np.array(dataSet).T
得到我们的数据之后，当然就是⽣成我们的signature matrix ，这个时候当然就是⽤到我们的minhash 这个函数，对我们的原始矩阵进⾏⼀个⾏的置换，这个时候找到某列的第⼀个元素为1 的⾏号作为我们的signature matrix 的特征值。
会议记录表模板我们肯定不会直接把这个矩阵放到内存⾥⾯排序进⾏⾏置换的操作，这样实在是太占内存了，我们介绍过⼏种⽅法，对我们的⾏号进⾏置换。依次查询即可。
吃草猫如果我们按照我们之前章节⾥⾯的算法的思路就是对⾏号进⾏排序，或者说是置换，这个时候我们来查找置换后的⾏得到的列中第⼀次出现1的那个⾏的⾏号。
#!/usr/bin/env python
# coding=utf-8
from random import shuffle
import numpy as np
import hashlib
玉米粒煮多久能熟
def generateSig(matrix):
"""
generate the signature value for the signature matrix
心雄万夫param matrix: input matrix
"""
# 在这⾥我们得到原始矩阵的⾏号
rowSeries= [i for i in range(matrix.shape[0])]
#在这⾥我们设置我们的signature签名矩阵的初始值 result = [-1 for i in range(matrix.shape[1])]
colcount = 0
# 对⾏号重新排序
shuffle(rowSeries)
for i in range(len(rowSeries)):
rowIndex = rowSeries.index(i)
for j in range(matrix.shape[1]):
if result[j]==-1 and matrix[rowIndex][j]!=0:
result[j]=rowIndex
colcount += 1
if colcount == matrix.shape[1]:
break
return result
def genSigMatrix(matrix,k):
'''
generate the signature matrix
:param matrix : the input matrix
:param k : k =n*r n is the number of band
r is the number of row in each band
'''
sigMatrix = []
for i in range(k):
sig = generateSig(matrix)
sigMatrix.append(sig)
return np.array(sigMatrix)
当然我们还有其他的解决办法，⽐如我们随机选取⼀⾏，⽽不⽤对我们的整个⾏进⾏重拍我们可以向下⾯这样做。
这个算法的主要思想就是利⽤随机⾏数，抽取⼀⾏，然后逐列查询，如果改⾏的这⼀列元素刚好是1，那么我们就把对应的签名矩阵的列填上我们抽取的⾏号，不是1的元素的列继续对⾏遍历，当然我们会删除之前抽取的⾏号
import numpy as np
import random
import hashlib
def sigGen(matrix):
"""
* generate the signature vector
:param matrix: a ndarray var
:
return a signature vector: a list var
"""
# the row quence t
qSet = [i for i in range(matrix.shape[0])]
# initialize the sig vector as [-1, -1, ..., -1]
result = [-1 for i in range(matrix.shape[1])]
count = 0
激励员工正能量的句子
while len(qSet) > 0:
# choo a row of matrix randomly
randomSeq = random.choice(qSet)
for i in range(matrix.shape[1]):
if matrix[randomSeq][i] != 0 and result[i] == -1:
英文励志短句result[i] = randomSeq
count += 1
if count == matrix.shape[1]:
break
# return a list
return result
通过这⼀步之后我们得到了我们的signature matrix ，这个时候我们要计算这些signature 是不是能够被映射到同⼀个bucket ⾥⾯。
我们需要把我们的matrix 划分成不同的bands , 每⼀个band ⾥⾯包含有r ⾏。然后映射到不同的buckets ⾥⾯，经过我们的分析，我们知道如果两个签名是相似的，那么他们会被映射到同⼀个buckets ⾥⾯。这个时候我们LSH避免了两两⽐较，这个时候LSH极⼤的提⾼了运算的效率。
