在推荐系统中，主要分为召回跟排序两个阶段。
随着机器学习的发展，越来越多问题转移到deep learning上面解决，而系统实际部署在基于Tensorflow的Google Brain上，模型有接近10亿级参数，训练样本千亿级别。
所以，如此之大数量级的数据量，如果要通过常规方法，计算item两两之间的相似度，那么计算量级要到（n^2）级别，实在是太久了。针对这一现象，聪明的人类提出了NN的方法：
目前主流的索引技术有：
海量数据的检索方式，Hash是重要的索引技术。所谓hash，简而言之，就是将原始数据通过一个函数（hash）映射到新的数值。比如自定义一个hash 2 x + 1 2x+1 2x+1，原始数据有[2,4,6,8]，通过hash可以映射到[5,9,13,17]。
针对海量且高维的数据如何进行查找：
LSH，Locality-Sensitive Hashing，局部敏感哈希
上面提到即使是相邻的元素，也有可能分到不同的bucket，下面举个栗子~：
$$
Hash(127) = 127%8 = 7;
Hash(123) = 123%8 = 3;
Hash(1023) = 1023%8 = 7;
$$
从上面的例子可以看出通过hash把127和1023分到了同一个桶7，而与127更加相邻的123却分到了桶3。所以LSH一定程度上会丢失精度，但是精度换时间，这种买卖的交易是值得的。
在计算文本相似度中，有：
有了Jaccard相似度，但是面对海量数据，高维 => 矩阵非常大的时候，我们的目标是需要找到一个Hash函数，将原来的Jaccard相似度计算，等同于降维后的相似度矩阵计算（Input Matrix => Signature Matrix）。
针对这个hash函数，聪明的人类提出了MiniHash。MiniHash需要准备两个东西：
下面上图：
上图中红黄蓝表示随机置换的顺序表，而右边的是输入矩阵Input Metrix。
假设我们取蓝色的置换顺序表，那么我们通过置换可以得到以下的Metrix（如下图所示）。可以看到原本的第3行（0101）置换到了第1行，原本的第7行（1010）置换到了第3行。
同样的，我们根据红色，黄色置换表，也可以得到不一样的Metrix。如下图所示的黄色置换表得到的Metrix。
有了三个置换的得到的Metrix后，重点来了。==对于每个metrix，我们取出每列首个为1的行数。==拿蓝色置换得到的矩阵为例（如下图），第1列首个1的行数为2，第2列首个1的行数为1，第3列为2，第4列为1，所以最终可以得到（2121）这个hash后的数值。
如此类推，由黄色+红色+蓝色的置换+hash后，可以得到以下的Signature Metrix。
有了MiniHash得到的Signature Metrix，我们就可以计算Jaccard相似度了。如下图所示，第1行为原输入矩阵的Jaccard相似度，第2行为通过MiniHash降维后得到的Signature Metrix的Jaccard相似度。可以看出降维前后的相似度差距不是很大，但是两者之间的计算时间+空间量级得到了大大压缩。精度换时间，何乐而不为~
当数据量非常大的时候，计算量随之也会成倍的增加。我们利用LSH+MiniHash的算法，将可能相似的用户以较大概率分到同一个桶内，这样每一个用户的“相似用户候选集”就会少很多，大大降低计算复杂度。其中主要的思想就是：
在MiniHash降维的基础上，将得到的Signature向量分成多段(band)。
将Signiture矩阵分成b组(即b个bands)，每组由r行组成。（如下图所示）
对每一组进行hash，各个组设置不同的桶空间。只要两列有一组的MinHash相同，那么这两列就会hash到同一个桶而成为候选相似项.(如下图所示)
对于以上分组，我们假设对于某行，两列MinHash的值相同的概率为s（两列的相似度），有：
在某个band，值都相等的概率是 S r S^r Sr
在某个band，值不相同的概率是 1 − S r 1-S^r 1−Sr
两个文档存在b个band，这b个band都不相同的概率是 ( 1 − S r ) b (1-S^r)^{b} (1−Sr)b
b个band里，至少有一个相同的概率是 1 − ( 1 − S r ) b 1-(1-S^r)^{b} 1−(1−Sr)b，即两列成为候选相似对的概率是 1 − ( 1 − S r ) b 1-(1-S^r)^{b} 1−(1−Sr)b。
以上我们将其称之为And Then Or方法，先要求每个band的所有对应元素必须都相同，再要求多个band中至少有一个相同。符合这两条，才能发生hash碰撞。下面我们举个例子用以理解：假设两列MinHash的值相同的概率s=0.8，20个band，每个band 5行，即b=20, r=5。有
而针对b和r的取值，我们需要考虑：
对于LSH的一般定义：
Locality-Sensitive Hashing是满足一定条件的Hash函数簇
令
d
1
d_1
d1<
d
2
d_2
d2是定义在距离测定d下的两个距离值，如果一个函数族的每一个函数f满足：
part1
首先我们看一下用MiniHash前后，jaccard相似度的对比。话不多说，先上代码：
from datasketch import MinHash
import jieba
#创建两个句子
sentense_1 = '今天我和朋友去打球，他说我打得很好。'
sentense_2 = '昨天我和朋友去打球，他说我打得没他好。'
#文本清洗，去标点符号，分词。
def clean(x):
symbol = '，。'
for i in symbol:
x = x.replace(i,'')
res = jieba.lcut(x)
return res
sentense_1 = clean(sentense_1)
sentense_2 = clean(sentense_2)
#查看一下清洗后的样式
sentense_1,sentense_2
#开始调用MiniHash方法
m1 = MinHash()
m2 = MinHash()
#对两个句子进行MiniHash操作
for d in sentense_1:
m1.update(d.encode('utf8'))
for d in sentense_2:
m2.update(d.encode('utf8'))
#打印MiniHash后，两个句子的相似度
print("使用MinHash预估的Jaccard相似度", m1.jaccard(m2))
#
s1 = set(sentense_1)
s2 = set(sentense_2)
actual_jaccard = float(len(s1.intersection(s2)))/float(len(s1.union(s2)))
print("未使用MinHash预估的Jaccard相似度实际值", actual_jaccard)
从上图结果可以看出，用了MiniHash的结果未必比没用的差（当然这可能存在偶然性）。这里只是想表明，计算相似度里面，MiniHash的效果跟原数据的差不多，但是时间跟计算复杂度上能压缩很多倍！
在datasketch中的MinHash()，有一些可调参数：
part2
了解了MiniHash的简单使用，再讲讲MiniHash+LSH的结合体。话不多说，线上代码：
from datasketch import MinHash,MinHashLSH
import jieba
sentense_1 = '今天我和朋友去打球，他说我打得很好。'
sentense_2 = '昨天我和朋友去打球，他说我打得没他好。'
test = '昨天我和朋友没去打球，他说我打得太好'
def clean(x):
symbol = '，。'
for i in symbol:
x = x.replace(i,'')
res = jieba.lcut(x)
return res
sentense_1 = clean(sentense_1)
sentense_2 = clean(sentense_2)
test = clean(test)
sentense_1,sentense_2,test
m1 = MinHash()
m2 = MinHash()
m3 = MinHash()
for d in sentense_1:
m1.update(d.encode('utf8'))
for d in sentense_2:
m2.update(d.encode('utf8'))
for d in test:
m3.update(d.encode('utf8'))
lsh = MinHashLSH(threshold=0.5, num_perm=128)
lsh.insert("m1", m1)
lsh.insert("m2", m2)
result = lsh.query(m3)
print("近似的邻居（Jaccard相似度>0.5）", result)
由上图可以得到与test相似度最高的sentense_1
part3
除了MiniHash+LSH，还可以用MinHashLSHForest，针对新闻中某句话Query进行TOP-K相似度输出。话不多说，先上代码（数据集链接）：
from datasketch import MinHash, MinHashLSH, MinHashLSHForest
from sklearn.feature_extraction.text import TfidfVectorizer
import jieba.posseg as pseg
import re
# 读取文件
f = open('./sentences.txt', 'r', encoding='UTF-8')
text = f.read()
# 以句号，叹号，问号作为分隔，去掉\n换行符号
sentences = re.split('[。！？]', text.replace('\n', ''))
# 最后一行如果为空，则删除
if sentences[len(sentences)-1] == '':
sentences.pop()
#查看简单清洗效果
sentences
# 将文本进行分词
def get_item_str(item_text):
item_str = ""
item=(pseg.cut(item_text))
for i in list(item):
#去掉停用词
if i.word not in list(stop):
item_str += i.word
#tfidf_vectorizer.fit_transform的输入需要空格分隔的单词
item_str += " "
return item_str
# 对文本创建MinHash
def get_minhash(item_str):
temp = MinHash()
for d in item_str:
temp.update(d.encode('utf8'))
return temp
# 设置停用词
stop = [line.strip().decode('utf-8') for line in open('stopword.txt').readlines()]
# 得到分词后的documents
documents = []
for item_text in sentences:
# 将item_text进行分词
item_str = get_item_str(item_text)
documents.append(item_str)
# 创建LSH Forest及MinHash对象
minhash_list = []
forest = MinHashLSHForest()
for i in range(len(documents)):
#得到train_documents[i]的MinHash
temp = get_minhash(documents[i])
minhash_list.append(temp)
forest.add(i, temp)
# index所有key，以便可以进行检索
forest.index()
query = '00:01:36，2019天猫双11总成交额超100亿元'
# 将query的内容进行分词
item_str = get_item_str(query)
# 得到query的MinHash
minhash_query = get_minhash(item_str)
# 查询forest中与m1相似的Top-K个邻居，此处K取3
result = forest.query(minhash_query, 3)
for i in range(len(result)):
print(result[i], minhash_query.jaccard(minhash_list[result[i]]), documents[result[i]].replace(' ', ''))
print("Top 3 邻居", result)
MinHashLSHForest流程总结