Содержание к диссертации
Введение
Глава 1. Современное состояние проблемы и критический анализ существующих методов обработки временных рядов .10
1.1 Методы анализа временных рядов в компьютерных системах .10
1.2 Анализ временных рядов телекоммуникационного трафика .13
1.3 Корреляционный анализ временных рядов .15
1.4 Спектральный анализ временных рядов 16
1.5 Фрактальный анализ нестационарных процессов
1.5.1 Классификация фракталов .18
1.5.2 Обзор методов получения фрактальных множеств .19
1.5.3 Фрактальная размерность .21
1.5.4 Методы определения фрактальной размерности 23
1.6 Вейвлет-анализ нестационарных процессов .25
1.6.1 Математические основы кратномасштабного анализа 30
1.6.2 Применение вейвлет-преобразований 35
1.6.3 Достоинства и недостатки вейвлет-преобразований 39
1.7 Выводы по главе 1 41
Глава 2. Математическое и алгоритмическое обеспечение обработки временных рядов в компьютерных системах . 43
2.1 Идентификация временного ряда 43
2.2 Математическая модель временного ряда .44
2.3 Модифицированный комбинированный подход для анализа временных рядов .46
2.4 Математическая и алгоритмическая реализация фрактального анализа временных рядов .48
2.4.1 Метод оценки показателя Херста 48
2.4.2 Метод оценки фрактальной размерности .53
2.5 Математическая и алгоритмическая реализация вейвлет-анализа временных рядов 60
2.6 Интерпретация вычисленных показателей хаотичности и результатов вейвлет – спектров 66
2.7 Корреляционный анализ вейвлет-спектров 67
2.8 Дополнительный показатель частотно-временного распределения нестационарных временных рядов 70
2.9 Выводы по главе 2 72
Глава 3. Численная и программная реализация фрактального и вейвлет-анализа временных рядов 74
3.1 Натурный эксперимент на примере обработки временного ряда базы данных информационной системы .74
3.2 Натурный эксперимент на примере обработки временного ряда сетевого трафика компьютерной системы 94
3.3 Выводы по главе 3. 102
Заключение .104
Обозначения и сокращения 105
Список использованных источников
- Анализ временных рядов телекоммуникационного трафика
- Математические основы кратномасштабного анализа
- Модифицированный комбинированный подход для анализа временных рядов
- Натурный эксперимент на примере обработки временного ряда сетевого трафика компьютерной системы
Введение к работе
Актуальность работы.
В настоящее время для изучения свойств сложных реальных систем и процессов широко применяется подход, основанный на анализе их выходных сигналов. Поэтому анализ систем и процессов, особенно при экспериментальных исследованиях, часто реализуется посредством обработки регистрируемых сигналов.
Почти в каждой предметной области существуют явления, которые необходимо изучать в их динамике, а совокупность регистрируемых сигналов подобного рода за определенный период времени и является временным рядом (ВР).
Для анализа временных рядов, которые представляют собой стационарные или нестационарные случайные процессы используют традиционные методы статистического анализа случайных величин и функций. Наиболее распространенными из них являются корреляционный и спектральный анализы, сглаживание и фильтрация данных, модели авторегрессии и прогнозирования.
Наряду с традиционными методами, в последние годы получают распространение способы обработки сигналов, основанные на фрактальном и вейвлет-преобразованиях. Отличительная особенность последних состоит в том, что они позволяют вскрыть особенности локальной структуры сложного сигнала и выявить различные его свойства, невидимые в режиме реального времени. В области вейвлет-преобразования выделяется дополнительная информация, недоступная в исходном виде. Важной характеристикой методов, основанных на фрактальных представлениях и вейвлет-преобразованиях, является их универсальность.
На сегодняшний момент времени ужесточаются требования к более качественному выявлению внутренних закономерностей в поведении временных рядов и прогнозу периодов устойчивости исследуемых процессов.
Поэтому возникает необходимость в разработке новых и модификации существующих алгоритмов анализа временных рядов в компьютерных системах.
Все это определило выбор темы диссертации, основную цель и исследовательские задачи.
Диссертационная работа посвящена решению проблемы по моделированию и идентификации временных рядов с применением комбинированного подхода для проведения многофакторного анализа нестационарных процессов.
Целью исследования является повышение качества идентификации и анализа временных рядов в компьютерных системах путем использования фрактального и вейвлет-анализа.
Объект исследования - временные ряды в компьютерных системах.
Предмет исследования - фрактальный и вейвлет-анализ.
Для достижения цели диссертационного исследования решались следующие задачи:
- разработать математическую модель временных рядов на основе фрактального и вейвлет-
анализа;
расширить возможности фрактального и вейвлет-анализа введением корреляционного анализа и показателя частотно-временного распределения нестационарных временных рядов;
разработать алгоритмическое и программное обеспечение, реализующих предложенные математическую модель, фрактальную и вейвлет-обработку временных рядов;
применить предложенный комбинированный подход, вычислительный алгоритм и программный комплекс для проверки адекватности модели на основе данных натурных экспериментов;
выявить закономерности в поведении временных рядов на примере базы данных информационной системы и сетевого трафика компьютерной системы.
Научная новизна работы заключается в следующем:
- разработана математическая модель временного ряда, отличающаяся тем, что введена
компонента хаотичности, в результате чего модель более точно отражает реальную ситуацию по
идентификации временного ряда на самоподобность по сравнению со статистическими методами
анализа;
предложен комбинированный подход для математического моделирования и численной реализации на основе сочетания фрактального, вейвлет-анализа временных рядов, корреляционного анализа вейвлет-скалограмм и дополнительного показателя частотно-временного распределения нестационарных временных рядов, позволяющего оценить скорость изменения компонентов сигнала - «динамики нестационарности»;
разработан комплекс алгоритмов и программ для анализа временных рядов на основе применения фрактального и вейвлет-анализа данных информационной системы (Свидетельство о государственной регистрации программы для ЭВМ № 2008613838, Свидетельство о государственной регистрации программы для ЭВМ № 2009610716).
Научные положения, выносимые на защиту:
- математическая модель временного ряда для описания всего многообразия процессов от
стохастических до хаотических и детерминированных;
- комбинированный подход применения алгоритмов математического моделирования и
численной реализации на основе сочетания фрактального, вейвлет-, корреляционного анализа и
динамики нестационарности;
- комплекс вычислительных алгоритмов для реализации предложенного подхода обработки
временных рядов;
- комплекс программ для идентификации и анализа временных рядов.
Практическая ценность работы:
разработано программное обеспечение, реализующее модель и алгоритмы обработки временного ряда;
разработанная математическая модель, алгоритмическое и программное обеспечение являются универсальными и применимы к исследованию нестационарных процессов, представленных временными рядами;
предложенный подход позволяет выявлять внутренние закономерности в поведении временных рядов в режиме реального времени и прогнозировать периоды устойчивости исследуемых процессов;
- разработанная модель и программный комплекс внедрены в: ООО «Строительная
компания Приамурья», OOO «Дальневосточная дорожно-строительная компания», ООО «ТКС
Холдинг», в учебный процесс ФГБОУ ВО «КнАГТУ»;
- результаты диссертационной работы находят применение и развитие при выполнении
Государственного задания Министерства образования и науки РФ 2.1898.2017/ПЧ «Создание
математического и алгоритмического обеспечения интеллектуальной информационно-
телекоммуникационной системы безопасности вуза» – руководитель проекта д.т.н., профессор
Амосов О.С.
Методы исследования. В диссертационной работе при решении поставленных задач были использованы: теория идентификации, математическое моделирование, математическая статистика, методы численного анализа, фрактальный, вейвлет-анализ, корреляционный анализ. В качестве инструментов моделирования и программирования применялись: пакет прикладных программ MATLAB, пакет статистических функций среды разработки программного обеспечения “Delphi”, а также средства высокоуровневого языка программирования для инженерных расчетов “IDL”.
Достоверность научных положений, выводов, рекомендаций, изложенных в диссертации,
подтверждаются применением общепризнанных методов обработки традиционного–
корреляционного анализа, и современных методов – фрактального и вейвлет-анализа, а также использованием большого объема информационных данных для натурных экспериментов, предоставленных отделом социального страхования г. Комсомольска-на-Амуре и ИТ-управлением ФГБОУ ВО «КнАГТУ».
Апробация результатов диссертации. Результаты научно-исследовательской работы по теме диссертации докладывались: на V конкурсе - конференции молодых ученых и аспирантов, организованной при поддержке администрации Хабаровского края в Институте водных и экологических проблем ДВО РАН г. Хабаровск, июнь 2003 г.; на международных научных
чтениях «Приморские зори – 2003», организованных Администрацией Приморского края,
ГОУВПО «ДВГТУ» и ТАНЭБ г. Владивосток, апрель 2003 г.; на научно-технической
конференции аспирантов и студентов ФГБОУ ВПО «КнАГТУ» г. Комсомольск-на-Амуре, апрель
2004 г.; на 4-й региональной научно-практической конференции «Дальневосточная весна»,
посвященной 50-летию ФГБОУ ВПО «КнАГТУ» г. Комсомольск-на-Амуре, май 2005 г.; на
международной конференции «Дальневосточная весна - 2007» ФГБОУ ВПО «КнАГТУ» г.
Комсомольск-на-Амуре, июнь 2007 г.; на расширенном семинаре на кафедре информатики ФГОУ
ВПО «АмГПГУ» г. Комсомольск-на-Амуре, февраль 2010 г.; на физико-математическом семинаре
на кафедре прикладной математики ФГОУ ВПО «ТОГУ» г. Хабаровск, май 2010 г.; на
расширенном семинаре на кафедре информатики ФГОУ ВПО «АмГПГУ» г. Комсомольск-на-
Амуре, сентябрь 2010 г.; на физико-математическом семинаре на кафедре прикладной
математики ФГОУ ВПО «ТОГУ» г. Хабаровск, февраль 2011 г.; на международной конференции
«Career and education 2013», Сингапур, г Сингапур март 2013 г.; на международной конференции
«Trends in nanotechnology international conference TNT-2013» Испания, г. Севилья, сентябрь 2013
г.; на физико-математическом семинаре ФГОУ ВПО «ТОГУ» г. Хабаровск, октябрь 2015 г.
Структура работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованных источников. Содержание изложено на 140 страницах. Список использованных источников содержит 149 наименований работ отечественных и зарубежных авторов.
Публикации и личный вклад.
Основные результаты диссертации отражены в 14 научных работах, в том числе 7 – в ведущих рецензируемых журналах, входящих в перечень ВАК. Проведение основного объема теоретических и экспериментальных исследований, включая обработку данных; разработка моделей, методов и алгоритмов для решения поставленной задачи; анализ и обобщение результатов, полученных в процессе вычислительных экспериментов с моделью выполнены лично автором. Получено два свидетельства о регистрации программы для ЭВМ.
Анализ временных рядов телекоммуникационного трафика
Фрактал — термин, введнный Бенуа Мандельбротом в 1975 году для обозначения нерегулярных самоподобных множеств. В этой области работали и другие ученые Пуанкаре, Жюлиа, Кантор, Хаусдорф, Безикович [15,20,46,56, 64,109,135,136]. Фракталом можно назвать бесконечно самоподобную геометрическую фигуру, каждый фрагмент которой будет повторяться при уменьшении масштаба [11]. Использование фрактальной природы итерационных отображений и решений дифференциальных уравнений достаточно красочно отображено в книгах Пейтгена Х.О. и Рихтера Р.Н. «Красота фракталов», Пейтгена Х.О. «Искусство фракталов. Введение в компьютерную графику» [82].
Фракталы дают очень компактный способ описания объектов и процессов. Большинство структур являются самоподобными и обладают свойством геометрической регулярности, что проявляется в их инвариантности по отношению к масштабу. Другими словами, при рассмотрении реальных объектов в разном масштабе, на каждом уровне будем находить одни и те же геометрические формы [15,29,33,34].
Существует общепринятая классификация фракталов: геометрические, алгебраические, стохастические.
1. Геометрические фракталы – это наиболее наглядные фракталы, которые в двухмерном случае получаются при помощи некоторой ломаной, называемой генератором. В течение одного шага алгоритма каждый из отрезков, который составляет ломаную будет заменен на ломаную-генератор в соответствующем масштабе. При бесконечном повторении этой процедуры, получится геометрический фрактал [36,46,110,121].
2. Алгебраические фракталы – это одна из наиболее крупных групп фракталов, получаемых с применением нелинейных процессов в n-мерном пространстве. Их генерируют с помощью алгебраических формул, иногда совсем несложных.
Установлено, что нелинейные динамические системы имеют несколько устойчивых состояний. Состояние, в котором находится динамическая система после ряда итераций, будет зависеть от ее начального состояния. Поэтому каждые устойчивые состояния (аттракторы) обладают некоторой областью начальных состояний, из которых система окажется в рассматриваемых конечных состояниях. В итоге, фазовое пространство системы будет разбито на области притяжения аттракторов. При фазовом двухмерном пространстве и окрашивании области притяжения разнообразными цветами, возможно получение цветового фазового портрета этой системы (итерационного процесса). Изменяя алгоритм выбора цветов, можно получать сложные фрактальные картины [15,19,39,56,111]. 3. Стохастические фракталы получаются при изменении случайным образом какие-либо параметров в итерационном процессе. При этом будут получаться объекты очень похожие на природные (несимметричность деревьев, изрезанность линии берега и т.д) [15,20,45]. Двумерные стохастические фракталы применяются для моделирования рельефов местности и поверхности моря [122,123].
В природных объектах всегда присутствует случайность. Фракталы, в которых в итеративной системе случайным образом будут меняться какие-либо параметры, будут называться стохастическими (стохастичность с греч. предположение) [15,20,40,75].
Метод получения фрактальных множеств "Система Итерируемых Функций" (Iterated Functions System - IFS) появился в середине 80-х годов в качестве простого средства получения фрактальных структур [20,64].
IFS - это система функций из фиксированного класса функций, совокупность сжимающих аффинных преобразований, которая отображает одно многомерное множество на другое. Аффинные преобразования включают в себя масштабирование, поворот и параллельный перенос. Наиболее простая IFS состоит из аффинных преобразований плоскости: Y = D X + E Y + F. В 1988 году был создан алгоритм известными американскими специалистам Барнсли и Слоан, сжимающий информацию в 500-1000 раз. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), т.е. коэффициентами этих преобразований (в данном случае А,B,C,D,E,F) [56Ml Если мы хотим закодировать изображение двумя аффинными преобразованиями, то будем определять его с помощью 12-ти коэффициентов. Если будем задаваться какой-то начальной точкой при запуске итерационного процесса, то после первой итерации получится две точки, после второй - четыре, после третьей - восемь и т.д.
После ряда десятков итераций будет получен набор точек, которые описывают закодированное изображение. Но сложно искать коэффициенты IFS, кодирующие произвольное изображение. Для построения IFS применимо не только аффинное преобразование, но и другие классы простых геометрических преобразований, задающиеся малым числом параметров. Например, проективные [56,64]: Х = (А1 Х + Вl Y + СТ)/(D1 X + El Y + FT), Y = (A2 X + B2 Y + C2)/(D2 X + E2 Y + F2), или квадратичные [56,64]: Х = А1 Х X + В1 X Y + C1 Y Y + D1 X + E1 Y + F1, Y = A2 X X + B2 X Y + C2 Y Y + D2 X + E2 Y + F2). преобразования на плоскости. Многие экспериментальные данные обладают фрактальной (самоподобной) статистикой, для анализа и моделирования которой можно использовать фрактальный анализ [56]. Кроме того, описываемые фигуры стремятся к масштабной инвариантности, то есть степень их неправильности или фрагментации неизменна во всех масштабах. Центральное место занимает фрактальная размерность. Одним из основных направлений фрактального анализа является изучение фрактальной размерности Dt временного ряда. 1.5.3 Фрактальная размерность
Фрактальная размерность Dt - основная характеристика фрактального объекта [46]. Dt отражает свойство масштабной инвариантности рассматриваемого множества [70,109]. Df =— lim\ \\ (1.2) - ln( ) где Ns - минимальное число n - мерных «шаров» радиуса є, необходимых для покрытия множества. Идея фрактальной размерности лежит в нетрадиционном представлении масштаба и размерности. Фрактальная размерность была впервые введена как коэффициент, описывающий геометрически сложные формы, для которых детали являются более важными, чем полный рисунок [17,48,49,51,70,109,112,116]. Для фрактальных объектов фрактальная размерность должна быть больше топологической (предложено Б. Мандельбротом): Dt dt. (1.3) Этому неравенству придается определенный физический смысл. Топологическая размерность - это обычная геометрическая размерность. Она принимает исключительно целые значения, то есть фракталы можно рассмотреть как множество точек, вложенных в пространство. Топологическая размерность точки равна 0, отрезка линии равна 1, поверхности - 2, объемных тел - 3. В обычных явлениях она характеризует количество параметров, которые необходимы для однозначного задания любой точки множества.
Математические основы кратномасштабного анализа
Сформулируем задачу структурно-параметрической идентификации. Пусть наблюдаются выходные значения y(t) ВР. Необходимо выбрать тип математической модели yM(t) временного ряда (структурная идентификация), оптимизировать ее параметры (параметрическая идентификация) путем вычисления ошибки идентификации s(t) = y(t) - yM(t) и определения соответствия выходных и моделируемых значений ВР с использованием некоторого критерия [83,138,139]. Структурная схема идентификации временного ряда (рис. 2.1) представляет собой частную задачу идентификации без наблюдаемого входного сигнала [138].
Структурная схема идентификации ВР На рисунке 2.1 приняты следующие обозначения: уt - выходные данные ВР; уМ {t) - выходные данные модели ВР; є(і) - разность (невязка) между выходными данными ВР и модели; g(t) - неконтролируемое возмущающее воздействие. Задача решается из условия минимума средней квадратической ошибки [83,138]: М {p[y(t\ yM(t)]} = M {є2 (t)} mm, где є(і) = y(t) - ум (О - ошибка идентификации; РЫЪ Ум (О] = є2 (О - функция потерь; м - знак математического ожидания.
Анализ временных рядов предполагает, что данные содержат систематическую составляющую (обычно включающую несколько компонент) и случайный шум, который затрудняет обнаружение регулярных компонент. Модель, которая трактует каждое значение временного ряда как сумму указанных выше компонент является аддитивной [93,119].
С учетом возможных диапазонов изменения показателей хаотичности предлагаем аддитивную математическую модель временного ряда с использованием компоненты хаотичности %t следующего вида [138,139]: уt=Zt+ 7t+t (2-1) где xt – компонента, выражающая меру хаотичности ряда, описывающая характер процесса и зависящая от Ht - показателя Херста или Dt - показателя фрактальной размерности; 77, - трендовая составляющая, чаще всего аппроксимируется полиномом 1-й, 2-й или более высокой степени [30,93]: - для линейного тренда: t]t = cx + Ъ\ где Ъ - координата пересечения оси абсцисс; с- угол наклона; - для логарифмического тренда: rjt = (с jg( )) + , где с и Ъ - это константы тренда, lg - логарифм; - для степенного тренда: rjt = cxb, где с иЬ - это константы тренда; - для экспоненциального тренда: rjt = се , где с и Ъ - константы, а е - основание натурального логарифма; - полином степени п: rjt = (e/)+...+( )+(V )+i, где с и константы; t = t0,tl,....tn- моменты времени; є- случайный шум. Введенная компонента %t выражает хаотичность ВР, позволяя выявить его персистентность. Предложенная модель является универсальной и может быть применена для идентификации и прогнозирования временных рядов из разных предметных областей.
Нами предложенная модель используется для анализа временных рядов базы данных информационной системы и сетевого трафика компьютерной системы, поскольку, раннее такая модель не применялась в этой области. 2.3 Модифицированный комбинированный подход для анализа временных рядов
Предлагается модифицированный комбинированный подход для анализа ВР, состоящий из следующих этапов: 1) Предобработка данных информационной системы, которая заключается в выборке статистических данных для формирования интересующего нас временного ряда. 2) Проведение комплексной обработки временного ряда методом фрактального (определение показателей хаотичности Ht и Dt ) и вейвлет-анализа. 3) Сравнительный анализ вейвлет-спектров путем получения численных значений корреляции двух сравниваемых процессов для выявления закономерностей. 4) Применение дополнительного показателя частотно-временного распределения нестационарных временных рядов, позволяющего оценить скорость изменения компонентов сигнала. 5) Оценка самоподобности на основе комбинированного подхода фрактального и вейвлет-анализа, корреляционного анализа и «динамики» нестационарности для идентификации ВР. 6) Выявление внутренних закономерностей в поведении временных рядов и его прогнозировании на основе трендовой составляющей и показателя хаотичности.
Данное комбинированное применение позволит получать наиболее обширную информацию об исследуемом процессе, как в количественных оценках (величина Ht ,Dt , величина корреляции, значение дополнительного показателя) так, и путем качественного анализа вейвлет-спектров, графиков корреляционного анализа и динамики нестационарности. Результатом решения будет полноценная объемная информация о временном ряде, по которой можно идентифицировать ВР и выявлять закономерности в поведении системы. Блок-схема алгоритма, отражающая последовательность всех этапов метода идентификации, представлена на рисунке 2.2.
Предложенный подход позволяет выявлять внутренние закономерности в поведении временных рядов в режиме реального времени и прогнозировать периоды предполагаемой устойчивости явления исследуемых процессов.
Модифицированный комбинированный подход для анализа временных рядов
В данном исследовании применили расчет фрактальной размерности с использованием поточечного метода. Данный алгоритм расчета на настоящий момент является общеизвестным, классическим и заключается в следующем [53].
Рассмотрим какое-либо множество случаев хх,х2, xN за исследуемый период, расположенных в -мерном пространстве (рис. 2.4) [107]. Опишем вокруг какого- либо случая сферу радиуса г и подсчитаем число случаев M(xt,r), попавших внутрь сферы. Вероятность того, что выборочный случай окажется внутри сферы, мы получим, разделив М(х1,г)на полное число случаев в исследуемом множестве [107]: Р(Х Г\ = МАЬЛ (2.12) N Как следует из определения фрактальной размерности, при малых г вероятность Р(хпг) должна вести себя как «г , где Dt - Хаусдорфова размерность множества. В таком случае: Р(х) = ЫЪёР(-х"г) (2.13) log г
Для некоторых множеств это определение не зависит от выбора случая х1. Но для многих других множеств Dt зависит от х. и поэтому лучше использовать усредненную поточечную размерность [107]. Рисунок 2.4 - График в двухмерном пространстве с выборочными точками и окружностью, внутри которой производится подсчет выборочных точек
При распределении случаев могут иметься пробелы, в результате чего Р{х„г) при г - 0 перестает быть непрерывной функцией от г. Чтобы получить усредненную поточечную размерность, выбираем случайным образом множество случаев размером L N и в каждом его случае вычисляем Р(хпг). После того как это сделано, усредненная Хаусдорфова размерность множества вычисляется по формуле: 1 L А = -ЕА0О (2.14) L /=i Число L подбираем опытным путем, начиная с какого-нибудь малого значения и постепенно увеличивая его до тех пор, пока Dt не достигнет предела.
С точки зрения вычисления процесс подсчета величин М(хпг) методом варьирования параметра г немного неудобен, так как заранее неизвестен критерий выбора граничных значений rmax и гтп
Также неизвестен алгоритм назначения коэффициента приращения /л \ для формирования прогрессии rj+l =ju-r.. Для того, чтобы получить гладкую зависимость Р(хп г) приращение ц слишком большим быть не должно, но и очень маленькие значения JU могут привести к ненужным вычислительным затратам. Тогда будем применять следующий вычислительный прием - расчет расстояния р от точки х. до всех точек исследуемого множества (пользуясь операцией вычитания векторов): pk=\xk-xt\, k = \,2,....,N.
Далее будем производить сортировку получившегося числового ряда pl,p2,...pN так, чтобы для любого к было выполнено условие рк рк+1.
Легко увидеть, что в результате данных преобразований будет получена последовательность радиусов сфер pl,p2,...pN для которых количество выборочных точек, оказавшихся внутри сферы соответственно равно 1,2,....,N. Тогда, для любого к справедливо равенство: М(х,,рк) = к. (2.15) На данный момент можно определить искомые граничные значения радиуса: rmax = pN, rmin = р2, и коэффициент приращения: Гтіп где Q - необходимое количество членов прогрессии; г ,...,г/,...,гшп (выбираем в диапазоне от 80 до 100). Учитывая эти величины, будем вычислять значения всех членов прогрессии: rj=rnvK-MJ \ j = 1,2,...., Q. Затем для каждого г будем находить такое значение индекса к ряда pl,p2,...,pN для условия: рк г} рк+1 Из полученного числового ряда kx,k2,...,kQ будем исключать повторяющиеся члены, и использовать данный ряд для вычисления вероятности P{xt,pkj) согласно формуле 2.12, которая с учетом упрощена до выражения: P(xt,pk) N ( 2.17) Выражение 2.13 в данном случае, теперь выглядит таким образом: Ц ( ,.) = Mm fo g P (jc,.,pfe.) o log p.. (2.18) где pk - граничные значения радиуса. Находим предел для поиска «наиболее линейного» участка зависимости log P{xi, /V ) от log рк. и построения линейной аппроксимации следующего вида: logP(xt,рк ) = Mogpk +с используя метод наименьших квадратов. Для оценки поточечной размерности возьмем Dt(x,) = -b.выражения 2.15 будет
Существует необходимость удаления из множества рк всех случаев, вносящих нелинейность в зависимость log Р(Х; ,рк) от log рк , соответственно все оставшиеся случаи будут находиться на линейном участке (рис. 2.5) [107]. log r Рисунок 2.5 – Пример оценки емкости Dt (xi ) методом линейной аппроксимации Эту процедуру реализуем методом итерационного алгоритма. Для каждого члена множества pkl,pk2,...,p производим тест - данный член будет временно удален из множества и вычислен коэффициент корреляции между log P(xj,pk.) и log рк для всех остальных членов, а после тестирования опять возвращены в множество. Выбракуем из множества те члены, во время теста которых, будет наблюдаться максимальное увеличение корреляции, и соответственно, вноситься наибольшая нелинейность. Процесс выбраковки продолжаем до тех пор, пока количество q членов множества рк. не будет уменьшено до 3-5. Тогда можно быть уверенным, что оставшиеся q точек будут лежать на линейном участке зависимости bg Р(х„рк) от log рк
Натурный эксперимент на примере обработки временного ряда сетевого трафика компьютерной системы
В связи с ростом частных внутренних сетей компаний, чрезвычайно важно, чтобы сетевые администраторы знали и умели управлять вручную различными типами трафика, который путешествует по их сети. Мониторинг и анализ трафика необходимы для того, чтобы более эффективно диагностировать и решать проблемы, когда они происходят, таким образом, не доводя сетевые сервисы до простоя в течение длительного времени.
В трафике в сетях сообщения представлены пакетами символов, которые могут иметь различную длину и передаваться друг за другом по каналам связи, соединяющим между собой узлы сети — устройства объединения, ответвления и перенаправления пакетов (рисунок 3.17).
Можно измерять также исходящий трафик из некоторого сетевого элемента независимо от получателя или входящий трафик в выбранный сетевой элемент, откуда бы он ни исходил. Измерение трафика при этом сводится к подсчету числа пакетов, проходящих по выбранному пути, и измерению длины каждого из пакетов. Под интенсивностью понимается количество байтов/пакетов трафика в единицу времени. Пакет представляет собой, определенным образом, оформленный блок данных, передаваемый по компьютерной сети в пакетном режиме.
Обрабатываемые информационные данные предоставлены ИТ-управлением ФГБОУ ВО «КнАГТУ». В качестве временного ряда была рассмотрена активность одного из портов маршрутизатора в части количества принятых байтов в единицу времени (байтовая интенсивность, единица времени равна приблизительно 3 секунды). По факту рассматривалась статистика за три весенних месяца, но с учетом практически нулевой активности в нерабочее время (ночное время и выходные) общая выборка составила 511800 значений
Как указано во множестве литературы сетевой трафик является самоподобным или фрактальным. Основываясь на утверждении (например, у Шелухина О.И.) [125,126], что показатель Херста Ht самоподобного ряда лежит на [0.5,1] и чем ближе Ht к 1 тем ряд более самоподобный, определяли самоподобность в заданном диапазоне для заданного набора данных. Таким образом, для рассматриваемого сетевого ряда рассчитывали значение Ht R/ S методом.
Для того, чтобы проанализировать телекоммуникационный трафик, предлагается использовать алгоритм, состоящий из следующих этапов [139]: 1) Предобработка временного ряда трафика, которая заключается в выборке статистических данных для формирования интересующего нас временного ряда. 2) Оценка показателя самоподобности с использованием различных методов, например, R/ S - метода и вейвлет-анализа. 3) Идентификация математической модели ВР путем аппроксимации с известными моделями или синтез структуры и параметров математической модели ВР.
Результатом решения будет полноценная объемная информация о временном телекоммуникационном ряде компьютерной системы, с выявленными характеристиками, по которым можно идентифицировать математическую модель ВР. Для решения какой-либо практической задачи, например, выявление аномалий в сетевом трафике для обеспечения целостности данных в компьютерной системе, ВР на управляемом промежутке времени необходимо сравнить с идентифицированной моделью и на основе результата произвести оценку.
Для снижения вероятности неверного истолкования результатов оценки Ht предлагается анализировать не только всю выборку, но и проводить анализ отдельных блоков данной выборки. При этом рассматривать блоки отдельно, со смещением окна и/или нарастающим образом. В зависимости от метода оценки Ht далее производить расчеты для каждого рассматриваемого блока (-ов) отдельно и находить математическое ожидание найденных результатов: Я, = Я,р, где S - количество блоков. Данный модифицированный показатель P=1 Ht, будет более адекватно отражать реальную ситуацию по идентификации телекоммуникационного временного ряда на самоподобность.
Для того, чтобы убедиться во фрактальности ряда использовали не сразу весь ряд, а его часть с последующим нарастанием, это позволило посмотреть если ли значительные изменения в значении Ht в зависимости от рассматриваемой длины. Каждый из данных диапазонов дробился на интервалы: эта статистика позволила увидеть при каких интервалах Ht стремится к 1, а при каких к 0.
Для примера на рисунке 3.18 представлен результат R/S анализа на всей выборке из 500000 значений. Здесь первоначальная выборка равна 20000 значений с последующим нарастанием 25 раз, начальный размер интервала равен 1000, максимальный размер интервала 50000. Красными точками отмечена накопленная статистика R/S и N, ломанная синяя линия - это логарифм от среднего R/ S и N, а черная прямая - это прямая наклон которой и есть показатель H .