Обчислювальні методи ідентифікації моделей в задачах прогнозування телетрафіку

Размещено на http://www.allbest.ru/

Харківський національний університет імені В.Н. Каразіна

УДК 519.246.85

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

Обчислювальні методи ідентифікації моделей в задачах прогнозування телетрафіку

01.05.02 - математичне моделювання

та обчислювальні методи

Тарек Юсеф Баді Біштаві

Харків - 2011

Дисертацією є рукопис.

Робота виконана в Харківському національному університеті імені В. Н. Каразіна, Міністерство освіти і науки України

Науковий керівник: доктор технічних наук, професор Жолткевич Григорій Миколайович, Харківський національний університет імені В. Н. Каразіна, завідувач кафедри теоретичної та прикладної інформатики.

Офіційні опоненти:

доктор технічних наук, професор Машталір Володимир Петрович, Харківський національний університет радіоелектроніки, декан факультету комп'ютерних наук;

доктор технічних наук, професор Глоба Лариса Сергіївна, Національний технічний університет України «Київський політехнічний інститут», завідувач кафедри інформаційно-телекомунікаційних мереж.

Захист відбудеться «16»червня 2011 року о 13-30 годині на засіданні спеціалізованої вченої ради Д 64.051.09 Харківського національного університету імені В. Н. Каразіна за адресою: 61022, м. Харків, пл. Свободи, 4, ауд. 6-52.

З дисертацією можна ознайомитись у Центральній науковій бібліотеці Харківського національного університету імені В. Н. Каразіна за адресою: 61022, м. Харків, пл. Свободи, 4.

Автореферат розісланий «____»_______________2011 року.

Вчений секретар спеціалізованої вченої ради С.І. Шматков

Загальна характеристика роботи

Актуальність теми. Моделювання телетрафіка відіграє значну роль у проектуванні та управлінні комп'ютерними мережами. Однак властивості нестаціонарності, самоподібності та нелінійності його характеристик обмежують застосування ефективних методів стохастичного прогнозування, розроблених для стаціонарних або спеціальних випадків нестаціонарних часових рядів (далі - ЧР), та роблять це завдання важкоздійснюваним.

Проблема ідентифікації моделей часових рядів. Рішення аналітика з вибору моделі ЧР часто слідує за аналізом графіків вихідного ряду, його перших різниць та їх коррелограм. Візуальний аналіз - невід'ємна частина базових технологій прогнозування нестаціонарних часових рядів, таких як методологія Бокса-Дженкінса. Також в цих технологіях припускають, в процесі побудови моделей, неодноразові кроки з прийняття рішень людиною. Тому слід зазначити, що робота програмної системи, що використовує сучасні методи та технології побудови моделей, завжди буде значно поступатися за ефективністю роботі кваліфікованого інженера.

Проблеми визначення деяких параметрів є загальними для багатьох моделей нестаціонарних часових рядів. Такими параметрами, зокрема, є:

- загальна кількість точок ряду, які використовуються при його аналізі,

- кількість точок ряду, що становлять «горизонт» прогнозу (на скільки кроків вперед він будується),

- порядок авторегресії (або інакше - розмір «вікна» прогнозу, розмірність «навчального прикладу»).



Рис. 1. Функціональна модель процесу синтезу моделей ЧР

Внаслідок цих причин автоматизація побудови прогнозу для нестаціонарних часових рядів є важкоздійснюваним завданням. На сьогоднішній день на ринку програмного забезпечення, серед інструментів підтримки аналізу та прогнозування ЧР, відсутні програмні рішення, що забезпечують автоматизацію синтезу навіть базових моделей. У зв'язку з цим розробка методів ідентифікації моделей часових рядів з урахуванням специфіки характеристик телетрафіка є актуальним завданням.

Метою роботи є зниження трудомісткості моделювання часових рядів для прогнозування характеристик телетрафіка за рахунок використання експертної системи продукційного типу.

Для досягнення мети були поставлені такі завдання:

1. сформувати набір базових методів моделювання телетрафіка на основі аналізу існуючих методів моделювання часових рядів,

2. вибрати і обґрунтувати критерії ефективності синтезу моделей,

3. сформувати набір евристик для приміщення в базу знань експертної системи,

4. розробити методи ідентифікації моделей часових рядів на основі спеціалізації існуючих методів з урахуванням особливостей поведінки телетрафіка,

5. розробити систему прогнозування телетрафіка, засновану на знаннях, реалізувавши її програмний прототип.

Об'єкт дослідження - процес передачі інформації клієнтам інформаційно-комунікаційних мереж.

Предмет дослідження - обчислювальні методи синтезу моделей телетрафіка на базі часових рядів.

Наукова новизна дисертаційної роботи

Уперше:

1) запропоновано метод ідентифікації моделей нестаціонарних часових рядів, що ґрунтується на використанні експертної системи продукційного типу, база знань якої містить евристики, які використовуються при аналізі характеристик телетрафіка, що дозволило автоматизувати процес синтезу моделей часових рядів для досліджуваного випадку і, таким чином, знизити затрати на обслуговування клієнтів телекомунікаційних систем;

2) розроблено метод побудови ансамблю предикторів часового ряду зі слабко корельованими помилками прогнозування за рахунок багатоцільового навчання предиктора за допомогою генетичного алгоритму багатокритеріальної оптимізації, що дозволяє будувати ансамблі предикторів з ефективним усередненим значень прогнозів;

Отримали подальший розвиток

3) рекурентний варіант нейронної мережі Non-linear Autoregressive Model with External Inputs (далі - NARX), параметри архітектури і розмір навчальної множини якої розраховувалися за допомогою методів нелінійного аналізу динамічних систем,

4) відомі нейромережеві моделі часових рядів, спеціалізовані з метою врахувати специфіку телетрафіка за рахунок додавання додаткових змінних на вхід мережі, - а саме:

- значень умовної дисперсії ЧР, які були отримані за допомогою моделі General Autoregressive Conditional Heteroskedasticity (далі - GARCH);

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

Особистий вклад здобувача. Усі результати роботи були отримані здобувачем особисто.

Практичне значення результатів

Розроблені моделі і методи дозволили автоматизувати процес ідентифікації моделі при прогнозуванні телетрафіку, що дозволяє:

- виключити людину з процесу моделювання при задовільному рівні прогнозу;

- знизити час моделювання характеристик телетрафіка;

- забезпечити вирішення завдання ідентифікації в реальному масштабі часу, що дозволяє рекомендувати результати дисертаційної роботи для використання в системах управління процесами передачі даних.

Результати роботи були впроваджені у спільному підприємстві ТОВ "Eclipse_SP".

Основний зміст роботи

У вступі обґрунтована актуальність теми дисертаційної роботи, викладені мета і завдання роботи, об'єкт і предмет дослідження. Сформульована наукову новизну, практичне значення результатів.

У першому розділі розглядається загальна характеристика стану проблеми дослідження та моделювання трафіку в телекомунікаційних мережах на основі аналізу публікацій з даної проблематики. Розглянуто основні поняття, пов'язані з аналізом характеристик трафіку в телекомунікаційних мережах.

Відзначено основні властивості телетрафіку, що ускладнюють його аналіз - нестаціонарність, нелінійність, самоподібність.

У другому розділі описані моделі часових рядів, що ефективно використовуються на практиці, зокрема - при побудові прогнозу для характеристик телетрафіка. Вибір цих моделей був підтверджений статистичними випробуваннями, які були проведені автором цієї роботи з використанням даних об'єднаного телетрафіка різного типу (бездротові мережі, інтернет-трафік web-сервера, ethernet-трафік), агрегованого по часових інтервалах різної довжини. Докладно ці експерименти описані у Додатку Б. Далі наводиться короткий огляд цих моделей.

Модель авторегресії. Основне припущення полягає в тому, що поточне значення ряду є лінійною комбінацією попередніх значень та випадкової «помилки»:

, (1)

де і - параметри моделі, - випадкова помилка чи «білий шум». При побудові моделі необхідно вирішити два завдання: вибір порядку та оцінку параметрів.

Модель ковзаючого середнього. Ці моделі будують на підставі припущення про те, що поточне значення стаціонарного ряду представляється у вигляді лінійної комбінації поточної та минулих значень помилки, тобто

(2),

де - параметри моделі, - білий шум, - порядок моделі. Для цієї моделі також коротко розглянуто питання оцінки параметрів.

Autoregressive Integrated Moving Average (далі - ARIMA). Бокс та Дженкінс запропонували методологію ARIMA(p, d, q), в якій основною служить змішана модель авторегресії порядку p і ковзаючого середнього порядку q для стаціонарного ряду, отриманого з вихідного за допомогою взяття кінцевих різниць d разів.

(3)

Оцінка параметрів p, q проводиться на основі евристик, що використовуються, в основному, при візуальному аналізі автокоррелограмм часового ряду. Ця методологія за багато років використання показала свою перевагу перед іншими підходами до побудови короткострокового прогнозу для нестаціонарних ЧР, і, на сьогоднішній день, вважається однією з найкращих з існуючих.

GARCH. Ця модель дозволяє враховувати нестаціонарність ЧР стосовно дисперсії. Зокрема, самоподібні випадкові процеси мають цю властивість. Використання цієї моделі дозволяє уточнити довірчий інтервал для математичного очікування майбутнього (прогнозованого) значення часового ряду. Стандартну модель GARCH(P, Q) для умовної дисперсії записують так:

(4)

з обмеженнями

,

де - -я точка часового ряду.

State Space Models (далі - SSM). Основна перевага цих моделей - їх універсальність. Зокрема, стаціонарність ЧР не передбачається. Загальний випадок для лінійної гауссової моделі одновимірного часового ряду можна представити за допомогою рівнянь:

,, (5)

,,

,

де - «спостережувані» значення часового ряду, - вектор станів («неспостережені» змінні), . Матриці передбачаються відомими або визначаються за даними за допомогою алгоритмів навчання (таким чином, можлива автоматизація побудови моделей часового ряду). Прогноз будується за допомогою фільтра Калмана. Для визначення параметрів моделей SSM розроблено ефективні за швидкістю роботи алгоритми.

«М'які обчислювання». Можливості нейронних мереж та генетичних алгоритмів у побудові лінійних і нелінійних моделей динамічних систем і випадкових процесів широко відомі і добре висвітлені в літературі. Проблеми методів ідентифікації нейромережевих моделей можна розділити на три частини:

- проблеми підбору архітектури мережі, пов'язані з відсутністю суворих правил побудови алгоритмів синтезу;

- проблема перенавчання (втрата можливості "узагальнення");

- загальні для всіх моделей проблеми, пов'язані з нестаціонарністю випадкового процесу - це стосується визначення прийнятного обсягу вибірки та довжини «ковзаючого вікна».

Генетичні алгоритми в цій роботі вони використовуються для багатокритеріального навчання предикторів. В цій роботі використовувалися нейронні мережі прямого поширення, мережі Кохонена, рекурентні (рекурентний варіант NARX).

Аналіз хаотичних часових рядів. Поєднання методів теорії стохастичного прогнозування з методами прикладного нелінійного аналізу хаотичних рядів у задачі прогнозування характеристик телетрафіка мотивовано як теоретичними результатами останніх десятиліть, так і прикладними дослідженнями. Відомі роботи, в яких показано, що моделі трафіку, при деяких умовах, можуть володіти складною поведінкою, що відповідає поняттям детермінованого хаосу. У зв'язку з цим інформація про інваріанти динамічної системи може бути корисна на етапі ідентифікації моделі.

Експоненти Ляпунова є величинами, що описують ступінь невизначеності майбутніх станів динамічної системи

, (6)

де - початковий стан, - елемент векторного поля динамічної системи, . Значення експонент Ляпунова є інваріантами, що не залежать від початкових умов. Необхідна умова хаотичності процесу, створюваного нелінійною динамічною системою, полягає в позитивності хоча б однієї експоненти Ляпунова. Будь-який -мірний хаотичний процес має експонент Ляпунова. Позитивні експоненти відображають нестійкість траєкторії системи в просторі станів. Також відомо, що найбільше значення з експонент Ляпунова визначає гoрізонт прогнозування хаотичного процесу.

Використання експонент Ляпунова та тесту Каплана-Гласса (див. розділ 4) вимагає попередніх розрахунків достатньої розмірності простору станів, відновлюваної по часовому ряду реконструкції динамічної системи, а також так званої нормалізованої затримки вкладення (normalized embedding delay) , яка являє собою деяке позитивне ціле число, використовуване у наступному конктексті: еволюція точок у відновлюваному за часовим рядом просторі станів відповідає еволюції точок вихідної динамічної системи, коли стани реконструкції розмірності будуються таким чином:

(7)

Існування мінімального значення розмірності, достатнього для реконструкції аттрактора нелінійної динамічної системи з одновимірного часового ряду, доведено Такенсом.

У третьому розділі розглядаються методи підвищення якості прогнозу за рахунок

- використання багатокритеріального навчання ансамблю предикторів,

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

- кластеризації ряду,

- використання моделі умовної дисперсії ЧР (GARCH).

Багатокритеріальне навчання предиктора за допомогою генетичного алгоритму. На сьогоднішній день відомі ряд методів і технік, що дозволяють підвищити якість прогнозу часового ряду за рахунок використання так званого «усереднювання по ансамблю». Очевидно, що основними факторами, що впливають на ефективність використання ансамблю предикторів є: 1)значення критерію ефективності кожного члена ансамблю, 2) залежності між "залишками" (помилками) кожного з них.

Застосування методу «посилення» (boosting), дозволяє підвищити точність прогнозу фактично за рахунок одержання групи предикторів зі слабко корельованими залишками. Природно було б поставити мету явно (декларативний підхід) - при навчанні предиктора використовувати два критерії: міру точності прогнозу та значення коефіцієнта кореляції між помилками членів ансамблю.

Основна ідея запропонованого в цієї роботі методу полягає в можливості використовувати методів багатокритеріальної оптимізації при побудові (навчанні) ансамблю предикторів часового ряду. Навчання нейронної мережі в задачах класифікації і регресії зводиться до задачі знаходження глобального мінімуму деякої функції - зазвичай, "функції помилок". Додавання критерію тягне використання методів багатокритеріальної оптимізації. У цій роботі ця ідея реалізована за допомогою генетичного алгоритму багатокритеріальної оптимізації. Далі описується чисельний експеримент, в якому показано позитивний ефект використання багатоцільового навчання нейронної мережі на прикладі прогнозування на один крок вперед обсягу трафіку бездротової мережі передачі даних. трудомісткість телетрафік евристика база

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

- 2 шари (з урахуванням вхідного).

- розмір 1-го шару - 3, другого - 1.

- перехідна функція - лінійна (purelin, MATLAB).

Нас цікавила, в основному, якісна сторона питання, тому архітектура мережі була обрана найпростіша (мережа з меншою кількістю ваг вимагає менше часу на навчання, а це полегшує відтворюваність експерименту). Навчання першого предиктора в ансамблі проводилося за допомогою генетичного алгоритму. В експериментах 1, 2 ансамбль складався з десяти предикторів. Для навчання останніх дев'яти використовувався метод багатокритеріальної оптимізації, реалізований на основі генетичного алгоритму. Цілями навчання були:

1. мінімізація медіани абсолютних величин помилок,

2. мінімізація абсолютної величини коефіцієнта лінійної кореляції помилок предиктора (на навчальній множині прикладів) з помилками попереднього предиктора.

В якості «попереднього предиктора» виступали:

3. в одному випадку - ансамбль з усіх навчених предикторів (Експеримент 1),

4. в другому випадку - останній навчений предиктор (Експеримент 2).

Розмір навчальної множини дорівнював 100 (точок часового ряду). У зв'язку з тим, що однією з важливих характеристик предиктора є можливість узагальнювання, якість предикторів випробовувалося на 100 точках часового ряду, віддалених з розривом в 100 точок вперед по відношенню до навчальної множини. Як заходи ефективності були використані

- середнє абсолютних величин помилок (mean of absolute values ??of errors, mae);

- медіана абсолютних величин помилок (medae).

- часто використовуваний показник точності прогнозу «series to error ratio», SER (в децибелах - краща точність відповідає більшому значенню)

(8)

де Е{.} - середнє значення, - значення часового ряду, - передбачені значення.

В експериментах 1 і 2 використовувалися: Ансамбль 1 - група предикторів, при побудові яких використовувалося одноцельове навчання. Ансамбль 2 - група предикторів, навчених з використанням 2-х описаних вище критеріїв.

Таблиця 1

Експеримент 1
	Ансамбль 1	Ансамбль 2	Різниця в %
SER	8.44	8.56	1.47
medae	12401	12215	-1.5
mae	17535	17080	-2.6

Таблиця 2

Експеримент 2
	Ансамбль 1	Ансамбль 2	Різниця в %
SER	8.44	9.34	10.70
medae	12401	12304	-0.78
mae	17535	16435	-6.27

В Експерименті 3 підхід до навчання, використаний в Експерименті 2, був випробуваний для розмірів ансамблю 5 і 15.

Таблиця 3

Експеримент 3
Розмір колективу	5	10	15 ("перенавчання")
SER	-31.20	9.34	-18.90
medae	42910	12304	38185
mae	376608	16435	145322

Як видно з Таблиць 1-3, по всіх трьох показниках точності використання методу показує кращі, ніж при звичайному усередненні результати.

Прогнозування екстремальних значень ряду є важко вирішуване завдання. Далі коротко описаний імунний алгоритм негативного відбору, використання якого показало кращі порівняно з іншими методами результати (експерименти описані у Додатку Б даної роботи). Алгоритм негативного відбору створений на основі уявлень про механізм відбору в імунній системі, здатної відрізняти "своє" від "чужого". У нашому випадку своє визначається як нормальний зразок даних, а чуже - як будь-яке відхилення від норми, що перевищує допустимі межі (різкий стрибок значення обсягу телетрафіка за відносно короткий проміжок часу). Для більшості методів прогнозування рідкісних явищ потрібна наявність апріорної інформації про різні умови виникнення аномалій або точна теоретична модель системи. Але бажано, щоб метод міг виявляти будь-які нові зміни, а не шукати їх серед раніше відомої множини подій. Алгоритм негативного відбору працює наступним чином:

- визначається "свій" як патерн нормальної активності або стійкої поведінки контрольованої системи. Набір даних, що описують нормальну динаміку процесів, представляється як множина з S рядків однакової довжини;

- створюється набір детекторів R, жоден з яких не збігається з будь-якою з рядків множини S. Використовується правило часткового відповідності (міри близькості наборів спостережень);

- дані контролюються шляхом безперервного зіставлення детекторів з новими надходженнями до S. Виявлення збігу з детектором розглядається як зміна (або відхилення) у поведінці контрольованої системи. Кандидати в набір детекторів у вихідному варіанті алгоритму генеруються ??випадково, а потім перевіряються на збіг з власними рядками, і кандидат відкидається, якщо виявляється збіг. Цей процес повторюється до тих пір, поки не буде згенеровано необхідну кількість детекторів. Можна отримати вірогідну оцінку числа детекторів, необхідного для забезпечення заданого рівня надійності. Задача виявлення аномалій зведена до задачі виявлення збігу з детектором, при цьому мається на увазі, що це збіг відповідає зміні патерну нормальної активності.

У Додатку Б описані результати експериментів, в яких на вхід багатослойного персептрона подавалися (як додаткові змінні) результати роботи класифікатора, реалізованого на основі алгоритму негативного відбору, а також значення умовної дисперсії, розрахованої за допомогою моделі GARCH, описаної у другому розділі. За допомогою даного підходу якість прогнозу аномалій вдавалося (в середньому по наборах даних, що були використані) підвищити на 7%.

Кластеризація ряду для побудови довгострокового прогнозу. Одним із підходів до аналізу нестаціонарних послідовностей є розбиття їх на квазі-стаціонарні підпослідовності. Результати експериментів, в яких використовувалася реалізація цієї ідеї, розміщені в Додатку Б. В середньому по використаним наборам даних цей метод поліпшує (в сенсі середньоквадратичної помилки) точність довгострокового прогнозу на 10 кроків уперед на 9.3%.

У четвертому розділі розглядаються питання, пов'язані з розробкою ав-автоматизованої системи прогнозування телетрафіка Traffic Analysis and Prediction System (далі - TAPES). На сьогоднішній день невідомо про існування розповсюджуваного програмного продукту, який забезпечує вирішення питання автоматизації аналізу та прогнозування ЧР, та придатного до використання у індустрії.

Перелічимо основні функції системи: 1)забезпечити мову взаємодії користувача з системою (в тому числі мову специфікації завдань), 2) забезпечити виконання завдань, пов'язаних з побудовою прогнозу, таких як попередній аналіз даних, перетворення вихідного ряду, формування множин навчальних прикладів, навчальної множини, множини для крос-валідації, множини для тестування моделі (back-testing), вибір базової моделі, оцінка параметрів моделі, розрахунок точкових та інтервальних оцінок прогнозів (у разі завдання регресії), віднесення послідовності точок ряду до класу (у разі завдань класифікації), перевірка адекватності моделей, розрахунок значення функції втрат; підсумкова порівняльна оцінка якості моделі.

При розробці мови специфікації завдань використовувалися ідеї та математичний апарат, викладені в роботах [1,2].

У зв'язку з тим, що причиною основних проблем автоматизації аналізу

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

Приклад евристики технології ідентифікації моделей ARIMA (процеси авторегрессіі і ковзаючого середнього) Бокса-Дженкінса:

- якщо значення оцінок автокореляційної функції на перших лагах є значимі і експоненціально зменшуються, а значення оцінок приватної кореляційної функції мають викид на лагу 1, і немає значимих оцінок значень на інших лагах, то це говоріть на користь моделі ARMA (1,0) (процес авторегресії першого порядку).

Приклад правила на мові CLIPS:

(defrule_035

(autocorr (lags 4) (dercrease exponentially) (ar1 0.9))

(partacorr (lag 1))

=>

(assert (base-model arima(1,0,0))

)

Приклад евристики для побудови ансамблів нейронних мереж:

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

Евристики у рамках технології аналізу хаотичних часових рядів. У роботі Каплана і Гласса запропоновано метод оцінки наявності детермінізму у часових рядах. Основна ідея методу полягає в тому, що математична модель, що описує динаміку детермінованої системи, відгук якої аналізується, передбачає єдине рішення. За допомогою отриманої за часовим рядом оцінки векторного поля системи ця властивість перевіряється чисельно. Отримана на виході оцінка відображає ступінь детермінізму ряду в шкалі від 0 до 1. Наприклад, для послідовності значень ряду, що представляють собою реалізацію випадкового блукання, вона дорівнює 0.

Метод помилкових найближчих сусідів (False nearest neighbors) є відносно простим способом визначення мінімальної прийнятною розмірності так званого «простору занурення» - реконструкції динамічної системи. Його основна ідея полягає в тому, що фазова траєкторія реконструкції з розмірністю не може мати самоперетинів.

Коротко алгоритм методу можна описати так: нарощуючи послідовно значення розмірності , будують стани (7) черговий реконструкції, розраховують для кожного стану число найближчих сусідів в околиці з заданим радіусом. На наступному кроці (з розмірністю ) перевіряють, скільки сусідів з попередньої реконструкції «залишилися близькими» в межах якогось порогового значення. На кроках алгоритму, в яких значення більше шуканого мінімального, значення кількості «помилкових сусідів» має впасти до нуля.

Метод визначення затримки вкладення. При побудові реконструкції значення затримки вкладення може бути взагалі будь-якою, але це справедливо тільки для часових рядів нескінченної довжини. На практиці використовуються методи, основані на наступних міркуваннях: прийнятне значення затримки повинно удовольняти двом критеріям: 1) воно повинно бути достатньо великим, щоб загальна кількість точок вихідного ряду, що використовуються при побудові множини станів (8) дозволяло охоплювати досить укладеної в них інформації про динамічну систему; 2) воно повинно бути не більше, ніж час, за який втрачається інформація про попередній стан системи.

Цим двом критеріям задовольняють метод, що використовує як евристику наступне правило: брати в якості значення затримки вкладення довжину затримки, що доставляє перший мінімум кількості взаємної інформації між и , які розглядаються як випадкові величини, розподілені по дискретному закону, який визначається скінченою кількістю інтервалів, що покривають множину значень точок часового ряду. Взаємна інформація розраховується на основі ентропії Шеннона:

, (9)

де

,

, .

При розрахунках використовуються вибіркові оцінки ймовірностей.

У Додатку Б описано експеримент, в якому розмір навчальної множини та архітектура рекурентної нейронної мережі формувалася на основі методів і евристик, описаних вище. В цілому результати свідчать на користь їх використання з метою скорочення часу на синтез нейромережевої моделі.

Засоби розробки програмного забезпечення визначалися цілями проекту і його класом (дослідницький працюючий прототип програмної системи). Використовувалася можливість виклику процедур інших програмних продуктів, а платформу dot-NET корпорації Microsoft використовували як інтегруючу середу, що включає функції взаємодії з користувачем. Діаграма компонентів TAPES представлена на мал. 2.

Рис 2 Діаграма компонентів системи TAPES

Режими роботи автоматизованої системи

Система TAPES може працювати в наступних режимах: «автоматичний» - пакетне завдання виконується у відповідності із специфікаціей (без втручання користувача), «напівавтоматичний» - система може звертатися до користувача з приводу вибору рішення, «середовище розробки експертної системи» - в цьому режимі можна модифікувати базу знань.

Таким чином, користувачами TAPES можуть бути: 1) проектувальники й адміністратори комп'ютерних мереж, інженери суміжних спеціальностей, фахівці з прикладної математики 2) фахівці з аналізу даних, 3)інженери по знаннях.

Висновки

Був виконаний огляд існуючих методів і моделей прогнозування часових рядів. Досліджено експериментально застосовність відомих моделей часових рядів для задачі прогнозування характеристик телетрафіка.

Розроблено метод ідентифікації моделей характеристик телетрафіка, що ґрунтується на використанні експертної системи продукційного типу, база знань якої містить евристики, що враховують його специфіку.

Розроблено моделі тимчасових рядів обсягу об'єднаного телетрафіка з урахуванням його особливостей.

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

Розроблені моделі і методи дозволили автоматизувати процес ідентифікації моделі при прогнозуванні телетрафіка, і, тим самим, знизити витрати на синтез моделей.

Список опублікованих праць

1. Биштави Тарек Юсеф Бади. Выполнимые спецификации в проектировании баз данных / Биштави Тарек Юсеф Бади, Жолткевич Г. Н., Соляник Ю. В. // Системи обробки інформації.- 2008. - Вип. 2(69) - 108 - 111.

2. Биштави Тарек Юсеф Бади. Об одной обобщенной модели вычислений и ее языковой реализации / Биштави Тарек Юсеф Бади, Жолткевич Г. Н., Соляник Ю. В.// Вестник Херсонского национального технического университета. - Выпуск. 2(35), 2009. - с. 95 - 100.

3. Биштави Тарек Юсеф Бади. Многокритериальное обучение предиктора в задаче прогнозирования телетрафика / Биштави Тарек Юсеф Бади, Жолткевич Г.Н., Соляник Ю.В. // Системи обробки інформації.- 2010. - Вип. 2(83). - 163-165.

4. Биштави Тарек Юсеф Бади. О прототипе экспертной системы для поддержки автоматизации прогнозирования характеристик телетрафика / Биштави Тарек Юсеф Бади, Жолткевич Г. Н., Соляник Ю. В. // Вестник Харк. нац. ун-та., - 2010. - № 926. Сер. "Математическое моделирование. Информационные технологии. Автоматизированные системы управления", - Вып. 15. - С. 39

5. Биштави Тарек Юсеф Бади. О функциональной структуре программного комплекса прогнозирования телетрафика / Биштави Тарек Юсеф Бади, Жолткевич Г. Н., Соляник Ю. В. // Системи управління, навигації і зв'язку. - 2010. - Вип. 3(15)

Анотація

Тарек Юсеф Баді Біштаві. Обчислювальні методи ідентифікації моделей в задачах прогнозування телетрафіку. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Харківський національний університет імені В. Н. Каразіна. - Харків. - 2011.

Дисертація присвячена проблемі зниження трудомісткості моделювання часових рядів для прогнозування характеристик телетрафіка за рахунок вико-користування експертної системи продукційного типу.

Моделювання телетрафіка грає значну роль у проектуванні та управлінні комп'ютерними мережами. Однак властивості нестаціонарності, самоподібності та нелінійності його характеристик обмежують застосування ефективних методів стохастичного прогнозування, розроблених для стаціонарних або спеціальних випадків нестаціонарних часових рядів. У зв'язку з цим завдання автоматизації побудови прогнозу для нестаціонарних часових рядів є важкоздійснюваним, а розробка методів ідентифікації моделей часових рядів з урахуванням специфіки характеристик телетрафіка є актуальним завданням.

Для ідентифікації моделей характеристик телетрафіка був розроблений і реалізований проект прототипу автоматизованої системи ідентифікації на основі продукційної експертної системи.

Розроблено моделі часових рядів обсягу об'єднаного телетрафіка з урахуванням його особливостей.

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

Розроблені моделі і методи дозволили автоматизувати процес ідентифікації моделі при прогнозуванні телетрафіка, що дозволяє:

- виключити людину з процесу моделювання при задовільному рівні прогнозу;

- знизити час моделювання характеристик телетрафіка;

- забезпечити вирішення завдання ідентифікації в реальному масштабі часу, що дозволяє рекомендувати результати дисертаційної роботи для використання в системах управління процесами передачі даних.

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

Аннотация

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Харьковский национальный университет имени В. Н. Каразина. - Харьков. - 2011.

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

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

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

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

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

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

- количество точек ряда, составляющих «горизонт» прогноза (на сколько шагов вперед он строится),

- порядок авторегрессии (или иначе - размер «окна» прогноза , размерность «обучающего примера»).

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

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

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

Разработаны модели временных рядов объема объединенного телетрафика с учетом его особенностей. В частности:

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

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

Получили дальнейшее развитие

- рекуррентный вариант нейронной сети Non-linear Autoregressive Model with External Inputs, параметры архитектуры и размер обучающего множества которой рассчитывались с помощью методов нелинейного анализа динамических систем,

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

- значений условной дисперсии временного ряда, которые были получены с помощью модели General Autoregressive Conditional Heteroskedasticity (GARCH);

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

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

Разработанные модели и методы позволили автоматизировать процесс идентификации модели при прогнозировании телетрафика, что позволяет:

- исключить человека из процесса моделирования при удовлетворительном уровне прогноза;

- снизить время моделирования характеристик телетрафика;

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

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

Abstract

Tareq Yousef Badei Bishtawi. Computational methods for teletfaffic models identification. - Manuscript.

Thesis for the scientific degree of the candidate of the technical sciences on the speciality 01.05.02 - mathematical modelling and computing methods. - V. N. Karazin Kharkiv National University. - Kharkiv. - 2011.

The dissertation is devoted to reducing the complexity of modelling time series to predict the teletraffic characteristics using expert system of production type.

Teletraffic modelling plays a significant role in designing and managing computer networks. However, the properties of non-stationarity, self-similarity, and nonlinearity of its characteristics constraints the application of effective methods of stochastic prediction, designed for stationary or special cases of non-stationary time series. In this connection automation of constructing prediction for non-stationary time series is difficult to implement, and developing methods to identify models of non-stationary time series of teletraffic characteristics is an urgent task.

To identify the models of teletraffic characteristics the software prototype of automated identification system based on a production expert system was developed. The teletraffic models taking into account its features were developed. In particular:

- a method for identification of models of non-stationary time series based on the use of production type expert system, which knowledge base includes heuristics that are used in the analysis of teletraffic characteristics was proposed, that will automate the process of time series models synthesis;

- a method for constructing an ensemble of time series predictors with weakly correlated forecast errors using multiobjective optimisation genetic algorithm was developed;

- neural network models which use the conditional variance and the results of immune negative selection algorithm as additional input variables were developed, thus improving the quality of rare events forecasting.

Specification language for tasks of time series analysis and prediction was developed.

The developed methods and models allow to:

- exclude people from the modelling process with a satisfactory level of prediction quality;

- reduce the model development time;

- provide a solution to the problem of identification in real time, allowing the results to recommend for use in the telecommunication systems.

Key words: model identification, time series prediction, teletraffic, stochastic processes, data analysis.

Размещено на Allbest.ru

...