Разработка математического и программного обеспечения идентификации объектов в базе данных на основе нестрогого соответствия тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Карахтанов, Дмитрий Сергеевич

• Карахтанов, Дмитрий Сергеевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Карахтанов, Дмитрий Сергеевич

ВВЕДЕНИЕ.

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

1.1 Проблемы идентификации объектов в базах данных.

1.2 Ограничения существующих поисковых алгоритмов.

1.3 Постановка задач исследования.

ГЛАВА 2. РАЗРАБОТКА ПРОЦЕДУР НЕСТРОГОГО СООТВЕТСТВИЯ.

2.1 Процедура определения функции релевантности.

2.2 Процедура вычисления расстояния между строками.

2.3 Процедура приближенного поиска по длинным строкам.

2.4 Процедура формирования ключа фонетической похожести.

Выводы.

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ОБЪЕКТОВ В БАЗАХ ДАННЫХ.

3.1 Алгоритм поиска и устранения дубликатов.

3.2 Алгоритм идентификации физических лиц.

3.3 Алгоритм поиска по отдельным атрибутам.

Выводы.

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

4.1 Особенности программной реализации средств автоматизации поиска дубликатов в базе данных.

4.2 Исследование эффективности разработанных алгоритмов в коммерческих базах данных.

4.3 Альтернативные применения.

Выводы.

Введение диссертации (часть автореферата) на тему «Разработка математического и программного обеспечения идентификации объектов в базе данных на основе нестрогого соответствия»

Актуальность темы. Неуклонный рост объемов- данных вызывает необходимость широкого использования передовых информационных технологий для1 эффективного управления» потоками данных. При этом наибольшую значимость приобретают задачи создания! эффективных инструментов оценки и контроля растущих потоков информации, оптимизации-процедур обработки, агрегации, обобщения, поиска и анализа данных. Возрастает спрос на создание, как корпоративных автоматизированных информационных систем (АИС), так и отдельных специализированных решений.

Автоматизированные информационные системы разрабатываются" на основе- информационно-аналитических баз данных, которые используются в качестве ключевого элемента системы и обеспечивают хранение и обработку всей- совокупности данных, поступающих от подразделений и* филиалов. С точки зрения технологий АИС представляет набор аппаратных средств, технологий, методов и алгоритмов, направленных на поддержку жизненного' цикла информации и включающих три основных процесса: обработку данных, управление информацией и управление знаниями.

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

Тематика диссертационной работы соответствует научному направлению Воронежского государственного технического университета "Вычислительные комплексы и проблемно-ориентированные системы управления".

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

Задачи исследования:

1. Провести анализ моделей, методов и алгоритмов поиска и сравнения объектов в реляционной базе данных;

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

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

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

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

Тематика работы соответствует п. 4 «Системы управления базами данных и знаний» и п. 7 «Человеко-машинные интерфейсы.» паспорта специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей».

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

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

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

- разработан алгоритм поиска по атрибутам1 на основе функции нестрогого соответствия, алгоритма фонетической похожести, расстояния Левенштейна, обеспечивающий поиск терминов, заданных в запросе, и/или их,расширений;

Практическая значимость работы заключается в создании процедур и функций, а также комплекса алгоритмов поиска и сравнения записей в БД;, которые позволяют:

- осуществлять расширенный поиск: и выдачу информации на основе функций нестрогого соответствия;

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

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

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

Реализация и внедрение результатов работы. Разработанное алгоритмическое и программное обеспечение использовано: в информационной системе ООО «Банковские информационно-аналитические системы»; в автоматизированной системе ООО «Кредитное бюро Русский Стандарт»; в информационно-аналитической системе Кредитной дирекции ЗАО «Банк Русский Стандарт», что подтверждается актами о внедрении.

Апробация работы. Теоретические и практические результаты, полученные в процессе исследования, докладывались и обсуждались на XIII научно-практической конференции «Реинжиниринг бизнес-процессов на основе современных информационных технологий. Системы управления процессами и знаниями» (СУЗ-РБП Москва, 2010), Международной научно -технической конференции «Современные информационные технологии» (Пенза, 2010), IV международной научно-практической конференции «Информационные технологии в образовании, науке и производстве» (Серпухов, 2010), XIII международной конференции «Проблемы управления безопасностью сложных систем» (Москва, 2010), XVI международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2011).

Публикации. По материалам диссертационной работы опубликовано 13 работ, в том числе 2 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит: в [1,11] -математическое обеспечение для устранения дубликатов записей в базе данных на основе нестрогого соответствия; в [7,9] — алгоритм идентификации объектов в базах данных; в [6] - результаты сравнительного анализа алгоритмов поиска; в [13] - специальное программное обеспечение поиска и устранения дубликатов в базе данных.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, одного приложения и списка литературы из 216 наименований, содержит 144 страницы основного текста, 25 рисунков, 37 таблиц.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Карахтанов, Дмитрий Сергеевич

Основные результаты, полученные в ходе научного исследования, заключаются в следующем:

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

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

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

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

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

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

7. Компоненты математического и программного обеспечения прошли государственную регистрацию в ФГНУ «Центр информационных технологий и систем органов исполнительной власти».

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Карахтанов, Дмитрий Сергеевич, 2011 год

1. Алиев; P.A., Абдикеев Н.М., Шахназаров М.М. Производственные системы; с искусственныминтеллектом.- М: Радио и связь. 1990, - 264 с.

2. Арсеньев Б. Ж. Интеграция! распределенных; баз данных / Арсеньев Б. П., Яковлев С. А. М.: Лань, 2001, - 464 с.3; Архангельский^ В-И:,. Богаенко И£Ш,. Грабовскиш Г.Г., Рюмшиш Н;А: Системы функции-управления. Киев:Техника, 1997,-208 с.

3. Асаи К., Ватада Д., Иван С. и др. Прикладные нечеткие системы. Под ред. Т. Тэрано, К. Асаи; Mi Сугено-М-"Мир;.1993;.-368 с:. .

4. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. — М.: Вильяме, 2009400 с.

5. Ахо A.B., Лам M C., Сети Р., Ульман Дж.Д. Компиляторы. Принципы, технологии и инструментарий; М.: Вильяме, 2008* — 1184 с.

6. Ашмаиов И., Харин Н. Интеллектуальные технологии обработки текстов-Mü: "Электронный офис", май-июнь Ь997, с. 24-25.

7. Белкина. Н. Кредитная истерия // "Smartmoney" № 44 (134).

8. Беллман Р., Заде Л. Принятие решений в расплывчатых условиях.- В кн.: Вопросы анализа и процедуры принятия, решений.- М.:Мир, 1976, с. 172-215.

9. Бен-Ган И. Microsoft SQL Server 2008. Основы T-SQL. М.:Русская Редакция, 2009, - 432 с.

10. Берштейн Л.С., Боженюк A.B. Нечеткие модели принятия» решений: дедукция, индукция, аналогия. Таганрог: Изд-во ТРТУ, 2001, 110 с:

11. Бойцов Л.М. Использование хеширования по сигнатуре для поиска по сходству // Прикладная математика и информатика, ВМиК МГУ, № 8, 2001, с. 135-154. .

12. Бондаренко A.B., Герасименко A.A. Об одном алгоритме нечеткого поиска именных компонент в специализированных, базах данных // Вестник компьютерных п информационных технологий. № 8 (12); 2005, с. 29-34.15.