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

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

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

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И МЕТОДОВ ТЕСТОВОГО РАСПОЗНАВАНИЯ ОБРАЗОВ С УЧЁТОМ ОГРАНИЧЕНИЙ НА РЕСУРСЫ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Саратов-2013

005532426

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

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

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

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

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

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

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

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

и управления Российской академии наук (г. Саратов)

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

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

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

Ученый секретарь диссертационного совета

А. А. Терентьев

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

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

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

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

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

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

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

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

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

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

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

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

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

1) На основе рассмотрения существующих подходов выбрать формальную модель процесса определения состояния (идентификации) объекта в рамках методологии распознавания образов.

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

3) Разработать методы и алгоритмы формирования тестов, позволяющие снизить затраты ресурсов и времени.

4) Оценить эффективность предлагаемых методов и алгоритмов путем проведения вычислительных экспериментов.

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

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

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

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

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

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

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

4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Дана следующая формальная постановка задачи распознавания образов при ограничениях на ресурсы. Дано множество Ж объектов предметной области. Для каждого объекта S £ M задано описание /(5) =

6

{а1(а2, ...,ап} в виде упорядоченной последовательности значений признаков из конечного множества признаков X = (х1,х2, ...,*„}, которое содержит п = признаков, которые могут быть использованы для описания объектов. Значение признака представляет собой пару (имя признака, значение) и может принимать одно значение из конечного множества допустимых значений признака Щ = (а*,а?, Известно,

что множество Ж представимо в виде объединения непересекающихся подмножеств Кг и К2 и ... ПК/ - классов. Информация о принадлежности объектов классам дана лишь для части объектов, называемых прецедентами. Множество М с Ж, содержащее все прецеденты, называют эталонным множеством. Другими словами, для каждого объекта множества М известна его принадлежность классу, то есть известны подмножества М1 с М; г = 177; 2 <1 < |М|; М( = М Л К с, М( Ф 0. Все объекты 5 6 М имеют различные описания е М 6 М: /(5р) Ф /(5Ч), при р = 1, \М\; ц = 1, \М\; р * ц.

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

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

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

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

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

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

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

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

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

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

Множеством Ь на множестве М называется множество, содержащее упорядоченные последовательности метрик = ^ а^; ¡' = 1,...,п для всех пар объектов Я/г^дЕр, которые принадлежит антирефлексивному, симметричному, транзитивному отношению р:

р=1 у \/с=р+1 )) где 6 Мр, £ Мк, Мр с М, Мк а М, М - множество эталонных объектов.

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

Теорема 2.3.1. Если множество М разбито на I > 2 классов Л^ с М, то мощность множества Ь1^ с Ь (I = 1,2, ...,п) на множестве М равна:

;=1 \<?=1 р=;+1 / где М1^ - подмножество множества М, содержащее все элементы с <у-ым (1 < д < к]) значением признака х,-; - подмножество множества М, содержащее все элементы с неопределённым значением признака Х(.

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

Дифференцирующая сила признака xt определяется как число элементов множества L значение метрики по признаку для которых равно единице:

Р, = |L'«|.

Дифференцирующая сила является мерой информативности признака с точки зрения его способности различать объекты из различных классов Mj с М. Чем больше значение Pi? тем больше пар объектов из различных классов различает признак xt и тем выше его информативность.

Величина Р,- определяет абсолютное значение дифференцирующей силы отдельного признака xt на множестве L, без учёта того какие пары объектов различаются другими признаками.

Разделяющая способность признака лг£ на множестве L определяется по формуле:

где

п

uhq ~ ^ shq-i=1

Величина Vi определяет значение разделяющей способности признака Xi на множестве L, при этом учитывается количество признаков, которыми различаются те же пары объектов, что и признаком х,. Чем меньше признаков различают те же пары объектов, что и признак xit тем выше разделяющая способность признака xt.

Таким образом, описанные способы оценки информативности признаков позволяют определить наиболее значимые для распознавания признаки.

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

Рассматривается случай, когда затраты ресурсов на измерение значения каждого признака одинаковы |л:| = |Xj| = = 1 ,п. В этом

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

IMI = kl * \х\.

Теорема 3.1.1. Тест а, обеспечивающий минимальные затраты ресурсов, при последовательном измерении признаков Х[ е X и равных затратах на измерение значений всех признаков, является минимальным тестом:

Vff 6 {о-} : |Н| = min |И| =» а 6 {ам1 ае[а]

где [сг] - множество тестов, {<тм} — множество минимальных тестов, а ||ст|| -стоимость теста.

Приводятся описания методов формирования тестов с минимальными затратами ресурсов при последовательном измерении признаков Х( £ X и равных затратах на измерение значений всех признаков.

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

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

Метод 3.1.3 сочетаете себе методы 3.1.1 и 3.1.2, обеспечивая в целом более точные результаты по сравнению с методом 3.1.1, и меньшие вычислительные затраты по сравнению с методом 3.1.2.

При последовательном измерении значений признаков х,- 6 X, составляющих тест а, общие затраты ресурсов равны сумме стоимостей признаков, составляющих этот тест:

И

1Н1=]Ч*(|.

¡=1

Теорема 3.2.1. Тест а, обеспечивающий минимальные затраты ресурсов, при последовательном измерении признаков Х{ Е X и различных затратах на измерение значений признаков является тупиковым тестом: Vff е {«г} = |Н| = min \\а\\ => ff е {ат},

сге{сг}

где {<т} - множество тестов, {ат} - множество тупиковых тестов, а ||ст|| -стоимость теста.

Приводятся описания методов формирования тестов с минимальными затратами ресурсов при последовательном измерении признаков Xi&X и различных затратах на измерение значений всех признаков.

Метод 3.2.1 является модификацией метода 3.1.1 для случая, когда стоимости признаков различны.

Метод 3.2.2 за счёт использования разделяющей способности в качестве меры информативности позволяет строить тесты, которые в целом имеют меньшую стоимость, однако метод требует больших вычислительных затрат по сравнению с методом 3.2.1.

Метод 3.2.3 сочетает в себе качества методов 3.2.1 и 3.2.2, обеспечивая в целом меньшие стоимости тестов по сравнению с методом 3.2.1 и меньшие вычислительные затраты по сравнению с методом 3.2.2.

Под затратами времени на измерение значения признака xj £ X подразумевается длительность работы (процесса) по измерению значения

10

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

Затраты времени на измерение значений признаков при параллельном выполнении работ по измерению значений признаков, составляющих тест а, равны

1М1 = . шах Ь|.

1=1.....М

На работы Ь; и Ь;- по измерению значений признаков х1 и X] могут накладываться следующие ограничения:

1) Работе Ьу по измерению значения признака X] обязательно предшествует работа по измерению значения признака

2) Работе по измерению значения признака х,- должна предшествовать работа по измерению значения признака X], либо наоборот - работе Ьу должна предшествовать работа

3) Работы Ь] и Ь; по измерению значений признаков X} и х^ должны производиться в пересекающиеся интервалы времени, то есть параллельно.

Пара работ (Ь(, Ьу) одновременно может принадлежать либо одному из отношений вг, либо отношению ст3, либо ни одному из них.

Приводятся описания методов формирования тестов с минимальными затратами времени при последовательно-параллельном измерении признаков XI е X и ограничениях на порядок измерения значений признаков.

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

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

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

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

Реализация предложенных методов выполнена в виде специализированного комплекса программ. Схема взаимодействия основных модулей комплекса программ представлена на рис. 1.

Рис. 1. Схема взаимосвязи основных модулей программного комплекса

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

Для проверки эффективности предложенных методов были проведены вычислительные эксперименты. Для каждой группы методов генерировалось по 100000 псевдослучайных таблиц первичных описаний размерностью от 5x5 до 12x12. Для каждой таблицы формировалось несколько тестов: один - методом перебора и по одному тесту при помощи каждого предложенного метода. При оценке результатов тест, полученный методом перебора, является наилучшим решением, а стоимость априорного множества признаков - худшим решением. Были найдены отношения стоимостей тестов и тестов, полученных перебором, для каждой таблицы.

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

"й- р

и

Размерность

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

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

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

Размерность

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

0,63 0,6 0 £о,33 >а 1 п' •на-

0 Е 0.43 § 1 0,4 я (5

0,3

3 6 7 8 9 10 11 12

Размерность

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

На рис. 6 показаны результаты сравнения времени построения теста методом перебора и предложенными методами.

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

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

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

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

Для измерения доступны 5 признаков - результат терапевтического осмотра, результат осмотра невропатолога, собственная оценка состояния пациента, общий анализ крови, результат ЭКГ. Все признаки принимают значения из множества {Болен (1), Здоров (0)}. Пример задания эталонного множества представлен в табл. 1.

Таблица 1

Класс Признак

Решение терапевта (*х) Решение невропатолога (*2) Собственная оценка сост. (*з) Общий анализ крови <**) Результат ЭКГ (*5)

Стационарное лечение Болен Болен Болен Болен Болен

Болен Болен Здоров Болен Болен

Болен Здоров Здоров Болен Болен

Амбулаторное лечение Болен Здоров Болен Болен Здоров

Здоров Болен Здоров Болен Здоров

Болен Болен Болен Здоров Здоров

Лечение без постоянного контроля Болен Здоров Болен Здоров Здоров

Здоров Болен Болен Здоров Здоров

Не нуждается в лечении Здоров Здоров Здоров Здоров Здоров

Время 10 мин 8 мин 1 мин 30 мин 20 мин

Заданы следующие ограничений на порядок измерения значений признаков: перед осмотром у невролога, пациент должен получить заключение терапевта. ЭКГ не может проводиться одновременно с осмотром терапевта или невропатолога. Общий анализ крови требует присутствия пациента только для взятия образца, большая же часть времени необходима для анализа образца и не требует присутствия пациента, что позволяет выполнять это исследование параллельно с другими. В формализованном виде данные ограничения записываются следующим образом:

<51:(х1,Х5),(Х2,Х5).

82:(х1,Х2).

В соответствии с методом 3.3.1 по табл. 1 строится булева таблица различий, на основе анализа которой определяется, что признак х4 -«общий анализ крови» является обязательным для идентификации состояния пациента. Поскольку при этом нет никаких ограничений на порядок измерения этого признака, он включается в формируемый тест.

Вычисляется информативность признаков хг, х2, х3 и х5 с учётом ограничений на ресурсы:

?! = 0.6 ,Р2 = 0.875, Р3 = 6 ,Р5= 0.3.

Признак х3 - «собственная оценка состояния» обладает наибольшей информативностью и поэтому включается в формируемый тест. После этого вновь вычисляются значения информативности признаков хъ х2 и

Р1 = 0.3,Р2 = 0.5, Р5 =0.15.

Признак х2 - «решение невропатолога» обладает наибольшей информативностью, однако посещению невропатолога должно предшествовать посещение терапевта. Таким образом, следующим в формируемый тест добавляется признак хх - «решение терапевта».

Информативность оставшихся признаков х2 и х5, с учётом ограничений на ресурсы, равна

Р2 = 0.375, Р5 = 0.05.

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

Предположим, что поступил очередной пациент. Используя полученный тест, определим класс, к которому он относится. Сначала необходимо начать измерение значения признака х4 - «общий анализ крови», параллельно с этим выполняется измерение значений признаков х3 и х±. После измерения значения признака хг измеряется значение признака х2. К моменту, когда будет известно значение признака х4, будут известны значения всех остальных признаков, составляющих тест. Таким образом,

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

х± = Болен, х2 = Болен, х3 = Болен, х4 = Здоров, будет отнесен к классу «Амбулаторное лечение». При этом затраты времени на распознавание составят 30 мин.

В заключении изложены основные результаты и выводы диссертационной работы.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Митрофанов A.A. Об одном методе оптимизации выбора распознающих признаков при ограниченных ресурсах / A.A. Митрофанов // Вестник Саратовского государственного технического университета. -2011. - № 3 (57). - Вып. 1. - С. 209-212.

2. Митрофанов A.A. Метод распознавания нежелательных электронных писем на основе тестовой модели с учётом ограничений ресурсов / A.A. Митрофанов // Системы управления и информационные технологии. - 2013. -№1(51). - Воронеж: Научная книга, 2013. - С. 89-93.

Публикации в других изданиях

3. Митрофанов А.А. Тестовое распознавание образов при ограниченных ресурсах / А.А. Митрофанов // Современные тенденции в науке: новый взгляд: сб. науч. тр. по материалам Междунар. заоч. науч.-практ. конф., 29 ноября 2011 г. - Ч. 1. - Тамбов: Изд-во ТРОО «Бизнес-Наука-Общество», 2011. - С. 70-72.

4. Митрофанов А.А. Метод формирования распознающих тестов на основе информации о принадлежности объектов классам / А.А. Митрофанов // Математические методы в технике и технологиях - ММТТ-25: сб. тр. XXV Междунар. науч. конф.: в Шт. / под общ. ред. А.А. Большакова. - Саратов: СГТУ, 2012. - Т. 10. - Секция 12. - С. 132-133.

5. Mitrofanov А.А. Selection of optimal conditional tests with minimal cost, by calculating features' ratings / A.A. Mitrofanov // ICIT-2012: Information and Communication Technologies in Education, Manufacturing and Research. 6-9 June, Saratov, Russia, 2012. - P. 34-35.

6. Митрофанов А.А. Особенности времени как ресурса в задачах распознавания образов при ограниченных ресурсах / А.А. Митрофанов // Перспективы развития информационных технологий: сб. материалов VIII Междунар. науч.-практ. конф. / под общ. ред. С.С. Чернова. -Новосибирск: ООО «Агентство «СИБПРИНТ», 2012. - С. 50-53.

7. Митрофанов А.А. Метод построения распознающих тестов с учётом стоимости измерения отдельных признаков / А.А. Митрофанов // По страницам диссертаций 2012 года: сб. материалов I Междунар. науч.-практ. конф. / под общ. ред. С.С.Чернова. - Новосибирск: Издательство НГТУ, 2012.-С. 70-73.

8. Mitrofanov А.А. Method for reducing the computational cost of the spam detection process / A.A. Mitrofanov //Modern informatization problems in simulation and social technologies: Proceedings of the XVIII-th International Open Science Conference (Lorman, MS, USA, January 2013)/ Editor in Chief Dr. Sci., Prof. O. Ya. Kravets. - Lorman, MS, USA: Science Book Publishing House, 2013.-P. 272-275.

Подписано в печать 04.06.13 Формат 60x84 1/16

Бум. офсет. Усл. печ. л. 1,0 Уч.-изд. л. 1,0

Тираж 100 экз. Заказ 90 Бесплатно

Саратовский государственный технический университет

410054, Саратов, Политехническая ул., 77 Отпечатано в Издательстве СГТУ. 410054, Саратов, Политехническая ул., 77 Тел.: 24-95-70; 99-87-39, e-mail: izdat@sstu.ru

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Саратовский государственный технический

университет имени Гагарина Ю.А.»

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

04201360708

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

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И МЕТОДОВ ТЕСТОВОГО РАСПОЗНАВАНИЯ ОБРАЗОВ С УЧЁТОМ ОГРАНИЧЕНИЙ

НА РЕСУРСЫ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: к.ф.-м.н., доцент С. В. Папшев

Саратов 2013

ОГЛАВЛЕНИЕ

Введение.......................................................................................................................4

Глава 1. Задача распознавания образов при ограниченных ресурсах.................14

1.1. Общая характеристика проблемы распознавания образов с учетом ограничений на ресурсы........................................................................................14

1.2. Содержательная постановка задачи распознавания образов при ограниченных ресурсах.........................................................................................18

1.3. Формальная постановка задачи распознавания образов при ограниченных ресурсах...................................................................................................................20

Глава 2. Способы оценки информативности признаков......................................28

2.1. Таблицы различий...........................................................................................29

2.2. Множество строк таблицы различий и некоторые его подмножества......30

2.3. Покрытия таблицы различий и их свойства.................................................37

2.4. Дифференцирующая сила и разделяющая способность признаков..........44

2.5. Способы определения малоинформативных признаков.............................46

Глава 3. Методы построения тестов с минимальными затратами ресурсов и времени......................................................................................................................51

3.1. Построение тестов с минимальными затратами ресурсов при равных затратах на измерение значений признаков........................................................52

3.2. Построение тестов с минимальными затратами ресурсов при неравных затратах на измерение значений признаков........................................................58

3.3. Методы построения тестов с минимальными затратами времени.............64

Глава 4. Реализация методов и исследование их характеристик........................74

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

4.2. Описание и результаты вычислительных экспериментов..........................79

Заключение.................................................................................................................90

Список источников....................................................................................................91

Приложение 1...........................................................................................................100

Приложение 2...........................................................................................................103

Приложение 3...........................................................................................................107

Приложение 4...........................................................................................................112

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

Внимание ученых, в большей степени, было сосредоточено на решении задач, с четкими, хорошо структурированными исходными данными, например, задаче распознавания печатных текстов. Позднее стали предприниматься попытки решения задач по неполным и слабоструктурированных данным. Решения такого рода задач, как правило, осуществлялись человеком-экспертом, на основании определённых знаний о предметной области и собственного опыта [46].

При решении подобных задач могут быть использованы методы распознавания образов. Задача распознавания состоит в определении класса некоторого заданного объекта по его описанию и эталонному множеству, содержащему описания объектов, классы которых определены [25, 39]. Объекты распознавания могут представляться в виде описаний - наборов значений некоторых признаков из множества всевозможных признаков, которыми могут описываться объекты. Некоторые подмножества признаков эффективны при решении одних задач и непригодны для решения других. Кроме того, получение значений признаков, как правило, связано с различными трудностями, обусловленными особенностями предметных областей, которые могут выражаться в виде ограничений. Наиболее значимыми являются ограничения ресурсов (временных, трудовых, финансовых и пр.) при измерении значений признаков распознаваемых объектов.

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

виде наборов значений признаков. Этот подход к распознаванию образов берет начало в фундаментальной работе А. И. Чегис и С. В. Яблонского о способах контроля электрических схем и формировании тестов [58]. Идеи, изложенные в этой работе, получили широкое распространение сначала в технической диагностике, а затем и во многих других областях - геологии, биологии, медицине, криминалистике и пр. Понятие теста широко применяется в теории автоматов, где при помощи тестов решаются задачи распознавания состояний автоматов [40, 53-55, 63]. В терминах распознавания образов, тест понимается как подмножество множества признаков объектов, такое что, значения этих признаков различны для всех объектов из разных классов. Применительно к задаче распознавания образов, в рамках данного подхода, предлагаются методы, основанные на комбинаторном анализе описаний объектов представленных в виде последовательности значений признаков. Подобные методы получили название логических или дискретных процедур распознавания. Основополагающими работами, связанными с логическими процедурами распознавания, являются работы С.В.Яблонского, Ю.И.Журавлева, и М.Н.Вайнцвайга [45].

Развитию методов тестового распознавания посвящены работы Ю. И. Журавлева, А. Е. Андреева, Э. Э. Гасанова, В. Б. Кудрявцева, Е. В. Дюковой, А. А. Кикабло [1, 24-27, 39]. В этих работах, среди прочих, рассматривается задача уменьшения числа признаков для распознавания и предложены способы оценки информативности отдельных признаков на основе множеств тестов, а так же установлены зависимости между весом признака, числом разделяемых строк и видом теста, который используется для оценки признака. Несмотря на то, что оценка информативности признака на основе множеств тестов достаточно эффективна, её получение связано с значительными вычислительными затратами на построение множеств тестов.

Различные подходы к решению задачи сокращения числа признаков для распознавания рассмотрены в [20, 39, 45, 59]. Решение этой задачи, как правило, сводится к решению задачи построения тупиковых покрытий булевых матриц, которая, так же может быть сформулирована как задача построения нормальной формы логической функции [58]. Получение оптимального решения возможно путём перебора всех возможных вариантов, однако эта задача имеет экспоненциальную сложность [45, 20].

При уменьшении числа признаков, по которым проводится распознавание, косвенно обеспечивается сокращение затрат ресурсов и времени [22, 27-30, 42, 50, 58]. Однако, для достижения наилучших результатов необходимо рассматривать модели распознавания, позволяющие учитывать затраты на измерение значений признаков и применять методы, позволяющие эти затраты сократить [8, 16]. При этом могут быть получены абсолютно другие подмножества признаков, которые, тем не менее, позволяют определить класс объекта.

Способы формирования множеств признаков для распознавания, с учётом ограничений на ресурсы в своих работах рассматривает А. Г. Горелик [16, 17]. Им предложены способы формирования, так называемых, «рабочих словарей признаков», которые используются в случае, когда существуют ограничения в финансовых затратах на измерительное оборудование. Недостатком предложенных им способов является отсутствие возможности параллельного вычисления значений признаков.

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

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

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

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

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

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

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

1. На основе рассмотрения существующих подходов выработать формальную модель процесса определения состояния (идентификации) объекта в рамках методологии распознавания образов.

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

3. Разработать методы и алгоритмы формирования тестов, позволяющие снизить затраты ресурсов и времени.

4. Оценить эффективность предлагаемых методов и алгоритмов путем проведения вычислительных экспериментов.

Методы исследований

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

Для проведения вычислительных экспериментов и моделирования использованы современные аппаратные и программные средства. Реализация алгоритмов выполнена на языке С# в среде программирования 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 статьи в журналах, включенных в перечень ведущих периодических изданий ВАК РФ.

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

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

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

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

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

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

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

Структура и объем работы

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

Краткое содержание работы

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

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

и

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

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

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

В разделе 2.1 дается определение и способ построения таблиц различий для заданного множества описаний объектов.

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

В разделе 2.4 даются 2 оценки информативности отдельных признаков и их множеств с использование�