关于局部敏感哈希算法,之前用 R 语言实现过,但是由于在 R 中效能太低,于是放弃用 LSH 来做相似性检索。学了 python 发现很多模块都能实现,而且通过随机投影森林让查询数据更快,觉得可以试试大规模应用在数据相似性检索 + 去重的场景。
私认为,文本的相似性可以分为两类:一类是机械相似性;一类是语义相似性。 机械相似性代表着,两个文本内容上的相关程度,比如 "你好吗" 和 "你好" 的相似性,纯粹代表着内容上字符是否完全共现,应用场景在:文章去重; 语义相似性代表着,两个文本语义上的相似程度,比如 "苹果" 和 "公司" 的相似性,本篇不做这一讨论
之前写关于 R 语言实现的博客: R 语言实现︱局部敏感哈希算法(LSH)解决文本机械相似性的问题(一,基本原理) R 语言实现︱局部敏感哈希算法(LSH)解决文本机械相似性的问题(二,textreuse 介绍)
机械相似性 python 版的四部曲: LSH︱python 实现局部敏感随机投影森林——LSHForest/sklearn(一) LSH︱python 实现局部敏感哈希——LSHash(二) 相似性︱python+opencv 实现 pHash 算法 + hamming 距离(simhash)(三) LSH︱python 实现 MinHash-LSH 及 MinHash LSH Forest——datasketch(四) .
本节参考:论文《基于随机投影的场景文本图像聚类方法研究》与博客 随机投影森林 - 一种近似最近邻方法(ANN)
当数据个数比较大的时候,线性搜索寻找 KNN 的时间开销太大,而且需要读取所有的数据在内存中,这是不现实的。因此,实际工程上,使用近似最近邻也就是 ANN 问题。 其中一种方法是利用随机投影树,对所有的数据进行划分,将每次搜索与计算的点的数目减小到一个可接受的范围,然后建立多个随机投影树构成随机投影森林,将森林的综合结果作为最终的结果。
建立一棵随机投影树的过程大致如下(以二维空间为例):
在数学计算上,是通过计算各个点与垂直向量的点积完成这一步骤的,点积大于零的点划分到左子树,点积小于零的点划分到右子树。 注意一点,图中不带箭头的直线是用于划分左右子树的依据,带箭头的向量是用于计算点积的。这样,原有的点就划分为了两部分,图例如下: 但是此时一个划分结果内的点的数目还是比较多,因此继续划分。再次随机选取一个向量,与该向量垂直的直线将所有点进行了划分。图例如下: 注意一点,此时的划分是在上一次划分的基础上进行的。 ? 也就是说现在图中的点已经被划分成了四部分,对应于一棵深度为 2,有四个叶节点的树。以此类推继续划分下去,直到每个叶节点中点的数目都达到一个足够小的数目。注意这棵树并不是完全树。
随机投影森林的建立需要两个参数,即单棵树的深度 + 森林数量。 这两个参数决定了数据集的分散程度以及随机投影后得到的向量维数。
利用这棵树对新的点进行最近邻计算时,首先通过计算该点与每次划分所用向量的点积,来找到其所属于的叶节点,然后利用这个叶节点内的?? 这些点进行最近邻算法的计算。 这个过程是一棵随机投影树的计算过程,利用同样的方法,建立多个随机投影树构成随机森林,将森林的总和结果作为最终的结果。 .
Wright 等人 已将随机投影的方法应用于视角变化的人脸识别,Nowak 等人 采用随机投影的方法学习视觉词的相似度度量,Freund 等人将随机投影应用于手写体识别上,取得了很好的效果。 .
论文《基于随机投影的场景文本图像聚类方法研究》中,将每一个叶子节点当成一维特征,用叶子节点的特征点个数作为叶子节点的描述,最后得到测试图像的特征向量。 有点类似 word2vec 之中的霍夫曼树。
论文中的实验结果: 其中,森林规模 10 棵。
由此可见,ASIFT 比 SIFT 对自然场景下的文本区域图像的局部特征描述更好更准确,这是因为 SIFT 只是具有尺度和旋转不变性,对于具有视角变化的相同文字却无法得到匹配描述,而 ASIFT 不仅对图像具有尺度旋转不变性,还具有仿射不变性,这种特性对自然场景下的文本处理有更好的实用性。 详细的 ASIFT 与 SIFT 对比可见论文。 .
LSHforest=LSH + 随机投影树 在 python 的 sklearn 中有 LSHForest 可以实现。官方文档在:sklearn.neighbors.LSHForest
- classsklearn.neighbors.LSHForest(n_estimators=10,radius=1.0,n_candidates=50,n_neighbors=5,min_hash_match=4,radius_cutoff_ratio=0.9,random_state=None)
随机投影森林是最近邻搜索方法的一种替代方法。 LSH 森林数据结构使用已排序数组、二进制搜索和 32 位固定长度的哈希表达。随机投影计算距离是使用近似余弦距离。
- n_estimators: int (default= 10)树的数量min_hash_match: int (default= 4)最小哈希搜索长度/个数,小于则停止n_candidates: int (default= 10)每一颗树评估数量的最小值,反正至少每棵树要评估几次,雨露均沾n_neighbors: int (default= 5)检索时,最小近邻个数,就怕你忘记忘了设置检索数量了radius: float, optinal (default= 1.0)检索时,近邻个体的距离半径radius_cutoff_ratio: float, optional (default= 0.9)检索时,半径的下限,相当于相似性概率小于某阈值时,停止搜索,或者最小哈希搜索长度小于4也停止random_state: int,RandomState instanceorNone, optional (default=None)随机数生成器使用种子,默认没有
附带属性:
- hash_functions_ : listofGaussianRandomProjectionHash objects
- 哈希函数g(p,x),每个样本一个哈希化内容
- trees_ :array, shape (n_estimators, n_samples)Eachtree (correspondingtoa hashfunction)
- 每棵树对应一个哈希散列,且这个哈希散列是经过排序的。显示的是哈希值。n_estimators棵树,n_samples个散列。original_indices_: array, shape (n_estimators, n_samples)
- 每棵树对应一个哈希散列,哈希散列是经过排序的,显示的是原数据序号index.
trees_ 和 original_indices_ 就是两种状态,trees_ 是每棵经过排序树的散列,original_indices_ 是每棵经过排序树的序号 Index. .
Fit the LSH forest on the data. 数据载入投影树
Get parameters for this estimator. 获取树里面的相关参数
检索函数,n_neighbors 代表所需近邻数, 不设置的话则返回初始化设置的数量,return_distance,是否打印 / 返回特定 cos 距离的样本。 返回两个 array,一个是距离 array,一个是概率 array
Computes the (weighted) graph of k-Neighbors for points in X 数量检索图,n_neighbors 代表所需近邻数, 不设置的话则返回初始化设置的数量,mode='connectivity'默认
添加数据到树里面,最好是批量导入。
Finds the neighbors within a given radius of a point or points. 半径检索,在给定的区间半径内寻找近邻,radius 为半径长度,return_distance 代表是否打印出内容。
Computes the (weighted) graph of Neighbors for points in X 半径检索图
Set the parameters of this estimator. 重设部分参数 .
- >>> from sklearn.neighbors import LSHForest
- >>> X_train = [[5,5,2], [21,5,5], [1,1,1], [8,9,1], [6,10,2]]
- >>> X_test = [[9,1,6], [3,1,10], [7,10,3]]
- >>> lshf = LSHForest(random_state=42)
- >>> lshf.fit(X_train)
- LSHForest(min_hash_match=4, n_candidates=50, n_estimators=10,
- n_neighbors=5, radius=1.0, radius_cutoff_ratio=0.9,
- random_state=42)
- >>> distances, indices = lshf.kneighbors(X_test, n_neighbors=2)
- >>> distances
- array([[0.069...,0.149...],
- [0.229...,0.481...],
- [0.004...,0.014...]])
- >>> indices
- array([[1,2],
- [2,0],
- [4,0]])
LSHForest(random_state=42) 树的初始化, lshf.fit(X_train) 开始把数据载入初始化的树; lshf.kneighbors(X_test, n_neighbors=2),找出 X_test 每个元素的前 2 个(n_neighbors)相似内容。 其中,这个是 cos 距离,不是相似性,如果要直观,可以被 1 减。 .
来源于:用 docsim/doc2vec/LSH 比较两个文档之间的相似度
- # 使用lsh来处理
- tfidf_vectorizer= TfidfVectorizer(min_df=3, max_features=None, ngram_range=(1, 2), use_idf=1, smooth_idf=1,sublinear_tf=1)train_documents= []
- for item_text in raw_documents:
- item_str = util_words_cut.get_class_words_with_space(item_text)
- train_documents.append(item_str)x_train= tfidf_vectorizer.fit_transform(train_documents)test_data_1= '你好,我想问一下我想离婚他不想离,孩子他说不要,是六个月就自动生效离婚'test_cut_raw_1= util_words_cut.get_class_words_with_space(test_data_1)x_test= tfidf_vectorizer.transform([test_cut_raw_1])lshf= LSHForest(random_state=42)
- lshf.fit(x_train.toarray())
- distances, indices = lshf.kneighbors(x_test.toarray(), n_neighbors=3)
- print(distances)
- print(indices)
一般 lsh 比较适合做短文本的比较
.
相关属性获得
- # 属性lshf.trees_# 每棵树,排序散列的哈希值lshf.hash_functions_# 每棵树的hash公式lshf.original_indices_# 每棵树,排序散列的序号index
最近邻检索的图:kneighbors_graph
- lshf.kneighbors_graph(X_test, n_neighbors=5, mode='connectivity')
新增数据到树里面:
- partial_fit(X_test)
来源: http://www.bubuko.com/infodetail-2036184.html