Очистка адресных данных — частный случай общей задачи очистки данных (data cleansing), переход от синонимов к каноническим именам, восстановление пропущенных адресных полей и почтового индекса, преобразование устаревших адресов к их актуальному виду и т. п.

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

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

 

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

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

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.

 

Основные проблемы

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

  • Текстовая запись адреса. Эти данные неструктурированы, поскольку порядок следования адресных наименований может быть произвольным. Данная особенность вытекает из специфики русского языка, где порядок следования слов в предложении не регламентирован.
  • Большое количество типов адресных объектов. Например, для населенных пунктов предусмотрено более 40 типов наименований, многие из которых в сознании жителей страны являются эквивалентными — например, поселок, поселок городского типа и рабочий поселок. Как следствие, при написании адреса один тип может ошибочно заменяться другим, а большое количество типов порождает еще большее количество их синонимов и вариантов сокращения.
  • Отсутствие единых правил, по которым устанавливается отношение подчиненности между населенными пунктами и вышестоящими объектами. Населенный пункт может подчиняться району, районному центру, региону или региональному центру. При написании такого рода адреса велика вероятность, например, в качестве родительского объекта указать имя районного центра вместо самого района.
  • Наличие нескольких способов адресации. В России таких способов два — по административно-территориальному делению (например, Бокситогорский р-н, деревня Великое Село) и по территориальному принципу организации местного самоуправления (Ефимовское городское поселение, деревня Великое Село). При написании адреса по ошибке могут одновременно использоваться оба способа.
  • Регулярные изменения в административно-территориальном делении. Например, в 2011 году произошло изменение границ Москвы, и часть населенных пунктов перестали подчиняться Московской области. Прежнее написание таких адресов стало ошибочным, и при их обработке нужно выполнять актуализацию. Однако при отправке подписных изданий по карточной системе доставки УФПС по-прежнему настаивает на указании адреса по старинке: например, Московская область, город Троицк.

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

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

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

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

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

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

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

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

Распознавание

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

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

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

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

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

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

В основе предлагаемого подхода лежат два принципа:

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

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

Жизненный цикл системы очистки адресных данных
Жизненный цикл системы очистки адресных данных

 

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

  1. Успешно очищенные. Такие записи полностью укладываются в существующую систему типов, а потому не содержат новой информации.
  2. Успешно распознанные, но очищенные не полностью — так как в их записях присутствуют незадействованные при распознавании фрагменты. Такие фрагменты содержат информацию, которая может представлять интерес для добавления новых типов и соответствующих им адресных объектов.
  3. Отбракованные. Это те адреса, которые невозможно распознать, используя эталонную базу. К этому классу относятся адреса, записанные с неисправимыми ошибками, а также отсутствующие в эталонном справочнике.

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

Серьезной проблемой, с которой приходится сталкиваться при выполнении кластеризации, является высокая вычислительная сложность, затрудняющая применение популярных алгоритмов к массивам из миллионов записей. Так, алгоритм иерархической кластеризации имеет вычислительную сложность N2 log(N) [2], где N — число объектов, подлежащих обработке. В случае массива из 106  адресов необходимо выполнить примерно 1014 операций сравнения, поэтому приходится разбивать задачу на подзадачи с меньшей размерностью. В нашем случае это сводится к разделению всех слов на ключевые и неключевые, что позволяет выполнить процесс кластеризации за два этапа. На первом этапе производится кластеризация с учетом только ключевых слов, а на втором — каждый полученный кластер разделяется на подкластеры по неключевым словам. Примерно так работает эксперт, группируя адреса вручную, выполняя сначала грубую разбивку на крупные кластеры с использованием лишь некоторых наиболее характерных слов, а потом проводя уточняющее разделение кластеров с использованием остальных слов.

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

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

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

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

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

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

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

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

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

 

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

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

 

***

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

Литература

  1. Алексеев С.С., Морозов В.В., Симаков К.В. Методы машинного обучения в задачах извлечения информации из текстов по эталону // XI Всероссийская научная конференция (RCDL’2009) «Электронные библиотеки: перспективные методы и технологии, электронные коллекции»: труды. Петрозаводск: КарНЦ РАН, 2009.
  2. Манинг К.Д., Рагхаван П., Шютце Х. Введение в информационный поиск. М.: И.Д. Вильямс, 2011. 528 с.
  3. Андреев А.М., Березкин Д.В., Симаков К.В. Метод обучения модели извлечения знаний из естественно-языковых текстов // Вестник МГТУ. Приборостроение. 2007. № 3.

Константин Симаков (skv@ixlab.ru), Илья Козлов (kozlovilya89@gmail.com) — сотрудники компании «Лаборатория по извлечению информации» (Москва).

1 Если вы оформили редакционную подписку на «Открытые системы» или другие журналы издательства — значит, автоматизированная очистка вашего почтового адреса была выполнена с использованием справочников КЛАДР и ФИАС. — Прим. ред.