# 一、MinHash
MinHash 是一种用于近似集合相似度计算的技术。它被广泛用于大规模数据集中的快速相似度估计，特别是在处理文本、图像和网络数据等领域。
MinHash 的基本思想是通过将集合中的元素哈希成一个较小的签名（通常是一个固定长度的整数或比特串），从而快速地比较两个集合之间的相似度。
MinHash 算法的主要步骤如下：
- 集合转换成签名：对于一个集合中的元素，通过哈希函数将其映射到一个固定长度的哈希值。通常会使用多个哈希函数生成多个哈希值，这样就得到了一个签名。
- 选择最小值：从生成的哈希值中选取最小的一个作为该集合的 MinHash 值。
- 重复以上步骤：对于每个集合，重复以上两个步骤，得到所有元素的 MinHash 值。
MinHash 的关键优势在于它可以以很小的内存占用和低计算成本来估计集合之间的相似度。这对于处理大规模数据集是非常重要的。
需要注意的是，MinHash 是一种概率性算法，它提供的相似度估计是以一定的概率为基础的。因此，在应用中需要根据具体情况进行适当的参数设置和结果解释。
# 二、LSH
局部敏感哈希（Locality-Sensitive Hashing，LSH）是一种用于在高维空间中快速搜索相似项的近似搜索技术。它特别适用于处理大规模数据集，其中传统的精确搜索方法可能变得过于昂贵或不可行。
LSH 的主要思想是将相似的项映射到相同的桶（buckets）中，从而可以在相似的项之间进行快速的搜索。它通过在数据集中构建哈希表来实现这一目的。
以下是 LSH 的一般工作流程：
- 特征提取：将数据点表示为特征向量，这些特征可以是任意类型的，例如文本、图像或数值数据。
- 哈希函数选择：选择一组哈希函数，这些函数将特征向量映射到哈希空间。这些哈希函数通常被设计为局部敏感的，也就是说，相似的项在哈希空间中有更高的概率被映射到相同的桶中。
- 桶的构建：将所有数据点通过哈希函数映射到桶中。
- 查询：给定一个查询项，将其通过相同的哈希函数映射到哈希空间，并查找相同桶中的项，以找到近似的邻居。
- 候选项筛选：对于返回的相邻项集，通过进一步的计算或筛选来确定最终的相似项。
常见的 LSH 变体包括：
- MinHash LSH * 用于处理集合数据的 LSH 变体，通过将集合映射到 MinHash 签名来进行相似度搜索。
- LSH Forest * 用于高维空间中的范围搜索，可以有效地处理最近邻搜索。
- SimHash LSH * 用于处理高维二进制数据的 LSH 变体，通过将特征向量映射到二进制码并进行哈希操作。
- Cosine LSH * 用于处理余弦相似度的 LSH 变体，通常用于文本或向量空间模型中的相似性搜索。
LSH 是一种强大的技术，可以用于许多领域，包括信息检索、推荐系统、图像和音频处理等。它提供了一种有效的方法来解决大规模数据集中的相似性搜索问题。
# 三、Jaccard 相似度
给定两个集合 A,B，Jaccard 系数定义为 A 与 B 交集的大小与 A 与 B 并集的大小的比值，定义如下：
Jaccard 相似度在如下问题取得较好效果：在大的语料库中寻找文本内容相似的文档，这里主要指字面上的相似，而非语义上的相似。
# 四、参考程序
from datasketch import MinHash, MinHashLSH | |
# 创建一个 MinHash 对象 | |
def create_minhash(data): | |
minhash = MinHash(num_perm=128) # num_perm 是哈希函数的数量，可以根据需要调整 | |
for d in data: | |
minhash.update(d.encode('utf8')) | |
return minhash | |
# 创建一些示例数据（中文长句子） | |
sentences = [ | |
"今天天气很好，阳光明媚，适合出门散步。", | |
"我喜欢读书，尤其是科幻小说。", | |
"这个城市的夜景非常漂亮，尤其是灯光璀璨的CBD区。", | |
"我的家乡是一个美丽的小镇，四季分明，景色宜人。", | |
"学习新知识让我感到充实和快乐。", | |
"我喜欢健身，每天都会去健身房锻炼。", | |
"这家餐厅的菜品非常美味，尤其是他们的特色菜。", | |
"我喜欢旅行，尤其喜欢去一些自然风光优美的地方。", | |
"听音乐是我放松心情的最爱之一。", | |
"看电影是我周末最喜欢做的事情之一，我喜欢各种类型的电影。" | |
] | |
# 创建 MinHash 对象并插入到 LSH 中 | |
lsh = MinHashLSH(threshold=0.5, num_perm=128) # threshold 是相似度阈值，可以根据需要调整 | |
for idx, sentence in enumerate(sentences): | |
minhash = create_minhash(list(sentence)) | |
lsh.insert(idx, minhash) | |
# 查找相似的集合 | |
query_minhash = create_minhash(list('听音乐是我放松心情的最爱')) | |
results = lsh.query(query_minhash) | |
# 输出相似度分数 | |
for result in results: | |
minhash = create_minhash(list(sentences[result])) | |
jaccard_similarity = query_minhash.jaccard(minhash) | |
print(f"与 sentence 相似的句子 {result} 的相似度分数为: {jaccard_similarity}") | |
# output | |
与 sentence 相似的句子 8 的相似度分数为: 0.8046875 |
