Введение к работе
Актуальность темы. Задачи распознавания состояния (идентификации) объекта на основе анализа априорной информации встречаются при анализе различных технических, социальных и экономических систем. К ним относятся, в частности, задачи технической и медицинской диагностики, геологической разведки, социального и экономического прогнозирования и пр.
При этом могут быть использованы методы распознавания образов. Задача распознавания состоит в определении класса некоторого заданного объекта по его описанию и эталонному множеству, содержащему описания объектов, классы которых определены. Объекты могут быть представлены в виде наборов значений некоторых признаков из множества всевозможных признаков, которыми могут описываться объекты. При этом на практике процесс измерения значения каждого признака связан с определёнными ограничениями и затратами ресурсов и времени.
В настоящее время широко применяются методы распознавания образов, основанные на комбинаторном анализе описаний объектов, представленных в виде наборов значений признаков. Этот подход к распознаванию образов берет начало в фундаментальной работе А. И. Чегис и С. В. Яблонского о способах контроля электрических схем и формировании тестов. В терминах распознавания образов тест понимается как подмножество множества признаков объектов, такое, что значения этих признаков различны для всех объектов из разных классов.
Развитию методов тестового распознавания посвящены работы Ю. И. Журавлева, А. Е. Андреева, Э. Э. Гасанова, В. Б. Кудрявцева, Е. В. Дюковой, А. А. Кикабло. В этих работах среди прочих рассматривается задача уменьшения числа признаков для распознавания, однако, при этом не учитываются ограничения на ресурсы.
Получение оптимального решения возможно путём перебора всех возможных вариантов, однако эта задача имеет экспоненциальную сложность.
Способы формирования множеств признаков для распознавания с учётом ограничений на ресурсы в своих работах рассматривает А. Г. Горелик. Недостатком предложенных им способов является отсутствие возможности параллельного вычисления значений признаков.
Ю. А. Бродской рассматривались задачи минимизации затрат ресурсов при распознавании и были предложены методы распознавания объектов при заданных ограничениях, позволяющие строить минимальные и близкие к минимальным тесты. Однако предложенные методы не учитывают возможность внесения корректировок во время выполнения процесса распознавания.
Данная работа посвящена исследованию и разработке математических моделей и методов тестового распознавания образов, которые позволяют учитывать затраты ресурсов и ограничения на порядок проведения работ по измерению значений признаков. В работе приведены методы формирования тестов, которые позволяют учитывать возможность параллельного измерения значений признаков, а также возможность изменения ограничений в процессе распознавания.
Цель и задачи работы
Целью данной работы является разработка математических моделей и методов тестового распознавания образов, отличающихся возможностью одновременно учитывать ограничения на ресурсы, время, порядок измерения работ и возможность параллельного измерения значений признаков.
Для достижения указанной цели решаются следующие задачи:
-
На основе рассмотрения существующих подходов выбрать формальную модель процесса определения состояния (идентификации) объекта в рамках методологии распознавания образов.
-
Развить математическую модель тестового распознавания образов, позволяющую учитывать ограничения на ресурсы, время и порядок измерения значений признаков.
-
Разработать методы и алгоритмы формирования тестов, позволяющие снизить затраты ресурсов и времени.
-
Оценить эффективность предлагаемых методов и алгоритмов путем проведения вычислительных экспериментов.
Объект и предмет исследования
Объектом исследования являются технические, социальные и экономические системы, представимые логическими моделями. Предметом исследования являются модели и методы распознавания образов при ограниченных ресурсах.
Методы исследований. Теоретическую и методологическую базу исследования составляют теория распознавания образов, теория множеств, теория искусственного интеллекта, методы оптимизации, дискретной математики и технической диагностики.
Для проведения вычислительных экспериментов и моделирования использованы современные аппаратные и программные средства. Реализация алгоритмов выполнена на языке C# в среде программирования MS Visual Studio 2010.
Научная новизна
Развита математическая модель распознавания образов, которая позволяет учитывать ограничения на ресурсы, время, порядок измерения значений признаков распознаваемых объектов, а также возможность параллельного измерения значений признаков.
Разработаны новые эффективные методы формирования тестов, которые обеспечивают сокращение затрат ресурсов на распознавание при одинаковых и различных затратах ресурсов на измерение значений отдельных признаков и последовательном выполнении измерений.
Для случаев, когда возможно параллельное измерение значений признаков объекта, разработаны эффективные методы формирования тестов с учётом ограничений на время и порядок измерения признаков. Предложенные методы позволяют вносить корректировки в процессе распознавания.
Научная и практическая значимость
Научная значимость состоит в разработке новых методов математического моделирования процесса распознавания с учётом ограничений на ресурсы время и порядок измерения значений признаков, а так же развитии приближенных методов анализа указанных моделей.
Практическая значимость состоит в том, что разработанные методы и алгоритмы могут быть использованы при решении практических задач в различных предметных областях, особенно в тех, где проблема оптимизации затрат ресурсов стоит особо остро, например, в медицине или микробиологии. Предложенные методы могут использоваться как для создания новых, так и для модернизации уже существующих интеллектуальных систем, с целью повышения эффективности и качества решения задач распознавания.
Основные положения, выносимые на защиту:
-
Предложенная математическая модель тестового распознавания образов позволяет учитывать ограничения на количество доступных ресурсов, время и порядок измерения значений признаков.
-
Разработанные методы построения тестов при ограничениях на ресурсы обеспечивают сокращение затрат невременных ресурсов на распознавание при последовательном проведении работ по измерению значений признаков и одинаковых затратах на измерение каждого признака.
-
Новые методы построения тестов обеспечивают сокращение затрат невременных ресурсов на распознавание при последовательном проведении работ по измерению значений признаков и различных затратах на измерение каждого признака.
-
При последовательно-параллельном проведении работ по измерению значений признаков разработанные методы построения тестов обеспечивают сокращение затрат времени на распознавание, в том числе за счёт определения наилучшего порядка выполнения работ.
-
Реализованный программный комплекс может использоваться для моделирования процесса распознавания при указанных ограничениях и формирования тестов с учётом ограничений на ресурсы, время и порядок измерения значений признаков исследуемых объектов.
Апробация работы. Основные результаты работы докладывались на следующих конференциях:
«Математические методы в технике и технологиях – ММТТ-25», (Волгоград, 2012); «ICIT-2012: Information and Communication Technologies in Education, Manufacturing and Research» (Саратов, 2012); «Перспективы развития информационных технологий» (Новосибирск, 2012); «Системы управления и информационные технологии» (Воронеж, 2013); «Проблемы управления в социально-экономических и технических системах» (Саратов, 2013); «Математические методы в технике и технологиях – ММТТ-26» (Нижний Новгород, 2013).
Работа многократно обсуждалась на научных семинарах кафедры «Информационные системы и технологии» Саратовского государственного технического университета им. Гагарина Ю.А. в 2010-2013 годах.
Публикации. По результатам диссертационной работы опубликовано 8 печатных работ, в том числе 2 статьи в журналах, включенных в перечень ведущих периодических изданий ВАК РФ.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка использованной литературы, включающего 72 наименования, и приложений.
