Содержание к диссертации
Введение
1. О задаче создания СПР функционального типа 15
1.1 СПР функционального типа и задачи их синтеза и верификации 15
1.2 СПР функционального типа и распознавание образов 26
1.3 Алгоритмические основы теории распознавания частично упорядоченных объектов 27
1.4 СПР функционального типа и теория поиска и хранения информации 34
1.5 Уточнение постановки задачи 40 *
Выводы по первой главе 43
2. Исчисление граней 44
2.1 Исчисление граней. Математическая модель 44
2.2 Особенности программной реализации исчисления граней 51
2.3 Некоторые алгоритмы исчисления граней 53
2.4 Минимизация покрытий подмножеств декартова произведения граней 58
Выводы по второй главе 60
3. Обобщенные графики отображений и алгоритмы верификации их непротиворечивости и полноты 61
3.1 Математическая модель СПР 61
3.2 Верификация непротиворечивости моделей СПР 66
3.3 Верификация полноты моделей СПР 67
Выводы по третьей главе 69
4. Синтез информационных сред, реализующих функциональные отображения 70
4.1 Синтез информационной среды в виде подграфика функционального отображения 70
4.2 Модифицированные алгоритмы распознавания 72
4.3 Алгоритм верификации полноты на основе модифицированного алгоритма 77
4.4 Использование структурных свойств решающего правила для ускорения принятия решений 79
4.5 Сложность алгоритмов распознавания 89
Выводы по четвертой главе 109
ГЛАВА 5. Программный комплекс POOREX 2002 и методика создания экспертных систем на его основе 110
5.1 Краткое описание программного комплекса POOREX 2002 110
5.2. Обменный формат для представления исходных данных и информационных сред 114
5.2.1 Схемы формата XSD 114
5.2.2 Схемы формата DTD 120
5.3 Методика создания и применения СПР с использованием программного комплекса POOREX 2002 122
Выводы по пятой главе 125
ГЛАВА 6. Экспериментальное исследование методики синтеза и верификации СПР 126
6.1 Примеры синтеза и верификации СПР 126
6.1.1 Предметная область «Genetics» 126
6.1.2 Предметная область «Substance State» :...141
6.2 Применение разработанных методов в федеральной системе
учета и контроля ядерных материалов 153
6.2.1 Подготовка исходных данных на POOREX 2002 ...155
6.2.2 Модификация АРМ 156
6.2.3 Исследование временных характеристик алгоритмов распознавания предметной области «Restricted combinations» 159
6.3 Исследование времени работы алгоритмов распознавания на случайных наборах данных ; 163
6.3.1 Исследование зависимости времени работы алгоритмов разделения от размерности области 163
6.3.2 Исследование зависимости времени работы алгоритмов распознавания от размерности области 164
6.3.3 Исследование зависимости времени работы алгоритмов разделения от числа граней решающей функции 166
6.3.4 Исследование зависимости времени распознавания от числа граней решающей функции 166
Выводы по шестой главе 167
Заключение 169
Список используемой литературы 172
Приложения 180
- Алгоритмические основы теории распознавания частично упорядоченных объектов
- Использование структурных свойств решающего правила для ускорения принятия решений
- Методика создания и применения СПР с использованием программного комплекса POOREX 2002
- Исследование зависимости времени работы алгоритмов распознавания от размерности области
Введение к работе
Диссертационная работа посвящена исследованию методов построения информационных сред, отражающих знания экспертов о соответствии наблюдаемых по определенным признакам ситуаций и принимаемых в этих ситуациях решений, а также обоснованию принципов построения и создания инструментальных средств программной реализации таких сред.
В работе решена задача синтеза и верификации таких сред и построенных на их основе экспертных систем принятия решений, обоснована и создана методика их программной реализации с использованием вырабатываемых экспертами обобщенных описаний указанного соответствия.
Актуальность проблемы.
Системы принятия решений создаются и используются для автоматизированного анализа ситуаций и принятия адекватного текущей ситуации решения. Настоящая работа посвящена теоретическому обоснованию и созданию методов и программных средств синтеза и верификации одного класса таких систем.
Аналитические системы принятия решения осуществляют его выбор, решая оптимизационную задачу определенного класса с учетом особенностей области поиска решения, ее ограничений и целевой функции. Известно большое разнообразие аналитических моделей и методов теории принятия решений и теории оптимизации, используемых при создании систем принятия решений этого класса.
Экспертные системы принятия решений аккумулируют опыт специалистов о соответствии на множестве ситуаций и решений и позволяют использовать этот опыт лицами, принимающими решения по наблюдаемым признакам текущей ситуации. Это соответствие в таких системах, как правило, первоначально описывается экспертами в явном виде или, возможно, в виде систем продукций. В этом классе мы выделяем системы, отражающие функциональ-
ные соответствия на множестве ситуаций и множестве решений и называем их экспертными системами принятия решений функционального типа. (Применительно к бинарным отношениям общего типа системы функционального типа могут создаваться как системы, отвечающие предикату "решение г соответствует ситуации s" на декартовом произведении множества решений и множества ситуаций).
Экспертные системы принятия решений функционального типа создаются на основе описания экспертами в том или ином удобном для них виде функционального соответствия, характерного для данной предметной области. По такому описанию синтезируется информационная среда, позволяющая по известному для нее алгоритму находить значения функционального соответствия при заданном наборе значений атрибутов ситуации. Важными характеристиками СПР является время поиска решения и сложность информационной среды.
Отметим аналогию с задачей синтеза схемы из функциональных элементов, реализующей данную булеву функцию. Эта функция должна быть описана в удобном для разработчика схемы виде (таблицей, покрытием множества единичных значений или в другом виде). По этому описанию тем или иным алгоритмом синтезируется схема из функциональных элементов, функционирование которой соответствует этому описанию. Схема имеет определенную сложность (число функциональных элементов) и время срабатывания, определяемое, например, длиной наиболее длинного пути от некоторого входа к выходу (глубиной схемы).
Булева функция может быть реализована программно путем имитации функционирования схемы. Заметим, что программная имитация может быть осуществлена в системе продукций, например как программа на языке ПРОЛОГ. В этом случае описание требуемой функции и информационная среда для вычисления ее значений отождествляются. Подобный подход возможен при программной реализации функциональных соответствий, описываемых функциями -значной логики при любом к.
Однако рассмотренный метод прямой аналогии с синтезом схем из функциональных элементов не самый эффективный метод программной реализации функциональных соответствий. На этом пути не удается получить нетривиальные оценки времени поиска решений: в этом случае глубина схемы не может быть ориентиром в оценке времени работы программы. В программировании значение функции можно получить и за один шаг, если ее таблицу записать в виде массива. Используя другие информационные среды, можно уменьшать объем требуемой памяти за счет увеличения времени поиска решения при сохранении возможности вычисления верхней оценки этого времени.
В этом проявляется отличие от реализации экспертной системы как системы продукционного типа, которая основана на аксиоматическом подходе к описанию состояний реальной системы и отношений на их основе и использовании правил индуктивного и дедуктивного вывода при извлечении решений [8, 12].
В настоящей работе изучается один из подходов к синтезу СПР функционального типа, позволяющий создавать информационные среды реализации конечных функциональных отношений, допускающие нетривиальные верхние оценки времени поиска решения. Сопутствующей задачей является задача верификации исходного описания функционального соответствия, реализуемого СПР. Создаваемое экспертами, оно, в силу человеческого фактора, может быть некорректным, то есть не отвечающим постулатам функционального соответствия. Возможны некорректности двух видов: неполнота (одной или более си- туаций в описании не сопоставлено решение) и нефункциональность, или противоречивость (некоторой ритуации сопоставлено более одного решения). Функциональность должна гарантироваться до начала синтеза информационной среды. Неполнота может допускаться как аспект неопределенности, она может выявляться как по исходным описаниям, так и анализом синтезированной информационной среды. Эти задачи решаются в диссертации на основе ал-
1 Если, конечно не имеется в виду случай полного распараллеливания вычислений в многопроцессорных системах.
-8-горитмов обоснованного в работе исчисления граней декартовых произведений решеток, составляющего также алгоритмическую базу для синтеза информационных сред.
Этот подход реализован в настоящей работе на основе развиваемой с участием автора теории распознавания частично - упорядоченных объектов [57, 76, 78, 100], методами которой синтезируются информационные среды для вычисления значений k-значной функции, и теории хранения и поиска информации [14], дающей метод получения нетривиальных верхних оценок времени поиска решения в таких средах.
Актуальность исследования описанного подхода к синтезу и верификации экспертных систем принятия решений функционального типа определяется широтой области использования таких систем во многих отраслях промышленности и экономики, а также недостаточной изученностью проблемы программной реализации функциональных соответствий в описанном выше аспекте, существенно отличающейся от проблемы их схемной реализации. Последнее обстоятельство является следствием более слабого состояния алгоритмической базы экспертных систем принятия решений по сравнению с алгоритмической базой аналитических систем принятия решений. Как следствие актуальным является и создание программно-инструментальных средств поддержки развиваемого в настоящей работе подхода к синтезу и верификации систем принятия решений функционального типа.
Цель работы
Цель настоящей диссертационной работы заключается в создании программных средств и методики построения экспертных систем принятия решений в задаваемой предметной области с оцениваемым временем принятия решений.
Основные направления работы сводятся к решению следующих задач:
- разработка алгоритмов и операций исчисления граней;
разработка алгоритмов верификации непротиворечивости и полноты обобщенных описаний функциональных отображений;
разработка алгоритмов построения решающих правил для задач теории распознавания частично упорядоченных объектов по обобщенным описаниям функциональных отображений;
разработка способа представления решающего правила как системы информационного поиска и получение теоретических оценок времени поиска;
разработка программного комплекса синтеза и верификации экспертных систем с оцениваемым временем принятия решений и методики создания таких систем.
Методы исследования
Поставленные задачи решаются с использованием методов дискретной математики, теории решеток, теории хранения и поиска информации, теории распознавания упорядоченных объектов, а также исчисления граней, являющегося обобщением исчисления бинарных кубических комплексов.
Достоверность научных результатов
Достоверность научных результатов подтверждена модельными примерами, данными автоматического тестирования и сравнительным компьютерным экспериментом. Научная новизна. Новыми являются:
Алгоритмы и операции исчисления граней и ее применение для верификации непротиворечивости и полноты функциональной модели СПР.
Общий алгоритм разделения и распознавания частично упорядоченных объектов на k-значной решетке по обобщенному описанию обучающей выборки, и его частные варианты.
Алгоритмы вычисления значения функции -значной логики, имеющие нетривиальные верхние оценки сложности.
-10-
4) Методика создания экспертных систем с оцениваемым временем
принятия решений
Практическая значимость работы.
На основе теоретических результатов работы разработан программный комплекс POOREX 2002, поддерживающий методику создания экспертных систем принятия решений функционального типа в задаваемой предметной области.
Разработанный на языке высокого уровня С++[70] программный комплекс POOREX 2002 имеет модульную структуру, что делает доступным встраивание его функциональных компонент в другие проекты.
Предложенные в работе алгоритмы применялись для проектирования программных и аппаратно реализуемых систем принятия решений.
Программный комплекс внедрен в Федеральной Системе Учета и Контроля Ядерных Материалов.
Реализация результатов.
Программный комплекс POOREX 2002 использован в ЦНИИ Атомин-форм при разработке АРМ подготовки сводной отчетности для выявления несовместимых сочетаний ядерных материалов в отчетных партиях. А также в учебном процессе МЭИ в курсе новых информационных технологий для магистров. Работа выполнена в рамках НИР № 1022002 «Анализ и разработка принципов алгоритмизации и верификации интеллектуальных систем функционального типа» кафедры ММ. Апробация работы.
Основные положения и результаты диссертации докладывались и обсуждались:
на 5-й международной научно-технической конференции студентов =*-и аспирантов «Радиоэлектроника, электротехника и энергетика» (г. Москва, 1999 г.)
на международном форуме информатизации МФИ-99 Информационные средства и технологии (г. Москва, 1999 г.)
на 10-й международной конференции «Проблемы управления безопасностью сложных систем» (г. Москва, 2002 г.)
на 9-й международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (г. Москва, 2003 г.)
Публикации, . По теме диссертации опубликовано 6 печатных работ: [1] Ополченов А.В., Фролов А.Б. Синтез и верификация систем принятия решений функционального типа. Известия Российской Академии наук. Теория и системы управления, JVs 5. 2002.
[2] Opolchenov А.V., Frolov А.В. Synthesis and verification of functional systems of a functional type. Journal of Computer and Systems Sciences International. Proceedings of Russian Academy of Science. Journal of Control Systems and Computers. N 5. 2002.
[3] Ополченов A.B., Фролов А.Б. Интервальный подход к построению систем принятия решений функционального типа // V Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. докл. — М. 1999. - С. 250
[4] Гришина Е.А. Ополченов А.В. Алгоритм компрессии данных на основе их функциональной интерпретации // Международный форум информатизации МФИ-99- Информационные средства и технологии: Докл. —Моск. энерг. инст. — 1999 -Т.2.-С.81-84
[5] Ополченов А.В. Сергеев С.А, Программный инструментальный комплекс для синтеза и верификации экспертных систем и его применение в атомной промышленности // Проблемы управления безопасностью сложных систем: Труды X международной конференции. Москва, декабрь 2002 г. / Под ред. Н.И. Архиповой и В.В. Кульбы. Часть 2. - М.: Pi 1У - Издательский дом МПА-Пресс. С. 217-219
-12-[6] Ополченов А.В. Синтез и верификация систем принятия решений функционального типа // IX Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. докл. -М. 2003.-С. 266-267.
Личный вклад автора:
[1,2] Автору принадлежит обоснование полноты системы операций исчисления граней, способы их имплементации, а также описание алгоритмов синтеза и верификации систем принятия решений, в частности существенное уточнение алгоритма синтеза в [2].
[3] Автору принадлежит изложение преимуществ обобщенного описания обучающей выборки и подхода к построению решающего правила на его основе.
[4] Автору принадлежит описание информационной структуры леса и обоснование ее использования для ускоренного поиска.
[5] Автору принадлежит описание программного инструментального комплекса и изложение его применения в федеральной системе учета и контроля ядерных материалов.
Структура и объём работы.
Диссертация состоит из введения, шести глав, заключения, списка литературы (109 источников) и приложений.
СОДЕРЖАНИЕ РАБОТЫ.
Во введении определена актуальность темы исследования, формулируются задачи исследования диссертации, раскрывается научная новизна и практическая значимость полученных результатов, приведены сведения об апробации и внедрении работы.
Первая глава посвящена анализу теоретических предпосылок диссертации [14, 76, 78] и уточнению задачи исследования с позиций теории построения систем принятия решений, теории распознавания образов, теории хранения и поиска информации.
Во второй главе уточняется понятие грани декартова произведения конечных множеств, описываются система операций на гранях и алгоритмы исчисления граней, в частности алгоритмы преобразования покрытий подмножеств декартова произведения гранями, и рассматриваются особенности их компьютерной реализации.
В третьей главе рассматриваются математические модели обобщенных графиков отображений реализуемых системами принятия решений функционального типа и алгоритмы верификации непротиворечивости и полноты таких моделей.
В четвертой главе описываются алгоритмы синтеза информационных сред, реализующих отображения, заданные обобщенным графиком. Описываются особенности компьютерной реализации этих алгоритмов с учетом возможной неполноты используемой компьютерной модели обобщенного графика отображения и с предупреждением о возможной неточности решения в этом случае. Исследуются варианты организации информационной среды, соответствующие алгоритмы поиска решений в таких средах и теоретические оценки их сложности.
В пятой главе приводится описание программного комплекса POOREX 2002 и созданной на его основе методики создания СПР функционального типа для задаваемой предметной области.
В шестой главе рассматриваются примеры систем принятия решений, сконструированных на основе предложенной в диссертации методики, результаты сравнительного тестирования различных методов реализации алгоритмов принятия решений при случайных исходных данных, экспериментальные данные, подтверждающие теоретические оценки времени принятия решений, а также результаты практического использования предложенной методики и разработанного программного обеспечения.
-14-В заключении приведены основные результаты исследований, полученные в диссертационной работе, а также сформулированы направления дальнейших исследований.
*
*
*
Алгоритмические основы теории распознавания частично упорядоченных объектов
Диссертационная работа посвящена исследованию методов построения информационных сред, отражающих знания экспертов о соответствии наблюдаемых по определенным признакам ситуаций и принимаемых в этих ситуациях решений, а также обоснованию принципов построения и создания инструментальных средств программной реализации таких сред.
В работе решена задача синтеза и верификации таких сред и построенных на их основе экспертных систем принятия решений, обоснована и создана методика их программной реализации с использованием вырабатываемых экспертами обобщенных описаний указанного соответствия.
Системы принятия решений создаются и используются для автоматизированного анализа ситуаций и принятия адекватного текущей ситуации решения. Настоящая работа посвящена теоретическому обоснованию и созданию методов и программных средств синтеза и верификации одного класса таких систем.
Аналитические системы принятия решения осуществляют его выбор, решая оптимизационную задачу определенного класса с учетом особенностей области поиска решения, ее ограничений и целевой функции. Известно большое разнообразие аналитических моделей и методов теории принятия решений и теории оптимизации, используемых при создании систем принятия решений этого класса.
Экспертные системы принятия решений аккумулируют опыт специалистов о соответствии на множестве ситуаций и решений и позволяют использовать этот опыт лицами, принимающими решения по наблюдаемым признакам текущей ситуации. Это соответствие в таких системах, как правило, первоначально описывается экспертами в явном виде или, возможно, в виде систем продукций. В этом классе мы выделяем системы, отражающие функциональ -6 ные соответствия на множестве ситуаций и множестве решений и называем их экспертными системами принятия решений функционального типа. (Применительно к бинарным отношениям общего типа системы функционального типа могут создаваться как системы, отвечающие предикату "решение г соответствует ситуации s" на декартовом произведении множества решений и множества ситуаций).
Экспертные системы принятия решений функционального типа создаются на основе описания экспертами в том или ином удобном для них виде функционального соответствия, характерного для данной предметной области. По такому описанию синтезируется информационная среда, позволяющая по известному для нее алгоритму находить значения функционального соответствия при заданном наборе значений атрибутов ситуации. Важными характеристиками СПР является время поиска решения и сложность информационной среды.
Отметим аналогию с задачей синтеза схемы из функциональных элементов, реализующей данную булеву функцию. Эта функция должна быть описана в удобном для разработчика схемы виде (таблицей, покрытием множества единичных значений или в другом виде). По этому описанию тем или иным алгоритмом синтезируется схема из функциональных элементов, функционирование которой соответствует этому описанию. Схема имеет определенную сложность (число функциональных элементов) и время срабатывания, определяемое, например, длиной наиболее длинного пути от некоторого входа к выходу (глубиной схемы).
Булева функция может быть реализована программно путем имитации функционирования схемы. Заметим, что программная имитация может быть осуществлена в системе продукций, например как программа на языке ПРОЛОГ. В этом случае описание требуемой функции и информационная среда для вычисления ее значений отождествляются. Подобный подход возможен при программной реализации функциональных соответствий, описываемых функциями -значной логики при любом к.
Однако рассмотренный метод прямой аналогии с синтезом схем из функциональных элементов не самый эффективный метод программной реализации функциональных соответствий. На этом пути не удается получить нетривиальные оценки времени поиска решений: в этом случае глубина схемы не может быть ориентиром в оценке времени работы программы. В программировании значение функции можно получить и за один шаг, если ее таблицу записать в виде массива. Используя другие информационные среды, можно уменьшать объем требуемой памяти за счет увеличения времени поиска решения при сохранении возможности вычисления верхней оценки этого времени.
В этом проявляется отличие от реализации экспертной системы как системы продукционного типа, которая основана на аксиоматическом подходе к описанию состояний реальной системы и отношений на их основе и использовании правил индуктивного и дедуктивного вывода при извлечении решений [8, 12].
В настоящей работе изучается один из подходов к синтезу СПР функционального типа, позволяющий создавать информационные среды реализации конечных функциональных отношений, допускающие нетривиальные верхние оценки времени поиска решения. Сопутствующей задачей является задача верификации исходного описания функционального соответствия, реализуемого СПР. Создаваемое экспертами, оно, в силу человеческого фактора, может быть некорректным, то есть не отвечающим постулатам функционального соответствия. Возможны некорректности двух видов: неполнота (одной или более ситуаций в описании не сопоставлено решение) и нефункциональность, или противоречивость (некоторой ритуации сопоставлено более одного решения). Функциональность должна гарантироваться до начала синтеза информационной среды. Неполнота может допускаться как аспект неопределенности, она может выявляться как по исходным описаниям, так и анализом синтезированной информационной среды.
Использование структурных свойств решающего правила для ускорения принятия решений
В литературе встречаются различные интерпретации задачи поиска. Поиск может рассматриваться как задача управления сближением поисковой системы с искомым объектом по неполной априорной информации [1, 36, 80], задача однократного поиска на некотором заданном множестве данных [6, 46] и задача многократного поиска на одном и том же множестве данных.
Последняя характерна для систем, использующих базы данных. Многократное обращение к данным порождает проблему организации данных с тем, чтобы на поиск затрачивалось наименьшее время. Процесс специальной организации данных, проводимый до начала поиска, называется предобработкой-Простейшим примером предобработки является сортировка. Иногда предобработка требует значительных затрат времени, однако это окупается ввиду многократности операций поиска.
Поиск по ключу является простейшим примером задачи поиска, встречающейся в базах данных. Любому объекту, хранящемуся в базе данных, соответствует свой уникальный ключ. По заданному ключу требуется найти объект с этим ключом, если такой объект имеется.
Задача поиска идентичных объектов [14] является более формальной постановкой задачи поиска по ключу. Дано некоторое конечное множество ключей и некоторое более широкое множество запросов. Задача состоит в нахождении в множестве ключей ключа идентичного ключу-запросу по произвольному запросу из множества запросов [15].
Другим примером является одномерная задача интервального поиска. Имеется конечное множество точек из отрезка [ОД] вещественной прямой. Множество запросов представляет собой совокупность всех возможных отрезков [u,v] находящихся внутри [0,1]. Требуется для произвольного запроса [u,v] из множества запросов найти все точки из исходного множества, которые попадают в данный отрезок [14, 44, 53, 72, 97, 101].
Различные формализации понятия задачи информационного поиска вводились в работах [7,14,44, 66, 68, 87, 107].
Так, в [87, 107] формализация вводилась следующим образом. Запрос к базе данных имеет тип Тх. База данных состоит из элементов типа Г2. Результат имеет тип Т3. Запрос рассматривается как отображение Q: Т\ X 27 1 —»7У Гз может, например, быть логическим типом, совпадать с Тг или быть множеством элементов типа 7.
В [14] вводится понятие тип задач информационного поиска где X — множество запросов к базе данных, Y— множество записей, р — отношение поиска, бинарное отношение, определенное на декартовом произведении X X У, позволяющее установить, когда запись из У удовлетворяет запросу из X. Задача информационного поиска определяется как где X— множество запросов, V — библиотека, т.е. некоторое конечное подмножество множества Y, р — отношение поиска, определенное на X X У. Данная терминология согласуется с терминологией, принятой в [81] если заменить термин «запись» на термин «документ». Согласно [81], информационный поиск представляет собой процесс отыскания в некотором множестве документов или текстов (поисковом массиве) таких, которые посвящены указанной в запросе теме (предмету) и поэтому содержат необходимые потребителю факты, сведения. Задачи поиска, в которых отношение поиска является отношением частичного порядка, встречаются во многих системах баз данных. В зависимости от интерпретации в литературе они носят название включающего поиска [69], дескрипторного поиска [66, 81, 82], поиска по ключевым словам [38], задачи о доминировании [44, 61] и т.п. Включающий поиск осуществляется в дескрипторных автоматизированных информационно-поисковых системах [3, 81, 82]. Информационный массив состоит из документов, каждый из которых описывается множеством дескрипторов. В запросе указывается некоторое подмножество дескрипторов, и необходимо найти в информационном массиве все документы, содержащие все дескрипторы, указанные в запросе. Занумеруем множество всех дескрипторов некоторым образом и припишем каждому документу булев вектор, длины равной мощности всех дескрипторов. На і-й позиции такого вектора присутствует 1 тогда и только тогда, когда /-й дескриптор входит в описание данного документа. Будем задавать запросы аналогичными векторами, содержащими І на i-й позиции тогда и только тогда, когда -й дескриптор входит в запрос. Отношение включающего поиска в этом случае будет иметь следующий вид: В общем случае включающий поиск применим всегда, когда элементы информационного массива задаются множеством свойств, причем необходимо перечислить все элементы с определенным набором свойств, задаваемых запросом. Задачи поиска, в которых отношение поиска является отношением линейного предпорядка, является одной из самых распространенных и простых. В геометрической интерпретации данная задача носит название одномерной задачи о доминировании [44, 61]. Эта задача имеет полное и окончательное решение [15] Задача о доминировании относится к интенсивно развивающемуся направлению, под названием вычислительная геометрия [44, 61]. Оно занимается исследованием сложности алгоритмов решения геометрических, в широком смысле, задач и имеет широкий круг применений. Многомерная задача о доминировании заключается в следующем: дано конечное n-мерное пространство точек, запрос представляет собой точку в этом пространстве, следует найти все те точки исходного пространства, которые не больше по каждой из компонент, чем запрос. Часто для исследования сложности поиска используется модель алгебраического дерева вычислений (АДВ) [86, 91, 104, 105].
Методика создания и применения СПР с использованием программного комплекса POOREX 2002
Представление информационной среды в виде подграфика отображения иллюстрируется примером 1,в) в главе I. Алгоритмы построения таких подграфиков по полному графику отображения (или заданному его подмножеству) разработан в теории распознавания частично упорядоченных объектов, ряд таких алгоритмов описан в п. 1.3. Применительно к рассматриваемой здесь задаче исходный график отображения или его заданный подграфик используется такими алгоритмами в качестве обучающей выборки. Решающее правило формируется алгоритмом разделения в виде подграфика, содержащего, возможно, меньшее число точек, чем исходный график (или подграфик).
Алгоритм распознавания по решающему правилу-формирует для любого заданного набора значений переменных значение некоторого отображения (которое совпадает с исходным, если решающее правило сформировано по его полному графику). Если алгоритмом разделения использовалась неполная обучающая выборка (не полный график отображения), то алгоритм распознавания формирует некоторое решение и для тех наборов, которые не были представлены в обучающей выборке, без соответствующего предупреждения. Последнее может быть осуществлено путем сопровождения исходного неполного графика предикатом, принимающим значение 1 на наборах, определяющих исходный график отображения, и формированием по этому предикату его подграфика с использованием того же алгоритма разделения.
В настоящем разделе описывается алгоритм разделения, отличающийся от базового алгоритма, описанного в п. 1.3, тем, что применяется к обобщенному графику отображения и формирует решающее правило в виде подграфика отображения, совпадающего с подграфиком, который формируется базовым алгоритмом (при детальном задании полного отображения) и отличающегося от этого подграфика в случае неполноты исходного отображения. В последнем случае реализуется отображение во множество i?U{-}, R — множество возможных решений, —" - символ неопределенности.
Алгоритм распознавания по такому подграфику отображения вычисляет точное решение, если соответствующий набор значений переменных учитывался обобщенным графиком отображения, в противном случае с соответствующим предупреждением предлагается прогнозируемое (возможное неточное) решение, которое находится по подграфику, отличающемуся от использованного отсутствием точек со значением "— .
В предлагаемой модификации алгоритма разделения [57, 100]9, обучающая выборка задается функциональной моделью (F, X) (см. представления (3.6, 3.7)), то есть покрытиями классов ядерной эквивалентности решающей функции и покрытием области определения СПР функционального типа.
Модифицируемый алгоритм Ам применяется к исходному описанию (3.6) решающей функции и исходному описанию (3.7) характеристической функции и формирует описание решающей функции в виде списка LA(j) и аналогичное представление характеристической функции в виде списка LA(x) 1. Пары вида (сг, v), где v = j(lnf а) исходного описания (3.3) решающей функции размещаются в списке L, который линейно (- ) упорядочивается по элементам а образующих его пар, образуется пустой список LA(f) и список LM = L. 2. Пока список LM не пуст, для его головного элемента ( т, v) списка L по . правилам базового алгоритма Ам вычисляется значение v= y/A(LA(f), Іпц/т)), где у/А - определенная для алгоритма А функция, и выполняется одно из следующих действий: а) если v = х, то для каждого элемента (о", v") єЬ такого что с єо" и v Vv в список LA(J) включается элемент (с, v"). В список LM включаются пары вида ((с, Supo1), v") (или ((с,с),—)), соответствующие тем элементам с множе ства і(о ) минимальных элементов дополнения грани в верхнем конусе ее инфи нума, для которых найдется элемент (cf, v ) списка L, такой что с ест", но с Ф Info (или если для всех & С І СҐ). б) если v Ф х и v Ф "-", то список L изменяется, как описано в п. а). Если при этом v Ф v то в конец списка LA(f) включается пара (Infer, pA(LA{f), Infer, у). Здесь рА - определенная для алгоритма А функция. Первоначальный вариант алгоритма данного типа описан в [74]. Здесь приводится описание, уточненное по результатам компьютерных экспериментов с использованием разработанного автором программно-инструментальной комплекса. в) если v #х, v v и v = "-", то список LA(f) изменяется, как описано в п. б). В список LM включаются пары (0(с, сґ), v )), соответствующие тем элементам с множества I (о) , для которых найдется грань о", представленная в некотором элементе (&, v ) исходного списка Z, такая, что с Sup (У, но не выполняется условие (Infer7 c)&(c Info/), где О — операция ограничения граней. После этого текущий элемент ( т, v) удаляется из списка LM и список упорядочивается, при этом из двух или нескольких одинаковых его элементов оставляется только единственный экземпляр. 3. Действия, аналогичные описанным в п.п. 1, 2 выполняются применительно к исходному описанию характеристической функции. Примечание. Значение х в некоторых парах (с/, х), включаемых в список LM, является символом неизвестности, означающим необходимость уточнения значения v =/(Info) Для формирования решающего правила в виде списка LA(f) требуется лишь однократная обработка элементов исходных предварительно упорядоченных списков LF и Lx. Алгоритм RA распознавания (принятия решений) использует в качестве решающего правила списки LJJ) и LA(x), сформированные модифицированным алгоритмом разделения Л.
Исследование зависимости времени работы алгоритмов распознавания от размерности области
Программно-инструментальный комплекс POOREX 2002 предназначен для экспериментального исследования СПР функционального типа и создания таких систем для различных областей применения.
В этом комплексе реализованы разработанные в диссертации и описанные в главах 2, 3, 4 алгоритмы, а также программы поддержки методик создания соответствующих информационных сред принятия решений.
Структурная схема комплекса дана на Рис, 5,1. Структурными единицами схемы являются экранные формы, программные модули, файлы обмен-ного формата, файлы синтезированной СПР. Стрелками на рисунке показаны потоки данных между структурными единицами.
Экранные формы обеспечивают интерактивное взаимодействие с пользователем.
Форма создания (или коррекции) описания предметной области предназначена для задания и отображения атрибутов характеризующих предметную область, списков значений этих атрибутов и списка возможных решений. Введенные данные сохраняются в обменном формате.
Форма создания (или коррекции) описания функционального отображения служит для задания и отображения решающей и характеристической функций модели в виде обобщенного или полного графиков отображений в терминах предметной области. Введенные данные преобразуются в соответствующую компьютерную модель.
На форме верификации модели в терминах предметной области отображается информация об областях, где исходная модель не удовлетворяет свойствам непротиворечивости или полноты. Для получения таких областей вызываются функции верификации непротиворечивости и полноты исходных описаний из компьютерной модели обобщенных графиков отображения.
На форме графического отображения модели осуществляется визуализация декартова произведения, определяемого атрибутами предметной области, отображаются обобщенные графики отображения, решающие правила и лес. При выборе набора отображается дескриптор, определяющий данный набор, если решающее правило построено.
Форма распознавания решения на задаваемом наборе отображает определяемое решение на любом наборе декартова произведения-, заданного на форме в терминах предметной области. Если при этом задаваемый набор не был учтен в исходном описании, предлагается прогнозируемое решение с соответствующим предупреждением.
Форма расчета теоретической сложности информационных графов отображает расчетные верхние оценки времени работы алгоритмов распознавания.
Форма сравнительного анализа времени работы на случайных наборах предназначена для статистического исследования алгоритмов разделения и распознавания.
В модуле, реализующем компьютерную модель исчисления граней реализованы все операции, отношения и алгоритмы, определенные для абстрактной модели исчисления граней.
Модуль, реализующий компьютерную модель обобщенных графиков отображения содержит, в частности, функции для сохранения данных в обменном файле и чтения обобщенных графиков отображения из таких файлов.
Содержащиеся в модуле генерации случайных моделей функции позволяют при помощи датчика случайных чисел получать модели обобщенных графиков, отвечающие задаваемым характеристикам и удовлетворяющие текущей предметной области. Такие модели используются для статистических исследований алгоритмов разделения и распознавания. Алгоритмы генерации построены таким образом, что генерируемые модели автоматически обладают свойством непротиворечивости.
Модуль синтеза решающих правил предназначен для синтеза верифицированной компьютерной модели обобщенных графиков отображения в соответствующую ей компьютерную модель решающих правил.
С помощью модуля построения леса и информационного графа из модели решающих списков строится модель леса.
Модуль, реализующий компьютерную модель решающих правил, леса и информационных графов содержит, в частности, функции позволяющие сохранять данные в файлах в обменном формате и чтения решающих правил и леса из таких файлов. Модуль компиляции заключительного варианта СПР позволяет получить СПР, настроенную на задаваемую предметную область, в виде исполняемого файла. В качестве языка представления описания функциональных систем в обменном формате может быть выбран, например, extensible Markup Language (XML) [59]. Описание функциональной системы может быть образовано тремя блоками: 1. описание предметной области, состоящее из её имени, имён атрибутов (переменных функциональной модели) и их параметров (число возможных значений и способ их задания), наименований классов (значений функции функциональной модели). 2. Описание функциональной модели, например, в виде списка пар ( интервал , значение ), 3. Описание области определения, например, в виде списка пар ( ин-тервал , логическое значение ). Правила описания этих блоков (язык для представления обобщенных графиков отображений) даны в следующем пункте. Программный комплекс POOREX 2002 в качестве языка представления описания функциональных систем использует XML (extensible Markup Language) [59]. Для описания логических структур файлов XML используются схемы одного из двух различных форматов по выбору пользователя: XSD (XML Schema Definition) или DTD (Data Type Definition). Последний представляет собой самый простой и распространенный диалект описания схем. Формат DTD позволяет описывать вложенность тегов и атрибутов. XML и, в самом упрощенном виде, тип хранимых данных. Самым широким спектром возможностей при описании XML-документа на сегодняшний обладает формат XSD. При использовании данного формата описания логической схемы файлов XML, содержащих данные модели принятия решений, все файлы Jhm, содержащие информацию о предметной области описываются файлом theme.xsd:
