Математические модели и методы идентификации объектов нечисловой природы в хранилищах данных тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Солодков, Алексей Юрьевич

• Солодков, Алексей Юрьевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Солодков, Алексей Юрьевич

ВВЕДЕНИЕ.

1. ОБЗОР. МЕТОДЫ ХРАНЕНИЯ И УПРАВЛЕНИЯ ДАННЫМИ. МЕТОДЫ НЕТОЧНОГО СОПОСТАВЛЕНИЯ СТРОК.

МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЙ.

1.1. Методы хранения и управления данными.

1.1.1. Базы данных.

1.1.2. Хранилища данных.

1.1.3. Очистка данных.

1.2. Методы неточного сопоставления строк.

1.2.1. Расстояние редактирования.

1.2.2. Нахождение наибольшей общей подпоследовательности.

1.2.3. Метод п-грамм.

1.2.4. Trie-деревья.

1.2.5. Хеширование.

1.3. Методы принятия решений.

1.3.1. Таблицы принятия решений.

1.3.2. Деревья принятия решений.

1.3.3. Фреймовые модели.

1.3.4. Нейросетевые методы.

1.3.5. Теория нечетких множеств.

1.3.6. Генетические алгоритмы.

1.3.7. Структурные методы анализа.

1.4. Выводы.

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

НА ПРИМЕРЕ ЮРИДИЧЕСКИХ ЛИЦ.

2.1. Алгоритмы сравнения реквизитов объектов.

2.1.1. Символьные поля.

2.1.2. Сложные символьные поля.

2.1.2.1. Наименование объекта.

2.1.2.2. Почтовый адрес.

2.1.3. Числовые поля.

2.2. Алгоритмы сравнения объектов.

2.2.1. Таблицы принятия решений.

2.2.2. Деревья принятия решений.

2.2.3. Структурный метод принятия решений.

2.3. Выводы.

3. ПРИМЕНЕНИЕ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ЮРИДИЧЕСКИХ ЛИЦ В ЗАДАЧЕ ПОСТРОЕНИЯ ХРАНИЛИЩА ДАННЫХ.

3.1. Выбор класса задач.

3.2. Построение хранилища данных

Управления Федеральной службы налоговой полиции по Саратовской области.

3.2.1. Особенности предметной области. Выбор СУБД.

3.2.2. Входной поток и Метапоток хранилища данных.

3.2.3. Восходящий поток.

3.2.4. Выходной поток.

3.2.5. Выбор реквизитов для принятия решения.

3.2.6. Построение дерева принятия решений.

3.2.7. Структурный метод принятия решений.

3.3. Выводы.

4. РЕАЛИЗАЦИЯ, ЭКСПЕРИМЕНТЫ, ВНЕДРЕНИЕ.

4.1. Оценки эффективности алгоритма.

Сравнение с традиционными методами.

4.2. Описание программной реализации алгоритма идентификации объектов нечисловой природы.

4.3. Технические характеристики.

4.4. Выводы.

Введение диссертации (часть автореферата) на тему «Математические модели и методы идентификации объектов нечисловой природы в хранилищах данных»

Хранилище данных - это предметно-ориентированный, интегрированный, привязанный ко времени и неизменяемый набор данных, предназначенный для поддержки принятия решений. Впервые концепция информационных систем с хранилищем данных была предложена специалистами фирмы 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. Достоверность и практическая ценность результатов, полученных в диссертационном исследовании, подтверждена актом внедрения в работу УФСНП РФ по Саратовской области.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Солодков, Алексей Юрьевич, 2006 год

1. Аведьян Э.Д. Алгоритмы настройки многослойных нейронных сетей / Э.Д. Аведьян // Автоматика и телемеханика. - № 4. - 1995. - С. 106-118.

2. Айвазян С.А. Прикладная статистика и основы эконометрики / С.А. Айвазян, B.C. Мхитрян М.: Юнити, - 1998. - С. 1022.

3. Андреев А.Б. Концепция регионального межведомственного банка данных / А.Б. Андреев, Б.Ю. Зинченко, В.И. Белоножкин // Информация и безопасность. 2002г. - №1. - С. 36-39.

4. Арсеньев Б. П. Система автоматизации семантической интеграции распределенных баз данных: дис. . кан. техн. наук / Б.П. Арсеньев. СПб.,- 1997.- С. 167.

5. Арсеньев Б.П. Интеграция распределенных баз данных / Б.П. Арсеньев, С.А. Яковлев. СПб.: Лань, - 2001. - С. 461.

6. Артамонов Р.Г. Алгоритмы клинической диагностики / Р.Г. Артамонов. // Медицинский научный и учебно-методический журнал.- 2002. № 11.-С. 7-20.

7. Благуш П. Факторный анализ с обобщениями / П. Благуш. М.: Финансы и статистика, 1989. - С. 248.

8. Бойцов Л.М. Синтез системы автоматической коррекции, индексации и поиска текстовой информации: дис. . кан. техн. наук / Л.М. Бойцов. М. -2003.-С. 147.

9. Борисов А.Н. Обработка нечеткой информации в системах принятия решений / А.Н. Борисов, А.В. Алексеев. М.: Радио и связь,- 1988.-С. 304.

10. Васильев М.А. Оценка эффективности проектов актов местного самоуправления: методы экспертной оценки / М.А. Васильев. Обнинск: Институт муниципального управления, - 2002. - С. 124.

11. Вороновский Г.К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К. Вороновский, К.В. Махо-тило, С.Н. Петрашев, С.А. Сергеев. Харьков: Основа, - 1997. - С. 212.

12. Гафт М.Г. О построении решающих правил в задачах принятия решений/ М.Г. Гафт, В.В. Подиновский // Автоматика и телемеханика,- 1981.-№6.-С. 128-138.

13. Гафт М.Г. Принятие решений при многих критериях / М.Г. Гафт.- М.: Знание, 1979. - С. 328.

14. Глушков В.М. Введение в АСУ / В.М. Глушков. Киев: Тэхника,- 1974.-С. 320.

15. Горбань А.Н. Нейронные сети на персональном компьютере / А.Н. Гор-бань, Д.А. Россиев. Новосибирск: Наука (Сиб. отделение), 1996. - С. 276.

16. Горбань А.Н. Обучение нейронных сетей / А.Н. Горбань. М.: СП Параграф,- 1990.-С. 159.

17. Гуров В.В. Инфокоммуникации юга России / В.В. Гуров // Журнал Сети и системы связи. -2003г.-№11.-С. 14-22.

18. Долотов Д. Хранилище данных для «Мострансгаза» / Д. Долотов // Журнал Открытые системы. 2003. - №3. - С. 15-17.

19. Дюбуа Д. Теория возможностей / Д. Дюбуа, А. Прад. М.: Радио и связь, - 1990.-С. 288.

20. Дюк В.А. Data Mining интеллектуальный анализ данных / В.А. Дюк // Byte (Россия). - 1999. - №9. - С. 18-24.

21. Емельянов С.В. Многокритериальные методы принятия решений / С.В. Емельянов, О.И. Ларичев. М.: Знание. - 1985. - С. 458.

22. Еремеев А.П. Параллельная модель для продукционной системы табличного типа / А.П. Еремеев // Изв. АН СССР, Техническая кибернетика. -1990.-№5.-С. 171-180.

23. Еремеев А.П. Продукционная модель представления знаний на базе языка таблиц решений / А.П. Еремеев // Изв. АН СССР Техническая кибернетика. 1987. - №2. - С. 196-207.

24. Ермаков А.Е. Ассоциативная модель порождения текста в задаче классификации / А.Е. Ермаков, В.В. Плешко // Информационные технологии. -2000.-№12.-С. 30-35.

25. Ермаков А.Е. Компьютерная лингвистика и анализ текста / А.Е. Ермаков // http://www.metric.ru/publications.asp?obno=305

26. Ермаков А.Е. Лингвистическая модель для компьютерного анализа тональности публикаций СМИ / А.Е. Ермаков, С.Л. Киселев // Компьютерная лингвистика и интеллектуальные технологии: труды Междунар. конференции Диалог'2005. М.: Наука, - 2005. - С. 312-313.

27. Ермаков А.Е. Морфологический анализатор основа поисковых систем/ А.Е. Ермаков // Компьютерные Вести. - 2004. - №15. Оhttp://kv.by/index2004154301.htm)

28. Ермаков А.Е. Синтаксический разбор в системах статистического анализа текста / А.Е. Ермаков, В.В. Плешко // Информационные технологии. -2002.-№7.-С. 15-17.

29. Ермаков А.Е. Тематический анализ текста с выявлением сверхфразовой структуры / А.Е. Ермаков // Информационные технологии. 2000. -№11.-С. 58-64.

30. Заде JI.A. Основы нового подхода к анализу сложных систем и процессов принятия решений / JI.A. Заде. М.: Математика сегодня,- 1974.-С. 249

31. Заде JI.A. Понятие лингвистической переменной и ее применение к принятию приближенных решений / JI.A. Заде. М.: Мир. - 1976. - С. 167.

32. Закревский А.Д. ЭКСИЛОР экспертная система логического распознавания / А.Д. Закревский // Управляющие системы и машины. - 1992. -№5/6.-С.118-125.

33. Иберла К. Факторный анализ / К. Иберла. М.: Статистика,- 1980.-С. 398.

34. Ивахненко А.Г. Персептроны / А.Г. Ивахненко. Киев : Наукова думка,- 1974.-С. 276.

35. Итоги науки и техники. Сер. Физ. и матем. модели нейронных сетей / под ред. А.А. Веденова. М.: ВИНИТИ, - 1990-1992. - Т. 1-5.

36. Керниган Б. Практика программирования / Б. Керниган, Р. Пайк. СПб.: Невский диалект, 2001. - С. 288.

37. Кини Р.Л. Принятие решений при многих критериях: предпочтения и замещения / Р.Л. Кини, X. Райфа. М.: Радио и связь, - 1981. - С. 560.

38. Киселев М. Средства добычи знаний в бизнесе и финансах / М. Киселев, Е. Соломатин // Открытые системы. 1997. - №4. - С. 41-44.

39. Кнут Д. Сортировка и поиск / Д. Кнут. М.: Вильяме, - т. 3.- 1978.-355 с.

40. Конолли Т. Базы данных. Проектирование, реализация и сопровождение. Теория и практика / Т. Конолли, К. Бегг, А. Страчан. М.: Вильяме, -2000.-С. 1120.

41. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М.: МЦНМО, - 2001. - С. 1296.

42. Кофман А. Введение в теорию нечетких множеств / А. Кофман.- М.: Радио и связь, 1982. - С. 432.

43. Кохонен Т. Ассоциативная память / Т. Кохонен. М.: Мир,- 1980.-С. 250.

44. Кохонен Т. Ассоциативные запоминающие устройства / Т. Кохонен. -М.: Мир,- 1982.-С. 384.

45. Кречетов Н. Продукты для интеллектуального анализа данных / Н. Кречетов // Рынок программных средств. 1997. - №14-15. - С. 32-39.

46. Лаборатория BaseGroup. Очистка и разбор текста// http://www.basegroup.ru/tasks/parsing.htm.

47. Ларичев О.И. Качественные методы принятия решений / О.И. Ларичев, Е.М. Мошкович. М.: Физматлит, - 1996. - С. 217.

48. Левченко В.И. Матричное представление нечетких предикатов и его приложение в экспертных системах / В.И. Левченко, А.А. Савинов // Изв. АН СССР. Техническая кибернетика. 1993. - №5. - С. 125-140.

49. Липинский Г.В. Russian Context Optimizer: путь к возможностям Oracle interMedia в русскоязычных базах данных / Г.В. Липинский // Доклад на XII конференции АПО/ROUG, 1 сент. 2000г. - Обнинск. - С. 42-50.

50. Литвак Б.Г. Экспертная информация: методы получения и анализа / Б.Г. Литвак.-М.: Радио и связь, 1981. - С. 305.

51. Лоби Дж. Логические таблицы принятия решения / Дж. Лобби. М.: Прогресс,-1971.-С. 139.

52. Лодыженский Г. Шлюзы как средство интеграции баз данных. Практический подход / Г. Лодыженский // Открытые системы 1999. - №02.

53. Мазов Н.А. N-граммные методы обработки текстовой информации / Н.А. Мазов. Новосибирск: Объединенный институт геологии, геофизики и минералогии Сибирского отделения РАН, - 1995. - С. 180.

54. Месси Дж. Л. Введение в современную криптологию / Дж. Л. Месси // ТИИЭР. 1988. - №5. - т.76.- С. 24-42.

55. Минский М. Персептроны / М. Минский, С. Пайперт. -М.: Мир,-1971.-С. 276.

56. Минский М. Фреймы для представления знаний / М. Минский. -М.: Мир,-1979.-С. 198.

57. Миркин Б.Г. Проблема группового выбора / Б.Г. Миркин. М.: Наука, - 1974.-С. 95.

58. Нечеткие множества в моделях управления и искусственного интеллекта / под ред. Д.А. Поспелова. М.: Наука, -1986. -С. 312.

59. Нечеткие множества и теория возможностей: последние достижения. / под. ред. P.P. Ягера. М.: Сов. Радио, -1986. - С. 408.

60. Орлов А.И. Нечисловая статистика / А.И. Орлов. М.: МЗ-Пресс, -2004.-С. 295.