我正在处理一个庞大的商业数据库。
我希望能够比较两个商业名称的相似性,看看它们是否可能是重复的。
下面是一个商业名称列表,应该测试为具有很高的重复概率,什么是一个好的方法去做这件事?
George Washington Middle Schl George Washington School Santa Fe East Inc Santa Fe East Chop't Creative Salad Co Chop't Creative Salad Company Manny and Olga's Pizza Manny's & Olga's Pizza Ray's Hell Burger Too Ray's Hell Burgers El Sol El Sol de America Olney Theatre Center for the Arts Olney Theatre 21 M Lounge 21M Lounge Holiday Inn Hotel Washington Holiday Inn Washington-Georgetown Residence Inn Washington,DC/Dupont Circle Residence Inn Marriott Dupont Circle Jimmy John's Gourmet Sandwiches Jimmy John's Omni Shoreham Hotel at Washington D.C. Omni Shoreham Hotel
您可以使用Levenshtein距离,它可以用来测量两个序列之间的差异(基本上是编辑距离)。
Python中的Levenshtein距离
我最近做了一个类似的任务,虽然我正在将新数据与数据库中的现有名称进行匹配,而不是在一个集合中查找重复项。名称匹配实际上是一项研究得很好的任务,有很多因素超出了匹配泛型字符串的考虑范围。
首先,我建议看一篇论文,如何玩“名字游戏”:比较rafo和lhuilley的不同启发式方法的专利检索。发布的版本是here,PDF是免费的here。作者提供了一个很好的总结,比较了许多不同的匹配策略。它们考虑三个阶段,称为解析、匹配和过滤。
解析包括应用各种清理技术。一些例子:
在我的例子中,我将所有字母折叠为小写,将所有标点符号替换为空白,将重音字符替换为非重音对应字符,删除所有其他特殊字符,并从列表后面名称的开头和结尾删除法律控制术语。
匹配是对已解析名称的比较。这可以是简单的字符串匹配、编辑距离、Soundex或Metaphone、组成名称的单词集的比较、字母集或n-grams(长度为n的字母序列)的比较。gram方法实际上对名字很好,因为它忽略了单词的顺序,对“示例部门”和“示例部门”有很大帮助。事实上,使用类似Jaccard index的简单方法比较bigram(2-grams,字符对)非常有效。与其他一些建议相反,在名称匹配方面,Levenshtein距离是较差的方法之一。
在我的例子中,我分两步进行匹配,首先比较分析的名称是否相等,然后使用Jaccard索引对其余的bigram集进行匹配。我没有实际计算所有名称对的所有Jaccard索引值,而是首先对给定大小的两组Jaccard索引的最大可能值设置一个界限,并且仅在该上限足够高到可能有用时计算Jaccard索引。大多数的名字对仍然很不相似,以至于它们不匹配,但这大大减少了进行比较的次数。
过滤是使用辅助数据从解析和匹配阶段拒绝误报。一个简单的版本是,看看匹配的名字是否对应于不同城市的企业,从而对应于不同的企业。这个例子可以在匹配之前应用,作为一种预过滤。之后可能会进行更复杂或耗时的检查。
我没怎么过滤。我检查了各国的公司,看它们是否相同,就是这样。数据中并没有那么多的可能性,一些时间限制排除了对额外数据的广泛搜索以增强过滤,而且无论如何,还有一个手动检查计划。
我想在优秀的公认答案中加上一些例子。在Python2.7中测试。
解析
让我们以这个奇怪的名字为例。
我们可以从删除法律控制条款(此处为有限责任公司)开始。要做到这一点,有一个很棒的cleancoPython库,它确实做到了:
删除所有标点:
(对于unicode字符串,以下代码可以工作(source,regex):
使用NLTK将名称拆分为标记:
小写所有标记:
删除停止语。请注意,这可能会导致像
On Mars
这样的公司出现问题,因为On
是一个停止词,所以与Mars
不正确匹配。我不包括重音和特殊字符在这里(改进欢迎)。
匹配
现在,当我们将所有公司名称映射到标记时,我们希望找到匹配的对。可以说,Jaccard(或Jaro Winkler)的相似性比Levenstein更好,但仍然不够好。原因是它没有考虑到名称中单词的重要性(就像TF-IDF那样)。因此,像“公司”这样的常用词对得分的影响,与可能唯一标识公司名称的词一样大。
为了改进这一点,您可以使用本awesome series of posts(不是我的)中建议的名称相似性技巧。下面是一个代码示例:
使用它,您可以匹配相似度超过特定阈值的名称。作为一种更复杂的方法,您还可以取几个分数(例如,这个唯一性分数,Jaccard和Jaro Winkler)并使用一些标记数据训练一个二元分类模型,在给定分数的情况下,如果候选对匹配与否,该模型将输出。更多关于这个的信息可以在同一篇博文中找到。
相关问题 更多 >
编程相关推荐