Подготовка данных с помощью Fuzzy Matching

Недавно передо мной встала задача — нужно было объединить 2 таблички, содержавшие информацию по зданиям. Казалось бы задача на 5 минут — берешь Excel, присоединяешь с помощью ВПР нужные записи и готово! Однако быстрая проверка показала, что таким образом я смог объединить только 20% записей. Сравнить списки вручную тоже было затруднительно, так как в каждом было по 15 тыс. записей, и мне пришлось бы перебирать их вручную, чтобы найти совпадения.

Тем не менее с использованием алгоритмов нечеткого соединения (fuzzy matching) мне удалось существенно улучшить результаты. Я смог сопоставить 58% зданий, а в некоторых случаях довести количество сопоставленных записей до 80%. 

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

Алгоритмы нечеткого соответствия

Задачи такого рода встречаются очень часто, особенно при объединении данных из разных систем или обработке данных, введенных людьми. Для таких случаев были разработаны алгоритмы нечеткого совпадения (по английски Fuzzy matching). Создано достаточно много алгоритмов, решающих эту задачу, из них наиболее популярные и  известные это алгоритм Левенштейна и алгоритм Жаро-Винклера.

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

Рассмотрим их работу на примере. У нас есть эталонные записи о клиентах, в которых указаны фамилия и имя клиента например, Иванов Иван. Мы хотим сравнить их с данными из другого списка, который назовем “Клиенты CRM”. Во втором списке ФИО вносились вручную оператором без какой-либо стандартизации. Например, ФИО клиента в одном месте могли быть записаны как Иванов Иван, в другом Иванов И., а в третьем Ивнов И. И. (обратите внимание на опечатку в фамилии). 

Эталонные записи

ФИО
Иван Иванов 
Николай Петров
Юлия Александрова

Клиенты CRM

ФИО
Иванов И.
Иван Ивнов
Николай Петров
Воронова Юлия Сергеевна
Н. Петров
Петров Н.
Михайлова Наталья
Юлия Сергеевна Воронова 

Видно, что данные клиентов достаточно похожи, и для поиска совпадений мы могли бы воспользоваться алгоритмом Левенштейна. Этот алгоритм присутствует во многих ETL инструментах, в том числе и в открытом инструменте Pentaho Kettle. Им я и воспользуюсь.

Обработка данных в Pentaho Kettle

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

Загрузка данных из Excel

Чтобы начать работу с данными, их необходимо сначала загрузить. Pentaho позволяет загружать данные из множества источников. Сейчас нас интересует шаг Microsoft Excel Input, который мы можем найти в папке Input. Как следует из названия, он позволяет загружать 

Затем откройте источник двойным щелчком мыши. Появится меню настройки, в котором мы должны произвести следующие действия:

  1. Указать (или изменить) имя этапа.
  2. Выбрать тип файла, который мы загружаем.
  3. Найти файл на диске и добавить его в список файлов, нажав на кнопку Add. Таким образом можно добавить в обработку несколько файлов.
  4. Проверить, что файл появился в списке.
Настройка источника Excel

Далее нам нужно перейти в закладку Sheets и указать из какого листа будут браться данные. Нажмите на кнопку Get sheetnames и в появившемся меню выберите лист Эталон. Лист должен появится в области Your Selection. Нажмите кнопку ОК.

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

Перейдите в закладку Fields и нажмите на кнопку Get Fields from header. В таблицу добавятся колонки из листа Excel. В нашем случае это одна колонка ФИО. Нажмите на ОК. 

Далее нам необходимо добавить вторую табличку. Так как данные для неё берутся из того же файла, что и эталонные, достаточно скопировать источник и поменять в нём название шага и выбрать лист Сравнение в разделе Sheets.

Теперь мы можем приступить к объединению записей.

Объединение записей с помощью Fuzzy match.

Добавим на экран шаг Fuzzy match, перенеся его из области Design. Далее необходимо присоединить наши источники Excel к новому шагу. Для этого щелкните на шаг “Эталонные записи” с зажатой кнопкой Shift левой кнопкой мыши и не отпуская кнопку протяните её к шагу Fuzzy match. Между шагами появится стрелка. Аналогично присоедините источник “Клиенты”. В результате трансформация должна выглядеть следующим образом.

Теперь мы можем настроить объединение источников. Щелкните 2 раза на шаг Fuzzy Match. Давайте разберёмся с его настройками.

Раздел Lookup stream отвечает за настройки эталонного набора данных, с которым сравниваются все записи.

  • Lookup step — шаг, содержащий эталонные названия объекта. В нашем случае это шаг Эталонные записи.
  • Lookup field — поле (колонка), содержащая эталонные записи. 

Раздел Main Stream имеет только один параметр — Main stream field, в котором указывается поле из набора данных, к которому мы хотим найти соответствие. В нашем примере это поле ФИО. Так как ранее мы уже указали, какой шаг содержит справочные данные, второй шаг автоматически считается источником данных для сопоставления, поэтому в нём не нужно указывать шаг.

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

  • Algorithm — алгоритм сравнения. По умолчанию выбран алгоритм Левенштейна, но можно посмотреть и другие.
  • Case Sensitive — должен ли алгоритм быть чувствительным к регистру, т.е. рассматривать заглавную и строчную буквы как разные символы?
  • Get closer value. Если выбрана эта опция, алгоритм покажет только одно наиболее похожее значение. Если снять опцию, то вы получите список всех подходящих по условиям значений, разделенных запятой.
  • Minimal/maximal value — минимальное и максимальное значение для алгоритма. Когда мы используем алгоритм Левенштейна — это максимальное/минимальное количество изменений в строках.

После заполнения всех настроек шаг должен выглядеть следующим образом. 

Теперь наша трансформация полностью готова. Нажмите на кнопку Run в верхней части экрана и подтвердите запуск нажатием на Run в появившемся меню.

После того как трансформация отработает, щелкните на шаг Fuzzy match и выберите закладку Preview data. Здесь мы можем увидеть результаты трансформации.

В колонке ФИО указаны значения из таблицы Клиенты, в колонке match — наиболее подходящий клиент из эталонного справочника, а в колонке measure value — разница в количестве перестановок. По этой разнице можно косвенно оценить качество подстановки в поле match. Чем больше число, тем больше разница, при этом ноль означает, что строка полностью соответствует эталону, а null — что подходящей строки (которая отличается максимум на 10 символов не нашлось).

Видно, что алгоритм успешно справился в большинстве случаев. Он нашел ФИО с перестановками, незначительными опечатками и отсутствующим отчеством. Однако его сбил с толку изменённый порядок имени и фамилии, что видно в строке 6. Если мы знаем, что формат ФИО в эталонном справочнике клиентов отличается от списка CRM, то мы можем заранее обработать данные, чтобы привести их к одному формату и повысить качество соединения записей.

Добавить комментарий

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.