标签：匹配 化以 记录 标记 布隆 过滤器 Bloom 我们

比较 Bloom 过滤器和标记化以匹配去识别的患者数据

了解 Datavant 用于匹配数据的标记化

Datavant 的使命是连接全球医疗保健数据，以改善患者治疗效果，同时维护患者隐私。 HIPAA 有一个 18条识别信息列表 为了满足去识别化的安全港方法，必须将其删除，并就如何将部分患者数据包含在记录中同时仍符合“去识别化”的条件提供进一步的指导。当然，目标是保护患者隐私，但不幸的是，如果患者的识别信息完全从记录中删除，则无法将患者的医疗保健数据合并到一个记录中（例如，住院）与数据另一份记录（例如，出院后的药房处方）。

至 跨数据集匹配患者数据 , Datavant 使用标记化技术，使我们能够对患者健康信息 (PHI) 进行去标识化，然后将其与其他数据集重新链接，同时保持个人身份信息 (PII) 的隐私。我们的标记化将 PII 替换为加密的“标记”，该“标记”无法通过逆向工程来揭示原始信息。使用这种技术，我们可以在任何数据集中创建相同的患者特定标记，这意味着可以使用患者标记组合两个不同的数据集以匹配相应的记录，同时还可以保持这些记录中 PII 的隐私。

我们的匹配过程从一对患者记录中生成一个三元一致向量：如果记录匹配，则为“true”，如果记录不匹配，则为“false”，如果因为无法比较它们而无法匹配，则为“null”，当，例如，一条记录缺少特定比较字段中的数据，例如中间名：

这个三元向量输入机器学习模型，然后确定被比较的记录是否属于同一患者。你可以阅读更深入的 我们在此处的标记化过程的摘要。

我们正在积极构建这项技术的未来，因此我们也会定期考虑替代我们当前战略的方案。跨数据集匹配数据的一种潜在替代策略是使用布隆过滤器。

什么是布隆过滤器？

构思 1970 年的伯顿·霍华德·布鲁姆 ，布隆过滤器是一种概率数据结构，用于确定特定元素是否是给定集合的成员。查询不会完全肯定地告诉您元素是否在集合中，而是会为您提供 可能性 一个元素在一个集合中，或者会告诉你它确实是 不是 在集合中。根据您的容忍度，您可能会收到误报，但您永远不会收到误报。有关 Bloom 过滤器的更深入的教程，有一些优秀的资源可在 Geeks for Geeks 编码介绍 , Github ， 乃至 维基百科 .

（顺便， 果蝇 已被证明展示了一种用于新颖性检测的神经数据结构，其功能类似于布隆过滤器。）

当可用数据使匹配尝试变得复杂时

布隆过滤器可用于将 PII 编码为易于比较的数字向量。与标记化相比，Bloom 过滤器的主要优势在于，它们在面对数据的细微差异时更加稳健，例如笔误，这会使精确匹配记录变得复杂。

为了说明这一点，请考虑仅包含几个 PII 元素的患者医院就诊记录：

约翰·奥谢，男性，1967 年 10 月 21 日，33756

在重复医院就诊时，在将 O'Shea 先生的数据输入系统时出现了笔误，并创建了一个新记录，其中只有一个拼写错误：

约翰·奥希，男性，1967 年 10 月 21 日，33756

由于 Datavant 的标记化在很大程度上依赖于完整的姓氏进行匹配，因此这些记录可能会因为拼写错误而无法匹配为属于一个人。

同样，在匹配过程中，通常存在两个主要问题：记录匹配的准确性和维护隐私的能力。我们先讨论匹配。

通过布隆过滤器进行概率匹配

布隆过滤器提供部分匹配，以解决小差异，如拼写错误。他们依靠 散列 创建一个过滤器，它本身就是一个给定长度的二进制向量 大号 旁边是一组 ķ 哈希函数 hᵢ 将数据元素映射到整数范围 1… 大号 .

例如，要将数据元素“JOHN”编码到布隆过滤器中，您可以使用每个散列函数对名称的每个字母进行散列 hᵢ 并将这些位置的位设置为 1。

以下是其工作原理的说明：

在这里，包含上述五个 PII 元素中的三个的记录使用五个散列函数（每个子元素下方的垂直数字列）散列到一个大型布隆过滤器中。每个子元素下的数字（双字母表示字母对或单字母表示单个日期数字）代表的是布隆过滤器中的位置，每次通过时都设置为 1。

一旦为记录填充了布隆过滤器，就可以通过计算两个二进制向量之间的距离来匹配其他记录的布隆过滤器编码。最常用的距离是 汉明距离 （最小数量 换人 需要将一个字符串更改为另一个字符串）在此处定义为精确位匹配的数量，并且 骰子指数 （用于衡量 相似 两个样本），它对位值 0 的匹配权重不足。我们可以将其写成一个等式：

探索我们如何使用布隆过滤器

我们试验了一个使用 Bloom 过滤器训练的模型，以使用包含以下配置文件字段的成对记录比较向量：

【DICE指数、性别特征、ZIP3特征、YOB特​​征、碰撞分数】

ZIP3 是 Datavant 使用而不是完整的邮政编码来定义“邮政区域”（基于 HIPAA 安全港规则），而 YOB 是出生年份，我们使用它而不是完整的出生日期。碰撞分数是根据名字/姓氏/出生十年组合的相对频率生成的。在美国，每年都有数千人出生时姓氏组合相同。碰撞分数帮助我们确定共享相同姓名/出生年份组合的记录属于同一个人的可能性。

不像我们在标记化过程中那样生成“匹配”/“不匹配”/“我不知道”的结果，布隆过滤器给出了一个介于 0 和 1 之间的数字，这是这两个过滤器置信度得分记录表示匹配，如果无法比较记录，则表示“我不知道”。 （同样，例如，如果一条记录有中间名而另一条记录没有，则无法比较中间名）。

在本实验中，布隆过滤器仅用于计算 DICE 索引。布隆过滤器通常是非常大的二元向量，经典机器学习模型难以处理太高维的数据。因为 DICE 索引捕获记录之间的微小差异，所以它减轻了上面前两个示例中所示的笔误问题。之间的 DICE 指数

约翰·奥谢，男性，1992 年 10 月 21 日，33756
约翰·奥希，男性，1992 年 10 月 21 日，33756

为 0.96（几乎相同），而 DICE 指数在

约翰·奥谢，男性，1992 年 10 月 21 日，33756
简，DOE，女性，1964 年 9 月 12 日，01111

为 0.20（几乎没有重叠）。

虽然我们无法绝对确定第一个示例中的匹配，但我们可以说这两个记录很可能属于同一个人。在第二个例子中，非常低的重叠程度告诉我们这些记录肯定不属于同一个人。

比较 Datavant 标记化与 Bloom 过滤器在记录匹配中的有效性

为了根据我们的标记化模型评估 Bloom 过滤器，我们使用了两个样本进行训练和评估：

• 我们之前通过预过滤过程识别为潜在匹配记录的 300,000 个现实世界数据对的小样本（即：至少有一个标记匹配）；
• 大约 300 万对的大样本，我们之前已将其确定为可能匹配的记录。

数据集分为 80% 的训练样本和 20% 的测试样本。为了比较，我们没有进行超参数调整或交叉验证。

对于每个数据集，我们训练了两个模型：

1. 我们的生产代币比较模型使用一小组所有潜在代币，这些代币代表客户可用于代币化的数据以及 [Gender、Zip3、YOB、Collision Scores] 字段；
2. 仅使用 Bloom 过滤器功能以及配置文件字段和碰撞分数的模型。

小型和大型数据集的结果

为了评估性能，我们查看了三个指标：
AUC-PR、召回@95% 和召回@99%。

AUC-PR（曲线精确召回面积）是一种性能指标，可用于在目标是定位正样本的环境中处理不平衡数据。在我们的例子中，我们正在寻找跨医疗记录的个人资料字段之间的正匹配，并且我们不想要误报，即：我们不希望返回不属于同一个人的记录之间的“匹配”。下表中给出的百分比是通过除以 # 个正面示例 / 总 # 个示例来计算的。

我们考虑的另一个性能指标是 [email protected]%。 AUC-PR 试图确定正确识别的阳性匹配的比例，而 [email protected]% 尝试识别正确识别的所有阳性匹配的比例，并且也以百分比来衡量。您可以阅读有关与机器学习相关的精确召回的更多信息 这里 .

在内部，我们使用 [email protected] 来评估新模型。 [email protected] 是模型以固定的 95% 准确率实现的召回率。在下表中，当模型阈值设置为 95% 的准确率时，令牌实现了 90% 的召回率。我们使用此指标是因为我们和我们的客户通常都要求将其作为匹配成功的最低精度水平。在召回中偏爱更高的精度可以降低返回误报的可能性。然后，模型的优化变成了在最低精度水平上最大化召回的问题。

小数据集上的结果

大型数据集的结果

您可以在上面的图表中看到，在这两个数据集中，使用 AUC-PR 评估时，令牌比布隆过滤器略有优势，而使用 [email protected]% 评估时，布隆过滤器模型比令牌有轻微优势。但是，Bloom 过滤器在 [email protected]% 的精确度（正确识别 99% 的匹配）下成功匹配显着下降。

布隆过滤器闪耀的地方

Bloom 过滤器优于令牌的一种情况是令牌关键 PII 上存在严重的文书错误。例如，如果姓氏拼写错误的可能性很高，我们确定布隆过滤器方法在确定匹配时可能会表现得更好。但是，与其他错误相比，用于此比较的数据集中的文书错误数量很少，因此布隆过滤器提供的性能提升在这里可以忽略不计。

预过滤：布隆过滤器匹配方法的一个缺点

Datavant 依靠令牌快速过滤任何给定记录的潜在匹配列表。我们对记录中的每个配置文件字段（名字、姓氏、ZIP3 等）进行标记，因此我们假设两条记录不太可能匹配，除非至少有一个标记在记录之间匹配，这意味着我们可以快速轻松地进行 -当我们收到新记录时并行化预过滤步骤。

在某些情况下，布隆过滤器允许使用一种称为 阻塞 （执行子集比较以减少必要比较的总数），但我们的标记化技术采用的预过滤策略在这方面更有效。通过消除将每条新记录与其他每条记录进行比较以定位潜在匹配项的需要，此阶段的效率有助于提高下游性能。

使用 Bloom 过滤器进行预过滤可能有另一种解决方法。请记住，我们比较 Bloom 过滤器编码的方法之一是通过汉明距离，将一个字符串更改为另一个字符串所需的最小替换次数。在这样的空间中，有有效的近似算法来检索最接近的 100（或任何其他 n ) 给定点的邻居。一个基准 最流行的算法可以在这里找到 .

匹配将涉及两个步骤。鉴于新记录，我们将：

1. 使用近似最近邻算法查找最近的 100 条已见记录；
2. 对这 100 条记录进行全面比较以创建新的匹配链接。

在这个过程中，我们可能会错过真正的正匹配，但我们会尝试通过允许传递连接来缓解这个问题（即：A 匹配 B，B 匹配 C，因此 A 通过传递连接匹配 C）。

保护隐私：关键任务性能指标

去识别和匹配程序有效性的另一个关键指标是它保护 PII 隐私的潜力。 Datavant 的标记化过程是 安全、透明和可审计 .

我们认为布隆过滤器容易受到频率攻击。恶意用户可以通过查看例如布隆过滤器位置中设置位的频率来重新识别部分数据集。

一种可能的防范措施是更换过滤器本身。我们关心的在布隆过滤过程中生成的二进制向量的主要特征是 距离 在用于查找匹配的两个二进制向量之间。如果我们不保存二进制向量，而是保存地图的输出：

f:[0,1]ᴸ → Rⁿ 这样

那么我们就有可能躲避频率攻击。

如文章顶部所述，Datavant 致力于在整个数据交换过程中保护隐私。为了让我们考虑在生产中使用 Bloom 过滤器，他们需要克服在这一关键任务性能领域中独立可审计性这一极其重大的障碍。

外卖

• 在匹配记录之间可能存在许多小差异的情况下，布隆过滤器比 Datavant 的标记化提供了边际优势。他们在 [email protected] 提供的这种稍微好一点的性能被以下因素所抵消：

1. 他们对频率攻击的脆弱性，
2. [email protected] 的性能较低，以及
3. 目前缺乏可审计性。 *****

• 最后，我们相信它们也比我们当前标记化中涉及的机器学习模型更难微调性能。

***** 这并不是说布隆过滤器不能变得安全，或者不能被审计，而是这样的审计需要大量的时间和资源。

注意：这些结论是根据对当前可用数据集的评估得出的，并且可能会随着新数据的变化而变化。

由 Sebastian Claici 和 Nicholas DeMaison 撰写，Jonah Leshin、Varun Lahoti、Arjun Sanghvi、Carlos Guzman、Aneesh Kulkarni 和 Bob Borek 提供了重要意见。

关于作者

Sebastian Claici 拥有麻省理工学院的计算机科学博士学位，他也是该校的研究助理。他于 2021 年加入 Datavant，担任数据科学家。通过联系 Sebastian 领英 .

Nicholas DeMaison 喜欢讲述关于复杂事物的简单故事。通过与尼克联系 领英 .

考虑加入 Datavant 团队？看看我们的 职业页面 并看到我们在 2022 年福布斯美国最佳创业雇主 .我们目前正在跨团队远程招聘，并希望与任何新的潜在 Datvanters 交谈，他们很好、聪明、能把事情做好，并希

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/40060/34433017

标签：匹配,化以,记录,标记,布隆,过滤器,Bloom,我们
From： https://www.cnblogs.com/amboke/p/16745664.html