复杂记录的重叠/相似性检测

Question

我正在从事一个涉及大量字段(大约15-20个)的记录的项目，我正在设法找到一种实现去重复的好方法。从本质上说，这些记录是人，还有一些额外的数据。例如，这些记录可能包括诸如姓名、姓氏、邮政地址、电子邮件地址等个人信息，但并非所有记录都有相同数量的数据。

目前，记录存储在关系数据库管理系统(MySQL)中，我希望在插入时检测副本，并将其插入，但标记为重复。它需要是快速的，因为我需要提供反馈，如果它是一个重复或不实时。数据集很大(数百万条记录)。

我考虑了以下选项，但我不确定哪些是最好的/如果它们是更好的选择：

• 使用MySQL内置的全文搜索和模糊搜索。这方面的主要问题是速度慢，只有最新版本支持使用InnoDB的全文索引(alternative engine是MyISAM，它不是很好，关键是不支持事务)，而模糊搜索本身并不是最好的相似性检测方法。
• 使用simhash或类似的。问题是，我也希望能够检测到同义词，但我看不出sim散列是如何处理的。例如，地址可能是：“某些道路”或“某些道路”。名字可能是："Mike“或"Michael”
• 使用Apache导数(elasticsearch/solr/etc)索引数据，并执行可能返回多个结果的查询。

在使用Apache方面，我一直在阅读有关相似性检测的文章，并使用余弦相似度从Lucene存储的术语频率向量生成一个从0到1的值。我可以将此应用于lucene查询的结果，并检查结果是否超过某个阈值。我担心的是，余弦相似度对于我存储的数据类型有多大的相关性，也就是说，与计算大型文本文档比较的余弦相似性相比，具有单个或少量单词的一些字段。

基本上，我想知道什么是去复制这类数据的最佳方法(或者将其作为替代，检测与此类数据的相似之处)？

Answer 1

没有消除复制的银弹。您应该首先关注规范化(从模式意义上来说，而不是从3NF)和标准化。这给了你一些公平的竞争环境，从这里开始进行比较。

要实现这一点，您需要应用适用于每种类型数据的标准化技术。与命名标准化相比，地址数据标准化是一个完全不同的问题域。这些数据标准化问题领域大多过于复杂，无法自行解决。考虑购买第三方软件进行邮政地址验证和标准化，以及一个名称标准化。

对于诸如电子邮件地址或电话号码之类的东西，您可能可以使用自己的方式，因为与之相比，它们是相对直接的。

一旦数据组件标准化，那么您就可以担心什么更好了:模糊匹配、Levenshtein距离或余弦相似性(等等)。

最好考虑像子元素一样进行匹配，而不是把记录作为一个整体。然后看看有多少子元素是合理匹配的。两个相同的名字与不同的电子邮件地址和邮寄地址是一个非常弱的匹配。两个几乎相同的名字和几乎相同的邮件地址，其中一条记录丢失了电子邮件地址，这可能是一个相当强的匹配。

Answer 2

对于许多去重复技术来说，正如Joel所指出的，数据标准化非常重要。但是如果你使用minhash的话，你可以不用它就能过日子。

您仍然希望尽可能地对数据进行规范化:例如大小写和空格规范化，忽略地址中的标点符号等等。如果您知道同义词组，甚至可以将同义词标准化；因此，“Saint Street”变成了"mt st Helens st“(引入这样的歧义通常不会损害您结果的准确性，但它可以提高记忆力)。

姓名和地址仍有可能不同，拼写错误，排序可能发生变化，并可能包括额外的项目，如中间名称，或不同的区域名称。这不一定是问题。

Min散列根据特性生成每个记录的多个散列。在许多实现中，人们只需将所有特性放入一个min散列生成器中，就可以得到50个散列；但在您的示例中，您可能希望将其拆分。取所有的名称字段，为每个字段生成7个字符的小块，并将这些块扔到一个散列生成器中，该生成器将产生5个散列。获取所有邮政/物理地址字段，并使用另一个min散列生成器执行同样的操作，该生成器将产生15个散列。从它自己的电子邮件地址派生出3个散列。诸若此类。

您为每种类型的信息保留的散列数可以根据该信息对于确定重复信息的重要性以及字段未被填充的可能性进行调整。最可靠的数据应该分配给它最多的散列。

因此，找到接近重复的东西是相当简单的。它比simhash慢，可以占用一些内存，因为它必须筛选大量的结果，计算每个结果的共享散列数。在最坏的情况下，可以从记录中非常通用的部分中选择几个minhashes，例如“@gmail”。在电子邮件地址，并可能存在于数十万甚至数百万其他记录。但最美妙的是，它让你找到的结果，不只是4%或5%的不同，而是20%，40%，或多少你喜欢，真的。

(您可以使用与同义词替换相同的技术来克服这些“泛型”minhashes，并将非常常见的泛型字符串(如"@gmail.com“)替换为较短的编码占位符，如"@G!”。这比你的7个字的瓦要短，所以它永远不会单独形成一块瓦。)

Min散列上有一些变体，它们通过减少哈希来表示相同的数据来提高结果(请参阅https://stackoverflow.com/questions/27712472/choosing-between-simhash-and-minhash-for-a-production-system)，但是如果每个记录的大小都很小，这可能不会带来很大的好处。您可能已经降低到每记录30或40散列(32位哈希可能就足够了)。如果您还没有缓解“泛型minhashes”问题，那么局部性敏感散列(LSH)会有很大帮助；尽管这会降低相似度估计的精度。

Answer 3

使电子邮件地址作为主键，始终是唯一的电子邮件地址。这样多余的数据就不会存在了。

否则，如果您有此人的地址和姓名，则可以使用这两种方式检查副本。