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

Пи ОД

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

БЕРИКОВ Владимир Борисович

МЕТОДЫ ПОСТРОЕНИЯ МОДЕЛЕЙ ОБЪЕКТОВ УПРАВЛЕНИЯ В КЛАССЕ ЛОГИЧЕСКИХ РЕШАЮЩИХ ФУНКЦИЙ

05.13.01 - Управление в технических системах

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

Новосибирск 1996

Работа выполнена в Институте математики имени С.Л. Соболева Сибирского Отделения Российской Академии Наук.

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

член - корреспондент РАЕН Лбов Г.С.

Официальные оппоненты:

- доктор технических наук, профессор Симонов М.М.

- кандидат технических наук

Курбангалеев З.Г.

Ведущая организация (предприятие) - Вычислительный центр СО РАН

Защита состоится 28 февраля 1996 г. в 10 часов на заседании диссертационного совета Д 063.34.03 в Новосибирском Государственном техническом университете - 6300Э2, г.Новосибирск - 92, пр. К.Маркса, 20, НГТУ.

С диссертацией можно познакомиться в библиотеке НГТУ.

Автореферат разослан

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

Г.П. Чикильдин

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

Актуальность проблемы. В настоящее время большое значение имеют опросы, связанные с анализом, прогнозом состояния и управлением азличными объектами. При этом информация о данных объектах часто меет вид набора наблюдений некоторых случайных, характеристик. В вязи с этим актуальной является задача разработки математических етодов регрессионного и дискриминантного анализа .- - . -аблюдений и построении на их оонове адекватной математической одели, описывающей свойства рассматриваемого объекта и позволяю-ей осуществлять эффективное управление им (стохастической иден-ификации объекта управления). Данные задачи возникают, как пра-ило, в условиях, когда исходная информация описывается характе-истиками разных типов (количественными и качественными), при ин-ормационной неопределенности (ограниченном объеме данных, отсут-твии априорных сведений о характере распределений). Кроме того, асто требуется получить математическую модель объекта управле-ия, сформулированную на языке логических суждений ("знаний"^. !етоды, основанные на логических решающих функциях, в отличие от олыпинства других, успешно решают такие задачи. Поэтому важным опросом становится дальнейшая разработка и теоретическое иссле-;ование этих методов.

Известно, что прогресс в области оптимального управления в начительной степени связан с разработкой и использованием мето-;ов решения экстремальных задач. Ранее ([4]) был предложен подход :. нахождению глобального экстремума, основанный- на многошаговом дативном случайном поиске с использованием на каждом шаге адап-■ации методов регрессионного анализа в» классе логических решающих >ункций. Для повышения качества получаемых решений необходимо юздание новых эффективных методов решения задач регрессионного, взлиза в данном классе.

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

Поставленная задача включает в себя ряд взаимосвязанных теор1 тических и технических вопросов, к которым относятся:

- исследование свойств логических решающих функций: сходимос-логических функций к оптимальным; представления логических фут ций в виде .деревьев решений; свойств критериев оптимальности.

- применение разработанных алгоритмов для решения зада1 оптимизации многоэкстремальных функций и задачи регрессионно] анализа с использованием активного эксперимента;

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

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

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

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

Введено понятие линейно-аддитивного критерия оптимальное: дерева решений и найдено необходимое условие его оптимальности.

Разработан рекурсивный метод построения дерева решений с опи мизируемой степенью ветвления в каадой вершине и регулируемс глубиной перебора ("и-метод").

Разработан алгоритм поиска приближенного значения глобально! экстремума вещественной фупкции' от разнотипных (дискретных непрерывных) переменных с применением и-метода.

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

Создана программная система ЛАСТАН, реализующая разработанш алгоритмы регрессионного и дискриминантного анализа.

Практическая ценность и реализация результатов работы.

Основную практическую ценность работы составляет разработанный н-метод, который может применяться при решении широкого круга задач многомерного статистического анализа (регрессионного и дис-криминантного анализа; ]сластер - анализа; анализа временных рядов). В отличие от большинства других методов этот метод позволяет строить логико-вероятностные модели изучаемых объектов или явлений. Применение деревьев решений дает возможность строить сложные иерархические модели, что позволяет находить иерархические взаимосвязи между различными свойствами объектов. Использование деревьев с произвольной степенью ветвления делает модель более естественной и удобной для восприятия. Регулируемая глубина перебора позволяет оптимальным образом сочетать требуемое качество решения с имеющимися возможностями ЭВМ (объемом памяти и быстродействием).

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

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

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

' Разработанные алгоритмы использовались•в Институте терапии СО РАМН (г.Новосибирск) для решения задач поиска маркеров атеросклероза, в лаборатории экологической информатики Института, химии нефти СО РАН (г. Томск) для решения задач моделирования и прогнозирования состояния окружающей среды, в Институте цитологии и генет:вси СО РАН (г. Новосибирск) для анализа селокционйых признаков злаковых культур, па ПО "Кировский завод" (г. Санкт-' Петербург) для решения задач, связанных с модернизацией оборудования цеха выпуска кабин тракторов, в Центральной клинической больнице СОРАМН для определения степени эффективности метода

лечения больных сахарным диабетом, в Институте общей паталогии и экологии человека СО РАМН для определения риска общепатологических синдромов, в Сибирском научно - исследовательском гидрометеорологическом институте для оперативного прогнозирования погоди в аэропортах Сибири. Модификация разработанной программной системы (система СПАРК) передана в Региональный Центр экстремальной медицинской помощи (г.Новосибирск) для анализа и прогнозирования чрезвычайных ситуаций [14].

Апробация работы. Основные положения работы докладывались и обсуждались на: школе-семинаре "Статистические методы распознавания образов и компьютерной кластеризации", г.Киев, сентябрь. 1989 г.; XI Всесоюзной конференции "Проблемы теоретической кибернетики", г.Волгоград, 1990 г.; Республиканской научной конференции "Математическое и программное обеспечение анализа данных", г.Минск, декабрь 1990 г.; I Всероссийской конференции "Математические проблемы экологии",г.Новосибирск, ишь 1992 г.; школе-семинаре "Компьютерный анализ данных и моделирование", г.Минск, декабрь 1992 г.; II Всероссийской конференции "Математические проблемы экологии", г.Новосибирск,-июнь 1994 г.; Меадународной конференции по математической логике, посвященной 85-летию со дня рождения А.И.Мальцева, ноябрь 1994 г.; конференции "Математические методы распознавания образов" (ММРО-7), г.'Пущино, сентябрь 1995 г., -Меадународной конференции "Компьютерный анализ данных и моделирование", г. Минск, сентябрь 1995 г., семинарах Института математики СО РАН и кафедры теоретической кибернетики НГУ.

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 147 странице машинописного текста, 22 рисунков, 6 таблиц, библиографию из 134 наименований отечественной.и зарубежной литературы и приложение.

СОДЕРЖАЩЕ РАБОТЫ

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

В -ПЕРВОЙ ГЛАВК диссертации' проводится краткий анализ литературы, посвященной решению задач регрессионного и диасриминантного анализа, вводятся основные понятия, используемые

в работе, приводятся полученные в работе основные теоретические результата.

В первом параграфе приводится обзор основной литературы, посвященной решению поставленной задачи.. Можно провести классификацию данных работ по следующим основным признакам: вид решаемой задачи (дискриминантного или регрессионного анализа); наличие или отсутствие априорной информации о принадлежности распределений к известному параметрическому классу функций (параметрический или непараметрический подход); тип. используемых переменных (только непрерывные, дискретные либо булевы, 'разнотипные). Делается вывод о том, что большинство работ посвящено вопросам разработки, исследования и применения методов, ориентированных на случай переменных одного и того же типа. К альтернативному подходу можно отнести методы, основанные на логических решающих функциях-от разнотипных переменных. Рассмотрению этого подхода и посвящена данная работа.

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

В зависимости от вида I^ будем различать следующие типы

переменных: х.- непрерывная : л^и ; либо - дискретная (с упорядоченным или неупорядоченным множеством значений):

л 11

Обозначим *•■•хВп-

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

переменные X - непрерывны.

Имеется также долевая ( предсказываемая ) переменная У, которая может быть либо непрерывной, либо дискретной.

В зависимости от типа предсказываемой переменной У рассматриваются задачи дискриминантного или регрессионного анализа.

Для задач дискрш.шюимного анализа ("распознавания образов", "классификации с учителем") переменная у - дискретная с неупорядоченным множеством значений в^Гих, ,...,6^}, к ^ 2. Символ

Б=1.,К, называют Б-м классом (или "образом").

Для задач регрессионного анализа переменная У - непрерывная: Случай дискретной упорядоченной У в данной работе не рассматривается.

Исследователь формирует случайную независимую выборку объектов

А={а1,...,аМ}, А = Г и одновременно путем проведения соответствующих измерений получает набор наблюдений - таблицу

бамныг У=((х1 ,у1 ),-..,(хН,у11)), где х1=(Х1 (а1) ,..., ^(а1)) -

вектор значений переменных для а-го объекта, у^У^*), ±=1,...,ы.

Обозначим через тс(х,у) закон распределения случайной величины (Х,У).

Основная задача заключается в следующем.. Используя наблюдения,

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

Н(71,г), вычисленная по выборке.

• Далее рассматривается класс логических регющих функций от разнотипных переменных [I]. .

Логическая решающая функция представляется в виде набора высказываний вида

"Если хсе3, то V = ув

где у53 € (Е1,...- разбиение пространства й, причем каждая область Ее представляется в следующем виде:

Е^Е®* ...

в!'с {В.} и {И ЛЕ •} и {В.},

Ы О « и — V

где Е.сБц, Е.Фф. В случае непрерывной переменной х. множеством Е-

«3 «3 0 и г)

может быть произвольный полуинтервал (а,ъ] числовой оси; в случае дискретной упорядоченной переменной х^ множество Е^ - объединение произвольных соседних -значений переменной, а в случае дискретной неупорядоченной переменной х. множество Е. - объединение любых ее

значений.. Пусть Фм -'множество всевозможных разбиений (Е1,...,5?®)

указанного вида, Ry- множество всех упорядоченных наборов вида

(у1,?2,...,?1), где у3^. Тогда каадаялара <а,г(а)>, где а с

Шы, г(а)е Ry определяет логическую решхщро фугшиию следующим

образом: t(x)=ys тогда и только тогда, когда х е Е?

Классом логических решающих функций Фм назовем множество логических решающих функций, определяемых всевозможными парами <а,г(а)>, где а е Фы, г(а)е

Далее в диссертации рассмотрен класс деревьев решений. Рассматриваются деревья решений с произвольной степенью ветвления, т.е. из каждой внутренней вершины дерева может выходить произвольное число ветвей, которым соответствуют простые высказывания "х-се.", где Е. с D-, е. имеют вид, описанный выше.

d J J J »)

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

Утверждение 1.1.1 Любую логическую функция мояно представить в виде некоторого дерева решений с числом конечных верам, равные

Г=ПЬ П I cardf U ({ai> U {b^})| +1 | , • ¿=1 0 з=й+1 s=i J

где I. - число значений дискретной переленной Х- (3=1,2,...,d), J J

a^. u b^ - значения границ интервалов, соответствующих тожествам

«J и

Е^ для непрерывной переменной X. (,j=d-fl,, — ,п) [17] (символом J ¿J

card здесь обозначена мощность соответствующего множества).

В-параграфе 1.2 исследуется вопрос о сходимости (в смысле . величины средних потерь) последовательности логических решающих функций, представленных в виде деревьев решений, к оптимальной решающей функции в случае задачи регрессионного анализа. Теорема 1.2Л Пусть для любого заданного распределения тс(х,у) случайной величина (x,Y) определена оптимальная решающая функция

y=i°(x) как такая функция, для которой выполняется: R(ic,f°)=inf

R(7t,f), где Ф - 1сласс фушщий, для которых существует жателгати■-ческое ожидание фушсции потерь. Тогда существует последовательность логических региахяцих фунщий, представленных в виде деревьев

решений, сго&шряся тю величине средних потерь к оптимальной решающей функции [161.

Для задачи дискришнантного анагяша в работах [2] (для числа классов, равного дву») и [3] (Д№ произвольного конечного числа классов) было доказано, что для любого заданного распределения вероятности ыовно найти танрю логическую решающую функцию, которая отличается по значению вероятности ошибки от оптимальной (байесовской) решавдв* -фаивдив sa сколь угодно «злую величину. В последней работа введено таи» понятие упорядочения классов распределений по сложности» используя в качестве меры сложности распределения число соответствующих логической решающей функции подобластей разбиения. Доказанное свойство сходимости означает, что класс логических решающих функвдй достаточно-"богат", т.е. дает принципиальную возможность решать задачи для сколь угодно сложных распределений.

Теорема 1.2 Л распространяет данный результат на случай задачи регрессионного анализа.

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

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

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

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

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

В работе доказываются утверждения, устанавливавшие свойства

монотонности функции эмпирического риска для условно-оптимальных (т.е. оптимальных при фиксированном числе конечных вершин) и эффективных (оптимальных в смысле Парето) деревьев решений.

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

Кроме•описанных способов сведения двукритериальной задачи эптимизации к скалярной задаче возможны и другие способы. В общем случае обозначим через (¡г(V),значение произвольного критерия а цля дерева г, вычисленное по таблице V. Обозначил через В

юрневую вершину дерева г, через В1 - ¿-¡о дочернюю вершину, а

крез А1- множество объектов, соответствующих вершине В1 (т.е.

гаких объектов.аел, что х.,(а)сБ^, где е^б- - подобласть, соот-

о и »] «]

зетствующая ветви (В,Б1) ), ,2,... ,1, где 1 - число дочерних зершин корневой вершины В. Поддерево с корневой вершиной В1 дерева £ обозначим через г1. Для каждого поддерева г1 можно определить значение гсритерия я^Л(V1), вычисленное по таблице у3,

соответствующей множеству объектов А1.

Определение. Назовсл критерий ц линейно-аддитивным, если для тОого дерева решений. 1 выполняется :

ч{: (V) 71 (У1 1 (У1 )+т° (V),

7°(V), 71(У1) ,..., ч1{ч1), 71(У1)>0, 1=0,1,2, ...,Х - некто-тые коэффициент.

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

Утверадение 1.3.6. (необходимое условие оптимальности для 1Ш1ейно-аддитив>юго критерия). Для того, чтобы дерево Т бшо )гшил!алышл в случае линейно -аддитивного критерия а, необходимо, тпобы каждое из поддеревьев г^ дерева г, 1-1,г...,I также было бы | шилалыаш.

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

Во ВТОРОЙ ГЛАВЕ диссертации (параграф 2.1) проводится обзор существующих методов построения деревьев решений в задачах дис• криминантного и регрессионного " анализа. Показано, что данные метода можно разделить на две основные группы. К первой группе относятся метода поиска строго - оптимального по заданному критерию качества дерева. Ко второй группе относятся методы направленного поиска оптимального дерева (в этом случае может.быть найдено локально - оптимальное дерево). К первой груше методов можно отнести методы полного перебора, метода, использующие динамическое программирование и методы типа "ветвей и границ"-

Общей чертой большинства известных направленных методов построения оптимальных деревьев является процесс последовательного независимого "разрастания" перспективных вершин в одноярусные поддеревья (т.н. "top-down" процесс). На основе обзора делаются следующие выводы:

1. Методы построения строго-оптимальных по критерию качества деревьев становятся мало эффективными для задач с большим объемом обучающей выборки и большим числом переменных'.

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

В параграфе 2.2 описывается предложенный рекурсивный метод направленного поиска оптимального дерева решений с переменной глубиной перебора и оптимизируемой степенью ветвления в вершинах, который для краткости будем называть R-методом [6,7,8,14]. Особенность данного метода заключается в способе "разрастания" перспективных вершин, который является некоторой модификацией метода динамического программирования.

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

В качестве критерия оптимальности дерева решений для Я-метода применяется описанный в параграфе 1.2 критерий, записанный в следующем виде: ч=а м^, + Е(у,г), где а > 0 - параметр "соотношения между сложностью и точностью решения". Полученное дерево может не быть строго оптимальным, поскольку' рассматриваются не всевозможные объединения вершин, а только такие, которые дают максимальное улучшение значения критерия. Так как оптимальные поддеревья ищутся независимо друг от друга, то для оптимальности всего дерева становится необходимым требование линейной аддитивности критерия.

Далее в работе оценивается трудоемкость и требуемая память для предложенного метода.

Можно привести следующие доводи в пользу предлагаемого л-метода, по отношению к существующим методами поиска оптимальных деревьев решений :

1. Я-метод позволяет увеличивать глубину перебора при построении поддеревьев; при этом строятся не одноярусные, а многоярусные поддеревья. Данное свойство.позволяет решать задачи с более сложными зависимостями и совместным влиянием различных переменных на предсказываемую величину.

2. Предлагаемый метод позволяет оптимизировать степень ~~ ветвления в каждой вершине дерева решений, что делает возможным

привлечение более широкого класса деревьев'(при той же глубине перебора) и тем самым улучшать качество решений.

3. й-метод позволяет оптимальным образом сочетать требуемую глубину перебора (а значит качество решения) с имеющимися в наличии ресурсами ЭВМ (объемом памяти и временем работы). При этом появляется возможность путем изменения глубины перебора привле-

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

В параграфе 2.3 проводится исследование эффективности и-метода на' тестовых и модельных примерах. Под модельными примерами имеются в виду таблицы данных, ■ полученные согласно заданному распределению ("модели") с помощью датчика случайных чисел. Разработана процедура статистического моделирования [12], которая служит для оценки вероятности ошибки (в случае задачи дискрими-нантного анализа) и использует понятие упорядочения классов распределений по сложности. Данная процедура состоит в многократном генерировании случайных выборок для обучения и контроля в соответствии со случайно выбранными распределениями различной сложности; построении с помощью исследуемого метода решающей функции:

оценке вероятности ошибки ,по контрольной выборке. Полученные оценки затем усредняются по всем экспериментам. С помощью программной системы "ПОЛИГОН", предназначенной для сравнения алгорит мов распознавания образов [4] проведено также сравненио метода с -некоторыми другими методами: методами, использующими линейные и квадратичные дискриминантные функции; методом, использующим непараметрические оценки плотности; существовавшими ранее методами, строящими решение в классе логических решающих функций.

Результаты исследований подтверждают эффективность разработанного метода.

В ТРЕТЬЕЙ ГЛАВЕ описывается применение R-метода для решения задач нахождения приближенного значения глобального экстремума вещественной функции и задачи регрессионного анализа с использованием активного эксперимента (планирования экстремального и регрессионного эксперимента). Первая задача уже решалась с использованием класса логических решающих функций, вторая задача с использованием . класса логических решающих функций ранее не решалась.

В параграфе 3.1 описан алгоритм глобальной оптимизации [II], реализующий метод случайного поиска с адаптацией. При всех прочих равных условиях предполагается, что вероятность нахождения глобального экстремума функции в произвольной подобласти E^cd (предполагается, что область D ограниченаУ тем больше, чем больше мощность подмножества и чем больше значение функции (при поиске глобального максимума) получено к рассматриваемому моменту поиска в данной подобласти. Сила указанной гипотезы, задаваемой в виде параметра адаптации, зависит от числа проведенных испытаний. Конкретный вид формализации данной гипотезы приводится в работе [Б]. В отличие от алгоритма, описанного в указанной работе, для разбиения области D на подобласти предлагается использовать R-метод построения дерева решений.

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

Отметим преимущества предложенного алгоритма по сравнению с существующими алгоритмами.

I.-Данный алгоритм позволяет находить экстремум функций от

разнотипных (дискретных и непрерывных) переменных;

2. Алгоритм может работать в условиях "зашумления" целевой переменной;

3. Реализация алгоритма не требует большого числа вспомогательных вычислений и памяти ЭВМ.

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

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

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

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

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

ЧЕТВЕРТАЯ ГЛАВА диссертации (параграф 4.1) посвящена компьютерной систеш ЛАСТАН [10,15], созданной в соавторстве с Лбовым Г.С. и Старцевой Н.Г. Система ЛАСТАН предназначена для анализа многомерной статистической информации с целью обнаружения логических закономерностей и принятия на их основе решений в различных трудаоформализуемых областях исследований : экологии, медицине, биологии и т.д. Методы, используемые системой ЛАСТАН, основаны на аппарате логических решающих функций и включают в себя описанный в параграфе 2.2 и-метод построения оптимального дерева решений.

В рамках системы ЛАСТАН на основе обнаруженных закономерностей могут быть решены следующие задачи.

1. Группировка объектов по похожести их характеристик (кластер - анализ).

2. Построение решанцих функций распознавания (задача дискрими-нантного анализа).

3. Предсказание значений количественной характеристики (задача регрессионного анализа).

4. Анализ и прогнозирование временных рядов.

В работе обосновывается выбор данного набора задан, описываются основные функции системы ЛАСТАН и способы их реализации, приводится блок-схема системы ЛАСТАН, проводится краткий сравнительный анализ системы ЛАСТАН с некоторыми другими пакетами, предназначенными для решения задач многомерного статистического анализа.

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

Отличительной чертой системы ЛАСТАН является то обстоятельство, что алгоритмы анализа данных, которые используются системой, основаны "целиком на классе логических решающих функций от разнотипных переменных, представленных в виде деревьев решений.

Другой отличительной характеристикой системы ЛАСТАН ' является сочетание следующих свойств:

1. Возможность обработки разнотипной информации (как количественной, так и качественной одновременно);

2. Выдача решения на языке, близком к естественному языку логических суждений ("знаний" о взаимосвязи характеристик исследуемых объектов);

3. Использование методов с более •слабыми ограничениями на класс распределений; при этом данные методы, по сравнению с известными, остаются более устойчивыми к малым объемам выборки;

4. Возможность выделять наиболее информативные характеристики объектов.

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

Параграф 4.2 посвящен описанию нескольких примеров применения системы ЛАСТАН для решения прикладных задач анализа данных. Пер-

вая из этих задач связана с экологическим мониторингом и обработкой наблюдений (изучение загрязнения реки Томь [10]), две следующие - с анализом медицинской информации (изучение возможности лечения методом волевой ликвидации глубокого дыхания больных сахарным диабетом, в сочетании с атеросклерозом; поиск.наиболее информативных маркеров атеросклероза).

Приводятся найденные с помощью системы ЛАСТАН закономерности, характеризующие взаимосвязи характеристик изучаемых объектов.

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

Основные результаты диссертационной работы состоят в следующем:

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

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

3. Введено понятие линейно-аддитивного критерия, оптимальности дерева решений и найдено необходимое условие его оптимальности.

4. Разработан и исследован рекурсивный метод построения ' дерева решений с оптимизируемой степенью ветвления в каждой вершине и регулируемой глубиной перебора ("Н-метод"). •

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

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

7. Создана программная система ЛАСТАН, реализующая разработанные алгоритмы регрессионного и дискриминантного анализа.

8. Решен ряд практических задач, связанных с анализом наблюдений (анализ загрязнения реки Томь; изучение возможности лечения боль-, ных сахарным диабетом; поиск наиболее информативных маркеров атеросклероза );

9. Результаты работы дают возможность, разрабатывать различные

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

ЦИТИРУЕМАЯ ЛИТЕРАТУРА

1) Лбов Г.С. Методы обработки разнотипных экспериментальных данных. - Новосибирск: Наука, 1981, - 156 с.

2) Манохин А.Н. О свойствах инвариантности и состоятельности алгоритмов распознавания, основанных на логических решающих функциях.- В кн: Эмпирическое предсказание и распознавание образов (Вычислительные системы, вып.83), - Новосибирск, 1980, с.42-52.

3) Лбов Г.С:,Старцева Н.Г. Сложность распределений в. задачах классификации. - ДАН, т.338, .Кб, 1994 г., с.592-594.

4) Лбов Г.С., Старцева Н.Г. Сравнение алгоритмов распознавания с помощью программной системы "Полигон"- Выч. с-мы, вып. 134, 1990 г„ с. 56-66.

5) Лбов Г.С. Алгоритмы поиска приближенного значения глобального экстремума функции- - Проблемы случайного поиска, Рига, Зинатпе, 1980, с.92-115.

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

6) Бериков В.Б. Рекурсивный алгоритм построения решающего правила распознавания в классе логических функций.- Тезисы докладов XI Всесоюзной конференции "Проблемы теоретической кибернетики", 4.1(2), Волгоград, 1990, с.9. ■

7) Бериков В.Б. Рекурсивный алгоритм решения задач регрессионного анализа, использующий логические функции. -Тезисы докладов Республиканской конференции "Математическое и программное обеспечение анализа данных", Минск, 1990, с.II. .

8) Бериков В.Б.-, Лбов Г.С. Рекурсивные алгоритмы решения задач дискриминантного и регрессионого анализа. - В кн: "Машинное моделирование и планирование эксперимента", Новосибирск, НЭТИ, 1991, с.48-56.

9) Бериков В.Б. Регрессионный анализ в классе логических функций с использованием активного эксперимента.-Тезисы докладов научной

Т8

школы-семинара "Компьютерный анализ данных и моделирование", Минск, 1992, с.8.

10) Лбов Г.С., Старцева Н.Г..Бериков В.Б. Изучение загрязнения реки Томь с помощью системы ЛЛСТЛН.-Тезисы докладов Всероссийской конференции "Математические проблемы -экологии", Новосибирск, 1992, с.27.

11) Лбов Г.С., Бериков В.Б., Зенкова H.A. Экспериментальное сравнение алгоритмов адаптивного поиска глобального экстремума функции.-В- кн: Труды учредительной конференции международной ассоциации "Нетрадиционные методы оптимизации", Красноярск, КИКТ, 1992, с. 48-52.

12) Бериков В.Б. Статистическое моделирование для оценки усредненной вероятности ошибки в зависимости от сложности

- стратегии природа.-Тезисы докладов конференции "Математические методы распознавания образов", Москва, 1993, с.13.

13) Lbov G., Berikov V. Recursive Method of Formation of the Recognition Decision Rule in the Class of Logical Functions.-Pattern Recognition and Image Analysis, Vol 3, № 4, 1993, pp.428431'.

14) Бериков В.Б. 0 возможности представления логической решающей функции в виде дерева решений. -Тезисы сообщений Международной конференции по математической логике, посвященной 85-летию со дня рождения А.И.Мальцева. Новосибирск, 1994, с.27.

15) Лбов Г.С., Старцева Н.Г..Бериков В.Б..Викентьев A.A. Система прогноза и анализа чрезвычайных ситуаций.-Тезисы докладов второй Всероссийской конференции "Математические проблемы экологии", Новосибирск, 1994, с.63-64. '

16) Berikov V. About convergence of logical decision functions to optimal decision functions.-Pat tern Recognition and Image Analysis, Vol. 5, JÉ1, 1995, pp.323-324.

17) Бериков В.Б. Представление логической решающей функции в виде дерева решений.-Тезисы докладов конф. "Математические методы распознавания образов" (ММРО-7), Москва, 1995, с.8.

18) Бериков В.Б., Лбов Г.С. Исследование рекурсивного метода построения логической решающей функции.- Сборник научных статей Международной конференции "Компьютерный анализ данных.и моделиро-ваше", Минск, 1995, с.40 - 44..