Содержание к диссертации
Введение
Глава 1. Анализ временных рядов
Глава 2. Модель нечеткого временного ряда
Глава 3. Реализация программной системы анализа нечетких временных рядов
Глава 4. Анализ адекватности и эффективности модели на основе вычислительных экспериментов
Выводы
Список литературы
- Анализ временных рядов
- Модель нечеткого временного ряда
- Реализация программной системы анализа нечетких временных рядов
- Анализ адекватности и эффективности модели на основе вычислительных экспериментов
Введение к работе
В настоящее время резко возрастает сложность создаваемых и эксплуатируемых технических систем. В процессе проектирования и эксплуатации таких систем моделирование является эффективным методом прогнозирования их основных характеристик поведения. Сложные технические системы, такие как вычислительные сети, обладают объективной неопределенностью, что требует дальнейшего расширения инструментария прогностики. Все чаще используются интеллектуальные методы, которые расширяют классическую классификацию прогностических методов и представляют сочетание формализованных процедур обработки информации, полученной по оценкам специалистов-экспертов. Интеллектуальные математические методы прогнозирования применяют в тех случаях, когда невозможно учесть влияние многих факторов из-за значительной сложности объекта прогнозирования или если недоступны объективные результаты измерений поведения объекта. В этом случае используются оценки экспертов.
Исследования данных и их методов анализа в последние десятилетия оформились в виде отдельного направления, называемого интеллектуальным анализом данных или Data Mining (DM), в котором анализ временных рядов получил понятие интеллектуальный анализ временных рядов или Times-Series Data Mining (TSDM). В работах ряда зарубежных ученых (X. Танаки, К. Хироты, Я. Капржика, В. Педрича) исследованы методы нечеткой регрессии, анализа данных нечетких временных рядов. Среди отечественных ученых данной теме посвящены работы И.З. Батыршина, СМ. Ковалева, Н.Г. Ярушкиной и др.
Несмотря на перечисленные работы, многие задачи анализа нечетких временных рядов остаются нерешенными, в частности, задачи анализа нечетких тенденций и генерации правил распознавания тенденций. Методы анализа нечетких временных рядов могут быть положены в основу создания библиотек имитационных моделей элементов сложных технических систем, в частности, вычислительных сетей.
Перечисленные особенности делают решение научно-технической задачи исследования и разработки нового инструментария прогностики на основе нечетких временных рядов и построения математических моделей конкретных устройств вычислительных сетей актуальным.
Целью диссертации является исследование прогностических возможностей нечетких тенденций нечетких временных рядов и построение на их основе математических моделей элементов вычислительных сетей.
Для достижения поставленной цели необходимо решить следующие задачи.
1. Провести сравнительный анализ существующих методов анализа нечетких временных рядов, выявить их возможности и ограничения.
2. Построить методику распознавания нечетких тенденций временных рядов и методику анализа временного ряда нечетких тенденций.
3. Сформировать алгоритм формирования временного ряда нечетких тенденций по исходному временному ряду и обратный алгоритм генерации ряда - представителя нечеткой тенденции.
4. Разработать метод генерации знаний о нечетких тенденциях в форме правил.
5. Разработать и реализовать программную систему - инструментарий для обработки нечетких временных рядов.
6. Разработать модели элементов вычислительных сетей на основе анализа нечетких временных рядов трафика.
В диссертационной работе использовались современная теория нечетких систем, теория вероятностей, методы математической статистики, теория имитационного моделирования. Научная новизна работы заключается в следующем.
1. Предложено определение временного ряда нечетких тенденций и разработана методика распознавания нечетких тенденций.
2. Разработаны алгоритмические операции обработки нечетких тенденций, а именно, операция формирования временного ряда нечетких тенденций по исходному временному ряду и обратная операция генерации ряда - представителя нечеткой тенденции.
3. Предложен метод генерации знаний о нечетких тенденциях в форме правил.
4. Разработана математическая имитационная модель терминал-сервера как элемента вычислительной сети, позволяющая оперировать прогнозными данными о трафике и вычислительной загрузке.
5. Исследована эффективность моделирования трафика в терминальных фрагментах вычислительной сети.
Достоверность научных положений, выводов и рекомендаций подтверждена результатами экспериментов, а также результатами использования материалов диссертации и разработанной системы в проектной организации в соответствии с актом внедрения.
Основные положения, выносимые на защиту
1. Временной ряд нечетких тенденций является результативным индикатором развития моделируемого процесса в сложной технической системе, описанного качественно, в лингвистических терминах.
2. Базовыми операциями обработки нечетких тенденций являются алгоритмические операции обработки нечетких тенденций, а именно, операция формирования временного ряда нечетких тенденций по исходному временному ряду и обратная операция генерации ряда -представителя нечеткой тенденции. 3. Нечеткая нейронная сеть предложенной архитектуры является эффективным генератором правил прогнозирования нечетких тенденций.
4. Разработанная математическая имитационная модель терминал-сервера как элемента вычислительной сети на основе временных рядов нечетких тенденций позволяет прогнозировать трафик сервера.
Разработанные методы и алгоритмы позволяют проектировщикам создавать модели элементов вычислительной сети с улучшенными характеристиками, а также сокращать время, затрачиваемое на проектирование вычислительных сетей, за счет моделирования принятых проектных решений.
Результаты диссертации и практические рекомендации использованы при проектировании вычислительной сети в ФНГЩ ОАО «НПО МАРС» (г. Ульяновск 2006 г.).
Основные положения и результаты диссертации докладывались, обсуждались и получили одобрение на IX национальной конференции по искусственному интеллекту с международным участием (г.Ульяновск, 2004 г.), на Международных конференциях «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике» (г.Ульяновск, 2004, 2005 гг.) и «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г.Москва, 2005 г. и 2007 г.).
В первой главе рассмотрены методы анализа временных рядов. Представлены возможности и ограничения статистических и интеллектуальных моделей. Особое внимание уделено использованию теории нечетких множеств. Изложены основные положения теории нечетких множеств и описаны модели нечетких временных рядов.
Во второй главе описана модель нечетких тенденций. Для описания развития моделируемого процесса в лингвистических терминах введено понятие временного ряда нечетких тенденций. Выделены базовые операции обработки нечетких тенденций и описана их реализация на основе теории нечетких множеств. Описана архитектура нечеткой нейронной сети для генерации правил зависимости.
В третьей главе рассмотрена программная реализация модели нечетких тенденций, содержащая все компоненты системы нечеткого вывода: блоки фаззификации и дефаззификации, блок нечеткого вывода, базу знаний. Для реализации системы нечеткого вывода выбран объектно-ориентированный метод программирования, позволяющий абстрагировать понятия модели нечетких тенденций в виде иерархии классов.
В четвертой главе изложено применение модели нечетких тенденций для моделирования работы узла вычислительной сети в рамках разработки программной системы автоматизированного проектирования ВС. Исследована эффективность моделирования предложенной в работе методики анализа временных рядов по сравнению с другими методами. Изучена возможность применения модели нечетких тенденций в других областях, в частности, в экономике.
Анализ временных рядов
Временным рядом (ВР) называют последовательность измерений у„ t=[l..N], обычно упорядоченную по времени. Измерения могут производиться непрерывно или через фиксированные интервалы времени, такие ряды называются непрерывными и дискретными соответственно. В дальнейшем будем рассматривать только дискретные временные ряды, как наиболее распространенные. Как правило, термин «временной ряд» сам по себе подразумевает, что это ряд является одномерным (скалярным). Часто важно рассмотреть совместную динамику набора временных рядов. Такой набор называют многомерным временным рядом, или векторным временным рядом. Многофакторные временные должны учитывать пространственные и временные изменения факторов, а так же запаздывание влияния этих факторов на зависимую переменную. Это позволяет учитывать развитие взаимосвязанных процессов.
Основная цель анализа временных рядов - определение природы ряда и прогнозирование будущих значений ряда. Результатом анализа является модель ряда, которая более или менее идентифицирована и формально описана. Основной чертой, выделяющей анализ временных рядов от статистического анализа и методов анализа данных, является существенность порядка, в котором производится наблюдения. Модели временных рядов используют при решении трех прикладных задач [Бокс, Дженкинс, 1974]: - прогнозирование будущих значений временного ряда по его текущим и прошлым значениям; - определение передаточной функции системы - определение динамической модели вход-выход; с помощью этой модели можно найти эффект на выходе инерционной системы по произвольно заданным рядам на входе; - проектирование регулирующих схем прямой и обратной связями, при помощи которых можно в максимально допустимых пределах компенсировать потенциальные отклонения выхода системы от желаемого номинала. В данной работе рассмотрим задачу прогнозирования, как наиболее распространенного приложения анализа временных рядов. Использование доступных к моменту времени наблюдений динамического ряда для прогнозирования его значений в некоторый момент времени в будущем является основой управления и оптимизации промышленных процессов, планирования в экономических системах.
По оценкам зарубежных и отечественных систематиков прогностики, насчитывается свыше ста методов прогнозирования [Тихонов, Кузьмищев, 2004], [Янч, 1974]. Число базовых методов, которые в тех или иных вариациях повторяются в других методах, гораздо меньше. Часть из этих методов относятся скорее к отдельным приемам или процедурам прогнозирования, другие представляют набор отдельных приемов, отличающихся от базовых или друг от друга количеством частных приемов и последовательностью их применения. В связи с этим отмечается отсутствие четкой систематизации, что приводит к дальнейшему расширению инструментария прогностики. В рамках классической классификации все методы принято делить на формализованные и интуитивные [Бурдо, Тихонов, 2001]. Интуитивные методы прогнозирования используют в тех случаях, когда невозможно учесть влияние многих факторов из-за значительной сложности объекта прогнозирования. В этом случае используются оценки экспертов. Классы интуитивных и формализованных методов схожи по своему составу с экспертными и фактографическими методами. Фактографические методы основаны на фактически имеющейся информации об объекте прогнозирования и его прошлом развитии. Экспертные методы базируются на информации, полученной по оценкам специалистов-экспертов. Интеллектуальные методы, которые все чаще используются в анализе временных рядов, в классических схемах классификации отсутствуют, либо присутствуют в виде отдельных методов.
Исследования данных и их методов анализа в последние десятилетия оформились в виде отдельного направления называемого Data Mining (DM), в котором анализ временных рядов получил понятие Times-Series Data Mining (TSDM) [Batyrshin, Sheremetov, 2005]. В рамках TSDM методы прогнозирования можно разделить на две группы: статистические и кибернетические методы. Эта схема основана на различных подходах к обучению математических моделей [Мусаев, 2004]. Следует отметить, что существует два мнения отнесения статистических методов к DM. Первый их них противопоставляет статистические методы и DM, его сторонники считают классические методы отдельным направлением анализа данных. Согласно второму подходу, статистические методы анализа являются частью математического инструментария DM. Большинство источников придерживается второго подхода [Piatetsky - Shapiro, www.kdnuggets.com]. В этой классификации различают две группы методов: - статистические методы, основанные на использовании усредненного накопленного опыта, который отражен в ретроспективных данных; - кибернетические методы, включающие множество разнородных математических подходов, основанных на использовании технологий искусственного интеллекта. Недостаток такой классификации: и статистические, и кибернетические алгоритмы тем или иным образом опираются на сопоставление статистического опыта с результатами мониторинга текущей ситуации.
Преимуществом такой классификации является ее удобство для интерпретации - она используется при описании математических средств современного подхода к извлечению знаний из массива исходных наблюдений (оперативных и ретроспективных). Статистический анализ рассматривает временной ряд как сумму детерминированного ряда и реализаций случайного ряда. В данной работе рассмотрим классические методы построения моделей составляющих временного ряда: регрессионные модели, вероятностные модели Бокса и Дженкинса, их одномерные и многомерные варианты.
Модель нечеткого временного ряда
Одним из результатов анализа данных является нахождение динамики развития свойств объектов. Исходные данные могут быть представлены в нечетком выражении, что может быть обусловлено экспертным оцениванием состояния системы, а так же несовершенными способами измерения параметров. Анализ временных рядов представленных нечеткими выражениями использует теорию нечетких множеств.
Рассмотрим временной ряд Y={yb t - последовательность моментов времени}, yteUy, для которого определен нечеткий временной ряд Y (1.4).
Подход с точки зрения мягких вычислений позволяет рассматривать динамику нечеткого временного ряда оценками, выраженными лингвистическими терминами тенденций.
Определение 1. Нечеткая тенденция (НТ). Пусть yh={yx,..-,ym} нечеткий временной ряд лингвистической переменной (Y,Ty,Uy,Gy,My), А=ІУЬ} множество нечетких временных рядов одинаковой длины. Тогда нечеткая тенденция г, определенная на д, есть совокупность упорядоченных пар: гдеМТІУА) представляет собой степень принадлежности уА кНТ.
Данное определение определяет нечеткую тенденцию как нечеткую переменную. Если говорить о тенденции как лингвистической переменной, терм-множеством которой является множество различных тенденций наблюдаемых на временном ряду, а универсумом - множество всевозможных функций, НТ определяется как щер - количество видов НТ, определенных на ВР; Y& - множество НВР переменной длины.
Тенденция нечеткого временного ряда есть нечеткая метка, выражающая поведение НВР. В этом случае понятие нечеткой тенденции расширяется, и позволяет вводить любые лингвистические термины тенденций. Эксперт может добавить к основным нечетким меткам нечеткой тенденции специфическое поведение временных рядов характерное для предметной области. Например, «неожиданный всплеск» можно описать нечетким временным рядом на интервале пяти отсчетов: «низкий», «низкий», «высокий», «низкий», «низкий».
Определяя нечеткую тенденцию на всех интервалах [t-m+l,t] временного ряда и позиционируя начало или окончание интервала к временной шкале, получим временной ряд нечеткой тенденции.
Определение 2. Временной ряд нечеткой тенденции (ВРНТ). Пусть {Уь,} - множество нечетких временных рядов длиной т, где Уь, ={y,-m+v...,y,}, y,eYt. Тогда временной ряд нечеткой тенденции есть упорядоченное во времени нечеткое множество:
Для лингвистической переменной «тенденция» временной ряд определяется совокупностью значений всех видов нечетких тенденций:
Получение нечеткого ВР из четкого на рациональных числах основано на операции фаззификации, т.е. перехода от количественных значений к лингвистическим оценкам. Процедура фаззификации достаточно широко описана в литературе [Заде, 1976]. Процесс нахождения степени принадлежности элементов Uy терминальному множеству Ту обозначим функционалом Fuzzy.
Для определения лингвистической переменной, выражающей нечеткую тенденцию, требуется выделить типичное поведение нечеткого временного ряда, то есть составить терминальное множество. Универсальное множество, согласно определению нечеткой тенденции, является множеством нечетких временных рядов, поэтому универсум можно представить как множество всевозможных графиков (функций), отображающих динамику. Задача эксперта выделить типичные (систематические) тенденции нечеткого временного ряда. При этом необходимо определить длину ряда т - интервал временной шкалы, на котором будет описываться тенденция. Для построения временного ряда нечеткой тенденции необходимо не только выделить их (обозначить лингвистические термы), но так же дать описание и найти тенденцию на нечетком временном ряду. Таким образом, функционал Tend включает в себя инструмент описания нечеткой тенденции, алгоритм нахождения соответствия нечетких временных рядов выбранному описанию, то есть алгоритм нечеткого оценивания.
Для анализа и построения четкого временного ряда по нечеткой модели необходима операция получения нечеткого временного ряда из оценки тенденции. Решение данной задачи обозначим функционалом deTend, являющимся обратным функционалом Tend: Y\=deTend[T],rAeYA, где Y A={y\} - множество типичных (характерных) нечетких временных рядов для НТ имеющих наибольшую степень принадлежности juT(y л)=тах(рт[?А]). Таким образом, каждому виду нечеткой тенденции может сопоставляться несколько интервальных нечетких временных рядов. Для решения задач прогнозирования достаточно определить часть элементов рядов у\, которые можно найти по остальным известным элементам ряда. Задача при этом аналогична построению графика по известным частям.
Реализация программной системы анализа нечетких временных рядов
Для анализа временных рядов по предложенной модели нечеткого временного ряда создано программное обеспечение (ПО) FuzzyTendNet. Программа написана в среде Microsoft Visual Studio .NET 2003 на языке Visual Basic .NET. Для функционирования программы необходимо следующее программное обеспечение: - операционная система семейства Windows 2000/ХР/2003; - набор библиотек Microsoft .NET Framework 1.1; - Microsoft Access. FuzzyTendNet занимает 280кБ на носителе информации и от 20мБ в оперативной памяти (в зависимости от загруженных временных рядов). ПО реализует все этапы построения МНТ на основе нечеткой логики. Сам процесс построения представлен графическим интерфейсом на основе элементов управления ОС Windows. Система решает широкий спектр задач: многомерный анализ, графическое представление информации, моделирование и прогнозирование, хранение базы знаний.
Для начала работы над формированием базы знаний необходимо установить соединение с базой данных Microsoft Access (имя файла и название таблицы указывает пользователь). При соединении пользователя становятся доступны поля базы данных, которые необходимо сопоставить с временными рядами в программе. После означивания ВР необходимо загрузить данные из базы, при этом данные помещаются в оперативную память. Таким образом, при расчетах база данных непосредственно не используется.
Тип ВР: «время», «вход», «выход» Тип устанавливает назначение ВР. «Время» - шкала времени. «Вход» и «Выход» - переменная является независимой или зависимой переменной. Возможно устанавливать оба типа. Нечеткая метка(НВР)-принадлежитконкретномуВР Идентификатор Идентификатор для хранения в базе знаний А, В, С, D Параметры трапециевидной функции принадлежности Нечеткаятенденция-принадлежитконкретномуВР Идентификатор Идентификатор для хранения в базе знаний Тип НТ: «вход», «выход» «Вход» и «Выход» - НТ является независимой или зависимой переменной. Возможно устанавливать оба типа. Правило распознавания-принадлежит конкретной НТ (момент, нечеткая метка) НВР описывающий НТ. Обратное (момент, НВР описывающий НТ. правило - нечеткая метка) принадлежит конкретной НТ ННС Выход Зависимая нечеткая тенденция временного ряда Логическое (Момент, вес, Элементы правил правило - нечеткая принадлежит тенденция) конкретной ННС Программа позволяет анализировать многомерные временные ряды, где несколько зависимых переменных зависят от собственных лагов и от лагов других переменных: где у),...,у-зависимые ВР; , ,..., , - независимые переменные. Данный вариант модели является моделью векторной авторегрессии и представляет собой удобный инструмент для одновременного моделирования временных рядов.
Область настройки нечетких тенденций Уравнение модели временного ряда представляет собой нечеткую нейронную сеть, содержащую подсети для каждой выходной тенденции. Каждая подсеть - это система логического вывода, состоящая из множества правил. Данные правила можно формировать вручную, что позволяет строить модели по экспертным знаниям о зависимости между переменными, а так же корректировать (редактировать) обученные сети. Построение ННС для дальнейшего оптимизации происходит в автоматическом режиме на основе установленных типов («вход», «выход») для ВР, НТ.
Анализ адекватности и эффективности модели на основе вычислительных экспериментов
Одной из задач моделирования является анализ пропускной способности вычислительной сети (ВС) (трафик, нагрузка, задержка и т.д.). В этом случае узлы сети выступают в роли генераторов и обработчиков трафика. Если для коммутирующего оборудования существует достаточно много библиотек позволяющих выполнять имитационное моделирование, то для узлов-пользователей необходимо реализовывать модели в каждом конкретном случае моделирования. Узел-пользователь является сложной многокомпонентной системой, состоящей из взаимосвязанных объектов: сетевое оборудование, программное и аппаратное обеспечение, внешние источники (пользователи, приборы и т.д.). Обычно исходными данными для генерации трафика узлов (моделирования работы) являются:
- генерирование исходящего трафика на основе накопленной статистики работы, экспертной оценки, накопленная статистика в экспертных оценках;
- генерирование исходящего трафика как результата моделирования обработки узлом входящего трафика.
Данные подходы к моделированию узла обладают рядом недостатков. В первом случае не возможно прогнозировать трафик по работе компонент узла. Во втором случае схемы обработки строятся по упрощенным алгоритмам обслуживания и управления очередями, способным описать лишь простые узлы (ftp-серверы, файловые серверы и т.д.), и имеют скорее теоретическую реализацию, чем практическую. На практике, часто, эксперту (пользователю) легче описать работу компонент узла некоторых параметров, которые представляют собой дискретные временные ряды. При этом параметры описываются не только числовыми значениями, но и экспертными оценками текущего состояния и их динамикой. Зависимость трафика от параметров работы достаточно сложна, поэтому необходимо на основе текущей работы узла (накопленным данным) построить функциональную зависимость, что является объектом анализа ВР.
По модели нечеткой тенденции проанализирована работа одного из узлов вычислительной сети УлГТУ и создана модель узла, генерирующая нагрузку сетевого интерфейса в зависимости от параметров работы пользователей, программного обеспечения и оборудования. Узлом является сервер под операционной системой Microsoft Windows 2003, выполняющий приложения в терминальном режиме. Основное пользовательское приложение: базы данных «1С:Предприятие», работающее в файл-серверном режиме, где данные расположены на этом же сервере. Администратор ВС может описать работу программного и аппаратного обеспечения, описать же работу сетевого оборудования (трафик) затруднительно. Определить зависимость объема трафика от работы приложений, выполняющихся на сервере, и работы пользователей так же затруднительно, так как отсутствует прямая связь между данными элементами. Но для проектирования общей ВС необходимо не только построить модель узла, генерирующий определенный трафик, но и смоделировать ситуации при различных режимах работы программного приложения.
Для описания сервера были выбраны данные из журнала событий прикладного ПО и журнала счетчиков ОС (табл. 4.1). Первые показывают действия пользователей, вторые - работу программного обеспечения и оборудования. Статистика собрана с 15 секундным интервалом в течение одного дня.
