Выясните, является ли название компании очень похожим на другое - Python

Я работаю с большой базой данных предприятий.

Я хотел бы иметь возможность сравнить два названия компаний по сходству, чтобы увидеть, могут ли они быть дубликатами.

Ниже приведен список фирменных наименований, которые должны проверяться как имеющие высокую вероятность дублирования, каков хороший способ для этого?

Джордж Вашингтон Мидл Шл
Школа Джорджа Вашингтона

Santa Fe East Inc
Восточный Санта-Фе

Чопт Креатив Салат Ко
Чопт Креатив Салат Компания

Пицца Мэнни и Ольги
Пицца Мэнни и Ольги

Ray's Hell Burger тоже
Ray's Hell Burgers

Эль Соль
Эль Соль де Америка

Олни Театральный Центр Искусств
Олни Театр

21 M Lounge
21M Lounge

Холидей Инн Отель Вашингтон
Холидей Инн Вашингтон-Джорджтаун

Residence Inn Washington,DC/ Дюпон Серкл
Резиденция Инн Марриотт Дюпон Серкл

Бутерброды Джимми Джона для гурманов
Джимми Джона

Omni Shoreham Hotel в Вашингтоне, округ Колумбия
Отель Омни Шорехам
Источник

10 ответов

Решение

Недавно я выполнил аналогичную задачу, хотя сопоставлял новые данные с существующими именами в базе данных, а не искал дубликаты в одном наборе. Сопоставление имен на самом деле является хорошо изученной задачей, с рядом факторов, которые не учитываются при сопоставлении общих строк.

Во-первых, я бы порекомендовал взглянуть на статью " Как играть в" игру имен ": патентный поиск, сравнивающий различные эвристики Раффо и Луилери". Опубликованная версия находится здесь, а PDF свободно доступен здесь. Авторы дают хорошее резюме, сравнивая ряд различных подходящих стратегий. Они рассматривают три этапа, которые они называют анализом, сопоставлением и фильтрацией.

Разбор состоит из применения различных методов очистки. Некоторые примеры:

  • Стандартизация букв (например, все строчные)
  • Стандартизация знаков препинания (например, запятые должны сопровождаться пробелами)
  • Стандартизация пробелов (например, преобразование всех пробелов в отдельные пробелы)
  • Стандартизация акцентированных и специальных символов (например, конвертирование акцентированных букв в эквиваленты ASCII)
  • Стандартизация терминов правового контроля (например, преобразование "Ко" в "Компания")

В моем случае я сложил все буквы в нижний регистр, заменил все знаки пунктуации пробелами, заменил акцентированные символы на неакцентированные, удалил все другие специальные символы и удалил юридические термины управления из начала и конца имен, следующих за списком.

Сопоставление - это сравнение проанализированных имен. Это может быть простое сопоставление строк, расстояние редактирования, Soundex или Metaphone, сравнение наборов слов, составляющих имена, или сравнение наборов букв или n- грамм (последовательностей букв длины n). Подход n-gram на самом деле довольно хорош для имен, поскольку он игнорирует порядок слов, что очень помогает в таких вещах, как "отдел примеров" или "отдел примеров". На самом деле, сравнение биграмм (2 грамма, пары символов) с использованием чего-то простого, например индекса Жакара, очень эффективно. В отличие от нескольких других предположений, расстояние Левенштейна является одним из худших подходов, когда речь идет о сопоставлении имен.

В моем случае я выполнил сопоставление в два этапа: сначала сравнил проанализированные имена на равенство, а затем использовал индекс Жакара для наборов биграмм на оставшихся. Вместо того, чтобы фактически вычислять все значения индекса Жакара для всех пар имен, я сначала наложил ограничение на максимально возможное значение индекса Жакара для двух наборов данного размера, и вычислял индекс Жакара только в том случае, если эта верхняя граница была достаточно высокой, чтобы потенциально быть полезным. Большинство пар имен были все еще достаточно различны, чтобы не совпадать, но это значительно сократило количество сравнений.

Фильтрация - это использование вспомогательных данных для отклонения ложных срабатываний на этапах анализа и сопоставления. Простая версия заключается в том, чтобы увидеть, соответствуют ли совпадающие названия предприятиям в разных городах и, следовательно, различным предприятиям. Этот пример может быть применен перед сопоставлением, как своего рода предварительная фильтрация. Более сложные или трудоемкие проверки могут быть применены впоследствии.

Я не делал много фильтрации. Я проверил страны для фирм, чтобы видеть, были ли они одинаковыми, и это было этим. В действительности не было так много возможностей в данных, некоторые ограничения по времени исключали какой-либо расширенный поиск дополнительных данных для усиления фильтрации, и в любом случае планировалась ручная проверка.

Источник

Я хотел бы добавить несколько примеров к превосходному принятому ответу. Протестировано в Python 2.7.

анализ

Давайте использовать это странное имя в качестве примера.

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

Мы можем начать с удаления условий правового контроля (здесь ООО). Для этого есть потрясающая библиотека Python cleanco, которая делает именно это:

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

Удалить все знаки препинания:

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

(для строк Юникода вместо этого работает следующий код ( 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']

Я не рассматриваю акцентированные и специальные символы здесь (улучшения приветствуются).

согласование

Теперь, когда мы сопоставили все названия компаний с токенами, мы хотим найти соответствующие пары. Возможно, сходство Жакара (или Яро-Винклера) лучше, чем Левенштейна для этой задачи, но все еще недостаточно хорошо. Причина в том, что он не учитывает важность слов в имени (как это делает 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

Используя это, вы можете сопоставить имена со сходством, превышающим определенный порог. В качестве более сложного подхода вы также можете взять несколько баллов (скажем, этот балл уникальности, Джакарда и Яро-Винклера) и обучить бинарную модель классификации, используя некоторые помеченные данные, которые при заданном количестве баллов будут выводить, если пара кандидатов это совпадение или нет. Подробнее об этом можно узнать из того же поста в блоге.

Источник

Существует отличная библиотека для поиска похожих / нечетких строк для python: fuzzywuzzy. Это хорошая библиотека-обертка после упомянутого измерения расстояния Левенштейна. Вот как можно проанализировать ваши имена:

#!/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

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])
Источник

Это немного обновление комментария Денниса. Этот ответ был действительно полезен, как и ссылки, которые он разместил, но я не мог заставить их работать сразу. Попробовав поиск 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

Источник

Я искал "расстояние редактирования питона", и эта библиотека стала первым результатом: http://www.mindrot.org/projects/py-editdist/

Другая библиотека Python, которая выполняет ту же работу, находится здесь: http://pypi.python.org/pypi/python-Levenshtein/

Расстояние редактирования представляет собой объем работы, которую необходимо выполнить для преобразования одной строки в другую, выполнив только простые, обычно символьные, операции редактирования. Каждая операция (подстановка, удаление, вставка; иногда транспонирование) имеет связанную стоимость, и минимальное расстояние редактирования между двумя строками является мерой того, насколько они различны.

В вашем конкретном случае вам может потребоваться упорядочить строки так, чтобы вы находили расстояние от более длинного до более короткого и меньше штрафовали за удаление символов (поскольку я вижу, что во многих случаях одна из строк является почти подстрокой другой), Таким образом, удаление не должно быть оштрафовано много.

Вы также можете использовать этот пример кода: http://norvig.com/spell-correct.html

Источник

Попробуйте использовать библиотеку Diff-Match-Patch. Вас заинтересует процесс Diff - применение diff к вашему тексту может дать вам хорошее представление о различиях, а также их программное представление.

Источник

То, что вы можете сделать, это разделить слова пробелами, запятыми и т. Д., А затем подсчитать количество слов, которые у него есть общего с другим именем, и добавить несколько слов, прежде чем оно будет считаться "похожим".

Другой способ - сделать то же самое, но взять слова и склеить их для каждого символа. Затем для каждого слова нужно сравнить, если буквы найдены в одинаковом порядке (с обеих сторон) для х символов (или процентов), то вы можете сказать, что слово тоже похоже.

Пример: у вас есть площадь и площадь

Затем вы проверяете по символам и обнаруживаете, что sqre все в квадрате и в том же порядке, тогда это похожее слово.

Источник

Алгоритмы, основанные на расстоянии Левенштейна, хороши (не идеальны), но их главный недостаток в том, что они очень медленны для каждого сравнения и касаются того факта, что вам придется сравнивать каждую возможную комбинацию.

Другим способом решения проблемы может быть использование вложения или пакета слов для преобразования названия каждой компании (после некоторой очистки и предварительной обработки) в вектор чисел. И после этого вы применяете неконтролируемый или контролируемый метод ОД в зависимости от того, что доступно.

Источник

Я создал matchkraft (https://github.com/MatchKraft/matchkraft-python). Он работает поверх нечеткого-нечеткого, и вы можете нечеткое сопоставление названий компаний в одном списке.

Это очень простой в использовании. Вот пример на Python:

      from matchkraft import MatchKraft

mk = MatchKraft('<YOUR API TOKEN HERE>')

job_id = mk.highlight_duplicates(name='Stackoverflow Job',
primary_list=[
    'George Washington Middle Schl',
    'George Washington School',
    'Santa Fe East Inc',
    'Santa Fe East',
    'Rays Hell Burger Too',
    'El Sol de America',
    'microsoft',
    'Olney Theatre',
    'El Sol'
 ]
)

print (job_id)


mk.execute_job(job_id=job_id)


job  = mk.get_job_information(job_id=job_id)
print (job.status)

while (job.status!='Completed'):
   print (job.status)
   time.sleep(10)
   job  = mk.get_job_information(job_id=job_id)


results = mk.get_results_information(job_id=job_id)
if isinstance(results, list):
  for r in results:
      print(r.master_record + ' --> ' + r.match_record)
 else:
     print("No Results Found")
Источник
Другие вопросы по тегам