авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 |

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

-- [ Страница 1 ] --


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

Митрофанов Андрей Андреевич

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

05.13.18 – Математическое моделирование,

численные методы и комплексы программ

Автореферат

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

кандидата физико-математических наук

Саратов – 2013

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

Научный руководитель: кандидат физико-математических наук,

доцент Папшев Сергей Владимирович

Официальные оппоненты: Шульга Татьяна Эриковна

доктор физико-математических наук, доцент, ФГБОУ ВПО «Саратовский государственный технический университет имени Гагарина Ю. А.», заведующая кафедрой «Прикладная информатика и программная инженерия»

Богомолов Сергей Анатольевич

кандидат физико-математических наук,
доцент, ФГБОУ ВПО «Саратовский экономический институт Российского социально-экономического университета

РЭУ имени Г.В. Плеханова», доцент

кафедры «Прикладная математика

и информатика»

Ведущая организация: Институт проблем точной механики
и управления Российской академии наук (г. Саратов)

Защита диссертации состоится 8 июля 2013 г. в 13 часов на заседании диссертационного совета Д. 212.242.08 при ФГБОУ ВПО «Саратовский государственный технический университет имени Гагарина Ю.А.» (410054, г. Саратов, ул. Политехническая, 77, корп. 1, ауд. 319).

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

Автореферат разослан «___» июня 2013 г.

Ученый секретарь

диссертационного совета А. А. Терентьев

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

Актуальность темы. Задачи распознавания состояния (идентификации) объекта на основе анализа априорной информации встречаются при анализе различных технических, социальных и экономических систем. К ним относятся, в частности, задачи технической и медицинской диагностики, геологической разведки, социального и экономического прогнозирования и пр.

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

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



Развитию методов тестового распознавания посвящены работы Ю. И. Журавлева, А. Е. Андреева, Э. Э. Гасанова, В. Б. Кудрявцева, Е. В. Дюковой, А. А. Кикабло. В этих работах среди прочих рассматривается задача уменьшения числа признаков для распознавания, однако, при этом не учитываются ограничения на ресурсы.

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

Способы формирования множеств признаков для распознавания с учётом ограничений на ресурсы в своих работах рассматривает А. Г. Горелик. Недостатком предложенных им способов является отсутствие возможности параллельного вычисления значений признаков.

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

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

Цель и задачи работы

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

Для достижения указанной цели решаются следующие задачи:

  1. На основе рассмотрения существующих подходов выбрать формальную модель процесса определения состояния (идентификации) объекта в рамках методологии распознавания образов.
  2. Развить математическую модель тестового распознавания образов, позволяющую учитывать ограничения на ресурсы, время и порядок измерения значений признаков.
  3. Разработать методы и алгоритмы формирования тестов, позволяющие снизить затраты ресурсов и времени.
  4. Оценить эффективность предлагаемых методов и алгоритмов путем проведения вычислительных экспериментов.

Объект и предмет исследования

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

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

Для проведения вычислительных экспериментов и моделирования использованы современные аппаратные и программные средства. Реализация алгоритмов выполнена на языке C# в среде программирования MS Visual Studio 2010.

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

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

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

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

Научная и практическая значимость

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

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

Основные положения, выносимые на защиту:

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях:

«Математические методы в технике и технологиях – ММТТ-25», (Волгоград, 2012); «ICIT-2012: Information and Communication Technologies in Education, Manufacturing and Research» (Саратов, 2012); «Перспективы развития информационных технологий» (Новосибирск, 2012); «Системы управления и информационные технологии» (Воронеж, 2013); «Проблемы управления в социально-экономических и технических системах» (Саратов, 2013); «Математические методы в технике и технологиях – ММТТ-26» (Нижний Новгород, 2013).

Работа многократно обсуждалась на научных семинарах кафедры «Информационные системы и технологии» Саратовского государственного технического университета им. Гагарина Ю.А. в 2010-2013 годах.

Публикации. По результатам диссертационной работы опубликовано 8 печатных работ, в том числе 2 статьи в журналах, включенных в перечень ведущих периодических изданий ВАК РФ.

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

Содержание работы

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

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

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

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





Множество признаков является тестом для , если подописания объектов, состоящие из значений признаков из , попарно различны для всех объектов, принадлежащих разным классам.

Тест называется тупиковым, если никакое его собственное подмножество не является тестом.

Тест называется минимальным, если во множестве тестов для не существует теста длины меньшей длины теста .

Множество должно формироваться таким образом, чтобы закономерности, связанные с классификацией на множестве , соответствовали закономерностям на множестве . Для каждого признака , известны нормы затрат различных видов ресурсов и/или времени, которые необходимы для измерения его значения (стоимость измерения признака или просто стоимость признака) – .

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

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

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

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

Различия между объектами можно представить в виде набора из таблиц размерности , строки и столбцы которых соответствуют объектам из . Элемент таблицы содержит значение метрики для объектов и :

Множеством на множестве называется множество, содержащее упорядоченные последовательности метрик для всех пар объектов , которые принадлежит антирефлексивному, симметричному, транзитивному отношению :


где ,, , , – множество эталонных объектов.

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



Pages:   || 2 | 3 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.