大家好，欢迎来到IT知识分享网。

LSH近似最近邻查找

NN与ANN

NN，Nearest Neighbor Search，最近邻查找问题； TOP N
KNN，K-Nearest Neighbor，k最近邻，查找离目标数据最近的前k个数据项
ANN，Approximate Nearest Neighbor，近似最近邻检索，在牺牲可接受范围内的精度的情况下提高检索效率
最近邻检索是线性复杂度的，当处理大规模数据时可以采用ANN方法
LSH，局部敏感哈希是ANN的一种

近似最近邻算法_k最近邻分类算法「建议收藏」

主要的索引技术：

基于树的索引技术（二叉树，B-Tree,B+Tree）
基于哈希的索引技术
基于词的倒排索引
海量数据的检索方式，Hash是重要的索引技术

比如1000w的数据量，采用树索引可能需要10次左右(log₂ⁿ)，采用哈希索引只需要1次；

近似最近邻算法_k最近邻分类算法「建议收藏」

LSH算法

针对海量 and 高维数据如何进行查找：

如果数据是低维 and 小数据 => 通过线性的方式查找
数据不仅海量，而且高维 => 需要降维，采用索引方式查找
- LSH，Locality-Sensitive Hashing，局部敏感哈希
需要查找与某个数据1个或多个相似的数据
最近邻查找方法（ANN，Approximate Nearest Neighbor）

近似最近邻算法_k最近邻分类算法「建议收藏」

传统的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到了同一个桶内）
将原始数据集合分成了多个子集合，每个子集合中的数据大概率是相邻的，而且子集合中的元素个数较少。
方便进行近邻查找 => 在一个很小的集合里查找相邻元素

近似最近邻算法_k最近邻分类算法「建议收藏」

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表示出现的个数（或有和没有）；

近似最近邻算法_k最近邻分类算法「建议收藏」

文档相似度计算：

Jaccard相似度：交集 / 并集
海量数据，高维 => 矩阵非常大的时候，目标需要找到一个Hash函数，将原来的Jaccard相似度计算，等同于降维后的相似度矩阵计算（Input Matrix => Signature Matrix（迁移| 采用矩阵））
原来文档的Jaccard相似度高，那么它们的hash值相同的概率高
原来文档的Jaccard相似度低，那么它们的hash值不相同的概率高。针对Jaccard相似度的为MinHashing(最小哈希)

近似最近邻算法_k最近邻分类算法「建议收藏」

7维降 3维

近似最近邻算法_k最近邻分类算法「建议收藏」

MinHash：

特征矩阵按行进行随机排列后，第一个列值为1的行的行号

Thinking 最小哈希值= 2 1 1 3
h(C1)=2，h(C2)=1，h(C3)=1，h(C4)=3

第一篇文档C1说的是 AI 成为趋势，依次…，最小哈希值是第一列值为1的行的行号；

近似最近邻算法_k最近邻分类算法「建议收藏」

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 ；

维度不同近似程度不同；

近似最近邻算法_k最近邻分类算法「建议收藏」

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);

近似最近邻算法_k最近邻分类算法「建议收藏」

MinHash执行：

对于hash函数：

h(x)= x mod 5

g(x)=(2x+1) mod 5

行数+1，每次进行h和g函数运算
如果列上的值为1，那么查看Hash得到的数值是否更小，更小则更新

=> 通过m个针对row index的Hash函数，完成m次行向量的置换（解决了行向量置换的问题）

近似最近邻算法_k最近邻分类算法「建议收藏」

LSH算法

MinHash+LSH：

1000W的用户 * 1000维降为10 维，列数少了但是个数并没有减少；要把这1000w降下来；

除了要解决Ci和Cj两两之间相似度的计算问题，当数据量大的时候，两两之间相似度计算次数为C_N²

当数据量N很大（>100万），计算量非常大

=> 将可能相似的用户以较大概率分到同一个桶内，这样每一个用户的“相似用户候选集”就会少很多，大大降低计算复杂度

LSH是相似度的近似求解方式

在MinHash基础上，将Signature向量分成多段(band)；

下图中将用户分为4个段，这4个段一块一块的进行操作；

近似最近邻算法_k最近邻分类算法「建议收藏」

将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个比较接近的用户；

近似最近邻算法_k最近邻分类算法「建议收藏」

minHash是降维、LSH是它哈希的方法；

每个band中有r rows 行，

假设对于某行，两列签名值相同的概率为s（两列的相似度）

在某个band，值都相等的概率是 s^r（一个值相等的概率为s，r个特征都相等的概率）
在某个band，值不相同的概率是 1 – s^r
两个文档存在b个band，这b个band都不相同的概率是 (1-s^r)^b
b个band里，至少有一个相同的概率是 1-(1-s^r)^b

=> 两列成为候选相似对的概率是 1-(1-s^r)^b

称之为And then OR方法，先要求每个band的所有对应元素必须都相同，再要求多个band中至少有一个相同。符合这两条，才能发生hash碰撞。

假设s=0.8，20个band，每个band 5行，即b=20, r=5

在某个band，值都相等的概率是 0.8⁵ = 0.328
在某个band，值不相同的概率是 1-0.8⁵ = 0.672
b个band都不相同的概率是 0.672²⁰ = 0.00035
b个band里，至少有一个相同的概率是 1-0.672²⁰ = 0.9996

b = 20, r = 5时的概率表

近似最近邻算法_k最近邻分类算法「建议收藏」

MinHash+LSH：
当b=100, r=4时，(1-s⁴)¹⁰⁰的曲线

近似最近邻算法_k最近邻分类算法「建议收藏」

当s超过某个阈值后，两个用户成为candidate用户的概率会迅速增加并接近于1。这个阈值，也就是概率变化最陡的地方，近似为 t = (1/b)^1/r

近似最近邻算法_k最近邻分类算法「建议收藏」

在使用过程中，我们需要确定

Smin，相似用户的阈值定义（近邻定义）

Signature向量的长度，降到k维embedding

针对b和r的取值，我们需要考虑：

如果想要尽可能少的出现false negative，需要选择b和r使得概率变化最陡的地方小于Smin（比如s在0.5以上才属于相似用户，选择b和r使得S曲线的最陡处小于0.5）

近似最近邻算法_k最近邻分类算法「建议收藏」

如果想要保证计算速度较快，并且尽可能少出现false positive，那么最好选择b和r使得概率变化最陡的地方较大（比如b=20，r=6）这样，s较小的两个用户就很难成为candidate用户，但同时也会有一些

“潜在”的相似用户不会被划分到同一个桶内

近似最近邻算法_k最近邻分类算法「建议收藏」

LSH的一般定义：

Locality-Sensitive Hashing是满足一定条件的Hash函数簇

令d1<d2是定义在距离测定d下的两个距离值，如果一个函数族的每一个函数f满足：

如果d(x,y)<=d1,则f(x)=f(y)的概率至少为p1，即P(f(x)=f(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

近似最近邻算法_k最近邻分类算法「建议收藏」

LSH算法工具

datasketch

海量数据相似查找，Python工具
支持多种统计方式
对常见的统计需求，在精确度，存储成本，计算成本之间进行了折衷，对每一个计算元素只接触一次的情况下，得到精度相当高的统计结果

MinHsh作为降维处理，检索过程中用MinHash LSH ；

近似最近邻算法_k最近邻分类算法「建议收藏」

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相似度>0.5） ['m2', 'm3']

datasketch中的MinHashLSHForest()：之前是相似的放到每个桶里边，现在是森林 – 树的方式；在一个叶子节点就是相似的；

局部敏感随机投影森林
http://ekzhu.com/datasketch/lshforest.html
论文：http://ilpubs.stanford.edu:8090/678/1/2005-14.pdf

求近似最近邻方法的一种（ANN）

随机选取一个从原点出发的向量，与这个向量垂直的直线将平面内的点划分为了两部分。当数目比较大的时候，可以继续进行划分

对应于一棵深度为2，有4个叶节点的树（划分出4个部分）。一直划分，直到每个叶节点中点的数目都达到一个足够小的数目，也就是将每次搜索与计算的点的数目减小到一个可接受的范围。建立多个随

机投影树构成随机投影森林，将森林的综合结果作为最终的结果

近似最近邻算法_k最近邻分类算法「建议收藏」

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
forest = 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', 'm3']

datasketch中的MinHashLSHEnsemble()：

http://ekzhu.com/datasketch/lshensemble.html
论文：http://www.vldb.org/pvldb/vol9/p1185-zhu.pdf
对于相似度的另一种计算方式，对于X和X’，Jaccard计算差很大
threshold 参数，Jaccard 距离阈值设定，默认为0.9
num_perm参数，Hash置换函数设定个数，默认为128
index()，内容载入LSHEnsemble系统
query(key, size)，查询与key相似的邻居

近似最近邻算法_k最近邻分类算法「建议收藏」

from datasketch import MinHash, MinHashLSH, MinHashLSHEnsemble
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 Ensemble
lshensemble = MinHashLSHEnsemble(threshold=0.8, num_perm=128)
# Index takes an iterable of (key, minhash, size)
lshensemble.index([("m2", m2, len(data2)), ("m3", m3, len(data3))])
# 判断lshensemble是否存在m2, m3
print("m2" in lshensemble)
print("m3" in lshensemble)
# 查询与m1相似度Containment大于0.8的集合
print("与m1相似度大于0.8的集合：")
for key in lshensemble.query(m1, len(data1)):
    print(key)

True
True
与m1相似度大于0.8的集合：
m2
m3

LSH算法工具总结

Step1，对文档进行k-shingle，即将文档切割成一个一个的元素，这些元素是由很多的字符串组成的（由k个字符串组成）
Step2，使用MinHash得到集合元素的签名
Step3，使用LSH加快候选相似对的查找，得到可能的候选对

近似最近邻算法_k最近邻分类算法「建议收藏」

案例

数据集：天猫双11新闻，对新闻中的句子进行检索

使用MinHashLSHForest，针对某句话Query进行TOP-K相似度输出

Step1、分词
Step2、创建MinHash
Step3、使用MinHashLSHForest进行Index
Step4、使用MinHashLSHForest进行Query，查询Top-K相似句子

# 读取文件
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()
# 将item_text进行分词
def get_item_str(item_text):
# 对item_str创建MinHash
def get_minhash(item_str):
# 设置停用词
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亿元'
# 将item_text进行分词
item_str = get_item_str(query)
# 得到item_str的MinHash
minhash_query = get_minhash(item_str)
# 查询forest中与m1相似的Top-K个邻居
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)

SimHash算法

汉明（Hamming）距离：

两个二进制串中不同位的数量
比如10001001和10110001，有3位不同，因此汉明距离=3
向量相似度越高，对应的汉明距离越小
在图片的识别中，汉明距离在0-10之间认为是相似的，采用汉明距离计算相似度可以大幅提升效率

10001001

10110001

SimHash算法：

LSH局部敏感哈希的一种
Paper: similarity estimation techniques from rounding algorithms
Google采用SimHash进行网页查重
Detecting Near-Duplicates for Web Crawling
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.7794&rep=rep1&type=pdf

SimHash算法：

Step1，设置SimHash的位数，比如32位，需要综合考虑存储成本以及数据集的大小
Step2，初始化SimHash，将各位初始化为0
Step3，提取文本中的特征，比如采用2-Shingles， “the cat sat on the mat”=>{“th”, “he”, “e “, ” c”, “ca”, “at”, “t “, ” s”, “sa”, ” o”, “on”, “n “, ” t”, ” m”, “ma”}
Step4，使用传统的hash函数计算各个word的hashcode，比如：”th”.hash = -502157718 ，”he”.hash = -369049682，……
Step5，对各word的hashcode的每一位，如果该位为1，则simhash相应位的值加它的权重（通常是出现的频率）；否则减它的权重
Step6，计算最后得到的32位的SimHash，如果该位大于1，则设为1；否则设为0

SimHash算法：

通过SimHash算法得到每篇文档的指纹（fingerprint）
计算两个文档指纹的海明距离
通常2篇文档的Hamming距离在3以内，就认为相似度比较高 => 两篇文档基本相同

一篇文档doc里会有n元语法，对每个特征求一个词频，feature 个数越多它的weight越大；对每个feature做一个hash编码，1代表正、0代表负，weight和它的关系可看做乘法的关系；

0 0就是两个负的w1，转换为带有权重的哈希编码；文档的指纹就相当于是它压缩之后的特征，做堆内的加法，add加完之后还是32位的，转换sign为0、1编码（大于1为1，小于1为0）；

精度损失了，但是速度快了；

近似最近邻算法_k最近邻分类算法「建议收藏」

0代表为负，1代表为正；

做对位加法（比如第一位的 -1 + 2 + -3 + 1 + -2 + -2 = -5）

近似最近邻算法_k最近邻分类算法「建议收藏」

如何通过SimHash进行相似文档的检索：

假设我们有10亿文档(2^34)，每来一个新文本我们都需要做10亿次的汉明距离计算=>计算量太大
假设SimHash签名为64位，我们认为两个文档SimHash的Hamming距离在3以内就是相似的(距离<=3)
通过抽屉原理，如果K=3，那么可以将SimHash分成 K+1=4段，如果两个SimHash的Hamming距离为3，那么至少有一段（16位）的SimHash是相同的；
采用索引的方式进行查找加速，取出每一段相同的候选文本
文档库中有2^34个签名，那么匹配上每个段的结果最多有2^(34-16)=262144个候选结果，四个段返回的结果总数=4*262144（大概100万）
原本需要比较10亿次 => 现在只需要比较100万次了，即在100万个候选结果中进行比较

近似最近邻算法_k最近邻分类算法「建议收藏」

simhash算法工具

SimHash：

pip install git+https://github.com/leonsim/simhash
Python实现的SimHash，可以得到某个文本的SimHash，以及SimHash距离
对3个文本进行SimHash，并计算文本SimHash距离
这个程序代码太乱,那个代码规范
这个程序代码不规范,那个更规范
我是佩奇，这是我的弟弟乔治

data = [
    '这个程序代码太乱,那个代码规范',
    '这个程序代码不规范,那个更规范',
    '我是佩奇，这是我的弟弟乔治'
]
vec = TfidfVectorizer()  //词向量 ，TFIDF是对句子做分词 
D = vec.fit_transform(data)
voc = dict((i, w) for w, i in vec.vocabulary_.items())
# 生成Simhash
sh_list = []
for i in range(D.shape[0]):
    Di = D.getrow(i)
    # features表示 (token, weight)元祖形式的列表
    features = zip([voc[j] for j in Di.indices], Di.data)
    sh_list.append(Simhash(features))
print(sh_list[0].distance(sh_list[1]))
print(sh_list[0].distance(sh_list[2]))
print(sh_list[1].distance(sh_list[2]))

Thinking：第一个句子和第二个句子相差也很大？


data = [
    '这个 程序 代码 太乱 那个 代码 规范',
    '这个 程序 代码 不 规范 那个 更 规范',
    '我 是 佩奇 这 是 我的 弟弟 乔治'
]
vec = TfidfVectorizer()
D = vec.fit_transform(data)
voc = dict((i, w) for w, i in vec.vocabulary_.items())
# 生成Simhash
sh_list = []
for i in range(D.shape[0]):
    Di = D.getrow(i)
    # features表示 (token, weight)元祖形式的列表
    features = zip([voc[j] for j in Di.indices], Di.data)
    sh_list.append(Simhash(features))
print(sh_list[0].distance(sh_list[1]))
print(sh_list[0].distance(sh_list[2]))
print(sh_list[1].distance(sh_list[2]))

Summary

文档之间Haming距离的计算：

Step1, 基于传统的IR方法，将文章转换为一组加权的特征值构成的向量
Step2，通过SimHash算法得到每篇文档的指纹（fingerprint）
Step3，计算不同文档之间的Haming距离

近似最近邻查找ANN的使用：

场景：对微博全量用户进行关注相似度计算，计算得到每个用户关注相似度最高的TOP-N个用户
方案1：用协同过滤，先定义相似性度量（cos，Pearson，Jaccard），然后通过两两计算相似度，得到相似度矩阵，从而进行Top-n筛选
- 时间复杂度为O(n^2)，即对每个用户，都和其他用户进行了比较
方法2：对于亿级的用户量，计算相似度非常耗时，即O(n^2)的时间复杂度很大。可以采用近似算法，通过牺牲一些精度来提高计算效率，比如MinHashLSH
Approximate Top-N，是在空间时间有限的条件下对最近邻的一种近似求解，适用于对海量数据进行相似性查找

LSH是一种ANN，在海量数据中找到一个高维度点相似的点集合

K-Shingles，K-Gram，对文档的转换，也就是对文档进行切割
MinHash降维，LSH减少查找范围
MinHash是一种降维技术，将一个大的集合中的元素转换为短小的签名，同时保持了这些集合中的元素的相似性
MinHash适用于集合表示，或者0-1数据类型（one-hot词向量）的降维与近邻查找
MinHashLSH 关注的是签名对可能的相似性,采用分桶的方式，将相似的集合至少在一个区间内冲撞，将冲撞的集合作为候选对象进行比较，从而找出相似的对象，时间复杂度由
SimHash算法高效，适用于长文本，Google将SimHash运用到了网页的去重中

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/29221.html

Arabic	Hebrew	Polish
Bulgarian	Hindi	Portuguese
Catalan	Hmong Daw	Romanian
Chinese Simplified	Hungarian	Russian
Chinese Traditional	Indonesian	Slovak
Czech	Italian	Slovenian
Danish	Japanese	Spanish
Dutch	Klingon	Swedish
English	Korean	Thai
Estonian	Latvian	Turkish
Finnish	Lithuanian	Ukrainian
French	Malay	Urdu
German	Maltese	Vietnamese
Greek	Norwegian	Welsh
Haitian Creole	Persian

近似最近邻算法_k最近邻分类算法「建议收藏」

LSH近似最近邻查找

LSH算法

LSH算法

LSH算法工具

SimHash算法

相关推荐

发表回复