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

Ответ 1

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

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

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

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

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

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

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

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

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

Ответ 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'

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

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

Ответ 3

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

Расстояние Левенштейна в 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])

Ответ 4

Существует большая библиотека для поиска похожих/нечетких строк для 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 Pizza",
     "Manny & Olga Pizza"),

    ("Ray Hell Burger Too",
    "Ray 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 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 Pizza", "Manny & Olga Pizza")
>>>  94 :: ("Ray Hell Burger Too", "Ray 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 Gourmet Sandwiches", "Jimmy John's")
>>> 100 :: ('Omni Shoreham Hotel at Washington D.C.', 'Omni Shoreham Hotel')

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

Ответ 5

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

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

Ex: у вас есть квадрат и квадрат

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

Ответ 6

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

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

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

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

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

Ответ 7

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