17

我以前从未构建过匹配算法，也不知道从哪里开始。所以这是我的基本设置以及我这样做的原因。如果我没有提出正确的问题，请随时纠正我。

我有一个人名和唯一标识符数据库。几个生成的标识符（内部生成的和一些第三方的）、姓氏、名字和出生日期是我将使用的主要标识符。

一年中我多次收到来自第三方的列表，需要导入并绑定到我数据库中的现有人员，但数据从来没有我的干净。ID 可能会改变，出生日期可能有错别字，名字可能有错别字，姓氏可能会改变，等等。

每次导入可能有 20,000 条记录，因此即使准确率为 99%，我仍需要手动输入 200 条记录并进行匹配。我认为在将传入人员与我的用户匹配时，我正在寻找更像 99.9% 的准确度。

那么，我该如何制定一个可以解决这个问题的算法呢？

PS 即使您没有确切的答案，但知道一些可参考的材料也会有所帮助。

PPS 一些例子类似于 m3rLinEz 写的：

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Original'

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:10/20/84  '- Typo in birth date'
ID: 0876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Wrong ID'
ID: 9876234 Fname: Jose     LName: Guitierrez-Brown Birthdate:01/20/84  '- Hyphenated last name'
ID: 9876234 Fname: Jose, A. LName: Guitierrez       Birthdate:01/20/84  '- Added middle initial'
ID: 3453555 Fname: Joseph   LName: Guitierrez       Birthdate:01/20/84  '- Probably someone else with same birthdate and same last name'
4

6 回答 6

10

您可能对Levenshtein distance感兴趣。

两个字符串之间的 Levenshtein 距离定义为将一个字符串转换为另一个字符串所需的最小编辑次数，允许的编辑操作是插入、删除或替换单个字符。它以 Vladimir Levenshtein 的名字命名，他在 1965 年考虑到了这个距离。1

可以比较您的每个字段并计算总距离。通过反复试验，您可能会发现允许将记录解释为匹配的适当阈值。我自己还没有实现这个，只是想到了这个想法：}

例如：

  • 记录 A - ID：4831213321，姓名：Jane
  • 记录 B - ID：431213321，姓名：Jann
  • 记录 C - ID：4831211021，姓名：John

A 和 B 之间的距离将低于 A 和 C / B 和 C，这表明匹配更好。

于 2010-01-29T17:55:26.887 回答
1

When it comes to something like this, do not reinvent the wheel. The Levehstein distance is probably your best bet if you HAVE to do this yourself, but otherwise, do some research on existing solutions which do database query and fuzzy searches. They've been doing it longer than you, it'll probably be better, too..

Good luck!

于 2010-01-29T18:15:33.007 回答
0

如果您正在处理这种大小的数据集和正在导入的不同资源，您可能需要研究身份管理解决方案。我对 Sun Identity Manager 非常熟悉，但对于您正在尝试做的事情来说，它可能有点过头了。这可能值得研究。

于 2010-01-29T17:57:13.220 回答
0

如果您从第 3 方获得的数据是一致的（每次格式相同），我可能会为您从中获取数据的每个第 3 方创建一个表格。然后每次将每组新数据导入同一张表。我知道有一种方法可以使用 SQL 语句根据每个表中的公共列连接这两个表。这样，您可以执行 SQL 查询并从多个表中获取数据，但让它看起来像是来自一个统一的表。类似地，可以找到在两个表中都没有匹配项的添加记录，然后手动配对。这样，您就可以将“干净”数据与从第三方获得的垃圾分开。如果您想要真正的导入，则可以使用该连接表创建包含所有数据的第三个表。

于 2010-01-29T17:59:24.790 回答
0

我会从容易接近 100% 的某些匹配开始并首先处理它们，所以现在你有一个需要修复的 200 个列表。

对于剩余的行，您可以使用贝叶斯定理的简化版本。

对于每个不匹配的行，假设数据包含以特定概率发生的特定更改，计算它与数据集中每一行匹配的可能性。例如，一个人以 0.1% 的概率更改姓氏（可能还取决于性别），以 0.01% 的概率更改自己的名字，并且以 0.2% 的概率出现一个拼写错误（使用Levenshtein 的距离来计算拼写错误的数量）。其他领域也以一定的概率发生变化。对于每一行，考虑所有已更改的字段，计算该行匹配的可能性。然后选择最有可能成为匹配的那个。

For example a row with only a small typo in one field but equal on all others would have a 0.2% chance of a match, whereas rows which differs in many fields might have only a 0.0000001% chance. So you pick the row with the small typo.

于 2010-01-29T18:01:42.103 回答
-5

正则表达式是你所需要的，为什么要重新发明轮子？

于 2010-01-29T17:47:42.923 回答