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

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

Донецький національний університет

УДК 004.832.34; 004.436.4

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

Спеціальність 05.13.06 - Інформаційні технології

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

кандидата технічних наук

Хмільовий Сергій Володимирович

Донецьк 2009

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

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

Науковий керівник: д.т.н., проф., Скобцов Юрій Олександрович, Донецький національний технічний університет, завідувач кафедри автоматизованих систем управління

Офіційні опоненти: д.т.н., проф., Кучеренко Євген Іванович, Харківський національний університет радіоелектроніки Міністерства освіти і науки України, професор кафедри штучного інтелекту;

к.т.н., доц. Петренко Тетяна Григорівна, Донецький національний університет Міністерства освіти і науки України, доцент кафедри комп'ютерних технологій.

Захист відбудеться «26» червня 2009 р. о 13.00 годині на засіданні спеціалізованої вченої ради К 11.051.08 у Донецькому національному університеті Міністерства освіти і науки України за адресою: Україна, 83000, м. Донецьк, пр. Театральний, 13, корп.4, ауд.416.

З дисертацією можна ознайомитись у бібліотеці Донецького національного університету за адресою: 83000, м. Донецьк, вул. Університетська, 24, головний корпус.

Автореферат розіслано «25» травня 2009 р.

Вчений секретар спеціалізованої

вченої ради К 11.051.08 ___________ Д. В. Шевцов

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ.

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

Аналізу, моделюванню й прогнозуванню процесів різної природи, у тому числі й за допомогою методів штучного інтелекту (генетичних алгоритмів, нечіткої логіки, нейронних мереж) приділялася велика увага в роботах Д. Гольдберга, З. Михалевича, Л. Заде, М. Негневицького, О. Кордона, Є.В. Бодянського, В.М. Курейчика, В. А. Крисілова, В.В. Круглова, О.В. Леоненкова, В.Є. Ходакова та багатьох інших.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами

Робота виконувалася відповідно до науково-дослідних робіт: Н-3-07 «Розробка наукових основ побудови комп'ютерних систем технічної й медичної діагностики», Д-11-04 «Розробка й дослідження нейромережевих і еволюційних методів побудови систем прийняття рішень», № ДР 0104U002394, а також Д-11-07 «Розробка й дослідження еволюційних і нейромережевих моделей, методів і алгоритмів у системах діагностики й прогнозування», № ДР 0107U001482.

Мета і завданя дослідження.

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

Для досягнення поставленої мети в роботі сформульовані й вирішені наступні завдання:

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

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

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

- створено програмне забезпечення технології _ алгоритми, що реалізують розроблені математичні методи, та інструментальні засоби, за допомогою яких реалізовано розроблені методи й алгоритми;

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

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

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

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

Наукова новизна отриманих результатів роботи визначається такими одержаними автором теоретичними й експериментальними результатами: прогнозний інформаційний технологія модель

1. Удосконалено метод застосування генетичних алгоритмів для відбору значущих факторів. Уведення адаптивного кроку компактного генетичного алгоритму в умовах стохастичності оцінки набору факторів для задач прогнозування дає можливість істотно скоротити час пошуку.

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

3. Набув подальшого розвитку метод побудови паралельних еволюційних алгоритмів. Побудовано розподілений еволюційний алгоритм для паралельного обчислення нечітких правил на основі моделі «робітник-хазяїн». На відміну від відомих методів, процес-сервер здійснює корекцію навчальної вибірки для процесів-клієнтів, що забезпечує краще настроювання створюваних правил на малоописані області простору пошуку. Експериментально отримано лінійне зростання швидкості створення бази знань при малій кількості клієнтів.

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

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

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

2. У держбюджетній темі Н-3-07 «Розробка наукових основ побудови комп'ютерних систем технічної й медичної діагностики» використані методи попередньої обробки даних, у тому числі для задач прогнозування. У темі Д-11-04 «Розробка й дослідження нейромережевих і еволюційних методів побудови систем прийняття рішень», № ДР 0104U002394 застосовані розроблені методи для еволюційного алгоритму видобування знань для задач класифікації, у темі Д-11-07 «Розробка й дослідження еволюційних і нейромережевих моделей, методів і алгоритмів у системах діагностики й прогнозування», № ДР 0107U001482 розроблені методи видобування знань були використані для задач прогнозування.

3. Розроблені алгоритми й програмне забезпечення застосовуються в навчальному процесі під час виконання лабораторних і курсових робіт навчальних курсів “Нечіткі методи обробки й аналізу даних”, “Еволюційні обчислення”, “Системи штучного інтелекту при розв'язанні технічних задач”, “Методи інтелектуальної обробки даних”, а також для виконання дипломних проектів і магістерських робіт студентами спеціальностей “Інформаційні керуючі системи й технології” і “Спеціалізовані комп'ютерні системи” Донецького національного технічного університету.

4. Розроблена підсистема прогнозування кількості підключень до автоматичних телефонних станцій (АТС) ВАТ «Промтелеком» дала можливість обґрунтувати прийняття рішень з приводу установки телекомунікаційного устаткування оператора. При точності, що перевершує точність нейронної мережі (на 2.5-8.1%), побудований набір правил, що становить базу знань, дозволяє визначити ступінь впливу кожного фактору на часовий ряд кількості підключень.

Особистий внесок здобувача. Усі положення, що виносяться на захист, отримані дисертантом самостійно. Публікації [1-3, 11] виконані автором самостійно. У публікаціях [4-10, 12-14] авторові належить програмна реалізація й тестування методів і алгоритмів. Також авторові належить: у [6] _ модифікація кроку КГА; у [7] _ математична реалізація задачі, вибір виду модифікованої функції належності; у [8] _ застосування еволюційної стратегії для настроювання параметрів лінгвістичної бази даних; у [9] _ проектування інструментальних засобів, у [10] _ одержання бази знань для прогнозування кількості підключень абонентів до АТС; у [13] _ ідея застосування еволюційної стратегії для процедури тюнінгу, у [14] _ модифікація фітнес-функції.

Апробація результатів дисертації. Основні положення результатів роботи доповідалися й обговорювалися на конференціях: VI науково-практична міжнародна конференція «Інформаційні технології в освіті і керуванні», Нова Каховка, 2004; Міжнародна наукова конференція «Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій» (ISDMIT'2006), Євпаторія, 2006; IX міжнародна науково-технічна конференція «Системний аналіз і інформаційні технології», Київ, 2007; IX науково-практична конференція «Інформаційні технології в освіті й керуванні», Нова Каховка, 2007; 20-а міжнародна школа-семінар «Перспективні системи керування на залізничному транспорті й прогресивні інформаційні технології», Алушта, 2007; ІІ Всеукраїнська науково-практична конференція «Сучасні тенденції розвитку інформаційних технологій у науці, освіті й економіці», Луганськ, 2008; VIII міжнародна конференція «Інтелектуальний аналіз інформації ІАІ-2008», Київ, 2008.

Публікації. За матеріалами роботи опубліковано 14 публікацій, з них 11 _ статті у фахових виданнях ВАК України, 3 тези в збірниках праць конференцій.

Структура й обсяг роботи. Дисертаційна робота складається із вступу, п'яти розділів, висновку й списку літератури. Загальний обсяг тексту дисертації 196 сторінок, у тому числі 151 сторінка основного тексту, 30 рисунків, з них 5 _ на окремих сторінках, 30 таблиць, список використаної літератури з 163 джерел, 8 додатків на 28 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У першому розділі «Аналіз інтерпретованих методів прогнозування часових рядів, визначення етапів процесу видобування знань» наведено аналіз задачі прогнозування кількості підключень абонентів до АТС, досліджено програмні продукти, здатні вирішити цю задачу. Проаналізовано методи, на основі яких функціонують досліджені програмні продукти.

Зроблено дослідження готових систем для рішення задачі прогнозування. У мережі Internet доступна інформація про понад десять програмних продуктів. Зроблено аналіз методів прогнозування, на яких основані ці програмні продукти.

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

Також розглянуто загальну структуру систем для розв'язання задачі видобування знань, до якої зводиться й задача прогнозування кількості підключень до АТС. Виділяють три етапи: попередньої обробки даних (препроцесингу), безпосередньо видобування знань, зокрема для розв'язання задачі прогнозування, і наступної обробки правил (постпроцесингу).

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

Зроблено висновки про необхідність:

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

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

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

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

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

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

Зроблено формалізацію розв'язуваної задачі. У процесі рішення задачі прогнозування потрібно знайти значення Y у майбутній момент часу на основі відомих попередніх значень

:

(1)

де - підмножина нерегульованих факторів задачі;

- підмножина регульованих параметрів задачі;

_ часовий ряд, представлений своїми значеннями в попередні моменти часу , де t-теперішній момент часу, k-глибина історичної вибірки.

Необхідно виконати побудову системи нечіткого висновку таким чином, щоб виконувалася мінімізація двох критеріїв: критерію точності системи (AC(FRSN)) і критерію інтерпретованості (IC(FRSN)):

, (2)

де FRSN _ нечіткий висновок, визначений як результат прийняття рішення системою нечіткого висновку на основі бази нечітких правил і значення вхідних змінних;

R - база нечітких правил.

Математичне забезпечення інформаційної технології необхідно створювати на основі створення системи нечіткого висновку (fuzzy rule-based system, FRBS): , де LV - множина з n вхідних і однієї вихідної лінгвістичних змінних; R - множина із n_pr правил бази правил; T - t-норма для оцінки ступеня істинності підвисновку правил і для процедури активізації; I - стратегія імплікації; T^* _ t-конорма для оцінки вихідної функції належності і визначення процедури акумуляції; DE - стратегія дефазифікації.

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

У процесі побудови системи можна виділити наступні етапи:

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

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

· Апробація інформаційної технології.

Кожний із цих етапів повинен бути виконаний і описаний. Послідовність створення інформаційної технології видобування знань показано на рис. 1.

Дослідження методів відбору факторів впливу показало, що в умовах стохастичності оцінки набору факторів існуючі методи вимагають доробки. Ці умови можуть бути отримані, наприклад, при прогнозуванні за допомогою нейронних мереж (НМ). У такому випадку порівняння якості двох наборів факторів можливе тільки з певною імовірністю. Як базові методи запропоновано використовувати генетичні алгоритми (ГА), які відрізняє повторюваність оцінки набору факторів. Повторюваність оцінки збільшує надійність порівняння якості двох наборів. Із всіх видів ГА обрані компактні генетичні алгоритми (КГА) внаслідок простоти реалізації при результатах, порівняних із результатами класичних ГА.

Модифіковано величину кроку КГА для мінімізації кількості порівнянь залежно від ступеня вірогідності оцінки якості набору факторів.

, (3)

де , _ функція Лапласа.

Уведення модифікованого кроку зміни КГА значно скорочє час знаходження рішення (до 90.6%) при збереженні точності.

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

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

Наведено метод побудови системи нечіткого висновку. У загальному випадку використовуються правила наступного вигляду: R_i: ЯКЩО x₁м_A1i, І…І x_n м_Ani, ТО y м_Bi, де х₁, х₂, …, x_n - вхідні лінгвістичні змінні, y - вихідна лінгвістична змінна, м_A1i, м_Ani, м_Bi _ функції належності відповідних підумов і підвисновку (у формі трикутних нечітких інтервалів).

Для поліпшення точності форма функцій належності підумов задається трьома дійсними числами і може довільно мінятися (під час використання вільної семантики правил). Настроювання форми підумов правил виконуються еволюційним алгоритмом. Хромосома має вигляд С=С1С2, де С1= С1₁,С1₂,…,С1_n,С1_y - вибір конкретного терму лінгвістичної змінної для кожного входу й виходу, С2=C2_a1 C2_b1 C2_c1 C2_a2 C2_b2 C2_c2…С2_an С2_bn C2_cn C2_ay C2_by C2_cy - точне настроювання нечітких функцій правила. За допомогою фрагмента С1 правила настроюються грубо, фрагмент С2 використовується для точного настроювання. Якщо використовуються тільки частини С1 хромосом, отримують правила лінгвістичної семантики, які можна пояснити в тому числі й словесно. У випадку використання фрагмента С2 отримують правила вільної семантики, інтерпретованість яких гірша.

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

Досліди з базовою фітнес-функцією показали незадовільну роботу її точнісних складових: кращим значенням фітнес-функції може відповідати гірше значення прогнозу. Як головну точнісну складової запропоновано використовувати так звану J-міру:

, (4)

де - кількість записів даних з навчальної вибірки (НВ), що відібрані частиною-умовою;

- кількість записів даних з НВ, що відібрані частиною-висновком;

- кількість записів даних з НВ, що відібрані повним правилом;

- загальна кількість даних у НВ.

У модифікованій фітнес-функції, крім J-міри, додані складові, що відповідають за малу кількість відібраних негативних прикладів і за несхожість правил між собою. Дослідження такої фітнес-функції в розділі 4, показали зростання точності прогнозування на 7.9-21.7%.

Одним з напрямів для поліпшення точності є модифікація лінгвістичної бази даних. Лінгвістична база даних (ЛБД) містить семантику термів лінгвістичних змінних, з яких відбувається генерація лінгвістичних правил. Крім лінгвістичних змінних, ЛБД містить дозволені інтервали для зміни функцій належності. Можливі напрями модифікації ЛБД такого виду:

· зміна кількості термів;

· зміна виду функцій належності;

· настроювання параметрів функцій належності.

Зміна кількості термів доцільна в інтервалі [3…11] і є переборною задачею.

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

Настроювання параметрів ЛБД повинно проходити на довільній функції належності, за яку обрано узагальнену дзвіноподібну функцію

, (5)

яка залежить від трьох параметрів, що вимагають оптимізації. Для оптимізації було використано еволюційну стратегію, оскільки величина прогнозу є стохастичною і вимагає кількаразової оцінки. Були отримані субоптимальні параметри (amin, a, amax, bmin, b, bmax, cmin, c, cmax), що використовуються в ЛБД. Створена лінгвістична база даних із оптимізованими параметрами показала значне збільшення точності результату (в 12-16 разів). Однак це було отримано за рахунок значного збільшення кількості правил бази знань. Питання про доцільність такого збільшення точності повинно вирішуватися експертно.

Для прискорення роботи алгоритму виконано перебудову еволюційного алгоритму для розподіленого виконання за схемою «робітник-хазяїн». Розширено поняття ГА:

, (6)

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

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

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

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

, (7)

де _ кількість правил, залишених хромосомою з набору;

wl - заданий користувачем коефіцієнт (важливості короткості бази знань).

Для прогнозування кількості підключень при величині wl = 0.3 відбулося зростання середньоквадратичного відхилення СКВ на 2,83-4,14% при зростанні абсолютної похибки прогнозування на 0-0.37% і зменшенні кількості правил на 36.68%.

Після мультисимпліфікації й зважуванні правила піддаються додатковому настроюванню (тюнінгу) за допомогою ще одного еволюційного алгоритму з дійсним кодуванням хромосоми. Створюються мультихромосоми зі склеєних разом частин С2 правил. Уперше запропоновано використати (1+1)-еволюційну стратегію й під час тюнінгу.

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

У четвертому розділі «Програмне забезпечення інформаційної технології видобування знань, їх тестування, технічне та організаційне забезпечення» наведено створення програмного, організаційного та технічного забезпечення інформаційної технології.

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

Створено блок-схеми математичних методів алгоритму. Виділені основні компоненти комплексу та зв'язки між ними, з використанням мови моделювання UML спроектовано діаграму компонентів. Для реалізації створюваних компонентів передбачено створення об'єктів (типів і класів):

· TExample: одна точка з НВ або тестової вибірки (ТВ);

· TMemberFunc: одна (під)умова правила;

· TRule: одне правило;

· TPrimaryFuzzy: об'єкт для лінгвістичної змінної;

· TDataSet: клас для множини навчальних і тестових даних;

· TPopulation: клас для нижнього рівня ГА (популяції правил);

· TGenerGa: верхній рівень ГА створення бази знань;

· TMultiSimpGa: об'єкт, що реалізує процедури мультисимпліфікації й зважування;

· TTuningGA: об'єкт, що реалізує тюнінг правил;

· TTunRule: одне правило для зважування.

Для реалізації застосованості різноманітних ФП створені базові класи TBaseRule, TBasePrimaryFuzzy, TBaseGenerGa і класи для конкретної ФП (наприклад, TGBellRule, TGBellPrimaryFuzzy, TGbellGenerGA).

Створено ієрархію об'єктів, представлену в термінах UML діаграмою класів.

Здійснено тестування створених інструментальних засобів. Більшість досліджень проводилося на декількох наборах (в основному 4 з 6), що мають різну складність апроксимації і взятих з різних джерел. Було зроблено порівняння з результатами робіт закордонних дослідників на даних тестових наборах (11 джерел), та з результатами НМ, що використовувалися, оскільки з їх допомогою можливо легко отримати досить точний результат.

Модифікація КГА зменшує час рішення (до 90.6%) при збереженні його точності.

Дослідження модифікації фітнес-функції показало: якщо лінгвістичних можливостей алгоритму достатньо для одержання точного результату, перевага тієї або іншої фітнес-функції є досить умовною: простір для пошуку обмежено. За необхідності використання правил з вільною семантикою є помітною перевага модифікованої фітнес-функції (на 7.9-21.7%). Результати, отримані функцією тільки зі складовою p1 (поліпшення на 6.5-25.9%), нестабільні: мають більше СКВ помилок, і не завжди кращі.

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

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

Результати дослідів підтверджують ефективність уведення процедури зважування (поліпшення точності від 23 до 27.5%). Упровадження еволюційної стратегії на етапі тюнінгу дало значне збільшення ефективності (43.7-45.1%), як і для базового алгоритму.

Загальне дослідження створеного програмного забезпечення інформаційної технології показало їх ефективність: точність практично на всіх наборах досягла точності, отримуваної НМ, і перевершила більшість результатів, отриманих закордонними дослідниками.

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

· вказівку про послідовність виконання технологічних операцій;

· перерахування умов, за яких виконується та чи інша операція;

· опис самих операцій.

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

У п'ятому розділі «Апробація інформаційної технології на задачі прогнозування завантаженості обладнання зв'язку» продемонстровано апробацію створеної системи на задачі прогнозування кількості підключень до АТС.

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

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

У результаті відбору значущих факторів для довгострокового прогнозу відібрано 3 фактори з 20, для короткострокового відібрано 4 фактори з 20. Для довгострокового й короткострокового прогнозування отримані й порівняно між собою бази знань на основі лінгвістичної й вільної семантик.

Для довгострокового прогнозування основний критерій точності accuracy criterion AC правил на основі лінгвістичної семантики (АС=2.204) й правил на основі вільної семантики (АС=2.194) мають близькі значення, досягаючи оптимальної точності. Величина кількості підумов бази знань лінгвістичної семантики, що є основною складовою критерію інтерпретованості interpretability criterion IC, дорівнює 141, вільної семантики IC_free - 30*K_free (база знань лінгвістичної семантики містить 47 правил, вільної семантики - 10 правил). Питання про перевагу однієї бази знань над іншою, і про величину коефіцієнта K_free (необхідність зниження інтерпретованості для скорочення кількості правил) пропонується вирішувати експертно.

Для короткострокового прогнозування основний критерій точності AC баз знань на основі лінгвістичної (АС=2.371) і вільної (АС=1.496) семантик істотно розрізняються. Кількість же підумов баз знань для даної задачі однакова й дорівнює 60 (15 правил). Оскільки при рівності кількості підумов баз знань лінгвістичної й вільної семантик перевага надається першій (на величину K_free), що визначається експертно, то експертно має бути визначено і в цьому випадку перевагу однієї бази знань над іншою (необхідність зниження інтерпретованості для збільшення точності прогнозу).

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

Отримані точність і якість бази знань достатні для вирішення задачі прогнозування кількості підключень абонентів, визначення завантаженості обладнання АТС і використовуються для обґрунтування прийняття рішень з приводу розширення потужностей оператора електрозв'язку, (це необхідно при використанні для розширення позикових коштів).

ВИСНОВКИ

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

У процесі проведення досліджень були отримані такі основні результати:

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

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

Набув подальшого розвитку метод побудови фітнес-функцій еволюційних алгоритмів. Як основну точністну складову фітнес-функції нечіткого еволюційного алгоритму вперше використано J-міру. Це дало можливість збільшити точність прогнозування для задач, що вимагають побудови правил вільної семантики, на 7.9-21.7%.

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

Модифікація системи нечіткого висновку шляхом заміни алгоритму Мамдані на спрощений алгоритм нечіткого висновку дозволяє збільшити швидкість нечіткого висновку (у порівнянні з алгоритмом Mамдані на 41.8% для тестового набору). Це дозволило застосовувати довільну зі стандартних функцій належності, застосування яких раніше було обчислювально складнішим у зв'язку з неможливістю аналітичного й складністю чисельного інтегрування.

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

Модифіковано фітнес-функцію на етапі постпроцесингу при використанні процедури спільної мультисимпліфікації й зважування. Модифікація дозволила одержувати більш короткі, більш інтерпретовані бази знань за рахунок погіршення точності. Для величини важливості короткості бази знань wl = 0.3 відбулося зростання СКВ від 2,8 до 4,1% при зростанні похибки прогнозування максимум на 0.37% і зменшенні кількості правил на 36.7% для задачі прогнозування кількості підключень до АТС.

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

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

Зроблено впровадження створеної системи для вирішення задачі прогнозування. Результати роботи використані для розв`язання задачі прогнозування кількості підключень до АТС ВАТ «Промтелеком». Це необхідно для розрахунку окупності капіталовкладень в АТС. Отримана прогнозна модель інтерпретована, що дає можливість керівному персоналу, який не володіє спеціальними математичними знаннями, обґрунтовувати прийняття рішень при розширенні підприємства, що є необхідним при використанні позикових коштів.

Результати роботи використано у держбюджетних темах Н-3-07 (застосовані методи попередньої обробки даних, у тому числі для задач прогнозування); Д-11-04 (застосовано розроблені методи для створення еволюційного алгоритму видобування знань для задач класифікації); Д-11-07 (використано розроблені методи видобування знань у задачах прогнозування); а також у навчальному процесі кафедри «Автоматизовані системи управління» Донецького національного технічного університету.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Хмелевой С.В. Методы повышения и оценки качества обучающей выборки для задач нейросетевого прогнозирования временных рядов/ С.В. Хмелевой // Наукові праці ДонНТУ серія: обчислювальна техніка та автоматизація. Донецк: ДонНТУ. 2006. Вип. 106. С. 87-94.

Хмелевой С.В. Создание и применение базы знаний на основе аппроксимативных нечетких логических контроллеров для прогнозирования internet траффика / С.В. Хмелевой // Наукові праці ДонНТУ Серія: “Обчислювальна техніка та автоматизація”. Донецьк: ДонНТУ. 2007. Випуск 13 (121). С. 132-139.

Хмелевой С.В. Параллельная реализация эволюционного алгоритма для создания базы знаний на основе нечетких логических контроллеров / С.В. Хмелевой // Інформаційно-керуючі системи на залізничному транспорті. 2007. №4 (66). С. 120-123.

Скобцов Ю.А. Генетический подход к прогнозированию цен на подержанные автомобили / Ю.А. Скобцов, С.В. Хмелевой // Вестник Херсонского государственного технического университета. 2004. том 19. С. 212-224.

Скобцов Ю.А. Генетический поход к задачам прогнозирования / Ю.А. Скобцов, С.В. Хмелевой // Наукові праці ДонНТУ Серія: “Обчислювальна техніка та автоматизація”. Донецк: ДонНТУ. 2005. Випуск 90. С. 127-136.

Хмелевой С.В. Некоторые аспекты предварительной обработки данных в задачах нейросетевого прогнозирования и классификации/ Ю.А. Скобцов, С.В. Хмелевой, З.В. Панченко // Вестник Донецкого Национального Университета. Серия А: естественные науки. Донецк: ДонНУ. 2005. №2, Часть 2. С. 381-386.

Скобцов Ю.А. Модификация функции принадлежности аппроксимативных нечетких логических контроллеров, настраиваемых с помощью генетических алгоритмов / Ю.А. Скобцов, С.В. Хмелевой // Вестник Херсонского национального технического университета. 2007. №4 (27). С. 411-420.

Хмелевой С.В. Исследование функций принадлежности нечетких логических контроллеров применительно к задачам аппроксимации, прогнозирования и классификации / С.В. Хмелевой, Ю.А. Скобцов // Вісник Донецького Інституту автомобільного транспорту. Донецьк: ТОВ «Дончанка-інформ». 2007. №4. С. 11-19.

Хмелевой С.В. Инструментальные средства для создания базы знаний на основе нечетких продукций, настраиваемых с помощью генетических алгоритмов. / С.В. Хмелевой, Ю.А. Скобцов, А.М. Фонотов // Сучасні тенденції розвитку інформаційних технологій в науці, освіті та економіці: Матеріали ІІ Всеукраїнської науково-практичної конференції. 8-10 квітня 2008р. М. Луганськ. Луганськ: Альма-матер. 2008. С. 103-105.

Хмелевой С.В. Прогнозирование временных рядов с помощью набора нечетких правил, настраиваемых с помощью генетических алгоритмов / С.В. Хмелевой, А.М. Фонотов, А.А. Теличко // Проблемы информационных технологий. 2008. №2(004). С. 144-154.

Хмелевой С.В. Исследование зависимости эффективности работы нечетких контроллеров от распределения данных в выборке/ С.В. Хмелевой // Материалы 9 международной научно-практической конференции "Системный анализ и информационные технологии". К.: НТУУ "КПИ". 2007. С. 137.

Скобцов Ю.А. Извлечение правил с помощью генетических алгоритмов в задачах классификации / Ю.А. Скобцов, Ю.А. Хмелевой // Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий: материалы научно-практической конференции. Херсон, изд-во Херсонского морского института. 2006. Том 4. С. 204-206.

Скобцов Ю.А. Применение эволюционной стратегии и мультисимплификации при генерации нечетких управляющих правил для прогнозирования internet траффика/ Ю.А. Скобцов, С.В. Хмелевой // Материалы восьмого международного научно-практического семинара «Практика и перспективы развития партнерства в сфере высшей школы». Донецк, ДонНТУ. 2007. Том 3. С. 302-313.

Хмелевой С.В. Модификация генетического алгоритма построения базы знаний на основе нечетких продукций. / С.В. Хмелевой, Ю.А. Скобцов // VIII международная конференция «Интеллектуальный анализ информации ИАИ-2008», Киев, 14-17 мая 2008г.: сб. тр./ ред. кол.: С.В. Сирота (гл. ред.) и др. К.: Просвита. 2008г. 608 с.: ил. С. 531-540.

АНОТАЦІЯ

Хмільовий С.В. Інформаційна технологія видобування знань для прогнозування часових рядів на прикладі завантаженості обладнання зв'язку. - Рукопис.

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

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

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

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

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

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

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

Модифіковано етап постпроцесінгу, де запропоновано засоби як для поліпшення точності, так і для інтерпретуємості правил: мультисимпліфікація, зважування правил, тюнинг. Доведено ефективність введення 1+1 - еволюційної стратегії в процедуру тюнингу.

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

Проведена апробація пакету на ОАО «Промтелеком» для задачі прогнозування завантаженості обладнання і прогнозування для цього кількості підключень до АТС підприємства.

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

ABSTRACT

Khmelevoi, S.V. Informational technology of knowledge discovery for time series forecasting by the example of carrier loading. - Manuscript.

A dissertation for obtaining the academic degree of Doctor in Technical Science (Ph.D. Thesis) in specialty 05.13.06 - Information Technologies - Donetsk National University, Donetsk, 2009.

An important scientific and practical problem of knowledge discovery for time series forecasting is being considered in the Thesis.

At the preliminary data processing stage the significant factors selection is found the most important. In conditions of the factor set valuation stochasticity (the one to be obtained at the time series forecasting using neural networks) the methods known are seldom applicable and require modifying. Here proposed a compact genetic algorithm (CGA), its probabilistic vector alteration step is modified. The modification changes the value of CGA probabilistic vector depending on comparison reliability of paraphernalia subset.

The knowledge discovery process has been conducted by means of automatically evolving fuzzy rules database construction. Automatic rules construction is being made with evolutionary algorithm.

...