Datasketch 教程

🕗 发布于 2024-09-30 03:49 数据去重

Datasketch 教程：近似集合操作和局部敏感哈希 (LSH)

Datasketch 是一个 Python 库，专注于高效的集合操作和局部敏感哈希（LSH）等近似算法。它特别适合处理高维数据，例如在海量数据中快速查找相似对象（如图片、文本、音频等）的应用场景。Datasketch 提供了 MinHash、HyperLogLog、b-Bit MinHash、Weighted MinHash、和 LSH 等强大的功能。

官方文档链接

Datasketch 的官方文档可以在 https://ekzhu.github.io/datasketch/ 找到。

一、安装

首先，安装 Datasketch 库：

pip install datasketch

二、MinHash 基本操作

MinHash 是一种用于集合相似度近似计算的算法，主要用于估计两个集合的 Jaccard 相似度。它通常用于查找相似文档、图片等应用中。

1. MinHash 的基本用法

假设我们有两个文档，每个文档可以被表示为单词的集合。我们可以使用 MinHash 来计算它们的 Jaccard 相似度。

from datasketch import MinHash

# 两个示例集合
set1 = {'apple', 'banana', 'grape'}
set2 = {'apple', 'orange', 'grape'}

# 创建 MinHash 对象
m1, m2 = MinHash(), MinHash()

# 为每个集合中的元素进行 MinHash 签名
for item in set1:
    m1.update(item.encode('utf8'))

for item in set2:
    m2.update(item.encode('utf8'))

# 计算两个集合的 Jaccard 相似度
similarity = m1.jaccard(m2)
print(f"MinHash 估计的 Jaccard 相似度: {similarity}")

在上面的代码中，MinHash.update() 用于将集合中的每个元素加入到 MinHash 对象中。最后，通过 jaccard() 方法估计两个集合的 Jaccard 相似度。

2. MinHash 计算精度的调节

MinHash 的计算精度可以通过设置哈希函数的数量来调节。哈希函数数量越多，计算的相似度越精确，但相应的时间复杂度和空间复杂度也会增加。

# 设置 MinHash 使用 128 个哈希函数
m1, m2 = MinHash(num_perm=128), MinHash(num_perm=128)

for item in set1:
    m1.update(item.encode('utf8'))

for item in set2:
    m2.update(item.encode('utf8'))

similarity = m1.jaccard(m2)
print(f"MinHash (128 个哈希函数) 估计的 Jaccard 相似度: {similarity}")

三、局部敏感哈希 (LSH)

局部敏感哈希 (LSH) 是一种用于高效查找近似最近邻的算法，能够加速海量数据中的相似搜索。Datasketch 提供了 MinHash LSH 来解决这个问题。

1. LSH 基本用法

使用 LSH，可以在大量集合中快速查找与目标集合相似的集合。以下示例展示了如何使用 LSH 查找相似集合。

from datasketch import MinHash, MinHashLSH

# 创建 MinHash LSH，设置阈值为 0.5
lsh = MinHashLSH(threshold=0.5, num_perm=128)

# 构建 MinHash 对象
m1, m2, m3 = MinHash(num_perm=128), MinHash(num_perm=128), MinHash(num_perm=128)

set1 = {'apple', 'banana', 'grape'}
set2 = {'apple', 'orange', 'grape'}
set3 = {'pear', 'banana', 'grape'}

# 为每个集合生成 MinHash 签名
for item in set1:
    m1.update(item.encode('utf8'))

for item in set2:
    m2.update(item.encode('utf8'))

for item in set3:
    m3.update(item.encode('utf8'))

# 将 MinHash 对象添加到 LSH
lsh.insert("set1", m1)
lsh.insert("set2", m2)
lsh.insert("set3", m3)

# 查询与 set1 相似的集合
result = lsh.query(m1)
print(f"与 set1 相似的集合: {result}")

在这个示例中，我们创建了一个 LSH 对象，设置了相似度阈值为 0.5。接着，我们将三个 MinHash 对象添加到 LSH 中，并使用 query() 方法查询与某个集合相似的集合。

2. LSH 批量插入和查询

如果有大量数据，Datasketch 支持批量插入和查询，以提高效率。

# 插入多个 MinHash 对象
lsh.insert_batch([("set1", m1), ("set2", m2), ("set3", m3)])

# 批量查询相似的集合
queries = [("query1", m1), ("query2", m2)]
results = lsh.query_batch(queries)

for query, result in zip(queries, results):
    print(f"与 {query[0]} 相似的集合: {result}")

3. 自定义 LSH 参数

LSH 的性能和准确性可以通过 threshold（相似度阈值）、num_perm（哈希函数数量）等参数进行调节。合理设置这些参数，可以在查询速度和准确性之间取得平衡。

# 创建 MinHash LSH，使用较高的相似度阈值
lsh = MinHashLSH(threshold=0.8, num_perm=256)

# 插入 MinHash 对象并进行查询
lsh.insert("set1", m1)
result = lsh.query(m1)
print(f"与 set1 相似的集合: {result}")

四、HyperLogLog (HLL) 使用

HyperLogLog (HLL) 是一种用于近似计数的算法，可以用于估计集合的基数（即集合中不重复元素的数量）。与 MinHash 不同，HyperLogLog 更加适合处理基数估计问题。

1. 基本用法

以下示例展示了如何使用 HyperLogLog 进行基数估计。

from datasketch import HyperLogLog

# 创建一个 HyperLogLog 对象
hll = HyperLogLog()

# 插入元素
for item in set1:
    hll.update(item.encode('utf8'))

# 估计集合基数
cardinality = hll.count()
print(f"集合的基数估计值: {cardinality}")

HyperLogLog 可以处理非常大的集合，并且内存占用极小，因此适合用于大规模数据集的去重计数。

五、Weighted MinHash (加权 MinHash)

Weighted MinHash 是一种扩展的 MinHash 算法，适用于集合中元素具有权重的情况。它可以用于计算带权重集合的 Jaccard 相似度。

1. 加权 MinHash 的使用

假设我们有两个带有权重的集合，Datasketch 的 Weighted MinHash 可以帮助我们计算其加权 Jaccard 相似度。

from datasketch import WeightedMinHash

# 两个加权集合，元素和对应权重
weights1 = {'apple': 1.0, 'banana': 2.0, 'grape': 1.0}
weights2 = {'apple': 1.0, 'orange': 2.0, 'grape': 1.0}

# 创建加权 MinHash 对象
wm1 = WeightedMinHash(seed=42)
wm2 = WeightedMinHash(seed=42)

# 更新 MinHash 对象，输入元素和对应权重
for item, weight in weights1.items():
    wm1.update(item.encode('utf8'), weight)

for item, weight in weights2.items():
    wm2.update(item.encode('utf8'), weight)

# 计算加权 Jaccard 相似度
weighted_similarity = wm1.jaccard(wm2)
print(f"加权 Jaccard 相似度: {weighted_similarity}")

六、总结

Datasketch 是一个功能强大的库，适合处理大规模集合相似性问题。通过 MinHash、LSH、HyperLogLog、Weighted MinHash 等工具，用户可以高效地处理集合相似性搜索、基数估计、去重计数等问题。

MinHash：用于快速计算集合之间的 Jaccard 相似度。
LSH：基于 MinHash 的局部敏感哈希，用于加速相似性搜索。
HyperLogLog：一种用于基数估计的高效算法。

Weighted MinHash：适用于带权重集合的相似度计算。

如果你需要处理海量数据并且需要进行相似度查询、基数估计等操作，Datasketch 是一个非常实用的工具。

原文地址：https://blog.csdn.net/jixiaoyu0209/article/details/142643908

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：在Python中实现多目标优化问题（2）
下一篇：完成UI界面的绘制

Unity 的 UI Event System 是一个重要的框架
UI 元素（如按钮、滑块等）可以通过实现特定的接口（如 `IPointerClickHandler`、`ISubmitHandler`）来响应事件，开发者可以定义在特定事件发生时执行的逻辑。Unity
阅读更多2024-10-03
Prompt 模版解析：诗人角色的创意引导与实践
Prompt 模版作为一种结构化工具，旨在为特定角色——本例中的“诗人”——提供明确的指导和框架。这一模版详尽地描绘了诗人的职责、擅长的诗歌形式以及创作规则，使其能在自动化系统中更加精确地执行任务。诗
阅读更多2024-10-03
Edge SCDN：安全与速度并进的解决方案
面对日益复杂的网络攻击手段，Edge SCDN凭借其强大的安全防护能力和灵活的部署方式，成为了企业构建稳定、安全在线环境的不二选择。Edge SCDN（边缘安全加速）正重新定义着内容分发与安全防护的边
阅读更多2024-10-03
过渡到内存安全语言：挑战和注意事项
内存安全问题已存在五十多年，它要求程序员从内存管理任务中抽离出来。
阅读更多2024-10-03
SSL VPN | Easyconnect下载&安装&使用（详尽）
EasyConnect是一款远程连接工具，为用户提供简便、快捷的远程访问和控制解决方案。
阅读更多2024-10-03
加密与安全_TOTP 一次性密码生成算法
为了验证 TOTP，服务端会接收用户输入的 OTP，并根据当前时间戳生成自己的 TOTP，进行比对。TOTP 是一种基于时间的动态密码算法，通过时间戳和共享密钥生成一次性密码，常用于双因素身份验证场景
阅读更多2024-10-03
基础IO：动静态库
必须要告诉编译器，头文件目录在哪？、静态库目录在哪？，以及要链接的静态库名称。
阅读更多2024-10-03
Linux之进程概念
1.一个冷知识：屏蔽力是一个人最顶级的能力，任何消耗你的人和事，多看一眼都是你的不对。2.你不用变得很外向，内向挺好的，但需要你发言的时候，一定要勇敢。正所谓：君子可内敛不可懦弱，面不公可起而论之。3
阅读更多2024-10-03
【C#生态园】探秘化学信息学库：功能、安装与配置一网打尽
本文将介绍六个常用的化学信息学库，分别是 RDKit、Open Babel、ChemAxon、CDK、Indigo Toolkit 和 Cheminformatics Suite。我们将对它们的核心功
阅读更多2024-10-03
【分布式训练 debug】VS Code Debug 技巧：launch.json实用参数
在使用Visual Studio Code (VS Code)进行调试时，文件是一个强大的工具，它允许你自定义调试会话。以下是一些实用的参数，可以帮助你更有效地调试Python代码。
阅读更多2024-10-03