Информационные технологии, №9, 2002

В.Э. Карпов, И.П. Карпова

Московский Государственный институт электроники и математики

(Технический университет)

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

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

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

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

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

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

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

Каждая из подобных систем по-своему уникальна и специфична с точки зрения сферы приложения. Например, в продукте фирмы Validy широко используются алгоритмы нечеткой логики, а в Apertus применяются правила, записываемые на специальном языке Object Query Language. Некоторые из этих систем (например Trillium), просматривают данные в поисках определенных образов и обучаются на основе найденной информации. В других образы, подлежащие распознаванию, задаются на этапе предварительного программирования.

Частные верификаторы предназначены для решения менее глобальных задач и обычно ограничиваются очисткой имен и адресов. Пакет компании PostalSoft содержит три библиотеки: исправления и кодировки адресов, оформления правильных имен и слияния/очистки. Первая библиотека корректирует адреса, вторая предлагает способ их стандартизации, третья выполняет т.н. консолидирующие функции. Система Nadis компании Group 1 Software придает адресам вид, отвечающий требованиям почтового ведомства (своего родного, американского). Nadis автоматически преобразует имя и адрес в стандарт Universal Name and Address data standard.

Объединяет подобные системы очистки одно – очень высокая стоимость. Та же Nadis стоит, в зависимости от платформы, от 65 до 250 тыс. долл. Поэтому разработка эффективных и недорогих методов очистки данных является весьма актуальной проблемой.

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

Итак, пусть имеется некоторое множество R баз данных, каждая из которых содержит фрагментарное описание некоторого множества общих объектов X.

И вот тут-то оказывается, что именно атрибут <Адрес> является одним из наиболее плохо формализованных. В подавляющем большинстве случаев адресная часть прописывается в одну строку, да еще самым замысловатым, одному только оператору известным образом. А в том ничтожно малом количестве ситуаций, когда адрес представляет собой множество атрибутов <Город>, <Дом>, <Улица>, <Квартира> и др., оказывается, что и улицу давно переименовали, и номер дома перепутан с номером строения и т.д.

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

Рассмотрим далее один из способов решения этой задачи.

Искажения адресной части можно классифицировать следующим образом:

• Синтаксические ошибки. Речь идет о структурных нарушениях. Например, сначала указывается город, а затем индекс, или просто отсутствуют некоторые составляющие.
• Лексические ошибки. Скажем, использование символа 'Ч' вместо цифры '4', нуля вместо буквы 'О' и т.п. Особенно это проявляется тогда, когда недобросовестный производитель занимается сканированием информации, не утруждая себя ее дальнейшей проверкой.
• Семантические ошибки. В основном речь идет о путанице между номером корпуса и номером дома или строения, о категории улиц (например, сокращение "пр." как проезд и проспект) и прочих ошибках, допускаемых даже на уровне определения адреса самими проживающими.
• Орфографические ошибки. Здесь и "Таллинская" вместо "Таллиннская", и "ул. Островитянина" вместо "ул. Островитянова" и т.д. и т.п.

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

Разбор адресной части, использующий принцип остатка, состоит из 5 этапов:

1. Предварительная обработка.
2. Классификация адреса.
3. Лексико-синтаксический анализ.
4. Постобработка.
5. Семантический анализ.

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

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

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

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

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

Теперь рассмотрим эти этапы подробнее.

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

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

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

Поэтому более перспективным представляется следующий подход.

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

Пусть в адресной строке находятся следующие атрибуты:

<ГОРОД>,<УЛИЦА>,<ДОМ>,<СТРОЕНИЕ>,<КОРПУС> и <КВАРТИРА>.

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

Тогда шаблон выделения названия населенного пункта может выглядеть так:

Далее можно попытаться выделить номер квартиры (если это записано в почти явном виде – "КВАРТИРА 245", "КВАРТИРА235" или "КВ.16"):

Аналогично выделяются из оставшейся части номер корпуса, строения и дома.

Сложнее обстоит дело тогда, когда номера пишутся вместе. Например, "...23-А-2-105-В". Шаблон для такого случая может выглядеть так:

Если же имеется строка вида "...8-8-6-47А", то, видимо, речь идет о доме, корпусе, строении и квартире:

Аналогично определяется и тип улицы – улица, шоссе, проспект и т.п.

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

После этого строка (точнее, множество выделенных атомарных атрибутов) готова к семантическому анализу.

Рассмотрим некоторые варианты решения этой задачи.

Явная орфо–фонетическая унификация

Введенное имя преобразуется следующим образом:

Система Soundex основана только на фонетической "близости" различных символов (для английского алфавита, естественно). К сожалению, такой подход не обеспечивает достаточной гибкости и, вообще говоря, чреват серьезными последствиями из–за своего "радикализма". В особенности, когда дело касается фонетически более сложного образования, такого как, например, русский язык.

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

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

Списковая метрика

Кроме оценки фонетической близости известны и иные способы определения степени сходства строк (цепочек) символов. Можно определять степень сходства через

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

Метод распознающих автоматов

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

Рассмотрим структуру распознающего автомата (рис. 3).

Рис. 3. Структура распознающего автомата

При этом необходимо соблюдение следующих условий:

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

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

Оценить значения вероятностей атрибутов шума можно исходя из различных соображений. В частности, в [5] приведена следующая статистика ошибок наборщиков (в процентах):

• Пропуск буквы – 0.38
• Замена буквы на другую – 0.34
• Лишняя буква – 0.6
• Перестановка двух соседних букв – 0.4
• Многобуквенные ошибки – 0.18

Видимо, эта статистика вполне может использоваться и для нашей задачи.

Следует отметить, что система не распознает "близости" входных символов (типа "похожести" звуков "Б"–"П", "В"–"Ф" и т.п.), т.е. не учитывает фонетические особенности реального языка. Однако использование процедуры предварительной орфо–фонетической унификации позволяет успешно справиться с этой проблемой.

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

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

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

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

Проверялись следующие методы:

1. Орфо–фонетическая унификация.
2. Списковая метрика (с процедурой перестановки) с предварительной орфо–фонетической унификацией и без нее.
3. Метод распознающих автоматов с предварительной орфо–фонетической унификацией и без нее.

При проведении экспериментов были получены следующие данные (табл.1):

Таблица 1. Результаты экспериментов по очистке данных

Полученные результаты свидетельствуют о том, что если при сопоставлении образца с элементами словаря предварительно преобразовать сравниваемые имена, то можно получить весьма неплохие и достаточно надежные результаты. Процедура предварительной орфо–фонетической унификации улучшает показатели распознавания в 1,5–2 раза. Использование этих методов позволяет автоматически очистить (распознать) от 10 до 45 процентов "грязных" данных.

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

Литература