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

I • - На правах рукописи

Неделько Светлана Валерьевна

МЕТОДЫ ПОСТРОЕНИЯ ЛОГИКО-ВЕРОЯТНОСТНЫХ МОДЕЛЕЙ ВРЕМЕННЫХ РЯДОВ

Специальность 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

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

ч 4 ЯНд 2010

Новосибирск - 2009

003490186

Работа выполнена в Учреждении Российской академии наук Институте математики им. С.Л. Соболева Сибирского отделения РАН и в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

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

профессор Лбов Геннадий Сергеевич

Официальные оппоненты: доктор технических наук

Золотухин Юрий Николаевич,

кандидат физико-математических наук, доцент Пестунов Игорь Алексеевич

Ведущая организация Учреждение Российской академии

наук Институт систем информатики имени А.П. Ершова Сибирского отделения РАН, г. Новосибирск

Защита состоится «21 » января 2010 года в 14 часов на заседании диссертационного совета Д 212.173.06 при Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет» по адресу: 630092, г. Новосибирск, пр. К. Маркса, 20.

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

Автореферат разослан декабря 2009 г.

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

Чубич В.М.

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

Актуальность проблемы

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

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

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

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

Цель работы

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

симость, возможность применения многовариантного решающего правила.

Задачи исследования

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

Выбор и обоснование критерия качества логико-вероятностной модели временного ряда.

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

Разработка и исследование метода адаптивного поиска дерева решений.

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

Применение разработанных методов к решению прикладных и модельных задач.

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

Методы исследования включают в себя аппарат теории вероятностей и математической статистики, теоретической кибернетики; математическое моделирование с применением средств вычислительной техники.

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

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

1. Предложен алгоритм построения логико-вероятностной модели многомерного разнотипного временного ряда на основе многовариантного решающего правила.

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

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

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

Научные результаты, выносимые на защиту

Критерий качества логико-вероятностной модели разнотипного временного ряда.

Алгоритм построения логико-вероятностной модели многомерного разнотипного временного ряда на основе многовариантного решающего правила.

Метод решения задачи прогнозирования временного ряда путём построения информативного пространства состояний.

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

Исследование качества прогнозирования в зависимости от длины реализации, сложности логико-вероятностной модели ряда и длины предыстории.

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

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

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

Разработано программное обеспечение, реализующее предложенные методы.

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

Достоверность результатов

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

Апробация работы

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

Международные конференции «Интеллектуализация обработки информации», г. Алушта: июнь 2002 г. (ИОИ-2002), июнь 2006 г. (ИОИ-2006), июнь 2008 г. (ИОИ-2008).

Международные конференции «Knowledge-Dialogue-Solution», г. Варна, Болгария: июнь 2006 г. (KDS-2006), июнь 2007 г. (KDS-2007).

Международная конференция «Classification, Forecasting, Data Mining», г. Варна, Болгария: июнь 2009 г. (CFDM-2009).

Семинары Института математики СО РАН.

Отдельные части работы прошли экспертизу в ходе выполнения проектов, поддержанных грантами РФФИ: № 04-01-00858-а, №07-01-00331-а.

Личный вклад

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

Публикации

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

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

Диссертационная работа состоит из введения, пяти глав, заключения, библиографического списка из 89 наименований отечественной и зарубежной литературы и трех приложений, изложенных на 149 страницах машинописного текста. Иллюстративный материал представлен 33 рисунками и 9 таблицами.

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

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

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

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

Постановка задачи прогнозирования. Имеется и-мерный временной ряд V = | г = 1, N }, г' =(г(.....г'„), ztj^Zj. Здесь - множество

п

допустимых значений _/'-й переменной ряда.

М

Пусть ряд является реализацией случайного л-мерного процесса г(/) с дискретным временем, который задается переходной (условной) вероятностной мерой —>[0,1], где Л - о-алгебра подмножеств из Ъ, а <1 — длина предыстории, которая определяет распределение в заданный момент.

Требуется на основе имеющихся данных V построить прогноз временного ряда в моменты времени ¡> N в соответствии с некоторым критерием (зависит от варианта постановки задачи).

Введём обозначения X , У = 2, причём X будем использовать для обозначения пространства предысторий, а У— для пространства значений в момент времени, для которого делается прогноз. Таким образом, У — пространство целевых, а X— прогнозирующих переменных.

Тогда переходную меру можно записать как

Р [г/г(г-1), г(/-2),..., г(г-</)] =Р [У/х].

В данных обозначениях вероятность события Еу е А, записывается как

Р (z{t)e Ey/z(t-í), z(t-2),..., z(t-d))S р{Еу/х) =р[у/х](е¥).

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

Решающая функция обычно определяется как отображение /: X —> У . Такую функцию будем называть одновариантным решающим правилом.

Многовариантное решающее правило есть /: X -» 5, где решение представляет собой множество пар я = к = 1,м|,

рк - оценка условной вероятности р[Еу¡х), В отличие от

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

Логико-вероятностную модель определим следующим образом:

Л ={(*&,

где Е1Х с X образуют разбиение аь = [¿^ | / = 1, пространства X.

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

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

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

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

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

Пусть заданы пространства X и У, вероятностные меры Р[У], совместное распределение и условная мера Р[к/х\,

хеХ.

Критерий информативности определим как

с1Р2

¿Ц йц

(1/л - разность плотностей;

7ф>[х,у]) = \р{р[¥1х\р[¥])йр[х],

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

Использовались следующие меры различия для распределений: уОс(Р1,Р2)= с1Рх —дивергенция Кульбака-Лейблера;

РЕ{р\'Рг)-\н(Рг)-Н{Р\)\ - разность энтропий;

Ри{РьР2)= ¡\dP2-dn\-

рм(Р1,Р2)^тах\Р1(А)-Р2(А)\.

АеВ

Здесь Н{р)--рс{р,^) = -\\п^ ¿Р, а ВсА - заданный класс подмножеств из а-алгебры А.

Для оценивания информативности модели введём переменную X, значения которой соответствуют областям разбиения аь ~ \е1х | ' = 1, для логико-вероятностной модели .

Для каждого х е X введём переменную У;, значения которой соответствуют областям Еу с; У многовариантного решения

= ^ = Гм},где Р1с=Р(Е£/х).

Критерий информативности модели: к(/1) = \р(р[¥~х /*], Р[¥~ ]) <1Р[Х].

Выборочное значение критерия получается подстановкой выборочных оценок вероятностей.

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

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

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

Метод построения эмпирической модели состоит в следующем.

Пусть Л = {Е0)^г\со=Тл}, и Е°'=г, соФт^Е*0 глЕт =0 1 0)= 1

- некоторое разбиение пространства Ъ. Тогда исходному многомерному ряду V можно сопоставить одномерную символьную последователь-

ность н> = < а/

Случайному процессу г(?) будет соответствовать процесс переходные вероятности для которого обозначим

/ЧК,^,...,^ =РШ = ®о1со{1-\) = со1.....*»(*-<*) = <%)■

Совместная вероятность есть

Раъ..щ, =р{ А = ) А Й'-Ф ¿Н] •

чг=0 ^ Чг=0

Критерий информативности Ки = \/±.и(1Р[Х,У] для разбиений принимает вид

Рщ Р со^,(^„.„ша

' Ра\аУ1...щ

/ ч к к

(Оа^1

или в эквивалентной форме

. к к . . Ки\Л)= X— X | Ра0а\...соа - Рео0Рй\...а)а\>

СОо=1 (Дд=\

к

где Рц а^ = 2 Рщ/Ц щ ' вероятность появления предыстории дли-к к

ны (1, рщ = Х- Т Ро0со1...соа ■ й»1=1

При ¿=1 получаем

Ки{Л)= £ Е | Рлад - РшоРац

¿Ц)=1 6^=1

Другие критерии качества эмпирической модели также легко вычисляются для процесса о)(?), в частности, критерий на основе дивергенции примет вид

км- Е — Л Рсицы

Щ

1п

Рщсо^-щ

0)4= 1 ~ " РсоцРа^.-хоа

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

0,65

г2 < 0,65

< 0,5

О

о

Переходные вероятности

1 2 3

1 0 1 0

2 0 0 1

3 1 0 0

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

Во втором параграфе рассматриваются варианты алгоритма прогнозирования многомерного разнотипного временного ряда с использованием различных классов разбиений пространства состояний:

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

На рис. 1 для модельной задачи приведены области, соответствующие состояниям случайного процесса, дерево решений, задающее разбиение на указанные области, и матрица переходных вероятностей Рш\со = Рашт /Ра> ■ Значения в таблице отражают вероятность перехода

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

Приведём пример реализации данного процесса в виде последовательности пар значений переменных и 2^. Имеем двумерный ряд: ((0,5;0,71), (0,73;0,45), (0,08;0,28), (0,04;0,85), (0,69;0), (0,49;0,55), (0,2;0,88), (0,83:0,39), (0,5;0,47), (0,87;0,81), (0,61 ;0,51), (0,39;0,23), (0,8;0,75), (0,7;0,32), (0,19;0,34), (0,74;0,95), (0,62;0,16), (0,33;0,45), (0,38;0,89), (0,85,0,25), (0,19;0,05), (0,65:0,68), (0,78;0,45), (0,46:0,04),...). Несмотря на простоту модели, при визуальном анализе приведённой реализации процесса закономерности неочевидны.

Алгоритм позволяет восстанавливать закономерности также при наличии «шума», когда нулевые переходные вероятности заменялись на 5, а единичные на 1-25, при 8 < 0,2, N ~ 100.

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

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

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

Во втором параграфе проведено статистическое моделирование в задаче классификации. Исследовано поведение алгоритма ЬЯР в зависимости от объёма выборки, числа конечных вершин дерева.

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

Рис. 2. Зависимость среднего критерия информативности эмпирической аппроксимации случайного процесса от числа областей разбиения к при Ы = 100 и различных 5: 1) 5 = 0; 2) 5 = 0,1; 3) 5 = 0,2; 4) 5 = 0,33. Для левой диаграммы <1=1, для правой <1 = 2

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

\р{Р'[¥1х],Р[У1х])йР[х}

или

Д"(р[х, У], Р'[Х, У ]) = р(Р'[х, У ], Р[Х, У ]),

где Р'\х,У\ есть выборочная оценка вероятностной меры. При этом наиболее подходящим расстоянием представляется рц.

В работе методом статистического моделирования исследована зависимость критерия Ри{р'[х,у\р\х,у\) от длины реализации и сложности модели к.

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

Практическим критерием выбора сложности может служить разность между получаемым значением информативности и значением информативности, полученным на такой же длины реализации «равномерного процесса» (этому соответствует кривая при 8 = 0,33).

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

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

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

Задача поиска глобального экстремума и алгоритм СПА для её решения рассматриваются во втором параграфе.

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

Таблица 1

Значения переходных вероятностей для состояний процесса, оцененные для событий с магнитудой не менее 5

А- г 1 2 3 4

0,39 1 0,48 0,32 0,1 0,1

0,33 г 0,37 0,41 0,12 0,1

0,12 3 0,34 0,28 0,23 0,15

0,16 4 0,24 0,24 0,1 0,42

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

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

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

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

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

В третьем параграфе решается задача выявления общих закономерностей в хоралах И.С. Баха.

Четвёртый параграф посвящён задаче прогнозирования состояния ионосферы.

Анализ метеорологических данных представлен в пятом параграфе.

Задача поиска закономерностей в сейсмических данных решена в шестом параграфе.

Для поиска закономерностей использованы данные по землетрясениям из общедоступной базы ftp://www.ncedc.org/pub/ са1а^5/сп5з/. Были выбраны сейсмические события за период

с 1970 по 2005 гг. ^ рис 3 Пространство состояний про-

Первый исследованныи цесса для событий с магнитудой

ряд был составлен из событий с не менее 5 магнитудой не менее 5, произо-

шедших между -10° и 10° географической широты и между 120° и

130° долготы (часть территорий Индонезии и Филиппин). Широта соответствует переменной долгота — Отрицательные значения соответствуют южной широте и западной долготе.

На указанном массиве данных было построено описанным выше алгоритмом дерево решений с числом конечных вершин 4. Глубина предыстории взята 1. Значение критерия Ки на данном дереве решений составило 0,072.

Полученное значение критерия невелико, однако природа сейсмических процессов такова, что сильные закономерности в такого рода данных отсутствуют. При этом найденные закономерности имеют высокую достоверность, поскольку на случайных перестановках вероятность получить значение критерия, превосходящее 0,072, имеет порядок КГ6.

На рис. 3 изображены выделенные состояния процесса, в табл. 1 приведены оценки переходных вероятностей.

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

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

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

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

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

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

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

3. Разработан алгоритм построения логико-вероятностной модели многомерного разнотипного временного ряда на основе многовариант-

ного решающего правила. Работоспособность методов проиллюстрирована на модельных задачах.

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

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

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

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

Список публикаций автора по теме диссертации

1. Миренкова С. В. Метод прогнозирования многомерного разнотипного временного ряда в классе логических решающих функций / С. В. Миренкова // Искусственный интеллект. - 2002. - № 2. -С.197-201.

2. Неделько С. В. Критерий информативности матрицы переходов и прогнозирование разнотипного временного ряда / С. В. Неделько // Искусственный интеллект. - 2004. - № 2. - С. 145-149.

3. Nedel'ko S. V. Extreme Situations Prediction by Multidimensional Heterogeneous Time Series Using Logical Decision Functions / S.V. Nedel'ko // Proc. of Xl-th Intern. Conf. «Knowledge-Dialogue-Solution», Varna, Bulgaria, 20-30 June 2005. - Vol. 1. - P. 84-87. [Прогнозирование экстремальных ситуаций на основе многомерных разнотипных временных рядов с использованием логических решающих функций].

4. Nedel'ko S. V. Extreme situations prediction by multidimensional heterogeneous time series using logical decision functions / S. V. Nedel'ko // Information Theories & Applications. - 2006. - Vol. 13, № 3. - P. 290294. [Прогнозирование экстремальных ситуаций на основе многомерных разнотипных временных рядов с использованием логических решающих функций].

5. Неделько С. В. Исследование связи характеристик алгоритма поиска глобального экстремума и класса функций в дискретном пространстве малой мощности / С. В. Неделько, В. М. Неделько // Искусственный интеллект. - 2006. - № 2. - С. 201-205.

6. Nedel'ko S. V. On relationship between a search algorithm and a class of functions on discrete space / V. M. Nedel'ko, S. V. Nedel'ko // Proc. of ХП-th Intern. Conf. «Knowledge-Dialogue-Solution», Varna, Bulgaria, 20-25 June 2006. - Vol. 1. - P. 287-291. [О связи между алгоритмом оптимизации и классом функций в дискретном пространстве].

7. Nedel'ko S. V. Finding the relationship between a search algorithm and a class of functions on discrete space by exhaustive search / V. M. Nedel'ko, S. V. Nedel'ko // Information Theories & Applications. - 2007. - Vol. 14. - P. 339-343. [Исследование связи между алгоритмом оптимизации и классом функций в дискретном пространстве с использованием полного перебора].

8. Неделько С. В. Построение логико-вероятностных моделей временного ряда при анализе сейсмических данных / С. В. Неделько, Т. А. Ступина // Научный вестник НГТУ. - 2007. - № 4 (29). -С.33-42.

9. Неделько С. В. Прогнозирование разнотипного временного ряда методом адаптивного формирования пространства состояний в классе логических решающих функций / С. В. Неделько // Proc. of ХШ-th Intern. Conf. «Knowledge-Dialogue-Solution», Varna, Bulgaria, 18-24 June 2007. - Vol. 1. - P. 118-122.

10. Неделько С. В. Адаптивное прогнозирование многомерного временного ряда / С. В. Неделько // Таврический вестник информатики и математики. - 2008. - № 2. - С. 104-110.

11. Неделько С. В. Исследование статистической устойчивости логико-вероятностных моделей временного ряда / С. В. Неделько // Научный вестник НГТУ. - 2008. - № 4 (33). - С. 43-52.

12. Неделько С. В. Построение логико-вероятностных моделей временных рядов с использованием цепей Маркова / С. В. Неделько // Classification, Forecasting, Data Mining: Int. book sériés «Information Science and Computing», № 8. - Supplément to the Int. J. «Information Technologies and Knowledge». - ITA, FOI ITHEA, Sofia, 2009. -Vol. 3. - P. 83-90.

13. Неделько С. В. Адаптивный поиск глобального экстремума на множестве деревьев решений / Г. С. Лбов, В. М. Неделько, С. В. Неделько // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09». - M.: Физматлит, 2009. - Т. 1,-С. 182-190.

14. Неделько С. В. Метод адаптивного поиска логической решающей функции / Г. С. Лбов, В. М. Неделько, С. В. Неделько // Сибирский журнал индустриальной математики. - 2009. - Т. ХП, № 3 (39). -С. 66-74.

Отпечатано в типографии Новосибирского государственного технического университета 630092, г. Новосибирск, пр. К. Маркса, 20, тел./факс (383) 346-08-57 формат 60 X 84/16 объем 1.25 п.л., тираж 110 экз.. заказ № 124 подписано в печать 17. 12.09 г

Введение.

Глава 1. Логико-вероятностные модели в задаче прогнозирования.

1.1. Обзор задач и методов анализа временных рядов.

1.1.1. Основные понятия.

1.1.2. Задачи анализа и прогнозирования временных рядов.

1.1.3. Задача построения решающей функции.

1.1.4. Методы анализа временных рядов.

1.2. Задача построения логико-вероятностной модели.

1.2.1. Особенности задачи прогнозирования временных рядов.

1.2.2. Постановка задачи прогнозирования.

1.2.3. Класс логических решающих функций.

1.2.4. Логико-вероятностная модель.

1.2.5. Универсальность класса моделей.

1.3. Критерии качества решения.

1.3.1. Меры различия для распределений.

1.3.2. Критерий информативности распределений.

1.3.3. Свойства дивергенции.

1.3.4. Критерий информативности модели.

1.4. Алгоритм построения логико-вероятностной модели.

1.4.1. Алгоритм поиска разбиения.

1.4.2. Алгоритм построения логико-вероятностной модели.

1.4.3. Иллюстрация работы алгоритма.

Выводы.

Глава 2. Построение пространства состояний процесса.

2.1. Метод построения информативного пространства состояний временного ряда.

2.1.1. Постановка задачи и основные идеи метода.

2.1.2. Критерии выбора эмпирической модели.

2.1.3. Связь дивергенции с критерием максимального правдоподобия.

2.1.4. Критерии качества логико-вероятностной модели.

2.2. Алгоритмы прогнозирования на основе выбора пространства состояний.

2.2.1. Разбиение в классе линейных функций.

2.2.2. Построение разбиения алгоритмом направленного поиска

2.2.3. Тестовый пример.

2.3. Обнаружение изменения свойств процесса.

2.3.1. Постановка задачи.

2.3.2. Метод решения.

2.3.3. Критерий минимума энтропии.

2.3.4. Пример работы алгоритма.

Выводы.

Глава 3. Исследование статистической достоверности решений.

3.1. Проверка «нулевой» гипотезы методом перестановок.

3.2. Статистическое моделирование в задаче классификации.

3.3. Исследование качества прогнозирования.

3.4. Оценивание смещения эмпирического риска.

Выводы.

Глава 4. Метод адаптивного поиска решающей функции.

4.1. Методы поиска логической решающей функции.

4.2. Метод адаптивного поиска глобального экстремума.

4.2.1. Задача поиска глобального экстремума.

4.2.2. Алгоритм СПА.

4.3. Алгоритм адаптивного поиска дерева решений.

4.3.1. Меры близости деревьев решений.

4.3.2. Исследование алгоритма.

4.4. Исследование связи между алгоритмом поиска экстремума и классом функций.

4.4.1. Описание задачи.

4.4.2. Постановка задачи.

4.4.3. Классы эквивалентности.

4.4.4. Класс функций для алгоритма СПА.

Выводы.

Глава 5. Решение прикладных задач.

5.1. Программное обеспечение.

5.2. Обзор прикладных задач репозитория UCI.

5.3. Задача выявления закономерностей в хоралах И.С. Баха.

5.4. Задача оценивания состояния ионосферы.

5.5. Анализ метеорологических данных.

5.6. Поиск закономерностей в сейсмических данных.

5.7. Задача сравнения текстур.

Выводы.

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

Актуальность проблемы

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

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

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

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

Цель работы

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

Задачи исследования

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

Выбор и обоснование критерия качества логико-вероятностной модели временного ряда.

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

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

Применение разработанных методов к решению прикладных и модельных задач.

Разработка и исследование метода адаптивного поиска дерева решений.

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

Методы исследования включают в себя аппарат теории вероятностей и математической статистики, теоретической кибернетики; математическое моделирование с применением средств вычислительной техники.

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

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

1. Предложен алгоритм построения логико-вероятностной модели многомерного разнотипного временного ряда на основе многовариантного решающего правила.

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

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

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

Научные результаты, выносимые на защиту

Критерий качества логико-вероятностной модели временного ряда.

Алгоритм построения логико-вероятностной модели многомерного разнотипного временного ряда на основе многовариантного решающего правила.

Метод решения задачи прогнозирования временного ряда путем построения информативного пространства состояний.

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

Исследование качества прогнозирования в зависимости от длины реализации, сложности логико-вероятностной модели ряда и длины предыстории.

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

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

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

Разработано программное обеспечение, реализующее предложенные методы.

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

Достоверность результатов

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

Апробация работы

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

Международные конференции «Интеллектуализация обработки информации», г. Алушта: июнь 2002 г. (ИОИ-2002), июнь 2006 г. (ИОИ-2006), июнь 2008 г. (ИОИ-2008).

Международные конференции «Knowledge-Dialogue-Solution», г. Варна, Болгария: июнь 2006 г. (KDS-2006), июнь 2007 г. (KDS-2007).

Международная конференция «Classification, Forecasting, Data Mining», г. Варна, Болгария: июнь 2009 г. (CFDM-2009).

Семинары Института математики СО РАН.

Отдельные части работы прошли экспертизу в ходе выполнения проектов, поддержанных грантами РФФИ: № 04-01-00858-а, № 07-01-00331-а.

Личный вклад

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

Публикации

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

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

Диссертационная работа изложена на 149 страницах машинописного текста и состоит из введения, пяти глав, заключения, библиографического списка из 89 наименований отечественной и зарубежной литературы и трех приложений. Иллюстративный материал представлен 33 рисунками и 9 таблицами.

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

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

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

3. Разработан алгоритм построения логико-вероятностной модели многомерного разнотипного временного ряда на основе многовариантного решающего правила. Работоспособность методов проиллюстрирована на модельных задачах.

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

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

6. Разработанный метод прогнозирования временного ряда путем построения информативного пространства состояний применен для решения нескольких прикладных задач: задачи анализа трехмерного временного ряда, представленного метеорологическими данными (температура воздуха, объем осадков, объем водостока), задачи поиска закономерностей в сейсмических данных, а также двух задач из репозитория 11С1. Оценена статистическая достоверность полученных закономерностей, проведено исследование поведения алгоритма на случайных перестановках значений временного ряда.

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

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

Заключение

1. Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин / М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр. М.: Наука, 1970. - 384 с.

2. Андерсон Т. Статистический анализ временных рядов / Т. Андерсон. М.: Мир, 1976.-755 с.

3. Бендат Дж., Пирсол А. Прикладной анализ случайных данных / Дж. Бендат, А. Пирсол. М.: Мир, 1989. - 540 с.

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

5. Блощицын В. Я., Лбов Г. С. О мерах информативности логических высказываний / В. Я. Блощицын, Г. С. Лбов // Доклады Республ. школы-семинара «Технология разработки экспертных систем», Кишинев. — 1987. -С. 12-14.

6. Бокс Дж., Дженкинс Г. Анализ временных рядов, прогноз и управление / Дж. Бокс, Г. Дженкинс. М.: Мир, 1974. - Т. 1. - 406 с.

7. Бонгард М. М. Проблема узнавания / М. М. Бонгард. М.: Наука, 1967. -320 с.

8. Борисов А. В. Методы анализа и оценивания в скрытых марковских системах при обработке разнородной информации: автореф. дис. . док. физ.-мат. наук : 05.13.01 / А. В. Борисов. Москва, 2008. - 32 с.

9. Боровков А. А. Теория вероятностей / А. А. Боровков. М.: Наука, 1986. -431 с.

10. Боровков А. А. Математическая статистика / А. А. Боровков. М.: Наука, 1984.-471 с.

11. Боровков А. А. О задаче распознавания образов / А. А. Боровков // Теория вероятностей и ее применение. 1971. - Т. 16, № 1. - С. 132-136.

12. Вайнцвайг М. Н. Алгоритм обучения распознаванию образов «КОРА» / М. Н. Вайнцвайг // Алгоритмы обучения распознаванию образов / Под ред. В. Н. Вапника. М.: Советское радио. — 1973. - С. 110-116.

13. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов / В. Н. Вапник, А. Я. Червоненкис. М.: Наука. - 1974. - 415 с.

14. Викентьев А. А. Свойства нормального расстояния и информативности на высказываниях экспертов / А. А. Викентьев // Компьютерный анализ данных и моделирование: сборник научных статей международной конференции, Минск, 4-8 сентября 1995. Т 2. - С. 78-80.

15. Витяев Е. Е. Извлечение данных из знаний. Компьютерное познание. Модели когнитивных процессов / Е. Е. Витяев. Новосибирск: Изд-во НГУ, 2006. - 293 с.

16. Воронин Ю. А. Введение мер сходства и связи для решения геолого-географических задач / Ю. А. Воронин. Доклады АН СССР. — 1971. — Т. 199, №5. г-С. 1011-1014.

17. Воронцов К. В. О комбинаторном подходе к оценке качества обучения алгоритмов / К. В. Воронцов // Доклады 11-й Всероссийской конф. «Математические методы распознавания образов». — М.: ВЦ РАН, 2003. -С. 47-49.

18. Гусев В. Д., Мирошниченко Л. А. Поиск комбинированных структур в ДНК-последовательностях / В. Д. Гусев, Л. А. Мирошниченко // Доклады 13-й Всероссийской конференции «Математические методы распознавания образов». М.: Макс-Пресс, 2007. - С. 473-476.

19. Данилов Д. Л., Жиглявский А. А. Главные компоненты временных рядов: метод «Гусеница» / Д. Л. Данилов, А. А. Жиглявский. Санкт-Петербург: Изд-во С-ПбГУ, 1997. - 308 с.

20. Донской В. И. Колмогоровская сложность классов общерекурсивных функций с ограниченной емкостью / В. И. Донской // Таврический вестник информатики и математики. 2005. - № 1. — С. 25-34.

21. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации / Ю. И. Журавлев // Проблемы кибернетики. -М.: Наука, 1978. Вып. 33. - С. 5-68.

22. Загоруйко Н. Г. Эмпирическое предсказание / Н. Г. Загоруйко. — Новосибирск: Наука, 1979. 124 с.

23. Загоруйко Н. Г. Самообучающийся генетический алгоритм прогнозирования (GAP) / Н. Г. Загоруйко // Вычислительные системы: Искусственный интеллект и экспертные системы. — Новосибирск: Изд-во Института математики СО РАН, 1997. Вып. 160. - С. 80-95.

24. Загоруйко Н. Г. Прикладные методы анализа данных и знаний /

25. Н. Г. Загоруйко. Новосибирск: Изд-во Института математики СО РАН, 1999.-270 с.

26. Загоруйко Н. Г., Бушуев М. В. Меры расстояния в пространстве знаний / Н. Г. Загоруйко, М. В. Бушуев // Вычислительные системы: Анализ данных в экспертных системах. — Новосибирск: Изд-во Института математики СО АН СССР, 1986. Вып. 117. - С. 24-35.

27. Канторович JI. В. О перемещении масс / JI. В. Канторович // Доклады АН СССР. 1942. - Т. 37, № 7-8. - С. 227-229.

28. Кендал М. Дж. Временные ряды / М. Дж. Кендал. М.: Финансы и статистика, 1981.-540 с.

29. Кендал М. Дж., Стьюарт А. Многомерный статистический анализ и временные ряды / М. Дж. Кендал, А. Стьюарт. — М.: Наука, 1976. 736 с.

30. Кульбак С. Теория информации и статистика / С. Кульбак. — М.: Наука, 1967.-408 с.

31. Курейчик В. М. Генетические алгоритмы. Состояние. Проблемы. Перспективы / В. М. Курейчик // Известия РАН: теория и системы управления.- 1999.-№ 1.-С. 144-160.

32. Лбов Г. С. Выбор эффективной системы зависимых признаков / Г.С. Лбов // Вычислительные системы. Новосибирск: Изд-во Института математики СО АН СССР, 1965. - Вып. 19. - С. 21-34.

33. Лбов Г. С. Об одном алгоритме распознавания в пространстве разнотипных признаков / Г. С. Лбов, В. И. Котюков, А. Н. Манохин. // Вычислительные системы. Новосибирск: Изд-во Института математики СО АН СССР, 1973.-Вып. 55.-С. 108-110.

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

35. Лбов Г. С., Бериков В. Б. Устойчивость решающих функций в задачах распознавания образов и анализа разнотипной информации / Г. С. Лбов, В. Б. Бериков. Новосибирск: Изд-во Института математики СО РАН, 2005.-218 с.

36. Лбов Г. С., Неделько В. М. Восстановление условного распределения на основе экспериментальных данных / Г. С. Лбов, В. М. Неделько // Информатика и процессы управления: межвузовский сборник. Красноярск: Изд-во КГТУ, 1997. - С. 54-61.

37. Лбов Г. С., Старцева Н. Г. Алгоритм многоклассового распознавания, основанный на логических решающих функциях / Г. С. Лбов, Н. Г. Старцева //Вычислительные системы. Новосибирск: Изд-во Института математики СО АН СССР, 1985.-Вып. 111.-С. 3-10.

38. Лбов Г. С., Старцева Н. Г. Сложность распределений в задачах классификации / Г. С. Лбов, Н. Г. Старцева // Доклады РАН. 1994. - Т. 338, № 5. -С. 592-594.

39. Лбов Г. С., Старцева Н. Г. Логические решающие функции и вопросы статистической устойчивости решений / Г. С. Лбов, Н. Г. Старцева. — Новосибирск: Изд-во Института математики СО РАН, 1999. 211 с.

40. Манохин А. Н. Методы распознавания, основанные на логических решающих функциях / А. Н. Манохин // Вычислительные системы. Новосибирск: Изд-во Института математики СО АН СССР, 1976. - Вып. 67. -С. 42-53.

41. Методы, критерии и алгоритмы, используемые при преобразовании, выделении и выборе признаков в анализе данных // Сборник статей. Вильнюс, 1988.- 150 с.

42. Миренкова1 С. В. Метод прогнозирования многомерного разнотипного временного ряда в классе логических решающих функций / С. В. Миренкова // Искусственный интеллект. 2002. - № 2. - С. 197-201.

43. Моттль В. В., Середин О. С., Сулимова В. В. Потенциальные функции для беспризнакового восстановления зависимостей на множествах сигналов и символьных последовательностей / В. В. Моттль, О. С. Середин,

44. B. В. Сулимова // Искусственный интеллект. 2004. - № 2. - С. 140-144.

45. Неделько С. В. Критерий информативности матрицы переходов и прогнозирование разнотипного временного ряда / С. В. Неделько // Искусственный интеллект. 2004. - № 2. - С. 145-149.1 Неделько С. В.

46. Неделько" С. В. Исследование связи характеристик алгоритма поиска глобального экстремума и класса функций в дискретном пространстве малой мощности / С. В. Неделько, В. М. Неделько // Искусственный интеллект. -2006.-№2.-С. 201-205.

47. Неделько3 С. В. Построение логико-вероятностных моделей временного ряда при анализе сейсмических данных / С. В. Неделько, Т. А. Ступина // Научный вестник НГТУ. 2007. - № 4 (29). - С. 33^12.

48. Неделько С. В. Адаптивное прогнозирование многомерного временного ряда / С. В. Неделько // Таврический вестник информатики и математики. -2008.-№2.-С. 104-110.

49. Неделько С. В. Исследование статистической устойчивости логико-вероятностных моделей временного ряда / С. В. Неделько // Научный вестник НГТУ. 2008. - № 4 (33). - С. 43-52.

50. Автору принадлежит подбор иллюстративных примеров, расчеты и анализ результатов.

51. Автору принадлежит постановка задачи, алгоритм построения пространства состояний процесса и методоценивания статистической достоверности решений.

52. Автором проведено статистическое моделирование при исследовании применимости метода случайногопоиска с адаптацией для построения дерева решений.

53. Неделько4 С. В. Метод адаптивного поиска логической решающей функции / Г. С. Лбов, В. М. Неделько, С. В. Неделько // Сибирский журнал индустриальной математики. 2009. — Т. XII, № 3 (39). - С. 66-74.

54. Никифоров И. В. Последовательное обнаружение изменения свойств временных рядов / И. В. Никифоров. М.: Наука, 1983. - 199 с.

55. Рачев С. Т. Задача Монжа-Канторовича о перемещении масс и ее применение в стохастике / С. Т. Рачев // Теория вероятностей и ее применения. — 1984. Т. 29ю - Вып. 4. - С. 625-653.

56. Ростовцев П. С. Алгоритм построения типологий для больших массивов социально-экономической информации / П. С. Ростовцев // Модели агрегирования социально-экономической информации: сборник научных трудов. Новосибирск: Изд-во ИЭ и ОПП СО АН СССР, 1978.

57. Старцева Н. Г., Людвина Н. А. Регрессионный анализ для структурированных объектов / Н. Г. Старцева, Н. А. Лю двина // Доклады РАН. 1996. - Т. 346, № 5. - С. 600-602:

58. Ступина Т. А. Об одном из подходов к анализу одномерного временного ряда / Т. А. Ступина //Труды VII-международной конференции «Интеллектуальный анализ информации, ИАИ-2007», Киев, 2007. — ISBN 978-996-7115-77-7.-С. 336-340.

59. Сухарев А. Г. Оптимальный поиск экстремума / А. Г. Сухарев. — М.: Изд-во МГУ, 1975.

60. Хант Э., Марин Дж., Стоун Ф. Моделирование процесса формирования понятий на вычислительной машине / Пер. с англ. — М.: Мир, 1970. — 304 с.

61. Шугай Ю. С., Доленко С. А. Нейросетевые алгоритмы прогнозирования событий и поиска предвестников в многомерных временных рядах / Ю. С. Шугай, С. А. Доленко // Искусственный интеллект. 2004. - № 2. -С. 211-215.

62. Berikov V. On the convergence of logical decision functions to optimal decision functions / V. Berikov // Pattern Recognition and Image Analysis. — 1995.-Vol. 5.-№ l.-P. 1-6.

63. Breiman L., Friedman J. H., Olshen R. A., Stone C. J. Classification and regression trees / L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone. Belmont, CA, Wadsworth. - 1984.

64. Duda R. O., Hart P. E. Pattern Classification and Scene Analysis / R. O. Duda, P. E. Hart. New York, London, Sydney, Toronto, 1973. - 422 p.

65. Hughes G. F. On the mean accuracy of statistical pattern recognizers / G.F.Hughes // Information Theory. IEEE Transactions. — 1968. Vol. 14, № l.-P. 55-63.

66. Hyafil L., Rivest R. Constructing optimal binary decision trees is NP-complete / L Hyafil, R Rivest // Information Processing Letters 2. 1976. - P. 15-17.

67. Kalles D. Lossless fitness inheritance in genetic algorithms for decision trees / D Kalles // CoRR Электронный ресурс. 2006. - Режим доступа: http://arxiv.org/abs/cs/0611166. - Загл. с экрана.

68. Kretowski М., Grzes М. Global Induction of Oblique Decision Trees: An Evolutionary Approach / M. Kretowski, M. Grzes // IIPWM. Advances in Soft Computing. Springer-Verlag, Berlin, Heidelberg, 2005. - P. 309-318.

69. Kruskal J. B. Multidimensional Scaling by Optimizing Goodness of Fit to a Non-metric Hypothesis / J. B. Kruskal // Psychometrika. 1964. - Vol. 29. -P. 1-27.

70. Lbov G. S. Logical Function in the Problem of Empirical Prediction /

71. G. S. Lbov // Handbook of Statistics: Classification, Pattern Recognition and Reduction of Dimensionality. North-Holland Publ. Сотр., Amsterdam, New York, 1983.-Vol. 2.-P. 1130-1165.

72. Lbov G. S., Berikov V. B. Recursive Method of Formation of the Recognition Decision Rule in the Class of Logical Functions / G. S. Lbov, V. B. Berikov // Pattern Recognition and Image Analysis. 1993. - Vol. 3, № 4. - P. 428-431.

73. Lbov G. S., Stupina T. A. Application of the multivariate prediction method to time series / G. S. Lbov, T. A. Stupina // Proc. of Xl-th Intern. Conf. «Knowledge-Dialogue-Solution», Varna, Bulgaria, 20-30 June 2005. — Vol. 1. — P. 6067.

74. Lopez de Mantaras R. A distance-based attribute selection measure for decision tree induction / R. Lopez de Mantaras // Machine Learning. 1991. -P. 81-92.

75. Michalski R. S. Pattern recognition as rule-guided inductive inference /

76. R. S. Michalski // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1980. - Vol. PAMI-2, № 4. - P. 349-361.

77. Nedel'ko V. M. Problem of recovering a conditional distribution and multiversion deciding functions / V. M. Nedel'ko // Computer data analysis and modeling. Minsk, 2001. - Vol. 2. - P. 151-156.

78. Nedel'ko"" S. V. Finding the relationship between a search algorithm and a class of functions on discrete space by exhaustive search / V. M. Nedel'ko,

79. S. V. Nedel'ko // Information Theories & Applications. 2007. - Vol. 14. -P. 339-343. Исследование связи между алгоритмом оптимизации и классом функций в дискретном пространстве с использованием полного перебора.

80. Papagelis A., Kalles D. Breeding Decision Trees Using Evolutionary Techniques / A. Papagelis, D. Kalles //International Conference on Machine Learning, Williamstown, Massachusetts, June-July 2001. P. 393-400.

81. Quinlan J. R. C4.5: Programs for Machine learning / J. R. Quinlan. Morgan Kaufmann Publishers, 1993.

82. Raudys S., Statistical and neural classifiers / S. Raudys. Springer, 2001.

83. Simovici D. A., Jaroszewicz S. A New Metric Splitting Criterion for Decision Trees / D. A. Simovici, S. Jaroszewicz // Parallel Algorithms Appl. 2006. -№21(4).-P. 239-256.

84. Stupina T. A. Application of the Heterogeneous system prediction method to pattern recognition problem / T. A. Stupina // International Journal ITHEA, ISSN 1310-0513. 2007. - Vol. 13, № 3. - P. 84-87.

85. Vapnik V. Statistical Learning Theory / V. Vapnik. John-Wiley & Sons, Inc.- 1998.-740 p.

86. Wolpert D. H., Macready W. G. No Free Lunch Theorems for Search /

87. D. H. Wolpert, W. G. Macready / Santa Fe Institute report, SFI-TR-95-02-010.- 1996.