阅读目录(Content)
LSH近似最近邻查找LSH算法LSH算法LSH算法工具SimHash算法
回到顶部(go to top)LSH近似最近邻查找
NN与ANN
NN，Nearest Neighbor Search，最近邻查找问题； TOP N
KNN，K-Nearest Neighbor，k最近邻，查找离目标数据最近的前k个数据项
ANN，Approximate Nearest Neighbor，近似最近邻检索，在牺牲可接受范围内的//代码效果参考：http://www.lyjsj.net.cn/wx/art_23360.html
精度的情况下提高检索效率最近邻检索是线性复杂度的，当处理大规模数据时可以采用ANN方法
LSH，局部敏感哈希是ANN的一种
主要的索引技术：
基于树的索引技术（二叉树，B-Tree,B+Tree）
基于哈希的索引技术
基于词的倒排索引
海量数据的检索方式，Hash是重要的索引技术
比如1000w的数据量，采用树索引可能需要10次左右(log2n)，采用哈希索引只需要1次；
LSH算法
针对海量 and 高维数据如何进行查找：
如果数据是低维 and 小数据 => 通过线性的方式查找
数据不仅海量，而且高维 => 需要降维，采用索引方式查找
LSH，Locality-Sensitive Hashing，局部敏感哈希
需要查找与某个数据1个或多个相似的数据
最近邻查找方法（ANN，Approximate Nearest Neighbor）
传统的HashTable用于检索数据，无法将相似的数据放到同一个Bucket中，比如h=x mod w
LSH将相邻的数据，通过映射后依然保持相邻的关系，即保持局部的敏感度Locality-Sensitive
哈希是精确查找，LSH是相似查找，127、123是很接近的数字，应该放到一个桶bucket中 ；
Hash(127) = 127%8 = 7;
Hash(123) = 123%8 = 3;
Hash(1023) = 1023%8 = 7;
LSH：
通过Hash Function，每个Bucket会落入一些原始数据，属于同一个桶内的数据有很大可能是相邻的（也存在不相邻的数据被hash到了同一个桶内）
将原始数据集合分成了多个子集合，每个子集合中的数据大概率是相邻的，而且子集合中的元素个数较少。
方便进行近邻查找 => 在一个很小的集合里查找相邻元素
MinHash算法
文档相似度计算：
k-shingle，也称为k-gram，文档中任意长度为k的字符串。将每篇文档可以表示成文档中出现一次或者多次的k-shingle的集合
比如document="abcdabd"，当2-shingle组成的集合为 {ab,bc,cd,da,bd}
如果两个文档相似，那么他们会有很多的shingles也是相同的
文本越长，K取值越大。K的经验值参考，短文本K=5，长文本K=10
纵向表示文档、横向表示特征，0和1表示出现的个数（或有和没有）；
文档相似度计算：
Jaccard相似度 ： 交集 / 并集
海量数据，高维 => 矩阵非常大的时候，目标需要找到一个Hash函数，将原来的Jaccard相//代码效果参考：http://www.lyjsj.net.cn/wx/art_23358.html
似度计算，等同于降维后的相似度矩阵计算（Input Matrix => Signature Matrix（迁移| 采用矩阵））原来文档的Jaccard相似度高，那么它们的hash值相同的概率高
原来文档的Jaccard相似度低，那么它们的hash值不相同的概率高。针对Jaccard相似度的为MinHashing(最小哈希)
7维 降 3维
MinHash：
特征矩阵按行进行随机排列后，第一个列值为1的行的行号
Thinking 最小哈希值= 2 1 1 3
h(C1)=2，h(C2)=1，h(C3)=1，h(C4)=3
第一篇文档C1说的是 AI 成为 趋势，依次...，最小哈希值是第一列值为1的行的行号 ；
MinHash：
Thinking Ci与Cj的MinHash相等的概率P(h(Ci)=h(Cj))，与Ci,Cj Jaccard相似度的关系
A 相等
B 不相等
C 不确定
对于Ci与Cj，对应的行有三种可能：
A类：两列的值都为1； 交集
B类：其中一列的值为0，另一列的值为1； 并集
C类：两列的值都为0.
C类行对于结果计算没有影响，可以删除
P(h(Ci)=h(Cj))=P(删掉C类后，第一行为A类) = A类行的个数/ 所有行的个数 = a/ (a+b)
P(h(Ci)=h(Cj))= Jaccard(Ci,Cj)
用Ci，Cj的MinHash值相等的概率，对他们的Jaccard相似度进行估计
MinHash：
分别经过3次随机置换（红、黄、蓝）
每次置换后，采用MinHash得到Signature
使用Sig矩阵相似度用来近似估计原始矩阵Input Matrix的Jaccard相似度
蓝色变化后的miniHash值为 2 1 2 1，黄色 2 1 4 1 ，红色 1 2 1 2；从7维降 3 维，转换了3次；7个特征 - 3个特征；
input matrix 中C1 和C3的相似度为： 3/4， signature maxtrix M的相似度为 2/3 ；同理可得C2和C4、 C1和C2、C3和C4 ；
维度不同 近似程度不同；
MinHash执行：
如何对海量数据进行排序 => 存储空间，计算时间 （通过打擂法）
=> 有多个hash函数,通过hash i得到最新的行号，如果此时列上的元素为1，而且新行号比原来记录的M值小，那么更新M值
for each hash function hi do
compute hi (r);
for each column c
if c has 1 in row r
for each hash function hi do
if hi (r) is smaller than M(i, c) then
M(i, c) := hi (r);
MinHash执行：
对于hash函数：
h(x)= x mod 5
g(x)=(2x+1) mod 5
行数+1，每次进行h和g函数运算
如果列上的值为1，那么查看Hash得到的数值是否更小，更小则更新
=> 通过m个针对row index的Hash函数，完成m次行向量的置换（解决了行向量置换的问题）
LSH算法
MinHash+LSH：
1000W的用户 1000维 降 为10 维，列数少了 但是个数并没有减少；要把这1000w降下来；
除了要解决Ci和Cj两两之间相似度的计算问题，当数据量大的时候，两两之间相似度计算次数为CN2
当数据量N很大（>100万），计算量非常大
=> 将可能相似的用户以较大概率分到同一个桶内，这样每一个用户的“相似用户候选集”就会少很多，大大降低计算复杂度
LSH是相似度的近似求解方式
在MinHash基础上，将Signature向量分成多段(band)；
下图中将用户分为4个段，这4个段 一块一块的进行操作；
将Signiture矩阵分成b组，每组由r行组成
对每一组进行hash，各个组设置不同的桶空间。只要两列有一组的MinHash相同，那么这两列就会hash到同一个桶而成为候选相似项。
左下粉色那块是降维后的矩阵，每一段都采用hash的方式，会告诉你它放在哪个buckets里桶里面，如果这两段是相似的他们就会放到一个桶里面；
假设b = 20, 每组 即每段有5维，桶是存储数据的检索方式，基于bands来映射的，比如第1个bands通过哈希函数映射到桶2，第5个bands通过哈希函数映射到桶2；放到一个桶里说明他们局部是相似的；
每个bands都有r rows行，比如r=5;
比如之前1000w的用户经过哈希之后变成 b个bucket 假设有20个，每个桶假设有100个，20 100=2000个比较接近的用户；
minHash是降维、LSH是它哈希的方法；
每个band中有r rows 行，
假设对于某行，两列签名值相同的概率为s（两列的相似度）
在某个band，值都相等的概率是 sr （一个值相等的概率为s，r个特征都相等的概率）
在某个band，值不相同的概率是 1 - sr
两个文档存在b个band，这b个band都不相同的概率是 (1-sr)b
b个band里，至少有一个相同的概率是 1-(1-sr)b
=> 两列成为候选相似对的概率是 1-(1-sr)b
称之为And then OR方法，先要求每个band的所有对应元素必须都相同，再要求多个band中至少有一个相同。符合这两条，才能发生hash碰撞。
假设s=0.8，20个band，每个band 5行，即b=20, r=5
在某个band，值都相等的概率是 0.85 = 0.328
在某个band，值不相同的概率是 1-0.85 = 0.672
b个band都不相同的概率是 0.67220 = 0.00035
b个band里，至少有一个相同的概率是 1-0.67220 = 0.9996
b = 20, r = 5时的概率表
MinHash+LSH：
当b=100, r=4时，(1-s4)100 的曲线
当s超过某个阈值后，两个用户成为candidate用户的概率会迅速增加并接近于1。这个阈值，也就是概率变化最陡的地方，近似为 t = (1/b)1/r
在使用过程中，我们需要确定
Smin，相似用户的阈值定义（近邻定义）
Signature向量的长度，降到k维embedding
针对b和r的取值，我们需要考虑：
如果想要尽可能少的出现false negative，需要选择b和r使得概率变化最陡的地方小于Smin（比如s在0.5以上才属于相似用户，选择b和r使得S曲线的最陡处小于0.5）
如果想要保证计算速度较快，并且尽可能少出现false positive，那么最好选择b和r使得概率变化最陡的地方较大（比如b=20，r=6）这样，s较小的两个用户就很难成为candidate用户，但同时也会有一些
“潜在”的相似用户不会被划分到同一个桶内
LSH的一般定义：
Locality-Sensitive Hashing是满足一定条件的Hash函数簇
令d1
如果d(x,y)= p1
如果d(x,y)>=d2,则f(x)=f(y)的概率至多为p2，即p(f(x)=f(y)) <= p2
那么称F为(d1,d2,p1,p2)-sensitive的函数族。
Jaccard相似性对应的LSH为MinHash,是(d1,d2,1-d1,1-d2)-sensitive
LSH算法工具
datasketch
海量数据相似查找，Python工具
支持多种统计方式
对常见的统计需求，在精确度，存储成本，计算成本之间进行了折衷，对每一个计算元素只接触一次的情况下，得到精度相当高的统计结果
MinHsh作为降维处理，检索过程中用MinHash LSH ；
datasketch中的MinHash()： 降维
num_perm参数，Hash置换函数设定个数，默认为128 维，如果需要提高精度，可以提高该数值，比如设置num_perm=256
update函数，内容Hash化m1.update(content)
merge函数，Hash合并，比如m1.merge(m2)
from datasketch import MinHash
data1 = 【'这个', '程序', '代码', '太乱', '那个', '代码', '规范'】
data2 = 【'这个', '程序', '代码', '不', '规范', '那个', '更', '规范'】
m1 = MinHash() //重采样
m2 = MinHash()
for d in data1:
m1.update(d.encode('utf8')) //MinHash降维之后的结果；
for d in data2:
m2.update(d.encode('utf8'))
print("使用MinHash预估的Jaccard相似度", m1.jaccard(m2))
s1 = set(data1)
s2 = set(data2)
actual_jaccard = float(len(s1.intersection(s2)))/float(len(s1.union(s2))) //交集 /并集
print("Jaccard相似度实际值", actual_jaccard)
使用MinHash预估的Jaccard相似度 0.6015625
Jaccard相似度实际值 0.625
datasketch中的MinHashLSH()： 检索的方式
http://ekzhu.com/datasketch/lsh.html
threshold 参数，Jaccard 距离阈值设定，默认为0.9 （目标是找邻居，这里设置阈值的大小，大于阈值0.9即是邻居）
num_perm参数，Hash置换函数设定个数，默认为128 （默认降维个数128）
weights (tuple, optional)，优化Jaccard 阈值，能够弹性选择
params (tuple, optional)，bands 的数量与规模大小
insert(key)，内容载入LSH系统 ；加载数据 索引，类似数据库
remove(key)，移除相关hash值
query(key)，查询内容需要时minHash化
from datasketch import MinHash, MinHashLSH
data1 = 【'这个', '程序', '代码', '太乱', '那个', '代码', '规范'】
data2 = 【'这个', '程序', '代码', '不', '规范', '那个', '更', '规范'】
data3 = 【'这个', '程序', '代码', '不', '规范', '那个', '规范', '些'】
m1 = MinHash() //做降维处理
m2 = MinHash()
m3 = MinHash()
for d in data1:
m1.update(d.encode('utf8'))
for d in data2:
m2.update(d.encode('utf8'))
for d in data3:
m3.update(d.encode('utf8'))
lsh = MinHashLSH(threshold=0.5, num_perm=128) //数据库检索 局部敏感哈希 ，大于阈值0.5的即是邻居
lsh.insert("m2", m2)
lsh.insert("m3", m3)
result = lsh.query(m1)
print("近似的邻居（Jaccard相似度>0.5）", result)
近似的邻居（Jaccard相似度
datasketch中的MinHashLSHForest()： 之前是相似的放到每个桶里边，现在是森林 - 树的方式；在一个叶子节点就是相似的；
局部敏感随机投影森林
论文：
求近似最近邻方法的一种（ANN）
随机选取一个从原点出发的向量，与这个向量垂直的直线将平面内的点划分为了两部分。当数目比较大的时候，可以继续进行划分
对应于一棵深度为2，有4个叶节点的树（划分出4个部分）。一直划分，直到每个叶节点中点的数目都达到一个足够小的数目，也就是将每次搜索与计算的点的数目减小到一个可接受的范围。建立多个随
机投影树构成随机投影森林，将森林的综合结果作为最终的结果
datasketch中的MinHashLSHForest()：
num_perm参数，Hash置换函数设定个数，默认为128
l 参数，代表prefix trees的数量，默认为8
add(key)，内容载入LSHForest系统
query(key, k)，查询与key相似的Top-K个邻居 ，之前用的是阈值 threshold
from datasketch import MinHash, MinHashLSH, MinHashLSHForest
data1 = 【'这个', '程序', '代码', '太乱', '那个', '代码', '规范'】
data2 = 【'这个', '程序', '代码', '不', '规范', '那个', '更', '规范'】
data3 = 【'这个', '程序', '代码', '不', '规范', '那个', '规范', '些'】
# 创建MinHash对象
m1 = MinHash()
m2 = MinHash()
m3 = MinHash()
for d in data1:
m1.update(d.encode('utf8'))
for d in data2:
m2.update(d.encode('utf8'))
for d in data3:
m3.update(d.encode('utf8'))
# 创建LSH Forest
//代码效果参考： http://www.lyjsj.net.cn/wz/art_23356.htmlforest = MinHashLSHForest()
forest.add("m2", m2)
forest.add("m3", m3)
# 在检索前，需要使用index , 创建树的过程
forest.index()
# 判断forest是否存在m2, m3
print("m2" in forest)
print("m3" in forest)
# 查询forest中与m1相似的Top-K个邻居
result = forest.query(m1, 2)
print("Top 2 邻居", result)
True
True
Top 2 邻居 【'm2', <span style="color: rgba(1
