弄清楚企业名称是否与另一个企业名称非常相似 - Python

Question

我正在使用大型企业数据库.

我希望能够比较两个商业名称的相似性,看看它们是否可能是重复的.

下面是一个应该测试的企业名称列表,它们很可能是重复的,有什么好办法可以解决这个问题？

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

Answer 1

我最近做了类似的任务,虽然我将新数据与数据库中的现有名称进行匹配,而不是在一组中查找重复项.名称匹配实际上是一项经过充分研究的任务,除了您考虑匹配通用字符串之外,还有许多因素.

首先,我建议看一篇论文,如何玩"名称游戏":专利检索比较 Raffo和Lhuillery的不同启发式.已发布的版本在此处,PDF可在此处免费获取.作者提供了一个很好的总结,比较了许多不同的匹配策略.他们考虑三个阶段,他们称之为解析,匹配和过滤.

解析包括应用各种清洁技术.一些例子:

• 标准化字母(例如全小写)
• 标准化标点符号(例如,逗号必须后跟空格)
• 标准化空格(例如,将所有空白空间转换为单个空格)
• 标准化重音和特殊字符(例如,将重音字母转换为ASCII等效字符)
• 规范法律控制条款(例如,将"公司"转换为"公司")

在我的情况下,我将所有字母折叠为小写,用空格替换所有标点符号,用非重音符号替换重音字符,删除所有其他特殊字符,并从列表后面的名称的开头和结尾删除法律控制术语.

匹配是解析名称的比较.这可以是简单的字符串匹配,编辑距离,Soundex或Metaphone,比较组成名称的单词组,或比较字母组或n- gram(长度为n的字母序列).该ñ -gram方法实际上是相当不错的名字,因为它忽略了词序,帮助了很多的东西,如"的例子部门"与"例子部门".实际上,使用简单的Jaccard索引比较bigrams(2-gram,字符对)是非常有效的.与其他几个建议相反,Levenshtein距离是名称匹配方面较差的方法之一.

在我的例子中,我分两步进行匹配,首先比较解析后的名称是否相等,然后使用Jaccard索引来计算余下的bigrams集合.我没有实际计算所有名称对的所有Jaccard索引值,而是首先对两组给定大小的Jaccard索引的最大可能值进行约束,并且只有在该上限足够高时才计算Jaccard索引.可能有用.大多数名称对仍然不同,以至于它们不匹配,但它大大减少了比较的次数.

过滤是使用辅助数据来拒绝解析和匹配阶段的误报.一个简单的版本是查看匹配的名称是否与不同城市的企业相对应,从而与不同的企业相对应.该示例可以在匹配之前应用,作为一种预过滤.之后可能会应用更复杂或耗时的检查.

我没有做太多的过滤.我检查了各个公司的国家,看看它们是否相同,就是这样.数据中没有那么多的可能性,一些时间限制排除了对增加过滤的额外数据的广泛搜索,并且无论如何都计划进行人工检查.

Answer 2

我想在一些优秀的答案中添加一些例子.在Python 2.7中测试过.

解析

让我们用这个奇怪的名字作为例子.

name = "THE |  big,- Pharma: LLC"  # example of a company name

我们可以从删除法律控制条款(此处为LLC)开始.要做到这一点,有一个很棒的cleanco Python库,它正是这样做的:

from cleanco import cleanco
name = cleanco(name).clean_name()  # 'THE | big,- Pharma'

删除所有标点符号:

name = name.translate(None, string.punctuation)  # 'THE  big Pharma'

(对于unicode字符串,以下代码可以使用(source,regex):

import regex
name = regex.sub(ur"[[:punct:]]+", "", name)  # u'THE  big Pharma'

使用NLTK将名称拆分为令牌:

import nltk
tokens = nltk.word_tokenize(name)  # ['THE', 'big', 'Pharma']

小写所有标记:

tokens = [t.lower() for t in tokens]  # ['the', 'big', 'pharma']

删除停用词.请注意,它可能会导致公司出现问题,例如On Mars错误匹配Mars,因为它On是一个停用词.

from nltk.corpus import stopwords
tokens = [t for t in tokens if t not in stopwords.words('english')]  # ['big', 'pharma']

我这里不包括重音和特殊字符(欢迎改进).

匹配

现在,当我们将所有公司名称映射到令牌时,我们希望找到匹配对.可以说,Jaccard(或Jaro-Winkler)的相似性比Levenstein更好,但仍然不够好.原因是它没有考虑名称中单词的重要性(如TF-IDF那样).因此,像"公司"这样的常用词会影响得分,就像可能唯一识别公司名称的词一样.

为了改进这一点,您可以使用在这个令人敬畏的系列帖子(不是我的)中建议的名称相似性技巧.这是一个代码示例:

# token2frequency is just a word counter of all words in all names
# in the dataset
def sequence_uniqueness(seq, token2frequency):
    return sum(1/token2frequency(t)**0.5 for t in seq)

def name_similarity(a, b, token2frequency):
    a_tokens = set(a.split())
    b_tokens = set(b.split())
    a_uniq = sequence_uniqueness(a_tokens)
    b_uniq = sequence_uniqueness(b_tokens)
    return sequence_uniqueness(a.intersection(b))/(a_uniq * b_uniq) ** 0.5

使用它,您可以匹配具有超过特定阈值的相似性的名称.作为一种更复杂的方法,您还可以使用几个分数(例如,这个唯一性分数,Jaccard和Jaro-Winkler)并使用一些标记数据训练二元分类模型,如果候选对,将给出多个分数输出是不匹配.有关这方面的更多信息可以在同一篇博文中找到.

Answer 3

您可以使用Levenshtein距离,该距离可用于测量两个序列之间的差异(基本上是编辑距离).

Levenshtein在Python中的距离

def levenshtein_distance(a,b):
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a,b = b,a
        n,m = m,n

    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)

    return current[n]

if __name__=="__main__":
    from sys import argv
    print levenshtein_distance(argv[1],argv[2])

Answer 4

有很好的库可以搜索python:fuzzywuzzy的类似/模糊字符串.在提到的Levenshtein距离测量时,这是一个很好的包装库.在这里如何分析您的名字:

#!/usr/bin/env python

from fuzzywuzzy import fuzz

names = [
    ("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"),
]

if __name__ == '__main__':
    for pair in names:
        print "{:>3} :: {}".format(fuzz.partial_ratio(*pair), pair)

>>>  79 :: ('George Washington Middle Schl', 'George Washington School')
>>> 100 :: ('Santa Fe East Inc', 'Santa Fe East')
>>> 100 :: ("Chop't Creative Salad Co", "Chop't Creative Salad Company")
>>>  86 :: ("Manny and Olga's Pizza", "Manny's & Olga's Pizza")
>>>  94 :: ("Ray's Hell Burger Too", "Ray's Hell Burgers")
>>> 100 :: ('El Sol', 'El Sol de America')
>>> 100 :: ('Olney Theatre Center for the Arts', 'Olney Theatre')
>>>  90 :: ('21 M Lounge', '21M Lounge')
>>>  79 :: ('Holiday Inn Hotel Washington', 'Holiday Inn Washington-Georgetown')
>>>  69 :: ('Residence Inn Washington,DC/Dupont Circle', 'Residence Inn Marriott Dupont Circle')
>>> 100 :: ("Jimmy John's Gourmet Sandwiches", "Jimmy John's")
>>> 100 :: ('Omni Shoreham Hotel at Washington D.C.', 'Omni Shoreham Hotel')

另一种解决此类问题的方法可能是Elasticsearch,它也支持模糊搜索.

Answer 5

这是对丹尼斯评论的一点更新。这个答案非常有帮助，他发布的链接也是如此，但我无法让它们立即工作。在尝试 Fuzzy Wuzzy 搜索后，我发现这给了我一组更好的答案。我有一个很大的商家列表，我只想将它们分组在一起。最终我将拥有一个可以用来尝试一些机器学习的桌子，但目前这需要付出很多努力。

我只需要稍微更新一下他的代码并添加一个函数来创建 tokens2Frequency 字典。原来的文章也没有这个，然后函数没有正确引用它。

import pandas as pd
from collections import Counter
from cleanco import cleanco
import regex
import nltk
from nltk.corpus import stopwords
nltk.download('stopwords')

# token2frequency is just a Counter of all words in all names
# in the dataset
def sequence_uniqueness(seq, token2frequency):
    return sum(1/token2frequency[t]**0.5 for t in seq)

def name_similarity(a, b, token2frequency):
    a_tokens = set(a)
    b_tokens = set(b)
    a_uniq = sequence_uniqueness(a, token2frequency)
    b_uniq = sequence_uniqueness(b, token2frequency)
    if a_uniq==0 or b_uniq == 0:
        return 0
    else:
        return sequence_uniqueness(a_tokens.intersection(b_tokens), token2frequency)/(a_uniq * b_uniq) ** 0.5

def parse_name(name):
    name = cleanco(name).clean_name()
    #name = name.translate(None, string.punctuation)
    name = regex.sub(r"[[:punct:]]+", "", name)
    tokens = nltk.word_tokenize(name) 
    tokens = [t.lower() for t in tokens]
    tokens = [t for t in tokens if t not in stopwords.words('english')] 
    return tokens

def build_token2frequency(names):
    alltokens = []
    for tokens in names.values():
        alltokens += tokens

    return Counter(alltokens)

with open('marchants.json') as merchantfile:
    merchants = pd.read_json(merchantfile)

merchants = merchants.unique()
parsed_names = {merchant:parse_name(merchant) for merchant in merchants}
token2frequency = build_token2frequency(parsed_names)

grouping = {}
for merchant, tokens in parsed_names.items():
    grouping[merchant] = {merchant2: name_similarity(tokens, tokens2, token2frequency) for merchant2, tokens2 in parsed_names.items()}

filtered_matches = {}
for merchant in pcard_merchants:
    filtered_matches[merchant] = {merchant1: ratio for merchant1, ratio in grouping[merchant].items() if ratio >0.3 }

这将为您提供最终的过滤名称列表以及它们匹配的其他名称。它的基本代码与另一篇文章相同，只是补充了一些缺失的部分。这也是在 Python 3.8 中运行的