局部敏感性哈希是指：相似的哈希具有相似的原始序列
整体思路：
- 首先将数据装在不同的桶里（通过桶之间的Jaccard系数计算原始数据hash）
- 得到hash生成的规则
- 用这个规则来转换新的数据
- 将新数据生成的hash与原有的所有hash进行比较，选择最相似的
注：最后比较的过程不是两两匹配，每个不同的算法都有不同的简化的方式
局部敏感性hash详细请参考：https://www.cnblogs.com/fengfenggirl/p/lsh.html
一、原生python实现
文章、代码地址：https://blog.csdn.net/sgyuanshi/article/details/108132214
import numpy as np
from typing import List, Union
class EuclideanLSH(object):
def __init__(self, tables_num: int, a: int, depth: int):
"""
:param tables_num: hash_table的个数
:param a: a越大，被纳入同个位置的向量就越多，即可以提高原来相似的向量映射到同个位置的概率，
反之，则可以降低原来不相似的向量映射到同个位置的概率。
:param depth: 向量的维度数
"""
self.tables_num = tables_num
self.a = a
# 为了方便矩阵运算，调整了shape，每一列代表一个hash_table的随机向量
self.R = np.random.random([depth, tables_num])
self.b = np.random.uniform(0, a, [1, tables_num])
# 初始化空的hash_table
self.hash_tables = [dict() for i in range(tables_num)]
def _hash(self, inputs: Union[List[List], np.ndarray]):
"""
将向量映射到对应的hash_table的索引
:param inputs: 输入的单个或多个向量
:return: 每一行代表一个向量输出的所有索引，每一列代表位于一个hash_table中的索引
"""
# H(V) = |V·R + b| / a，R是一个随机向量，a是桶宽，b是一个在[0,a]之间均匀分布的随机变量
hash_val = np.floor(np.abs(np.matmul(inputs, self.R) + self.b) / self.a)
return hash_val
def insert(self, inputs):
"""
将向量映射到对应的hash_table的索引，并插入到所有hash_table中
:param inputs:
:return:
"""
# 将inputs转化为二维向量
inputs = np.array(inputs)
if len(inputs.shape) == 1:
inputs = inputs.reshape([1, -1])
hash_index = self._hash(inputs)
for inputs_one, indexs in zip(inputs, hash_index):
for i, key in enumerate(indexs):
# i代表第i个hash_table，key则为当前hash_table的索引位置
# inputs_one代表当前向量
self.hash_tables[i].setdefault(key, []).append(tuple(inputs_one))
def query(self, inputs, nums=20):
"""
查询与inputs相似的向量，并输出相似度最高的nums个
:param inputs: 输入向量
:param nums:
:return:
"""
hash_val = self._hash(inputs).ravel()
candidates = set()
# 将相同索引位置的向量添加到候选集中
for i, key in enumerate(hash_val):
candidates.update(self.hash_tables[i][key])
# 根据向量距离进行排序
candidates = sorted(candidates, key=lambda x: self.euclidean_dis(x, inputs))
return candidates[:nums]
@staticmethod
def euclidean_dis(x, y):
"""
计算欧式距离
:param x:
:param y:
:return:
"""
x = np.array(x)
y = np.array(y)
return np.sqrt(np.sum(np.power(x - y, 2)))
if __name__ == '__main__':
data = np.random.random([10000, 100])
query = np.random.random([100])
lsh = EuclideanLSH(10, 1, 100)
lsh.insert(data)
# 开始查询
res = lsh.query(query, 20)
res = np.array(res)
print(np.sum(np.power(res - query, 2), axis=-1)) # 计算LSH的结果与query的结果的差距
all_data = np.concatenate((data, [query]))
sort = np.argsort(np.sum(np.power(all_data - query, 2), axis=-1)) # 线性查找真正的最接近的曲线
print(np.sum(np.power(all_data[sort[:20]] - query, 2), axis=-1)) # 计算最接近的20个结果
print(np.sum(np.power(all_data[sort[-20:]] - query, 2), axis=-1)) # 对比计算最远的20个结果
二、第三方库datasketch使用
github项目地址：https://github.com/ekzhu/datasketch
pip安装：pip install datasketch
1. 官方示例
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)
得到的结果：
Approximate neighbours with Jaccard similarity > 0.5 ['m3', 'm2']
2. LSH算法
文档地址：http://ekzhu.com/datasketch/documentation.html?highlight=minhashgenerator#minhash-lsh
import numpy as np
from datasketch import WeightedMinHashGenerator
from datasketch import MinHashLSH
from tqdm import tqdm
all_data = np.random.random([10000, 100])
query = np.random.random([100])
mg = WeightedMinHashGenerator(all_data.shape[1])
lsh = MinHashLSH(threshold=0.7)
for index, value in tqdm(enumerate(all_data)):
m_hash = mg.minhash(value)
lsh.insert(index, m_hash)
result = lsh.query(mg.minhash(query))
print(result)
# 开始验证
print(np.sum(np.power(all_data[result] - query, 2), axis=-1)) # 计算LSH的结果与query的结果的差距
total_data = np.concatenate((all_data, [query]))
sort = np.argsort(np.sum(np.power(total_data - query, 2), axis=-1)) # 线性查找真正的最接近的曲线
print(np.sum(np.power(total_data[sort[:20]] - query, 2), axis=-1)) # 计算最接近的曲线
print(np.sum(np.power(total_data[sort[-20:]] - query, 2), axis=-1))
3. MinHashLSHForest
MinHashLSHForest可以选择Top K的内容
import numpy as np
from datasketch import WeightedMinHashGenerator
from datasketch import MinHashLSHForest
from tqdm import tqdm
all_data = np.random.random([10000, 100])
query = np.random.random([100])
mg = WeightedMinHashGenerator(all_data.shape[1])
forest = MinHashLSHForest()
for index, value in tqdm(enumerate(all_data)):
m_hash = mg.minhash(value)
forest.add(index, m_hash)
forest.index() # 重要！在此之后才可以使用查询功能
result = forest.query(mg.minhash(query), 20) # 选择top20
print(result)
# 开始验证
print(np.sum(np.power(all_data[result] - query, 2), axis=-1)) # 计算LSH的结果与query的结果的差距
total_data = np.concatenate((all_data, [query]))
sort = np.argsort(np.sum(np.power(total_data - query, 2), axis=-1)) # 线性查找真正的最接近的曲线
print(np.sum(np.power(total_data[sort[:20]] - query, 2), axis=-1)) # 计算最接近的曲线
print(np.sum(np.power(total_data[sort[-20:]] - query, 2), axis=-1))
