寻找近似重复记录的技术

Question

我试图清理一个数据库，多年来它已经积累了许多重复记录，名称略有不同。例如，在公司表中，存在像"Some Company Limited"和"SOME COMPANY LTD!"这样的名称。

我的计划是将问题表导出到R中，将名称转换为小写，替换常见的同义词（如"limited"->"ltd"），去除非字母字符，然后使用agrep来查看相似之处。

我的第一个问题是，agrep只接受单个模式匹配，循环每个公司名称以匹配其他名称很慢。（需要清理的一些表可能有数万甚至数十万个名称要检查。）

我简要地看了看tm包（JSS article），它似乎非常强大，但更适用于分析大块文本，而不仅仅是名称。

我有几个相关的问题：

1. tm包是否适用于这种任务？

2. 是否有比agrep更快的替代方案？（该函数使用莱文斯坦编辑距离，据说很慢。）

3. 除了agrep和tm之外，R中是否有其他合适的工具？

4. 我应该在R中做这件事，还是直接在数据库中处理？（它是一个Access数据库，所以如果可能的话，我想避免触及它。）

- Richie Cotton

---

与如何测量字符串相似性有关。 - Joshua Ulrich

Answer 1

如果您只是在处理一些相对规范的小批次数据，那么RecordLinkage包中的compare.linkage()或compare.dedup()函数应该是一个很好的起点。但是，如果您有大量数据需要处理，那么您可能需要进行更多的调整。

我使用RecordLinkage中的jarowinkler()、levenshteinSim()和soundex()函数编写自己的函数，并使用自己的加权方案（另外，目前您无法在RecordLinkage中使用soundex()来处理大型数据集）。

如果我想要匹配两个名称列表（"记录链接"），那么我通常会将它们都转换为小写并删除所有标点符号。为了解决"Limited"与"LTD"之间的问题，我通常创建另一个向量，其中包含每个列表的第一个单词，这样可以额外加权第一个单词。如果我认为一个列表可能包含缩略语（比如ATT或IBM），那么我会对另一个列表进行缩略词处理。对于每个列表，我最终得到了一个字符串数据框，我希望进行比较，并将其作为单独的表格写入MySQL数据库中。

为了避免出现太多候选项，我使用LEFT OUTER JOIN将这两个表格连接在一起，并使用两个列表之间必须匹配的内容（也许是每个列表中的前三个字母或缩略词中的前三个字母和第一个单词）进行匹配。然后，我使用上述函数计算匹配分数。

你仍然需要进行大量的手动检查，但是可以按照分数进行排序，以快速排除不匹配项。

- Richard Herron

---

对于解释如何归一化文本的方法予以赞赏，这个“第一步”经常被忽视。使用tolower()和gsub()函数来实现。我也做了很类似的事情，通过查看summary(as.factor(my_vector))来确认不匹配的内容。有时候解决问题非常简单，用代码写出来反而比试图使用正则表达式更加简洁明了。 - Brandon Bertelsen

@AndrewMedico 是的，看起来这个包在CRAN上已经不再活跃了。你可以从存档中获取过去的版本。我有义务成为这个包的维护者吗？ - Richard Herron

@RichardHerron 感谢您指出这些软件包，它们现在已经在CRAN上了。如果我只有数值列，并且它们由随机波动引起差异，我想在数值数据中查找匹配项，您有什么建议吗？ - Richi W

@Richard，这个包似乎不再在CRAN上了。你能否请查一下？谢谢！ - questionmark

@questionmark 你指的是哪个Richard（Richard还是RichardHerron）？以及是哪个包？我看到这个：https://cran.r-project.org/web/packages/RecordLinkage/index.html 已经在CRAN上了。 - Richi W

Answer 2

也许Google Refine可以帮助你。如果你有很多异常情况并且还不知道它们的全部，那么这个工具可能更适合你。

- Etienne Racine

---

我没有使用过Google Refine，但是我被它的视频所吸引。它似乎很擅长处理模糊匹配，最重要的是，它似乎可以保存底层代码，这样如果需要再次运行或者想在类似的数据上运行相同的算法时就可以使用了。 - Farrel

Answer 3

你正在进行的操作被称为记录链接，这是一个已经研究了几十年的广泛领域。幸运的是，有很多工具可以为此而制作。基本上，你可以将它们指向你的数据库，设置一些清理和比较器（如Levenshtein或Jaro-Winkler等），然后它们就会为你完成工作。

这些工具通常具有解决性能问题的功能，因此即使Levenshtein速度较慢，它们也可以快速运行，因为大多数记录对从未进行比较。

上面的维基百科链接中有许多可用的记录链接工具。我个人使用Java编写了一个名为Duke的工具，并且已经成功地使用它来完成了这项任务。如果你想要一个大而昂贵的工具，可以购买主数据管理工具。

- larsga

Answer 4

在您的情况下，可能会使用编辑距离计算等方法，但如果您需要在基于较大文本的文档中查找近似重复项，则可以尝试使用http://www.softcorporation.com/products/neardup/。

- vadim