logo标签列表

大量联系人的数据去重算法

algorithmduplicatesfuzzy-logicrecord-linkage
7
我正在开发一个应用程序，它必须能够在存储在SQL Server数据库中的数十万个联系人信息中查找和合并重复项。我必须比较表中的所有列，每个列都有一个权重值。比较必须基于权重值进行。根据比较结果和等价度，我必须决定自动合并联系人还是请求用户注意。我知道有许多模糊逻辑算法可用于去重。
请参阅http://www.melissadata.com/中的N-gram或Q-gram算法。这种算法对于大型数据集是否可行？如果不行，可以指导我使用哪些算法或从哪里开始吗？
以下是我想要实现的示例：
Gonzales = Gonzalez (two different spelling of different name)
Smith = Smyth (Phonetic sound the same)
123 Main st = 123 Main street (abbrevation)
Bob Smith = Robert Smith (synonym)
我需要执行相似度比较。例如，如果两个人拥有相同的电子邮件地址并且姓名类似于“Pravin”和“Praveen”，我必须能够找到这些记录。 - Shankar
在我的情况下，史密斯先生和史密斯也可能是重复的。 - Shankar
数据是否有结构化的方式：名字：Bob，姓氏：Smith，地址：123 Main Street，电子邮件：bob.smith@stackoverflow.com？还是只是一行文本：“Bob Smith，123 Main Street，bob.smith@stackoverflow.com”？ - Asaf
是的，正如指定的那样，数据是一个 SQL 表格，格式为（名字，姓氏，电子邮件，电话等...） - Shankar
3个回答
6
这整个研究领域通常被称为记录链接（具有讽刺意味的是，它有大约十几个重复的名称）。有很多工具可以让您配置特定数据的匹配项，处理数据并为您输出重复项。如果您回答一些关于潜在匹配正确性的问题，有些工具甚至会为您创建匹配项。
Q / N-gram比较（和索引）是解决此问题的一种可能方法，但还有其他许多方法。您很快就会发现，不同类型的比较器适用于不同类型的数据。我自己没有尝试过Q-gram索引，但该领域的研究人员告诉我它相对较慢。
至于与语音键函数（例如Soundex或Metaphone等）进行比较，只适用于您拥有小文本字段的情况，例如单独的名字字段，姓氏字段，中间名字段等。即使在这种情况下，这些功能也倾向于相当粗略。请注意Soundex。它不仅非常粗糙，将非常不同的名称转换为相同的键，而且还错过了一些应该被视为相同的类似名称。Metaphone要好得多。
维基百科的记录链接页面曾经有一个工具列表，但编辑们已将其删除。我编写了一个名为Duke的开源工具来解决这类问题。它具有遗传算法，可以帮助您创建配置，或者您可以手动编写配置。还有其他工具可用。
我建议您使用已经存在的工具，而不是试图从头开始解决这个问题。
2
我认为去重名字的最佳选择是使用音标编码器。 音标编码器能够去重同一名称的不同拼写。以下是一些常见名称的示例：
分组：Kathryn 名字：[Kathryn，Katharine，Katherin，Katherynn，Kathrynn，Katherynne，Kathrynne，Catherine，Cathryn，Catharine，Catherin，Catherynn，Cathrynn，Catherynne，Cathrynne] 分组：Assaf 名字：[Assaf，Asaf] 分组：Megan 名字：[Megan，Meagan，Meghan，Meaghan] 分组：Allison 名字：[Allison，Alyson，Allyson，Alison，Allisyn] ============================================================== 语音编码器：Caverphone2 ---- 名字分组：Kathryn ---- 编码后的名字：{KTRN111111=16} ---- 名字分组：Assaf ---- 编码后的名字：{ASF1111111=3} ---- 名字分组：Megan ---- 编码后的名字：{MKN1111111=5} ---- 名字分组：Allison ---- 编码后的名字：{ALSN111111=6} ============================================================== 语音编码器：DoubleMetaphone ---- 名字分组：Kathryn ---- 编码后的名字：{K0RN=16} ---- 名字分组：Assaf ---- 编码后的名字：{ASF=3} ---- 名字分组：Megan ---- 编码后的名字：{MKN=5} ---- 名字分组：Allison ---- 编码后的名字：{ALSN=6} ============================================================== 语音编码器：Nysiis ---- 名字分组：Kathryn ---- 编码后的名字：{CATRYN=7，CATARA=6，CATARY=5} ---- 名字分组：Assaf ---- 编码后的名字：{ASAF=3} ---- 名字分组：Megan ---- 编码后的名字：{MAGAN=5} ---- 名字分组：Allison ---- 编码后的名字：{ALASAN=3，ALYSAN=3，ALASYN=2} ============================================================== 语音编码器：Soundex ---- 名字分组：Kathryn ---- 编码后的名字：{K365=8，C365=9} ---- 名字分组：Assaf ---- 编码后的名字：{A210=3} ---- 名字分组：Megan ---- 编码后的名字：{M250=5} ---- 名字分组：Allison ---- 编码后的名字：{A425=6} ============================================================== 语音编码器：RefinedSoundex ---- 名字分组：Kathryn ---- 编码后的名字：{C30609080=5，K3060908=5，K30609080=4，C3060908=5} ---- 名字分组：Assaf ---- 编码后的名字：{A0302=3} ---- 名字分组：Megan ---- 编码后的名字：{M80408=5} ---- 名字分组：Allison ---- 编码后的名字：{A070308=6} ==============================================================
在这个例子中，您可以看到对于Caverphone和DoubleMetaphone，所有的姓名都被编码成了相同的字符串。你应该根据你的数据选择合适的编码器，使用哪种编码器取决于姓名所属的语言和词源（例如英文名、德文名等）。
“Mr John”和“John”算作相同的字符串吗？我认为用语音算法时不算。而且我不仅要比较姓名，还要比较表格中的所有列，每一列都有一个权重值。根据比较结果，我需要决定是否自动合并联系人或请求用户注意。 - Shankar
1
当比较名字时，您并不真正关心称号。只需删除任何发现的称号即可。没有必要编写算法来执行此操作。从姓名开头删除“先生”、“夫人”、“女士”、“工程师”、“博士”、“教授”或其他您知道的常见称号。 - Asaf
1
如果你交换名字，音标相似度匹配就会失败。将“Mark Smith”写成“Smith, Mark”是非常常见的。你必须使用基于令牌的匹配。 - alzaimar
我编辑了我的问题。基于令牌的匹配是否适用于我指定的所有情况？ - Shankar
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接