Содержание к диссертации
Введение
Глава 1. Обзор смежных областей 14
1.1. Концепция универсального сервера 14
1.2. Методы идентификации и сравнения нетрадиционных типов информации 19
1.3. Нейронные сети и идентификация 26
1.4. Ассоциативно-пульсационные нейронные сети 32
1.5. Выводы 33
Глава 2. Математическая модель использования р-нейронных сетей в системах обработки и хранения информации 34
2.1. Методы исследований 34
2.2. Основные алгоритмы 35
2.3. Формирование описывающих векторов 37
2.3.1. Элементы нейронной сети 37
2.3.2. Потоки данных в нейронной сети 37
2.3.3. Структура нейронной сети 38
2.3.4. Абстрагирующий слой 39
2.3.4.1.Топология абстрагирующего слоя 39
2.3.4.2. Структурная схема примитивов абстрагирующего слоя 42
2.3.4.3.Функционирование примитивов абстрагирующего слоя 45
2.3.4.4.Работа абстрагирующего слоя 46
2.3.5. Слой ассоциации 50
2.3.5.1. Топология слоя ассоциации 50
2.3.5.2.Структурная схема примитивов слоя ассоциации 50
2.3.5.3.Функционирование примитивов слоя ассоциации 52
2.3.5.4. Работа слоя ассоциации 52
2.3.6. Слой приведения 53
2.3.7. Блок принятия решения 58
2.3.8. Работа р-нейронной сети 61
2.4. Сравнение векторов сверток 61
2.4.1. Основные принципы сравнения 61
2.4.2. Алгоритмы сравнения, устойчивые к параллельным искажениям 65
2.5. Выводы 68
Глава 3. Реализация системы получения описывающих векторов 69
3.1. Реализация пульсационной-нейронной сети 69
3.1.1. Общее описание программного комплекса и комплексаработ 69
3.1.2.Состав программного комплекса 71
3.1.3.Результаты работы 72
3.2. Общие принципы реализации нейронной сети на основе р-нейронов 74
3.2.1. Топология слоев 74
3.2.2. Реализация блока принятия решения 75
3.2.3.Реализация слоя предворительной обработки 77
3.2.4.Реализация абстрагирующего слоя 77
3.2.5.Реализация слоя ассоциации 83
3.3. Модифицированные свертки 92
3.4. Описание объектов, наложенных друг на друга 93
3.5. Применение системы идентификации в хранилищах данных...95
3.5.1. Общие принципы 95
3.5.1. Обработка информации на этапе ввода в хранилища данных 96
3.5.2. Поиск информации 98
3.5.2.1. Поиск по образцу 98
3.5.2.2. Поиск при помощи запросов 100
3.5.3. Обучение системы 102
3.6. Индексирование данных 102
3.6.1. Общий подход 102
3.6.2. Дерево уточняющего ассоциативного поиска 103
3.6.3. Дерево максимального различия "потомков" 105
3.7. Выводы 106
Глава 4. Оценка эффективности 107
4.1. Оценка системы с точки зрения универсального сервера 107
4.2. Сравнительный анализ характеристик данной системы 109
4.3. Сравнительный анализ характеристик системы при работе с текстовой информацией 113
4.4. Выводы 114
Заключение 116
Публикации 120
Список использованных источников 121
Словарь терминов и сокращений 127
- Методы идентификации и сравнения нетрадиционных типов информации
- Структурная схема примитивов абстрагирующего слоя
- Обработка информации на этапе ввода в хранилища данных
- Сравнительный анализ характеристик данной системы
Введение к работе
Объект исследования
Распознавание образов[20,21,24-28,44,47] представляет собой направление, связанное с разработкой методов и построением систем для установления принадлежности некоторого объекта к одному из заранее выделенных классов объектов[8,18,40]. Процесс распознавания основан на сопоставлении признаков, характеристик исследуемого объекта с признаками, характеристиками других известных объектов, в результате чего делается вывод о наиболее правдоподобном их соответствии. Адаптивное распознавание представляет собой способность адаптации в процессе распознавания образов, то есть динамическую настройку к конкретным входным данным[6,13,14,11]. Данные методы на практике широко используются для организации нечеткого поиска информации в хранилищах информации (ХИ), поисковых системах, аналитических системах, корпоративных системах, системах искусственного интеллекта (СИИ). Под нечетким поиском понимается возможность найти достаточно близкое приближение к запрошенному образцу информации[21,22]. Нечеткий поиск устраняет необходимость знать точное написание каждого термина или представлять для поиска точное изображение.
Можно выделить два направления исследований в данной области -это расчет близости (похожести) объектов[17] и построение индексов для быстрого поиска таких объектов. Каждое направление на сегодняшний момент является актуальным.
Актуальность проблемы
Сегодня начали предъявлять к серверам данных все более серьезные требования, и вследствие этого выяснилось, что стандартные файловые
системы не вполне пригодны для вычислений в новых условиях. Поэтому все более пристальное внимание начинают привлекать базы данных. Известно, что в файловой системе пользователь осуществляет навигацию на основе имен файлов, типов файлов и т.п. Это приемлемо только для управления относительно небольшим количеством данных. Для больших объемов удобнее использовать системы управления базами данных (СУБД), обеспечивающие быстрый и удобный доступ к данным посредством запросов. Они представляют собой надежную платформу для построения приложений, осуществляющих высокоскоростные транзакции, однако их слабая сторона - управление сложными типами данных [22,31]. К таким данным принято относить двумерную графику, трехмерные сцены, звуковую информацию, временные ряды, видеоинформацию и т.п. В отдельную категорию принято выделять картографическую информацию. В СУБД такие данные, как правило, хранятся в формате LOB (большие двоичные объекты), который накладывает ряд ограничений. Там так же часто хранят HTML- и VRML-документы, а также Java-апплеты и сервле-ты.
Ситуация в компьютерной индустрии складывается таким образом, что рост популярности данных нетрадиционных типов не учитывать нельзя [27]. Во-первых, значительно увеличивается количество разрабатываемых мультимедийных проектов. В среднем, каждый такой проект включает сотни тысяч звуковых, видео, анимационных и других объектов, которые используются многократно. Разработчик, пытаясь найти объект по имени файла, рискует заблудиться в длинном алфавитном списке. Так, некоторые разработчики утверждают, что на поиск ранее созданных объектов у них уходит от 10 до 20% рабочего времени. Причем данные недостаточно просто разместить на сервере, а необходимо регулярно обновлять. Эти данные требуют эффективного управления. Обычные файловые сие-
темы справиться с этой задачей не в состоянии. Использование СУБД также не решит всех проблем. Для решения этой проблемы нужны новые технологии, основанные на распознавании образов, в том числе адаптивном, а также нечетком поиске.
Подобные проблемы наблюдаются в области создания аналитических систем. Аналитические системы для поддержки принятия решений используются в самых разнообразных сферах. Например, в коммерции, торговле, финансах, в государственной деятельности, разведке, в работе юридических служб и законодательных органов и т. д. Для выработки корректного решения системный аналитик должен получать данные из самых разных источников: внутренних и внешних баз данных, архивов, электронных статистических сборников и справочников[23,29]. Кроме того, он должен принимать во внимание оперативно поступающую информацию. Качественная работа аналитика невозможна без использования информационных ресурсов сети Internet, куда, по некоторым оценкам, каждый день добавляется терабайт новой информации. Для успешного ведения системных исследований в таких условиях требуются соответствующие инструментальные средства, позволяющие ежедневно анализировать гигабайты данных всевозможных типов. Средства поиска данных играют определяющую роль в обеспечении эффективности и производительности аналитической системы в целом. Однако, помимо поисковых средств система управления должна иметь ряд дополнительных, функциональных возможностей, отличающих ее от обычной информационно-справочной системы, а именно:
- сочетание средств ретроспективного анализа с оперативным досту-
пом к информации, поступающей в режиме реального времени;
- структурирование результатов исследований;
- поддержка и совместное использование структурированной информации, неструктурированных текстов, графики, видео и т. п.
В данной ситуации также невозможно решить все проблемы традиционными средствами. В частности, нельзя для хранения информации ограничиться традиционными СУБД. Традиционные системы поиска информации развивались в тесной взаимосвязи с СУБД (РСУБД, ОРСУБД), поэтому они были ориентированы в основном на работу с относительно простыми или структурированными типами данных. Но при обработке произвольной цифровой информации средства SQL СУБД оказываются малоэффективными. Большинство реляционных процессоров использует индексы В-Тгее, хорошо подходящие для поиска текста и численной информации в стандартных реляционных таблицах, но они малопригодны для работы с изображениями и другой мультимедийной информацией. Для работы с ней необходимо реализовать возможности сравнения, идентификации и классификации с применением технологий нечеткого поиска. Очевидно, что традиционные методы СУБД и РСУБД для этого не годятся [27].
В настоящее время ведутся работы по созданию систем, способных решать эти проблемы, есть некоторые результаты, но также еще очень много нерешенных проблем [56,57], очевидно, не хватает новых технологий в этой области. В частности, шире должны использоваться системы адаптивного распознавания образов для ускорения поиска информации [13,32].
Проблема приближенного поиска графической информации в ХД стоит достаточно остро. Человек не всегда может точно сформулировать, что он хочет найти, часто он может это представлять лишь примерно [20]. Современные СУБД, ориентированные на концепцию уни-
версального сервера (КУС) предоставляют удовлетворительные возможности нечеткого поиска для полнотекстовой информации [9-13]. Хуже обстоит дело с подобными возможностями для графической информации [31]. Хорошие результаты здесь показывают лишь узкоспециальные системы, способные работать только в своей сверхузкой области. Подобные проблемы есть и с аудио информацией и другими видами информации.
Остроту вышеописанных проблем, в некоторой степени, способно снять использование пульсационных нейронных сетей специального вида для обработки информации. В частности, возможно использование PCNN (Pulse-Coupled Neural Network) [47,49,53] - пульсационно-ассоциативных нейронных сетей и сетей на р-нейронах (р-НС) [29,31,32], а также построенного на их основе специализированного метода обработки информации [27].
Цель диссертационной работы
Цель диссертационной работы - разработать метод адаптивного распознавания образов, применимый на практике и способный работать со сложными типами данных, например: двухмерная графика, трехмерные сцены и др. Эта разработка должна способствовать ускорению таких операций, как идентификация, классификация, поиск, в том числе нечеткий. Данная разработка должна проверить границы применимости пульсационных нейронных сетей (ПНС), для решения поставленной задачи, на примере двумерных графических изображений.
Решение этой научно-технической задачи позволит работать со сложными типами данных в реальном режиме времени. В частности, двух-, трехмерной графикой, полнотекстовой информацией, а в перспективе с аудио и др.
Решение этой научно-технической задачи позволит выполнять такие операции, как: сравнение по выбранным параметрам, идентификация, классификация, поиск, в том числе нечеткий.
На данном этапе необходимо не только идентифицировать данные, но и выявлять все множество близких данных, особенно это актуально применительно к нестандартным типам. Например, очевидно, что даже одно и то же графическое изображение, отсканированное два раза, из-за искажений может различаться, поэтому необходимо использование методов приближенного поиска, которые позволят выявлять такие скрытые дубли в ХД, а также позволят находить изображения близкие к данным. Такие же примеры можно привести и в отношении звуковой информации, трехмерных сцен и т.п. Такие возможности позволят как экономить время на поиске информации, так и осуществлять эти операции на новом уровне.
Диссертационная работа направлена на оптимизацию методов нечеткого поиска. Так операции поиска, сравнения и идентификации должны быть построены исходя из критериев максимальной распознаваемости и минимальной избыточности информации, а также максимальных скоростных характеристик.
Направление исследований
Основным направлением исследования, для решения поставленной задачи, были выбраны пульсационные нейронные сети специального вида. Такие сети выполняют три операции над данными:
фильтрация;
абстракция данных;
ассоциация данных.
Было разработано семейство сетей с последующим сравнением их методами имитационного моделирования. Оценивались следующие параметры:
быстродействие создания описывающего вектора;
объем описывающего вектора;
адекватность описания исходной информации;
скорость поиска исходной информации по описывающему вектору.
Методика исследований
Основным методом исследований было создание математических моделей и их оценка по результатам имитационного моделирования. Как критерии были выбраны несколько параметров: быстродействие, объем описывающего вектора, адекватность описания исходной информации, скорость поиска. Результаты экспериментов сравнивались как между собой, так и с результатами работы других методов.
На защиту выносятся
Метод обработки данных, основанный на автоматическом абстрагировании и автоматической ассоциации данных.
Структура пульсационной нейронной сети.
Схемы функционирования пульсационной нейронной сети.
Примитивы абстрагирующего слоя сети.
Примитивы ассоциирующего слоя сети.
Метод индексирования СТД для адаптивного распознавания образов.
Научная новизна
Предложена математическая модель адаптивного распознавания образов на основе пульсационных нейронных сетей (ПНС).
Разработана структура, примитивы, способ функционирования специализированной ПНС.
Показана возможность использования ПНС для адаптивного выделения информации в целях последующих операций классификации, идентификации и сравнения СТД.
Разработан способ индексирования СТД, выделенных при помощи ПНС для последующего быстрого поиска, в том числе нечеткого.
Практическая полезность
Эмпирически доказана возможность построения универсальных систем адаптивного распознавания образов.
Эмпирически доказана возможность построения специализированных систем адаптивного распознавания образов на основе ПНС.
Эмпирически доказана возможность построения ассоциативной памяти на сотни тысяч записей СТД.
Эмпирически доказано ускорение операций поиска информации в хранилищах данных, в том числе нечеткого, а также операций идентификации и классификации для СТД.
Апробация работы
1. Результаты исследований были оформлены в виде программного продукта - библиотеки классов, который представляет собой реализацию описанного в диссертационной работе метода. На библиотеку было получено регистрационное свидетельство (РОСПАТЕНТ per. № 2002610360, при-
ложение № 4). Данный программный продукт был успешно внедрен на практике, а именно:
а) в системе распознавания и идентификации адреса почтового от
правления в ГЦ МПП (Главный Центр Магистральных Перевозок
Почты, приложение № 2);
б) В системе идентификации изменений в изображении охраняемых
объектов (разработка ЗАО «РосСфера»);
Программный комплекс распознавания и идентификации адреса почтового отправления был представлен:
на всероссийской выставке «Связь: почта, телеграф, телефон.», Москва, 8-12 сентября 2001 г.;
на всероссийской специализированной выставке «Русская тройка», Санкт-Петербург, 22-24 сентября 2001 г.
Программный продукт, на основе данной модели, был успешно внедрен на практике. Это свидетельствует о работоспособности системы и подхода в целом, что подтверждено соответствующим актом о внедрении.
2. Был создан программный комплекс для исследования свойств пуль-сационных нейронных сетей. Он использовался как лабораторный комплекс в проведенных исследованиях.
Результаты работы используются в учебном процессе кафедры МОВС МИРЭА(ТУ) в курсе «Базы данных» (приложение № 3).
Результаты работы апробированы в докладах на конференциях и семинарах:
49-ая научно-техническая конференция МИРЭА (21 мая 2000 г.);
научно-практическая конференция в рамках всероссийской программы «Электронная Россия» «Современные информационные технологии в управлении и образовании - новые возможности и перспективы» (18,19 февраля 2001 г.);
50-ая юбилейная научно-техническая конференция МИРЭА (10-18 мая 2001 г.);
научно-практическая конференция в рамках всероссийской программы «Электронная Россия» «Современные информационные технологии в управлении и образовании - новые возможности и перспективы» (11,12 декабря 2001 г.);
научно-технический семинар «Теория информационных систем», МИРЭА (23 мая 2002);
52-ая научно-техническая конференция МИРЭА (13 мая 2003 г.).
Основные научные результаты
Математическая модель адаптивного распознавания образов на основе ПНС.
Структура, примитивы, способ функционирования специализированной ПНС.
Модель использования ПНС для адаптивного выделения информации в целях последующих операций классификации, идентификации и сравнения.
Модель ускорения операций поиска, в том числе нечеткого, информации СТД в ХИ.
Методы идентификации и сравнения нетрадиционных типов информации
Методы идентификации и сравнения мультимедийной информации строятся на алгоритмах распознавания образов [31,36]. Под распознаванием, понимают отнесение конкретного объекта (реализации), представленного значениями его свойств (признаков), к одному из фиксированного перечня образов (классов) по определённому решающему правилу в соответствии с поставленной целью [7,23-25]. Отсюда следует, что распознавание может осуществляться любой системой (живой или неживой), выполняющей следующие функции: измерение значений признаков, производство вычислений, реализующих решающее правило [26]. При этом перечень образов, информативных признаков и решающие правила либо задаются распознающей системе извне, либо формируются самой системой [21].
Большое количество производителей работает с алгоритмами распознавания образов, но их разработки оптимизированы под определенную задачу и поэтому не годятся для концепции Универсального Сервера.
Основной, используемой сейчас на практике, универсальной технологией в этой области можно назвать технологию адаптивного распознавания образов. Например, система построенная на таких принципах -APRP (Adaptive Pattern Recognition Processing) [20] фирмы Convera (Excalibur Technologies Corp.), - это технология адаптивного распознавания образов в «чистом виде» , разработанная около 30 лет назад доктором Джеймсом Дау III (James Dow III). Ядро технологии выросло из его работ, посвященных изучению и разработке сетевых моделей, способных идентифицировать, или, точнее, распознавать присутствие тех или иных образов в составе данных специфического вида. В своей работе, связанной с изучением физиологии центральной нервной системы земноводных существ, Дау пытался понять, как лягушки с их ограниченными зрительными способностями распознают объекты окружающего их мира. Модель зрительного аппарата земноводных и была положена доктором Дау в основу его технологии индексирования данных и нечеткого поиска. В результате был создан комплекс методов, способных адаптироваться к особенностям обрабатываемой информации.
Основу поискового механизма составляет нейронная сеть [39,48], позволяющая выделять в зашумленной битовой последовательности "похожие фрагменты", не требуя точного контекстного совпадения запроса и фрагмента. В результате оказывается, что системе безразлично к информации какого вида относится битовая последовательность и что ищется: текст, звук, изображение и т.п. Такой способ поиска относится к разряду нечеткого [23]. Он строится на постулате - чем больше фрагментов совпадает, тем больше вероятность, что это то, что мы ищем. Такой поиск позволяет определять степень совпадения найденной информации с запросом. Вы можете сформулировать эффективный запрос по неточным образцам [21,25]. Получив запрос найти какой-либо объект, подобная система просматривает образы и составляет список "ближайших приближений" к тому, что было описано в запросе. Затем система упорядочивает содержимое этой области по степени вероятности того, что тот или иной найденный на этом объект является истинной целью поиска. Можно установить "ближайшую десятку", "ближайшую сотню" и т. д. Это потенциально создает среду поиска, в которой пользователь может проводить поиск в интерактивном режиме, чтобы найти ответ, предварительно не определив точно, что же является ответом. Другой пример - RCO[57], разработанная для совместной работы с Oracle interMedia, здесь подобная технология применяется для работы с полнотекстовой информацией. Алгоритмы RCO[10-15], используемые при реализации нечеткого поиска, основаны на так называемой "системе ассоциативного" доступа. Такую систему можно классифицировать как ассоциативную память большой емкости. Для ускорения поиска предварительно создается индекс, содержащий фрагменты информации со ссылками на источник, в которых эти фрагменты встретились. Таким образом, происходит поиск исходной информации, фрагменты которой совпадают с фрагментам в запросе. Задавая длину фрагментов и их количество, можно регулировать полноту поиска — производить отбор по степени близости к запросу.
Каждому элементу, обрабатываемому данными способами, ставится в соответствие некоторый вектор признаков - дескриптор. На основе дескрипторов автоматически устанавливаются гиперссылки, а в процессе поиска дескриптор шаблона сравнивается с дескрипторами данных, хранящихся в базе. В итоге выдается список, ранжированный по степени сходства с образцом. При этом пользователь может задавать различные весовые коэффициенты для сравниваемых параметров (для графических изображений, например - это может быть композиция, цвет, контрастность). Следует отметить, что сравнение проводится по объективным критериям, а не по субъективным признакам, воспринимаемым только человеком. Поэтому информация, близкая по заданным объективным параметрам, может быть отличная друг от друга по существу.
Под нечетким поиском понимается возможность найти достаточно близкое приближение к запрошенному термину, фразе или изображению. Нечеткий поиск устраняет для пользователя необходимость знать правильное написание каждого термина, с которым он работает или представлять для поиска точное изображение. Таким образом, автоматически становится допустимой ошибка, как во входных данных, так и в терминах запроса. Используя эту технологию всегда можно найти ближайшее приближение к элементам, заданным в качестве объектов поиска. Нечеткий поиск, например, полезен в ситуациях, когда ввод данных осуществляется с помощью оптического распознавания символов, так как процесс OCR, как уже говорилось, не является на 100% точным даже при очень высоком качестве печати. Например, если на данной странице с помощью OCR не удалось абсолютно правильно считать ни одного слова, практически никакая система четкого поиска не имеет шансов добиться успеха при поиске этой страницы.
Структурная схема примитивов абстрагирующего слоя
Одним из важнейших направлений повышения эффективности управления в любых облостях человеческой деятельности является ускорение процессов обработки информации. В последнее время все больший вес и значимость приобретают такие специфические ее виды как двумерная графика, звук, трехмерные сцены и т.д. На сегодняшний день существует много подходов для решения проблем связанных с такими видами информации, но все они имеют свои недостатки. Большое количество производителей работает с алгоритмами распознавания образов, но их разработки оптимизированы под определенную задачу. Существует ряд относительно универсальных систем, но их практическое использование затруд-ненон из-за ряда недостатков. Очевидно, что не хватает новых технологий в этой области. Одним из новых подходов - это технологии на основе пульсационных нейронных сетей. В частности ассоциативные-пульсационные нейронные сети - третье поколение нейронных сетевых моделей, которые построены на импульсных нейронах, и следовательно, намного ближе к естественным нейронным сетям описанным в биологии, чем классическая искусственная нейронная сеть.
В основе моделирования лежит теория подобия [3] которая утверждает, что абсолютное подобие может иметь место лишь при замене одного объекта другим, точно таким же. В общем случае при моделировании абсолютное подобие не имеет места и исследователь стремится к тому, чтобы модель достаточно хорошо отображала исследуемую сторону функционирования объекта. В нашем случае была создана методами аналитического моделирования [37] математическая абстракция - р-нейронная сеть [32], посредством которой можно осуществлять адаптивное распознавание образов. В общем виде без детальной проработки р-нейронная сеть мало пригодна на практике. Детальная же ее проработка была осуществлена при помощи методов имитационного моделирования, то есть в данной работе был использован комбинированный аналитико-имитационный метод.
Р-нейронная сеть на практике превратилась в целое семейство сетей [29] близких по структуре, но с разными характеристиками. Имитационные исследования позволили выбрать оптимальные модели для практического использования в определенных условиях, а также уточнить идеологию систем, в которых могут использоваться данные технологии.
Ввиду специфики задачи, очевидно, что на определенном этапе имитационное моделирование превращается в так называемый производственный эксперимент, т.к. задача построения модели адаптивного распознавания образов подразумевает, как итог, построение некой работоспособной системы, основанной на этих принципах. Задача такой системы - сравнение, идентификация и классификация информации.
Для успешной работы со сложными типами данных, в том числе и с данными мультимедиа, нужны несколько иные подходы [31 ] для организации хранения и обработки, чем для традиционных данных. Иной подход обусловлен более сложной структурой, и, как правило, большим объемом. Для ускорения поиска и обработки таких данных прибегают к следующей схеме. На этапе ввода информации в хранилища данных формируются описывающие вектора (дескрипторы), соответствующие каждому образцу. По этим векторам в последующем можно сравнить саму исходную информацию. В связи с этим всю систему поиска условно можно разбить на три части: 1) формирование описывающего вектора; 2) сравнение описывающих векторов; 3) дораспознавание информации. Основа подхода, описанного в данной диссертационной работе -это формирование описывающих векторов определенного вида. Описывающие вектора получаются как результат работы нейронной пульса-ционной сети, состоящей из двух основных слоев: абстрагирующего и ассоциирующего, а также одного вспомогательного слоя, предназначенного для предварительной обработки данных. В двух основных слоях обработка данных происходит не однократно, а по замкнутому циклу до выполнения определенных условий. Вспомогательный слой построен на основе слоя, применяющегося в пульсационно-ассоциативных нейронных сетях (PCNN - Pulse-Coupled Neural Networks) [47,49,53]. Такие сети способны выделять отдельные объекты или области из общего изображения в случае, если речь идет об изображениях или трехмерных сценах. Они способны выделять и/или группировать некие составляющие информации по определенным признакам. Основные слои работают с данными, полученными этим слоем. Второй слой выполняет операцию абстракции данных, результатом его работы является вектор, описывающий отдельные объекты изображения. Третий слой группирует некоторые объекты и область по заданным правилам -выполняет операци р-ассоциации. В результате работы слоев получается описывающий вектор.
Второй этап предлагаемого подхода - сравнение описывающих векторов либо статистическими методами, либо посредством нейронных сетей для идентификации, сравнения, классификации исходной информации. Иными словами, анализируя описывающие векторы, делаются выводы относительно исходной информации.
В настоящей работе также рассмотрены способы индексации данных и дескрипторов для ускорения поиска исходной информации. Корме того приведены модели и примеры использования данного подхода в хранилищах данных, в том числе в универсальных серверах.
Обработка информации на этапе ввода в хранилища данных
В состав программного комплекса входит СУБД InterBase, расширенная посредством UDF дополнительными возможностями, в частности, такими как: - построение специального индекса для ускорения поиска информации; - расчет близости (схожести) образцов; - подготовка данных для построения дескриптора исходного образца; - обеспечение управления созданием гиперссылок между образцом и дескриптором; управление процессом поиска информации по шаблону; управление процессом поиска информации по образцу. В состав программного комплекса входит также программа, являющаяся интерфейсом между пользователем и системой в целом. Она позволяет пользователю (экспериментатору): - формировать библиотеку изображений; - управлять библиотекой изображений; - управлять процессом получения дескриптора; - производить наблюдение за процессом получения дескриптора на всех этапах; - получать данные для формирования запросов к системе на предмет поиска интересующих изображений; - собирать и отображать данные для оценки работы алгоритмов, примененных в системе; - визуализировать процессы, происходящие в слоях р-НС. В данный программный комплекс также входит ряд утилит и программ для решения следующих задач: - предварительная обработка изображений; - создание специальной структуры БД; - сбор статистических данных в БД. Были сгруппированы в отдельную библиотеку объекты (классы C++), посредством которых производятся: - операции расчета близости; - операции индексирования данных; - операции идентификации. Некоторые итоги работы были оформлены в виде библиотеки классов для адаптивного распознавания образов FUNSR (РОСПАТЕНТ per. № 2002610360, приложение № 4). Данная библиотека позволяет эмулировать пульсационные нейронные сети специального вида на основе пульсационно-абстрагирующего и пуль-сационно-ассоциирующего слоев для обработки одномерных и двумерных данных разного происхождения. Посредством подобной обработки создаются дескрипторы для последующего распознавания образов на их основе. Библиотека также содержит примитивы для построения сетей для данных большей мерности. Для сравнения дескрипторов библиотека содержит средства расчета близости дескрипторов, полученных вышеописанным способом как в целом, так и поэлементно. Библиотека содержит специализированный класс для работы с текстовой информацией, позволяющий сравнивать ее на предмет близости, строить специализированный индекс для нечеткого поиска. Библиотека написана на языке C++ и предназначена для ЭВМ IBM PC 386 и выше под управлением ОС Windows 95/98/Me/NT/2000/XP.
Библиотека была использована в качестве ядра программы распознавания почтовых адресов, что зафиксировано соответствующим актом о внедрении. Технология была представлена на всероссийской выставке «Связь: почта, телеграф, телефон» в 2001 году, где получила положительные отзывы, а также была представлена на отраслевой почтовой выставке в 2001 году в Санкт-Петербурге. Программа внедрена в производственный процесс в ГЦ МПП (Главный Центр Магистральных Перевозок Почты, приложение № 2). При создании данного программного продукта были опробованы на практике модели и методы, описанные в диссертации. Практика показала жизнеспособность предложенного подхода и сравнительно достаточную производительность вышеописанной библиотеки.
Данная библиотека классов используется в разрабатываемом комплексе по охране объектов. В частности, экземпляры классов библиотеки, эмуирующие работу нейронной пульсационнои сети, производят первичную обработку изображений, поступающих от видеокамер, а также они отвечают за отсев визуальноблизких изображений на этапе записи в хранилище данных.
Р-нейронная сеть (р-НС) в данном программном комплексе ориентирована на работу с двумерной графикой. Для слоев абстрагирования и ассоциации в рамках одной нейронной сети выбиралась одинаковая топология. Для разных р-НС были использованы два вида топологии. 1)Топология х/4. В этом случае один нейрон имеет 4 двунаправленные связи (или 8 однонаправленных) с четырьмя соседними нейронами (рис.3.1а). 2)Топология х/8. В этом случае один нейрон имеет 8 двунаправленных связей (или 16 однонаправленных) с восемью соседними нейронами (рис.3.16). Блок принятия решения (БПР) в использованных сетях реализован как переключатель потоков данных с заранее фиксированной программой переключений. Программа переключений выбиралась в процессе того или иного опыта. В нашем случае были использованы следующие программы переключений:
Сравнительный анализ характеристик данной системы
Концепция универсального сервера накладывает на хранилища данных определенные ограничения. В первую очередь, они должны работать с любыми типами данных, в том числе с большими бинарными объектами любого рода.
Сервера баз данных, на основе которых создаются хранилища данных, обладают несколькими критическими ресурсами, такими как объем памяти для хранения данных и время доступа к данным. Концепция УС, в первую очередь, выдвигает высокие требования к времени доступа к данным. Очевидно, что одним из основных препятствий здесь является поиск данных. Для ускорения поиска сложных типов данных есть несколько возможностей, одна из них: создание и хранение дескрипторов, наравне с исходными данными. Это позволит сэкономить время на поиске информации, так как именно дескрипторы индексируются для ускорения поиска. Нужно заметить, что для некоторых типов это единственный универсальный способ поиска информации, например, для графических изображений. Данная система удовлетворяет требованиям КУС. С другой стороны, объемы дескрипторов должны быть относительно небольшими. Это позволит не занимать лишнюю память для их хранения. Как видно из таблицы 3.5 и таблицы 3.6 пункта 3.2.5, данная система имеет возможности по варьированию этого параметра в широких пределах.
Очевидно, что в некоторых случаях удобно не хранить исходную информацию, например, в случае отслеживания прохождения информации в операционных базах данных и т. п. Для этого дескриптор должен быть достаточно информативным. Проведенные опыты (табл. 1.6.) позволяют сказать, что системы, построенные на вышеописанных принципах, позволяют это делать.
Методы сравнения сложных типов данных в универсальных серверах должны быть наиболее быстрыми и эффективными. Для первичного, "грубого" поиска вполне достаточно адаптивного метода. Это самый быстрый, но иногда не самый точный метод. Для уточнения результатов поиска в таких случаях следует использовать методы корреляционного анализа. Дескриптор, полученный вышеописанным способом, позволяет такие операции.
Схема, предложенная в настоящей диссертационной работе, целиком удовлетворяет концепции УС. Помимо объектно-ориентированного подхода, который предполагает данная схема, она работает на основе дескрипторов. Такой дескриптор может быть создан в любой момент времени и легко может храниться в базе данных наряду с исходной информацией ввиду своего небольшого объема. В то же время такой дескриптор достаточно информативен и может использоваться без исходной информации. Подобные дескрипторы можно сравнивать как при помощи корреляционного и кластерного анализа, так и посредством нейронных сетей.
Для оценки эффективности данной системы, построенной на основе пульсационной нейронной сети (р-НС), необходимо выбрать параметры оценки. К таким параметрам можно отнести: - объем описывающего вектора; - скорость создания описывающего вектора; - скорость поиска информации по описывающему вектору; - идентифицируемость информации по описывающему вектору; Как видно из главы 3, данная система создает маленький по объему описывающий вектор (от 0,001% до 0,3% от исходного изображения) в зависимости от характера изображений (табл.3.4, 3.5, 3.6). Эта система может достаточно эффективно работать с фотографическими изображениями, рисунками, чертежами и др. технической документацией. Данная система отлично работает с текстовой информацией. Так как она построена на принципах оценки внешней схожести, то у неё не возникнет проблем с идентификацией текста, который выглядит внешне одинаково (например, идентификации одной и той же страницы, изображенной в графическом формате), данная система может текстовую информацию рассматривать как рисунок без анализа содержимого текста. Описанный выше лабораторный комплекс не ориентирован на работу с текстовой информацией. Однако, существует система, построенная на тех же принципах, но ориентированная на текстовую информацию, которая с успехом применяется на практике в ГЦ МПП (Главный центр магистральных перевозок почты), о чем свидетельствует соответствующий акт о внедрении. Сравним объемы описывающих векторов, полученные с использованием алгоритма, описанного в настоящей диссертационной работе и полученные алгоритмами других систем. Для такого сравнения возьмем наиболее близкую систему на основе APRP. Эта система применяется на практике, например, в некоторых программных продуктах Informix (Informix Universal Server).
