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

ВВЕДЕНИЕ.

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

1.1. Подсистема ассоциативного поиска в базе данных как объект проектирования.

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

1.3. Анализ нейросетевых методов для решения задачи ассоциативного поиска.

1.3.1. Применение многослойных персептронов.

1.3.2. Ассоциативный поиск с самообучением на основе самоорганизующихся карт Кохонена.

1.3.3. Автоассоциативные сети для ассоциативного поиска.

1.3.4. Сети встречного распространения.

1.3.5. Повышение эффективности на основе гибридных нейронных сетей

1.4. Анализ средств моделирования ИНС.

1.5. Цель и задачи исследования.

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

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

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

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

Таким образом, актуальность темы диссертационной работы обусловлена необходимостью разработки методов и средств ассоциативного поиска информации на базе спроектированных нейронных структур с оптимально настроенными параметрами в рамках подсистемы СУБД.

Работа выполнена в соответствии с межвузовской комплексной научно-технической программой 12.11 «Перспективные информационные технологии в высшей школе» и НИР «Вычислительные системы на базе нейрокомпьютеров, транспьютеров и оптических ЭВМ» в рамках одного из основных направлений Воронежского государственного технического университета «Системы автоматизированного проектирования».

Цель и задачи исследования. Целью диссертационной работы является разработка и практическая реализация комплекса алгоритмов и программных средств ассоциативного поиска образов в базе данных с помощью нейросетевых методов в рамках подсистемы СУБД.

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

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

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

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

При разработке программных средств использован объектно-ориентированный подход и средства языка программирования С++. Подсистема индексирования образов в базе данных разработана для отечественной реляционной СУБД ЛИНТЕР и внедрена в информационно-аналитическую систему «Невод».

Реализация результатов работы. На основе разработанного программно-методического комплекса создана система ассоциативного поиска изображений, внедренная в рамках информационно-аналитической системы (ИАС) анализа криминальной информации «Невод», разрабатываемой фирмой «РелЭкС».

Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях, семинарах и совещаниях: «Математическое моделирование систем. Методы, приложения и средства» (Воронеж, 1998), «Микроэлектроника и информатика - 98» (Москва, 1998), «Интеллектуальные информационные системы» (Воронеж, 1999), ежегодных научных конференциях профессорско-преподавательского состава Воронежского государственного технического университета (1998, 1999).

Публикации. По материалам диссертации опубликовано 10 работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения. Работа содержит 125 с. машинописного текста, включая 16 рисунков, 8 таблиц, 6 приложений и список литературы из 89 наименований.

4.3. Основные выводы главы

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

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

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

3. Разработано и внедрено программное обеспечение системы ассоциативного поиска фотографий в базе данных в рамках информационно-аналитической системы «Невод», отличающейся достаточно высокой точностью и скоростью поиска фотографий размерностью до 200 на 200 пикселей на базе персональных компьютеров.

4. Проведен анализ быстродействия полученных средств ассоциативного поиска в зависимости от количества записей в БД для случаев использования имитационных моделей ИНС и аппаратного ускорителя на основе ПЛИС ХШпх.

ЗАКЛЮЧЕНИЕ

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

1) определена задача ассоциативного поиска объектов в базе данных как задача классификации образов, предложены методы решения на основе аппарата искусственных нейронных сетей и сформулированы принципы построения соответствующей подсистемы СУБД и состав основных проектных процедур процесса проектирования средств ассоциативного поиска в базе данных;

2) разработаны алгоритмы индексирования образов в базе данных и алгоритм ассоциативного поиска, использующие модели ИНС с оптимально настроенными параметрами и позволяющие автоматизировать процедуру поиска в базе данных объекта по заданному образу без ограничений на количество обрабатываемых записей;

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

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

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

125

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

7) разработано и внедрено программное обеспечение системы ассоциативного поиска фотографий в базе данных в рамках информационно-аналитической системы «Невод», обеспечивающей возможность поиска фотографий размерностью до 200 на 200 пикселей; предложено использовать аппаратный ускоритель на базе ПЛИС ХШпх, позволяющий повысить скорость ассоциативного поиска фотографий в 5 и более раз.

1. Aarts Е. Н. L., Korst J. Н. М. Boltzmann machines and their applications //Lect. Notes Comput. Sei., 1987. - V.258. С. 34 - 50.

2. Aarts E. H. L., Korst J. H. M. Boltzmann machines for travelling salesman problem //European J. Oper. Res, 1989. V.39. C. 79 - 95.

3. Abu-Mostafa Y. S., Jaques J. N. St. Information capacity of the Hopfield model //IEEE Trans. Inform. Theory, 1985. V.31. C. 461.

4. Ackley D. H., Hinton G. E., Sejnowski T. J. A learning algorithm for Bolzmann machines //Cognit. Sei., 1985. V.9. N 1. С. 147 - 169.

5. Aleksander Igor, Morton Helen An introduction into neural computing. London: TJ Press Ltd, 1991. 180 c.

6. Amari S. Field theory of self-organizing neural networks //IEEE Trans. Syst., Man, Cybern, 1983. V. 13. С. 741.

7. Artificial Intelligence //Amsterdam: Time-Life-Books, 1986. N3 - c. 15.

8. Bardcev S. I., Okhonin V. A. The algorithm of dual functioning (back-propagation): general approach, vesions and applications. Krasnojarsk: Inst, of biophysics SB AS USSA 1989. 150 c.

9. Brunak S., Lautrup B. Neural Network. Computers with intuition. Singapore: World Scientific, 1990.

10. Carpenter G.A., Grossberg S. Pattern Recognition by SelfOrganizing Neural Networks. Cambridge: MIT Press,1991.1 l.Fogelman Soulie F. Neural networks, state of the art, neural computing //London: IBC Technical Services, 1991. C. 65 - 75.

11. Fox G. C., Koller J. G. Code generation by a generalized neural network: general principles and elementary examples //J. Parallel Distributed Comput, 1989. Y.6. N2. C. 388 - 410.

12. Funakashi K. On the approximate realization of continuous mappings by neural networks //Neural Networks, 1989. N 2. C. 182 - 192.

13. Grossberg S. Some networks that can learn, remember and reproduce any number of complicated space-time patterns // Journal of Mathematics and Mechanics, 19:53-91, 1969.

14. Guralink G., Zemach C., Warnock Т. An algorithm for uniform random sampling of points in and on a hypersphere // Information Processing Letters 21 (1985) 1721, North-Holland, 1985. C, 17-21.

15. Hecht-Nielsen R. Applications of counterpropagation networks // Neural Networks 1:131-39, 1988.

16. Hertz J., Krogh A., Palmer R. Introduction to the theory of neural computation. -Redwood City: Addison-Wesley, CA 94065, 1991. 195 c.

17. Hopfield J. J. Neural networks and physical systems with emergent collective computational abilities. //Proc. Natl. Acad. Sei. 1984. V. 9. C. 147-169.

18. Hopfield J. J., Tank D. W. Neural computation of decision in optimization problems //Biol. Cybernet, 1985. V.52. C. 115.

19. Jondarr C. Back Propagation Family Album // Technical Report C/TR96-05. Department of Computing, Macquarie University, NSW 2109, 1996. 63 c.

20. Juell P., Marsh R. A hierarchical neural network for human face detection // Pattern Recognition. V. 29, N 5. Pattern Recognition Society, 1996. C. 781-787.

21. Kohonen T. SelfOrganization and Associative Memory. Third Edition. New York: Springier-Verlag, 1989.

22. Kulkarni A.V., Kanal L.N. Proc. 4th Int. Joint Conf. On Pattern Recognition, Kyoto. New York: IEEE. c. 238-283.

23. Lachenbruch P.A., Goldstein M // Biometrics 35, 1979. C. 69-85.

24. Martin Riedmiller, Heinrich Braun. A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In Proceedings of the IEEE International conference on Neural Networks. Univercity of Carlsruhe. W-76128 Carlsruhe FRG, April 1994.

25. Martin Riedmiller. RPROP description and implementation details. Univercity of Carlsruhe. W-76128 Carlsruhe FRG, January 1994.

26. Microsoft ODBC 2.0 programmers reference and SDK guide. Washington: Microsoft Press, 1994. - 703 c.

27. Shiffmann W. , Joost M. , Werner R. Optimization of the backpropagation algorithm for training multilayer perceptrons. Univercity of Cobleng, Institute of Physics. 1993.

28. Tank D.W., Horfield J J. Simple "neural" optimization networks: An A/D converter, signal decision circuit, and a linear programming circuit. IEE Transactions on Circuits and Systems CAS-33(5):533-41.

29. Wasserman А.1., Information System Design Metodology, J. Am. Soc. Inf. Sei., 31, 1 (Jan, 1980).

30. Wasserman Philip D. Neural Computing. Theory and Practice. New York: Van Nostrand Reinhold, 1989. 314 с.

31. ХШпх Data Book, Xilinx, Inc., 1999.

32. Аведьян Э. Д. Алгоритмы настройки многослойных нейронных сетей //Адаптивные и робастные системы: сб. статей М.: 1995. - с. 106 - 118.

33. Анил. К. Джейн, Жианчанг Мао, Моиуддин K.M. Введение в искусственные нейронные сети // Открытые системы. N4, 1997. с. 17-24

34. Антонов И.А., Салеев В.М. Экономичный способ вычисления ЛП -последовательностей // Ж. вычисл. матем. и матем. физ., 1979, 16, N5, с. 243-245.

35. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ: Пер. с англ. М.: Мир, 1978. -616 с.

36. Бойченко И.А., Мучник Ф.М., Пешков A.B. Возможности мобильной СУБД ЛИНТЕР на рынке пользователей ПЭВМ // Управляющие системы и машины, 3/4 1992. с. 124-127.

37. Борисов В.Л., Федоров М.Г., Эксаревский A.B. Применение нейронной сети в качестве селектора для оптимального выбора выполняемой ветви программы // Микроэлектроника и информатика 98: Тез. Всерос. межвуз. науч.-техн. конф.-М., 1998.-С. 103.

38. Борисов В.Л., Эксаревский A.B., Эксаревская М.Е. Нейросетевой алгоритм индексирования двоичных образов в информационной системе // Математическое моделирование систем. Методы, приложения и средства: Сб. науч. тр. Воронеж: ВГУ, 1999. - 214 с.

39. Галушкин А.И., Фомин Ю.И. Нейронные структуры как линейные последовательные машины.: Учебное издание. М.: Изд-во МАИ, Под ред. В.К.Левина, 1991. - 80 с.

40. Гончаров Е.А., Каплинский А.И., Эксаревский A.B. Программная эмуляция искусственной нейронной сети, осуществляющей выделение объектов на изображении // Интеллектуальные информационные системы: Тр. Всерос. конф. Воронеж: ВГТУ, 1999 - С. 191.

41. Горелик A.JT., Скрипкин В.А. Методы распознавания: Учеб. пособие для вузов. 2-е изд., перераб. и доп. - М.: Высшая школа, 1984. - 208 с.

42. Дейт К. Введение в системы баз данных. Пер. с англ. 6-е изд. - К.: Диалектика, 1998.-784 с.

43. Джеффри Е. Хинтон. Как обучаются нейронные сети //В мире науки, 1992. -N 11 -N 12. с. 103- 107.

44. Дуда Р., Харт П. Распознавание образов и анализ сцен: Пер. с англ. М.: Мир, 1976.-512 с.

45. Крамер Г. Математические методы статистики. Пер. с англ. М.:Мир, 1975. -648 с.

46. Кузнецов С.Д. Введение в СУБД: Часть 2 // СУБД, N2, 1995.

47. Куссуль Э.М. Ассоциативные нейроподобные структуры. К.: Наукова думка, 1990. - 253 с.

48. Куссуль Э.М. и др. Нейронные классификаторы с распределённым кодированием входной информации //Нейрокомпьютер. 1994. - №3,4. -С.13-24.

49. Ладыженский Г.М. Системы управления базами данных коротко о главном. //СУБД, N2, 1995.

50. Ланкастер П. Теория матриц. М:. Наука, 1978. - 560 с.

51. Логовский A.C., Якушев Д.Ж. Нейропакеты: что, где, зачем // Успехи современной радиоэлектроники. N2, 1997, С. 11-18.

52. Маккалок Дж., Питтс У. Логические исчисления идей, относящихся к нервной деятельности. Автоматы. М.: ИЛ, 1956. 214 с.

53. Марр Д. Зрение. Информационный подход к изучению представления и обработки зрительных образов. -М.: Радио и связь. 1987. -400 с.

54. Минский М., Пейперт С. Персептроны. М.: МИР, 1971. 261 с.

55. Норенков И. П., Маничев В. Б. Основы теории и проектирования САПР. -М.: Высш. шк, 1990. 335 с.

56. Патрик Э. Основы теории распознавания образов: Пер. с англ. М.: Сов. радио, 1980.-408 с.

57. Применение ПЛИС Xilinx для построения нейронных сетей. Воронеж, Scan Engineering Telecom, 1999.

58. Программируемые логические интегральные схемы фирмы Xilinx. Каталог продукции. Воронеж. Scan Engineering Telecom, 1999.

59. Прэтт У. Цифровая обработка изображений. В 2-х книгах. Пер. с англ. М.: Мир, 1982. Кн. 1 - 312 е., кн. 2 - 480 с.

60. Разработка САПР. В 10-и книгах, А. В. Петров, В. М. Черненький. Проблемы и принципы создания САПР. Кн. 1. М.: Высш. школа. 1990. -144 с.

61. Распознавание образов: состояние и перспективы: Пер. с англ./ К. Верхаген, Р. Дейн, Ф. Грун и др. М.: Радио и связь, 1985. - 104 с.

62. Роджерсон Д. Основы СОМ. Пер. с англ. М.: Издательский отдел "Русская редакция" ТОО <Channel Trading Ltd.>, 1997. - 376 с.71 .Розенблат Ф. Принципы нейродинамики. М.: Мир, 1965. - 302 с.

63. Страуструп Б. Язык программирования С++: Пер. с англ. М.: Радио и связь, 1991.-352 с.

64. Тиори Т., Фрай Дж. Проектирование структур баз данных: В 2-х кн. Кн. 1. Пер. с англ. М.: Мир, 1985. - 287 с.

65. Тиори Т., Фрай Дж. Проектирование структур баз данных: В 2-х кн. Кн. 2. Пер. с англ. М.: Мир, 1985. - 320 с.

66. Трикоз Д. В. Нейронные сети: как это делается? //Компьютеры + программы, 1993. -N4(5). С. 14-20.

67. Тэнк Д. У., Хопфилд Д. Д. Коллективные вычисления в нейроноподобных электронных схемах //В мире науки, 1988.-N2-C. 44- 53.

68. Универсальная плата цифровой обработки сигналов XDSP-680: Техническое описание. Воронеж, Scan Engineering Telecom, 1998.

69. Фу К. Структурные методы в распознавании образов: Пер. с англ. М.: Мир, 1977.-320 с.

70. Фукунага К. Введение в статистическую теорию распознавания образов: Пер. с англ. М.: Мир, 1977. - 320 с.

71. Цуприков С. Нейронные вычисления берутся на вооружение финансистами //Moscow: Computerworld, 1985 N 7 - с. 57- 58.81 .Цыпкин Я. 3. Адаптация и обучение в автоматических системах. М.: Наука, 1968.- 256 с.

72. Шеперд Г.М. Нейробиология. В 2-х томах. М.: Мир. - 1987.

73. Шумский С. А., Яровой A.B., Зорин O.J1. Система контекстной категоризации и ассоциативного поиска текстовых документов // Сборник докладов V Всероссийской конференции "Нейрокомпьютеры и их применение", М.: Радио и связь, 1999. С. 125-129.

74. Эксаревский A.B., Борисов B.J1. Нейросетевая информационная система для поиска объектов по фотографии // Интеллектуальные информационные системы: Тр. Всерос. конф. Воронеж: ВГТУ, 1999 - С. 211.

75. Эксаревский A.B., Борисов B.JI. Применение нейронных сетей для индексирования больших двоичных объектов в базе данных// Интеллектуальные информационные системы: Тр. Всерос. конф. Воронеж: ВГТУ, 1999-С. 216.

76. Эксаревский A.B., Воищев A.B. Проектирование подсистемы ассоциативного поиска в базе данных на основе нейронных сетей // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр. Воронеж: ВГТУ, 1999 - С. 43-48.

77. Эксаревский A.B., Эксаревская М.Е., Борисов B.JI. Нейросетевой алгоритм индексирования изображений в системе управления базами данных // Математическое моделирование систем. Методы, приложения и средства: Тез. конф. Воронеж: ВГУ, 1998. - С. 67.

78. Яншин В.В., Калинин Г.А. Обработка изображений на языке Си для IBM PC: Алгоритмы и программы. М.: Мир, 1994.- 240 с.

79. Содержимое заголовочного файла с описаниями общих интерфейсов системыассоциативного поискаif clef WIN32 include <windows.h> encli f

80. Интерфейс управляющего модуля :lass CAssocIndexMainlnterfасеubl ic :virtual long GetlnputSize() = 0; virtual short GetlnputElementSize() = 0;virtual BOOL GetlnputPortion (long startpos, long length,

81. BYTE *buf) = 0; virtual void SetOutputSize(long size) = 0; virtual void SetOutputElementSize(short size) = 0; virtual BOOL SetOutputPortion(long startpos, long length,

82. Описание значения параметров struct pmival {pmi^type type; // тип значенияunion {short smallint; long integer; double dbl;val; // общая область для представления значения

83. Описание параметра struct pmiparaminfо {char *szName; // имя параметраpmival info; // тип и значение по умолчанию;

84. Error = states pState. trainpatterns[pErrorPattern+ + ]; Error *= Error; ErrorSum += Error; pState--;

85. Конец цикла обучения eturn ErrorSum;