Лучший способ очистить и нормализовать большой объем данных, используя алгоритм сопоставления строк
В настоящее время я работаю над проектом моделирования данных как часть моего летнего проекта в университете. Данные клиента нуждаются в тщательной очистке, поскольку многие столбцы основаны на вводе человеком и имеют свободный текст.
Например, в столбце "Название компании" есть несколько записей для одной и той же компании. Для "Hugo Boss" это включает "Hugo Bos", "Huggo Boss", "Hugo Boss Ltd".
Я мог бы потенциально пройтись по каждой строке и определить все использованные значения и создать карту для каждой записи, однако, учитывая, что я имею дело с 1 миллионом записей, это очень много времени и не очень идеально.
Знают ли люди об исходном коде такой / подобной реализации? Я рассмотрел алгоритм сопоставления, однако они полагаются на предварительно вычисленный шаблон. Какие другие алгоритмы сопоставления или методы машинного обучения я могу использовать для разработки автоматизированного процесса, который очистил бы данные, т.е. сопоставил бы все разные имена с одним именем.
Любая помощь будет оценена.
4 ответа
Эта область исследований называется "Сопоставление данных" или "Связывание записей".
Есть очень хороший обзорный сборник техник, которые вы можете использовать Питером Кристеном. Он также углубляется в модели машинного обучения и в то, как улучшить их из базового подхода, такого как простые расстояния между струнами (как уже предлагалось в других ответах).
Чтобы дать вам преимущество, вы можете попытаться вычислить n-граммы символов ваших названий.
Для п = 3 и Хьюго Босс, вы получите
[hug, ugo, go , o b, bo, bos, oss]
Теперь вы можете вычислить сходство jaccard между двумя наборами этих ngram.
Вот, например, между 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. Это также очень быстро и хорошо масштабируется до миллиардов документов.
"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, потому что она сокращает длину строки.
Кроме того, вы можете сравнить буквенные нграммы в соответствии с рекомендациями Томаса в ответе о связи с записями, и это также упростит количество проверяемых нграмм.
Вот алгоритм 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 встречаются во многих языках программирования высокого уровня. В Python вы можете попробовать нечеткий пакет:
#!/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
Вы можете набирать и сопоставлять нграммы или полные имена.
Наконец, вы можете использовать имя режима в данных или другой метод для нормализации поля имени.
Вы можете попробовать aho-corasick конечный автомат и дополнить его подстановочным знаком. Другим вариантом является суффиксное дерево, то есть левенство в расстоянии. Вы можете попробовать мою PHP-реализацию aho-corasick @ https://phpahocorasick.codeplex.com/.
Другой вариант - посмотреть на расстояние Левенштейна https://en.wikipedia.org/wiki/Levenshtein_distance
Это поможет вам в таких случаях, как Хьюго Босс - Хьюго Босс, но не поможет Хьюго Босс - Хьюго Босс