ixLab. Лаборатория по извлечению информации

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

Очистка адресных данных – частный случай общей задачи очистки данных (data cleansing), часто решаемой ИТ-службами компаний. В рамках такой очистки выполняется приведение почтовых адресов, представленных, как правило, в неструктурированном виде, к единому стандарту. Данный процесс подразумевает выполнение операций по исправлению ошибок в именах и типах адресных объектов, переходу от синонимов к каноническим именам, восстановлению пропущенных адресных полей и почтового индекса, преобразованию устаревших адресов к их актуальному виду и т.п.

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

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

Очистка за рубежом

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

Microsoft предлагает продукт Data Quality Services (DQS), с помощью которого можно выполнять очистку адресных данных, но только после соответствующей настройки – готового решения не предлагается. Для работы системы требуется в каждом адресном поле определить область допустимых значений, а для каждого значения нужно задать его возможные синонимы. Поскольку значения в полях адреса не могут встречаться независимо, то необходимо создать правила, устанавливающие такие зависимости. Вместе эти данные образуют базу знаний, от полноты которой напрямую зависит способность системы обрабатывать реальные данные. Например, при настройке синонимов потребуется учесть, что слово микрорайон имеет более 30 сокращенных форм, встречающихся в реальных данных, а без этого адреса корректно обработать не удастся.

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

Аналогичные по назначению продукты предлагают IBM и Oracle. В Oracle Warehouse Builder предлагается набор инструментов по стандартизации адресных данных. В основе такой обработки лежит набор ключевых слов и использующих их шаблонов. Несмотря на то, что словарь ключевых слов и шаблоны сформированы на основе анализа миллионов реальных адресных записей, такое решение остается частным и не дает гарантии точности при обработке данных из новых источников. В связи с этим, производитель дополнительно предлагает интеграцию со специализированными решениями сторонних поставщиков.

Тем же путем следует IBM в линейке своих продуктов InfoSphere, где для нужд очистки адресов предлагается интеграция со сторонними продуктами AddressDoctor от Informatica и TS Quality от Trillium Software. Такой подход выглядит весьма логичным, поскольку качественная чистка адресных данных – это не просто продвинутый парсинг адресных строк, а обработка, учитывающая лингвистические особенности конкретного языка, специфику синтаксиса адресных записей, а также специфику почтовой адресации и административно-территориального деления конкретной страны. Для промышленной реализации такой обработки нужно регулярно выполнять работы по поддержанию базы знаний в актуальном и непротиворечивом состоянии. Кроме того, для выполнения актуализации устаревших адресов, необходимо иметь срезы, отражающие состояние системы почтовой адресации конкретной страны на конкретный момент времени. Все это приводит к тому, что чистку адресных данных нельзя выполнить средствами готового программного продукта, а следует говорить о сервисе, работоспособность и должный уровень качества которого непрерывно обеспечивается его поставщиком.

Зарубежный опыт демонстрирует продуктивность именно такого похода на примерах таких решений как AddressDoctor компании Informatica, AddressCorrect компании Intelligent Search Technology и Postal Address Verification компании CDYNE.

Основные проблемы, возникающие при очистке адресных данных

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

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

Тип каждого объекта (улица, город и пр.) может присутствовать слева или справа относительно имени, либо он может вообще отсутствовать. В силу синонимии тип может быть записан K-способами, поэтому для каждого из размещений имен будет иметь место (2K+1)^N вариантов размещения соответствующих типов. В адресной записи могут присутствовать разделители между полями (например, запятые). Разделители могут и отсутствовать, поэтому каждому варианту размещения имен и типов адресных объектов, будет соответствовать 2^N-1 вариантов размещения разделителей. Итоговое число вариантов написания адреса составит N!(2K+1)^N2^N-1. Простейший адрес, состоящий из четырех полей: город, улица, номер дома и номер квартиры, может быть записан 120 тыс. вариантов. Здесь мы полагаем N=4 и K=2, поскольку каждый тип может быть записан как минимум двумя способами – полным и сокращенным (например, проспект и пр-кт). Для выполнения очистки таких адресов с использованием шаблонов, потребуется учесть все варианты написания, что на практике достаточно сложно.

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

Москва, Тверская, д.1

Москва, Пушкинская, д.2

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

Москва, Кировская, д.3

В реальной жизни она указывает на деревню Москва в Кировской области. Однако интерпретация по шаблону приведет к тому, что Кировская будет объявлена улицей, которой в Москве нет.

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

Распознавание при очистке адресных данных

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

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

Решение обоих проблем ведется по двум следующим направлениям.

Обогащение эталонной адресной базы

Задача обогащения эталонной базы актуальна, когда фильтруемые системой очистки адресные записи заслуживают большего доверия, чем содержимое самой базы. С такой проблемой мы столкнулись при очистке адресов объектов Государственного кадастра недвижимости (ГКН), в котором ведется учет по всем объектам недвижимости России, а количество адресных записей, подлежащих обработке, исчисляется сотнями миллионов. При обработке адресов из ГКН есть уверенность в том, что данному источнику можно доверять не меньше, чем эталонным справочникам (КЛАДР и ФИАС), при этом содержимого этих справочников не хватает для очистки всех объектов ГКН. По нашим оценкам лишь 65% адресов ГКН удается привести к стандартному виду КЛАДР или ФИАС, а для стандартизации остальных 35% записей требуется выполнить обогащение эталонной базы. Такого рода обогащение состоит в добавлении недостающей информации в рамках существующей системы типов адресных объектов (например, добавление отсутствующих улиц в некоторых городах), а также в расширении самого состава типов, поскольку в адресах объектов ГКН присутствует информация, отобразить которую на существующие типы не представляется возможным.

Например, в КЛАДР и ФИАС отсутствуют такие типы объектов, как лесоперевалочная база, поселок индивидуальных застройщиков, дачное некоммерческое партнерство, жилой массив, и, как следствие, в этих справочниках отсутствуют соответствующие адресные объекты.

В основе разработанного нами подхода лежит два следующих принципа.

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

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

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

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

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

Большинство популярных алгоритмов использует векторную модель данных – объект представляется в виде многомерного вектора, при этом сходство объектов определяется как расстояние между векторами. При группировке адресов в качестве элементов векторов используются не задействованные при распознавании слова. Для вектора, соответствующего конкретной записи, значения элементов определяются весами слов, отражающими их важность для идентификации записи. Если слово не содержится в записи, то его вес равен нулю. Кроме того, при формировании характеристик выполняется замена самих слов их каноническими формами, что позволяет объединять в группы записи, содержащие различные словоформы одного и того же слова.

Ключевое значение для качественной кластеризации имеет определение весов слов. Наибольший вес должны получать слова, вносящие наибольший вклад при разделении адресов на кластеры, то есть, удовлетворяющие двум условиям: два адреса, содержащие такое слово, с высокой вероятностью принадлежат одному и тому же кластеру (являются однотипными); если же один адрес содержит это слово, а другой – нет, то эти адреса с высокой вероятностью принадлежат различным кластерам.

Для выполнения ранжирования слов по значимости была разработана весовая функция, учитывающая следующие характеристики слова:

Серьезной проблемой, с которой приходится сталкиваться при выполнении кластеризации, является высокая вычислительная сложность, затрудняющая применение популярных алгоритмов к массивам из миллионов записей. Так, алгоритм иерархической кластеризации имеет вычислительную сложность O(N²log(N)), где N – число объектов, подлежащих обработке. В случае массива из 10⁶ адресов необходимо выполнить примерно 10¹⁴ операций сравнения, поэтому приходится разбивать задачу на подзадачи с меньшей размерностью. В нашем случае это сводится к разделению всех слов на ключевые и не ключевые, что позволяет выполнить процесс кластеризации за два этапа.

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

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

Красноярский край, г. Красноярск, ул. Пушкина, 1

Красноярский край, г. Красноярск, ул. Дантона, 2

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

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

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

г. Красноярск, п. Индустриальный, 4

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

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

Качество очистки почтовых адресов

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

Полнота распознавания – отношение корректно распознанных к общему числу обработанных записей. Данный показатель определяется полнотой эталонной базы, поэтому изложенные методы обогащения нацелены как раз на повышение его значения. Опыт эксплуатации системы «Охотник за адресами» показывает, что в среднем полнота очистки адресных данных находится в диапазоне 0,92-0,99. Однако в особо сложных ситуациях, как в случае с обработкой адресов ГКН, данный показатель без использования обогащения достигает лишь 0,65. Использование предложенной технологии обогащения позволяет поднять его до 0,85.

Заключение

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

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

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

Бизнес направление

R&D направление

Особенности очистки адресных данных