找出一个业务名称是否与另一个名称非常相似-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

您可以使用Levenshtein距离，它可以用来测量两个序列之间的差异（基本上是编辑距离）。

Python中的Levenshtein距离

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 2

我最近做了一个类似的任务，虽然我正在将新数据与数据库中的现有名称进行匹配，而不是在一个集合中查找重复项。名称匹配实际上是一项研究得很好的任务，有很多因素超出了匹配泛型字符串的考虑范围。

首先，我建议看一篇论文，如何玩“名字游戏”：比较rafo和lhuilley的不同启发式方法的专利检索。发布的版本是here，PDF是免费的here。作者提供了一个很好的总结，比较了许多不同的匹配策略。它们考虑三个阶段，称为解析、匹配和过滤。

解析包括应用各种清理技术。一些例子：

• 标准化字体（例如，所有小写字母）
• 标点符号标准化（例如逗号后面必须有空格）
• 标准化空白（例如，将所有空白行转换为单个空格）
• 标准化重音字符和特殊字符（例如，将重音字母转换为等效的ASCII字符）
• 规范法律控制条款（例如，将“公司”转换为“公司”）

在我的例子中，我将所有字母折叠为小写，将所有标点符号替换为空白，将重音字符替换为非重音对应字符，删除所有其他特殊字符，并从列表后面名称的开头和结尾删除法律控制术语。

匹配是对已解析名称的比较。这可以是简单的字符串匹配、编辑距离、Soundex或Metaphone、组成名称的单词集的比较、字母集或n-grams（长度为n的字母序列）的比较。gram方法实际上对名字很好，因为它忽略了单词的顺序，对“示例部门”和“示例部门”有很大帮助。事实上，使用类似Jaccard index的简单方法比较bigram（2-grams，字符对）非常有效。与其他一些建议相反，在名称匹配方面，Levenshtein距离是较差的方法之一。

在我的例子中，我分两步进行匹配，首先比较分析的名称是否相等，然后使用Jaccard索引对其余的bigram集进行匹配。我没有实际计算所有名称对的所有Jaccard索引值，而是首先对给定大小的两组Jaccard索引的最大可能值设置一个界限，并且仅在该上限足够高到可能有用时计算Jaccard索引。大多数的名字对仍然很不相似，以至于它们不匹配，但这大大减少了进行比较的次数。

过滤是使用辅助数据从解析和匹配阶段拒绝误报。一个简单的版本是，看看匹配的名字是否对应于不同城市的企业，从而对应于不同的企业。这个例子可以在匹配之前应用，作为一种预过滤。之后可能会进行更复杂或耗时的检查。

我没怎么过滤。我检查了各国的公司，看它们是否相同，就是这样。数据中并没有那么多的可能性，一些时间限制排除了对额外数据的广泛搜索以增强过滤，而且无论如何，还有一个手动检查计划。

Answer 3

我想在优秀的公认答案中加上一些例子。在Python2.7中测试。

解析

让我们以这个奇怪的名字为例。

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

我们可以从删除法律控制条款（此处为有限责任公司）开始。要做到这一点，有一个很棒的cleancoPython库，它确实做到了：

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这样的公司出现问题，因为On是一个停止词，所以与Mars不正确匹配。

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那样）。因此，像“公司”这样的常用词对得分的影响，与可能唯一标识公司名称的词一样大。

为了改进这一点，您可以使用本awesome series of posts（不是我的）中建议的名称相似性技巧。下面是一个代码示例：

# 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）并使用一些标记数据训练一个二元分类模型，在给定分数的情况下，如果候选对匹配与否，该模型将输出。更多关于这个的信息可以在同一篇博文中找到。