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

Question

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

Чтобы привести пример, в названии Business Name имеется несколько записей для одной и той же компании. Для «Hugo Boss» включает в себя «Hugo Bos», «Huggo Boss», «Hugo Boss Ltd».

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

Знают ли люди об исходном коде такой/подобной реализации? Я рассмотрел алгоритм соответствия, однако они полагаются на предварительно вычисленный шаблон. Какой еще метод совпадения или методы машинного обучения можно использовать для разработки автоматизированного процесса, который бы очищал данные, т. Е. Сопоставлял бы все разные имена одному имени.

Любая помощь будет оценена по достоинству.

Answer 1

Другой вариант посмотреть на расстояния Левенштейна https://en.wikipedia.org/wiki/Levenshtein_distance

Это поможет вам в таких случаях, как Hugo Boss против Huggo Boss но не будет работать для Hugo Boss против Hugo Boss

Answer 2

Вы можете попробовать машину конечного состояния aho-corasick и увеличить ее с помощью подстановочного знака. Другим вариантом является дерево суффикса, то есть расстояние levensthein. Вы можете попробовать мою реализацию PHP aho-corasick @https://phpahocorasick.codeplex.com.

Answer 3

Это поле исследований называется «Согласование данных» или «Запись связи».

Существует very good survey book of techniques you can use by Peter Christen. Он также глубоко погружается в модели машинного обучения и как их улучшить с помощью базового подхода, такого как простые строки (как уже говорили другие ответы).

Чтобы дать вам начало, вы можете попытаться вычислить символы n-граммов ваших названий.

При п = 3 и Hugo Boss, вы получите

[hug, ugo, go , o b, bo, bos, oss] 

Теперь вы можете вычислить jaccard similarity между двумя наборами этих ngrams.

Вот, например, между Hugo Boss и Huggo Boss:

[hug, ugo, go , o b, bo, bos, oss] 
[hug, ugg, ggo, go , o b, bo, bos, oss] 
jaccard similarity: 0.6666666666666666 

Если вы не хотите, чтобы идти по пути реализации всех этих вещей самостоятельно, использовать Lucene. Это также очень быстро и хорошо масштабируется до миллиардов документов.

Answer 4

«Hugo Boss» включает в себя «Hugo Bos», «Huggo Boss», «Hugo Boss Ltd» .... Все вышесказанное будет иметь одинаковые значения soundex (фонетического алгоритма), за исключением последнего, LTD».

Вы можете сопоставить soundex с названиями компаний.Это должно работать над «Hugo Boss» «Hugo Bos» и «Huggo Boss». Однако «Hugo Boss Ltd» не будет соответствовать другой из-за LTD в конце. Этот метод хорошо работал для нечеткого соответствия, где я работаю, и результаты были полезны при сравнении между именами и фамилиями для установления личности.

Имейте в виду, что soundex не будет работать для таких вещей, как номера социального страхования. Он имеет более строгую область по сравнению с расстоянием, таким как расстояние редактирования.

Возможно, вы также можете удалить такие вещи, как «Ltd», «LLC», «Corp», которые являются общими для названий предприятий в вашем наборе данных. Это поможет создать структуру соответствия soundex, поскольку сокращает длину строк.

Кроме того, вы можете сравнить буквы ngrams, как рекомендовал thomas в своем ответе на запись, и это упростило бы количество ngrams для тестирования.

Вот алгоритм NYSIIS:

алгоритм, как описано в штата Нью-Йорк идентификации и разведки системы:

1. Translate first characters of name: MAC → MCC, KN → N, K → C, PH, PF → FF, SCH → SSS 
2. Translate last characters of name: EE → Y, IE → Y, DT, RT, RD, NT, ND → D 
3. First character of key = first character of name. 
4. Translate remaining characters by following rules, incrementing by one character each time: 
    1. EV → AF else A, E, I, O, U → A 
    2. Q → G, Z → S, M → N 
    3. KN → N else K → C 
    4. SCH → SSS, PH → FF 
    5. H → If previous or next is non-vowel, previous. 
    6. W → If previous is vowel, A. 
    7. Add current to key if current is not same as the last key character. 
5. If last character is S, remove it. 
6. If last characters are AY, replace with Y. 
7. If last character is A, remove it. 
8. Append translated key to value from step 3 (removed first character) 
9. If longer than 6 characters, truncate to first 6 characters. (only needed for true NYSIIS, some versions use the full key) 

SOUNDEX пакеты во многих языках программирования высокого уровня. В питона вы можете попробовать нечеткие пакет:

#!/usr/bin/env python 

import fuzzy 

names = [ 'Catherine', 'Katherine', 'Katarina', 
     'Johnathan', 'Jonathan', 'John', 
     'Teresa', 'Theresa', 
     'Smith', 'Smyth', 
     'Jessica', 
     'Joshua', 
     ] 

for n in names: 
    print '%-10s' % n, fuzzy.nysiis(n) 

Выход:

$ python show_nysiis.py 
Catherine CATARAN 
Katherine CATARAN 
Katarina CATARAN 
Johnathan JANATAN 
Jonathan JANATAN 
John  JAN 
Teresa  TARAS 
Theresa TARAS 
Smith  SNATH 
Smyth  SNATH 
Jessica JASAC 
Joshua  JAS 

В приведенном выше примере можно найти здесь: http://www.informit.com/articles/article.aspx?p=1848528

Вы можете ввести и матч ngrams или полные имена.

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