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

На правах рукописи

 

 

 

 

 

 

 

 

 

СОЛОДКОВ Алексей Юрьевич

 

 

 

 

 

 

МАТЕМАТИЧЕСКИЕ  МОДЕЛИ И МЕТОДЫ 
ИДЕНТИФИКАЦИИ ОБЪЕКТОВ НЕЧИСЛОВОЙ ПРИРОДЫ 
В ХРАНИЛИЩАХ ДАННЫХ

 

 

 

 

 

 

Специальность 05.13.18 – Математическое моделирование,  
численные методы и комплексы программ

 

 

 

 

 

Автореферат

диссертации на соискание  ученой степени

кандидата технических наук

 

 

 

 

 

 

 

 

 

Саратов 2006

 

Работа выполнена  в ГОУ ВПО «Саратовский государственный  
технический университет»

 

 

Научный руководитель:	кандидат технических наук, профессор  Каримов Равиль Нургалиевич
Официальные оппоненты:	доктор технических наук, профессор  Кушников Вадим Алексеевич   кандидат технических  наук, доцент   Квятковская Ирина Юрьевна
Ведущая организация:	Тамбовский государственный   технический университет

 

 

 

 

Защита состоится «3» ноября 2006г. в 13 часов на заседании диссертационного совета Д 212.242.08 при ГОУ ВПО «Саратовский государственный технический университет» по адресу: 410054, г. Саратов, ул. Политехническая 77, Саратовский государственный технический университет, ауд. 1/319.

 

 

 

 

 

С диссертацией можно ознакомиться в научно-технической библиотеке  
ГОУ ВПО «Саратовский государственный технический университет».

 

 

 

 

Автореферат разослан «02» октября 2006 года

 

 

 

 

 

 

 

Ученый секретарь диссертационного совета                                                                    А.А. Большаков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Классификаторы нечисловых реквизитов, в том числе имеющих сложную семантическую структуру на основе математической модели, генерирующие символьный либо числовой результат сравнения.
2. Метод проверки идентичности двух объектов на основе деревьев принятия решений и совокупности полученных результатов классификаторами по отобранным для идентификации реквизитам.
3. Математическая модель и метод идентификации нечисловых объектов, инвариантный по отношению к наличию пропусков и опечаток в данных с автоматической адаптацией набора реквизитов для сравнения.
4. Методика внедрения разработанного математического обеспечения при создании хранилища данных на примере Управления Федеральной службы налоговой полиции Российской Федерации (УФСНП РФ) по Саратовской области.

Практическую  значимость имеют:

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Анализ реально сложившейся  ситуации в базах данных (БД) показал, что нередки случаи искажения одного или нескольких реквизитов записей в разных БД, содержащих информацию об одном и том же объекте. Например, реквизит «наименование» предприятия «СаратовскиеАвиаЛинии» может иметь значение: «Саравиалинии», «Саравиа», «Авиа линии – Саратов», «Аэрофлот», «Маравиалинии» – ошибка в 1 знаке, «Саравиалниии» – транспозиция соседних символов. Интуитивно понятно, что эти названия относятся к одному и тому же юридическому лицу, однако при точном сравнении строк – они разные. При анализе БД одного из медицинских учреждений г. Саратова обнаружены записи, относящиеся к одному пациенту, при этом значения поля «ФИО» пациента со временем претерпевали следующие изменения:

1.	Ахмедов Байрам Юсуф-Оглы	3.	Ахмедов Байрам Юсуф оглы
2.	Ахмедов Байрам Юсуф Оглы	4.	Ахмедов Бейрам Юсуфович

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

 

Рис. 1. Причины возникновения искажений  в значении реквизита

 

Рис. 2. Причины появления опечаток

Существует достаточный  математический аппарат для анализа  и неточного сопоставления строк, например: расстояние редактирования, нахождение наибольшей общей подпоследовательности, метод n-грамм, trie-деревья, хеширование. Наиболее популярными для неточного сопоставления строк являются методы вычисления расстояния редактирования. Под расстоянием редактирования понимается метрика, определяющая «стоимость» преобразования одной строки в другую. Различают несколько операций, каждая из которых может иметь собственную стоимость: вставка символа, удаление, замена и транспозиция соседних символов. Если придать операциям вставки, удаления и замены вес, равный 1, то минимальная общая цена преобразования задается метрикой Левенштейна. Предпочтение метрике Левенштейна отдано многими разработчиками, исходя из двух факторов. Во-первых, расстояние Левенштейна формализует интуитивное понятие об «ошибке» и, во-вторых, существует множество алгоритмов эффективного его вычисления.