判断一个商名是否与另一个非常相似 - Python
我正在处理一个包含很多商家的大数据库。
我想比较两个商家的名字，看看它们是否相似，以判断它们可能是重复的。
下面是一组商家名字，它们应该被测试为有很高的重复可能性，请问有什么好的方法来进行这个比较呢？
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
10 个回答
有一个很棒的库可以用来在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，它也支持模糊搜索。
我想给这个很棒的被接受的答案添加一些例子。测试是在 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 字符串，下面的代码可以替代使用 (来源, 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），并使用一些标记数据训练一个二分类模型，这样在给定多个得分的情况下，它就能判断候选对是否匹配。更多内容可以在同一篇博客文章中找到。
我最近做过类似的事情，不过我是在数据库中把新数据和已有的名字进行匹配，而不是在同一组数据中寻找重复项。名字匹配其实是一个研究得很透彻的任务，涉及的因素比你想象的要复杂得多。
首先，我建议你看看一篇论文，如何玩“名字游戏”：比较不同启发式方法的专利检索，作者是Raffo和Lhuillery。你可以在这里找到发表的版本，PDF版本可以在这里免费下载。作者对几种不同的匹配策略进行了很好的总结，他们把这个过程分为三个阶段：解析、匹配和过滤。
解析阶段就是对数据进行各种清理。比如：
- 统一字母大小写（例如，全部小写）
- 统一标点符号（例如，逗号后面必须有空格）
- 统一空格（例如，把连续的空格变成一个空格）
- 统一带重音的特殊字符（例如，把带重音的字母转换成ASCII字符）
- 统一法律控制术语（例如，把“Co.”转换成“Company”）
在我的案例中，我把所有字母都变成小写，把所有标点符号替换为空格，把带重音的字符换成不带重音的字符，去掉了其他特殊字符，并且根据一个列表去掉了名字开头和结尾的法律控制术语。
匹配阶段就是比较解析后的名字。这可以是简单的字符串匹配、编辑距离、Soundex或Metaphone，或者比较名字中单词的集合，甚至是比较字母集合或n-gram（长度为n的字母序列）。n-gram方法对于名字来说非常有效，因为它忽略了单词的顺序，这样在处理“examples的部门”和“部门的examples”时就会更容易。实际上，使用简单的Jaccard指数比较二元组（2-gram，即字符对）是非常有效的。与其他一些建议相比，Levenshtein距离在名字匹配方面效果较差。
在我的案例中，我分两步进行匹配，首先比较解析后的名字是否相等，然后对剩下的名字使用Jaccard指数来比较二元组。我并没有计算所有名字对的Jaccard指数，而是先设定了一个最大可能值，如果这个值足够高，才会计算Jaccard指数。大多数名字对之间的相似度还是不够，因此没有匹配成功，但这样大大减少了需要比较的次数。
过滤阶段是利用辅助数据来排除解析和匹配阶段的误匹配。一个简单的例子是检查匹配的名字是否对应于不同城市的公司，从而确认它们是不同的公司。这个例子可以在匹配之前作为一种预过滤来使用。更复杂或耗时的检查可以在之后进行。
我没有做太多的过滤。我只检查了公司的国家是否相同，仅此而已。数据中实际上没有太多可能性，时间限制也让我无法进行广泛的数据搜索来增强过滤，反正后面还有手动检查的计划。