赞
踩
编辑:AI算法小喵 公众号
个人认为文本的相似性可以分为两类:一类是机械相似性;一类是语义相似性。机械相似性代表着,两个文本内容上的相关程度,比如“你好吗”和“你好”的相似性,纯粹代表着内容上字符是否完全共现,应用场景在:文章去重;语义相似性代表着,两个文本语义上的相似程度,比如“苹果”和“公司”的相似性。
今天跟大家分享在相似性检索+去重的场景下,如何基于Python中的datasketch来计算机械相似性。
datasketch这个模块有非常多的功能,主要是:
HyperLogLog
HyperLogLog++
MinHash LSH
MinHash LSH Ensemble
MinHash LSH Forest
MinHash
Weighted MinHash
其中 MinHash 与 simHash 不同,其主要采用的是 Jaccard距离,而LSHForest/sklearn是常规的Hash函数,所以可以用cosine距离。
其中,Jaccard距离较多地可以应用在BOW模型即词袋模型之上,图片和文字在用词袋模型表征特征的时候,较适合应用。
MinHash在检索场景应用比较多。每当有新的搜索,我们需要创建一个新的MinHash,同时与候选集求Jaccard相似性,然后根据一些阈值筛选符合的样例。
class datasketch.MinHash(num_perm=128, seed=1, hashobj=<built-in function openssl_sha1>, hashvalues=None, permutations=None)
MinHash 哈希化专属的距离是 Jaccard距离。
num_perm(int, optional):哈希置换函数设定个数,如果hashvalues有值,那么该参数将被忽略。
seed(int, optional):MinHash中随机种子。
hashobj(optional):MinHash的哈希方程式。
hashvalues(numpy.array or list, optional):哈希内部状态。若使用另外已经存在状态的MinHash,哈希初始化会更快。
permutations (optional):哈希置换函数的参数。如果有已经存在状态的MinHash,会更快。
当然,如果要节约内存可以使用:datasketch.LeanMinHash
MinHash
- from datasketch import MinHash
-
- data1 = ['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'datasets']
- data2 = ['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'documents']
-
- m1, m2 = MinHash(), MinHash()
- for d in data1:
- m1.update(d.encode('utf8'))
- for d in data2:
- m2.update(d.encode('utf8'))
- print("Estimated Jaccard for data1 and data2 is", m1.jaccard(m2))
-
- s1 = set(data1)
- s2 = set(data2)
- actual_jaccard = float(len(s1.intersection(s2)))/float(len(s1.union(s2)))
- print("Actual Jaccard for data1 and data2 is", actual_jaccard)
案例的大致步骤为:
MinHash初始化状态:需要预先设定MinHash()初始化
内容哈希化:内容m1.update哈希化
jaccard距离(用集合的方式求距离):
此外还有一些tips:
通过调整num_perm数量,来提高精度,代价是更多CPU消耗 + 更多内存:
m = MinHash(num_perm=256)
联合两个minhash,这样就可以更快地进行并行parallel MapReduce:
m1.merge(m2)
- def count(self):
- k = len(self)
- return np.float(k) / np.sum(self.hashvalues / np.float(_max_hash)) - 1.0
-
- m.count()
LSH 能够将相似的条例远大于非相似的,详细详细可见R语言实现︱局部敏感哈希算法(LSH)解决文本机械相似性的问题(一,基本原理)[1]
MinHashLSH(threshold=0.9, num_perm=128, weights=(0.5, 0.5), params=None)
threshold (float):Jaccard 距离阈值设定,默认为0.9
num_perm (int, optional):哈希置换函数设定个数,在weighted-MinHash中为样本规模大小。
weights (tuple, optional):优化Jaccard 阈值,能够弹性选择。
params (tuple, optional):bands 的数量与规模大小。
- from datasketch import MinHash, MinHashLSH
-
- set1 = set(['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'datasets'])
- set2 = set(['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'documents'])
- set3 = set(['minhash', 'is', 'probability', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'documents'])
-
- m1 = MinHash(num_perm=128)
- m2 = MinHash(num_perm=128)
- m3 = MinHash(num_perm=128)
- for d in set1:
- m1.update(d.encode('utf8'))
- for d in set2:
- m2.update(d.encode('utf8'))
- for d in set3:
- m3.update(d.encode('utf8'))
-
- # Create LSH index
- lsh = MinHashLSH(threshold=0.5, num_perm=128)
- lsh.insert("m2", m2)
- lsh.insert("m3", m3)
- result = lsh.query(m1)
- print("Approximate neighbours with Jaccard similarity > 0.5", result)
案例的大致步骤为:
MinHash初始化状态:需要预先设定MinHash\(num\_perm=128\)
初始化状态;
内容哈希化:内容m1.update哈希化;
MinHashLSH初始化:MinHashLSH\(threshold=0.5, num\_perm=128\)
内容载入LSH系统:lsh.insert\(“m3”, m3\)
,其中insert(Hash名称,minHash值)
查询: lsh.query
,其中查询的内容也必须minHash化。
同时,MinHashLSH不能采用多项内容 Top-K 查询。可以使用之后的 MinHash LSH Forest,同时Jaccard 距离可能不是最好的选择,也可以选择其他的距离,可见MinHash LSH Ensemble[2].
其他内容:
remove(key)
与lsh.insert(“m2”, m2),对应。
is_empty()
返回的是布尔值,检查hash是否为空
与文章LSH︱python实现局部敏感随机投影森林——LSHForest/sklearn(一)[3]类似,都是用来做随机投影森林的,这里专门使用minhash。
MinHash LSH可以使用 radius 或 阈值 查询。MinHash LSH Forest支持指定top-K查询内容,forest更少地占用空间。
MinHashLSHForest(num_perm=128, l=8)
与原论文使用prefix trees不同,作者这里把哈希值存储在每个哈希列表中。
num_perm就是随机置换函数的个数,l代表prefix trees的数量。
其中每个前缀树的最大深度K取决于num_perm、l
k = int(num_perm / l)
- from datasketch import MinHashLSHForest, MinHash
-
- data1 = ['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'datasets']
- data2 = ['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'documents']
- data3 = ['minhash', 'is', 'probability', 'data', 'structure', 'for',
- 'estimating', 'the', 'similarity', 'between', 'documents']
-
- # Create MinHash objects
- m1 = MinHash(num_perm=128)
- m2 = MinHash(num_perm=128)
- m3 = MinHash(num_perm=128)
- 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'))
-
- # Create a MinHash LSH Forest with the same num_perm parameter
- forest = MinHashLSHForest(num_perm=128)
-
- # Add m2 and m3 into the index
- forest.add("m2", m2)
- forest.add("m3", m3)
-
- # IMPORTANT: must call index() otherwise the keys won't be searchable
- forest.index()
- # Check for membership using the key
- print("m2" in forest)
- print("m3" in forest)
- # Using m1 as the query, retrieve top 2 keys that have the higest Jaccard
- result = forest.query(m1, 2)
- print("Top 2 candidates", result)
案例的大致步骤为:
MinHash初始化状态:需要预先设定MinHash\(num\_perm=128\)
初始化状态
内容哈希化:内容m1.update哈希化
MinHashLSHForest初始化:MinHashLSHForest\(num\_perm=128\)
内容载入投影森林之中:forest.add\(“m2”, m2\)
forest.index\(\)
,相当于update一下,更新一下
查询:lsh.query
,其中查询的内容也必须minHash化。
.
更多信息可查看MinHash LSH Ensemble[4]。
新距离:Containment,简单介绍一下。
案例一则:
- from datasketch import MinHashLSHEnsemble, MinHash
-
- set1 = set(["cat", "dog", "fish", "cow"])
- set2 = set(["cat", "dog", "fish", "cow", "pig", "elephant", "lion", "tiger",
- "wolf", "bird", "human"])
- set3 = set(["cat", "dog", "car", "van", "train", "plane", "ship", "submarine",
- "rocket", "bike", "scooter", "motorcyle", "SUV", "jet", "horse"])
-
- # Create MinHash objects
- m1 = MinHash(num_perm=128)
- m2 = MinHash(num_perm=128)
- m3 = MinHash(num_perm=128)
- for d in set1:
- m1.update(d.encode('utf8'))
- for d in set2:
- m2.update(d.encode('utf8'))
- for d in set3:
- m3.update(d.encode('utf8'))
-
- # Create an LSH Ensemble index with a threshold
- lshensemble = MinHashLSHEnsemble(threshold=0.8, num_perm=128)
-
- # Index takes an iterable of (key, minhash, size)
- lshensemble.index([("m2", m2, len(set2)), ("m3", m3, len(set3))])
-
- # Check for membership using the key
- print("m2" in lshensemble)
- print("m3" in lshensemble)
-
- # Using m1 as the query, get an result iterator
- print("Sets with containment > 0.8:")
- for key in lshensemble.query(m1, len(set1)):
- print(key)
更多信息可查看Weighted MinHash[5]。
Jaccard距离加权
- import numpy as np
- from datasketch import WeightedMinHashGenerator
- from datasketch import MinHashLSH
-
- v1 = np.random.uniform(1, 10, 10)
- v2 = np.random.uniform(1, 10, 10)
- v3 = np.random.uniform(1, 10, 10)
- mg = WeightedMinHashGenerator(10, 5)
- m1 = mg.minhash(v1)
- m2 = mg.minhash(v2)
- m3 = mg.minhash(v3)
-
- # Create weighted MinHash LSH index
- lsh = MinHashLSH(threshold=0.1, sample_size=5)
- lsh.insert("m2", m2)
- lsh.insert("m3", m3)
- result = lsh.query(m1)
- print("Approximate neighbours with weighted Jaccard similarity > 0.1", result)
[1]
R语言实现︱局部敏感哈希算法(LSH)解决文本机械相似性的问题(一,基本原理): https://blog.csdn.net/sinat_26917383/article/details/52451028
[2]MinHash LSH Ensemble: https://ekzhu.com/datasketch/lshensemble.html#minhash-lsh-ensemble
[3]LSH︱python实现局部敏感随机投影森林——LSHForest/sklearn(一): https://blog.csdn.net/sinat_26917383/article/details/70243066
[4]MinHash LSH Ensemble: https://ekzhu.github.io/datasketch/lshensemble.html
[5]Weighted MinHash: https://ekzhu.github.io/datasketch/weightedminhash.html
文章来源:https://blog.csdn.net/sinat_26917383/article/details/70332325
作者:悟乙己
编辑:@公众号 AI算法小喵
最后给大家推荐一下最近小编从最新的斯坦福NLP的公开课都放到了bilibili上了,都已做了中英翻译,大部分已经更新完毕了,给需要的小伙伴~
是最新的呦~
目录
词向量
神经分类器
反向传播和神经网络
句法结构
RNN
LSTM
机器翻译、Seq2Seq和注意力机制
自注意力和Transformer
Transformers和预训练
问答
自然语言生成
指代消解
T5和大型预训练模型
待更...
点击阅读原文直达b站~
进NLP群—>加入NLP交流群
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。