Математические модели и методы идентификации объектов нечисловой природы в хранилищах данных

Хранилище данных — это предметно-ориентированный, интегрированный, привязанный ко времени и неизменяемый набор данных, предназначенный для поддержки принятия решений. Впервые концепция информационных систем с хранилищем данных была предложена специалистами фирмы IBM [43]. Чрезвычайная сложность и, как следствие, высокая стоимость таких систем до середины 90-х годов XX века препятствовали их коммерческому внедрению. Основной вклад в становление технологии создания хранилищ данных внесли Барри Девлин, Уильям Инмон и Ральф Кимбал. В России разработкой и внедрением хранилищ данных занимается ряд компаний, таких как Intersoft Lab, Data Integration Software, РДТЕХ, Tomik, Трисофт, РЕЛЭКС и Аналитические технологии.

Наполнение хранилищ, как правило, осуществляется информацией из нескольких оперативных источников данных [18]. Наибольшую популярность приобрели базы данных. К сожалению, не все организации могут позволить себе разработку или впоследствии поддержку качественных систем хранения и обработки информации. Человеческий фактор и частичное отсутствие контроля данных на вводе либо неадекватная модель проверки информации приводят к появлению искажений в данных. Опечатки и пропуски присутствуют практически во всех реквизитах сохраненных объектов, в том числе и в идентификационных наборах. Основной причиной появления искажений является человеческий фактор на этапе ввода информации в базы данных. Особо остро проблема «загрязненных» данных препятствует созданию хранилища, когда отсутствует возможность повлиять на структуру и качество имеющейся информации. Такая ситуация типична, например, в правоохранительных органах, по роду деятельности которых необходима информация из многих разнообразных источников.

Управление федеральной службы налоговой полиции Российской Федерации по Саратовской области (УФСНП РФ по Саратовской области) регулярно получало БД от сторонних организаций. Для эффективного использования имеющейся информации необходимо было разработать хранилище данных с удобной системой поиска и представления информации. При построении хранилища данных, остро встала проблема наличия опечаток и пропусков данных в имеющихся БД [71, 73, 74, 75, 76, 78]. Разработка методов идентификации юридических лиц при построении информационного хранилища является предметом данной диссертационной работы.

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

Механизмы идентификации объектов в продуктах коммерческих фирм реализованы с использованием различного математического аппарата. Как правило, разработчики раскрывают алгоритмы, которые реализованы в программных продуктах. Однако по некоторым публикациям можно получить представление об используемых методах. Например, ООО «Аналитические технологии» в многомерном хранилище данных Deductor Warehouse использует нейронные сети. Компания РЕЛЭКС в основу идентификации в объектно-ориентированном хранилище данных «НЕВОД» использовала элементы нечеткой логики. В большинстве программного обеспечения алгоритмы идентификации используют аппарат обучения с учителем и различные справочники, которые формируются в процессе обучения. Такой подход имеет несколько недостатков. Во-первых, значительно различающиеся источники информации требуют персонального дополнительного обучения сети либо изменения функций принадлежности, что является весьма сложной и самостоятельной задачей. Во-вторых, идентификация, основанная на опорных справочниках, предъявляет высокие требования к их содержимому и влечет ложные выводы при наличии ошибок. Третьим недостатком является высокая трудоемкость при заполнении справочников и адаптации системы.

В БД задачи идентификации традиционно решаются следующими путями:

— выделяют один или несколько реквизитов, так называемые идентифицирующие наборы (ИН), однозначно определяющих запись в базе данных;

— вводят в состав реквизитов поле, имеющее априори уникальные значения, называемые первичным ключом;

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

Все вышеперечисленные методы оперируют точным равенством сравниваемых полей и бессильны при наличии ошибок, пропусков в данных или при несоответствии состава ИН, что приводит к следующим недостаткам:

— невозможности построения целостного хранилища данных,.

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

Решение поставленной задачи основывается, исходя из следующих соображений:

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

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

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

Приведем некоторые задачи, корректное решение которых практически невозможно без разработанных в данной диссертационной работе методов идентификации:

1) построение хранилища данных из нескольких БД;

2) аналитический поиск некоторых ситуаций по двум и более БД;

3) устранение дублирования объектов в рамках одной БД;

4) нахождение ошибочных/противоречивых объектов в БД;

5) разработка информационно-поисковой системы.

Целью диссертационной работы является разработка математических моделей и методов очистки данных и идентификации объектов нечисловой природы в хранилищах данных.

Для достижения указанной цели в работе решены задачи:

— выбор и обоснование метода неточного сравнения строк;

— разработан классификатор строковых реквизитов с получением как числовых, так и эвристических результатов сравнения;

— построена математическая модель реквизита, имеющего сложную внутреннюю семантическую структуру;

— выбор и обоснование методов принятия решения об идентификации объектов по совокупности результатов сравнений реквизитов;

— проверка метода идентификации на задаче интеграции различных баз данных в единое информационное пространство.

Научная новизна:

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

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

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

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

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

— универсальный программный комплекс, для СУБД ORACLE, предназначенный для проведения идентификации нечисловых объектов, таких как: юридические и физические лица, документы;

— хранилище данных, содержащее информацию из нескольких баз данных контролирующих органов Саратовской области, полученный с применением разработанных математических моделей и методов идентификации объектов;

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

На защиту выносятся:

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

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

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

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

Внедрение.

Разработанный метод идентификации был успешно применен в Управлении Федеральной службы налоговой полиции Российской Федерации по Саратовской области при решении задачи построения интегрированного банка данных по информации из нескольких БД государственных контрольных органов Саратовской области. Получен акт внедрения разработанных методов.

Апробация работы.

Основные теоретические положения и практические результаты работы обсуждались и докладывались на: V молодежной научно-технической конференции «Наукоемкие технологии и интеллектуальные системы 2003» (Москва, 2003), Всероссийской научно-практической конференции «Технологии Интернет — на службу обществу» (Саратов, 2003), XVI Международной научной конференции «Математические методы в технике и технологиях» (Ростов-на-Дону, 2003), Всероссийской научной конференции «Сложные системы. Анализ, моделирование, управление» (Саратов, 2004).

Публикации. Основные положения диссертации отражены в 8 публикациях, в том числе в 1 статье в журнале «Системная интеграция» рекомендованном ВАК. Без соавторов опубликовано 2 работы.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Изложена на 136 страницах, содержит 18 рисунков, 8 таблиц, список используемых источников включает 147 наименований.

Основные результаты диссертационной работы могут быть сформулированы в следующем виде:

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

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

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

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

5. Достоверность и практическая ценность результатов, полученных в диссертационном исследовании, подтверждена актом внедрения в работу УФСНП РФ по Саратовской области.

ЗАКЛЮЧЕНИЕ

.