Mažiausių absoliučių nukrypimų algoritmas

 

1.     Užduotis

Realizuoti AR-ABS - autoregresinį mažiausių absoliučių nukrypimų algoritmą, bei pritaikyti “call” centero duomenims esantiems faile call.data ir duomenims esantiems faile armatest. Taipogi realizuoti daugelio kriterijų įvertinimą.

2.     Teorinis algoritmo modelis

AR-ABS algoritmas yra sudaromas pagal ARMA modelį. Formaliai pastarąjį modelį galima aprašyti tokiomis formulėmis:

įtakos koeficientai nustatomi minimizuojant sekančią lygtį

 

AR-ABS algoritmas

Kadangi mažiausių kvadratų metodas yra labai jautrus dideliems nukrypimams duomenyse pvz.: minimizuojant kvadratinius nuokrypius didelis nuokrypis toks kaip 100 turi tokią pat įtaką kaip ir dešimt tūkstančių mažų lygių vienetui nuokrypių. Todėl ir kilo idėja mažiausių kvadratinių nuokrypių minimizavimą pakeisti nuokrypių absoliutiniais didumais minimizavimu[1; 6].

1.      Pasinaudotojus (2.1), (2.2) lygybėmis ir eliminavus slenkančio vidurkio dalį AR - ABS modelis apibrėžiamas taip:

  1. Pasinaudojus (2.4 ) formule nuokrypius galima išreikšti sekančiomis lygybėmis:

Sekantis žingsnis yra

funkcijos minimizavimas. Šis absoliutinių nuokrypių sumos minimizavimas atskleidžia AR-ABS pavadinimo prasmę.

  1. Funkcijos f(x) minimizavimui taikomas tiesinis programavimas. Tiesinė tikslo funkcija išreiškiama formule:

Tiesinės tikslo funkcijos sprendinio leistinoji sritis sudaroma iš sekančių ribojimų - nelygybių:

 

AR-ABS modelyje įvedama dar viena modifikacija, kiekvieną koeficientą a sudaro dviejų komponenčių vektoriai (2.11). Ši modifikacija savo ruožtu sumažina modelio jautrumą dideliems nuokrypiams.

Nors teorinis modelis reikalauja, kad visi a ir u būtų > 0, programinėje realizacijoje įvedamas apribojimas > λ, kur λ = -0,000001. Tuo siekiama užtikrinti, kad Lp_solve'as ras sprendinį. Kadangi modulio sprendimas pasinaudojant tiesiniu programavimu yra šiek tiek "dirbtinis" tai dėl kompiuterio skaičiavimo paklaidų įvertinimo ir kaupimo sprendinys gali būti nerandamas. Tačiau čia iđkyla problema, kokio dydţio paklaida λ turėtų būti, kad Lp_solvas rastų sprendinį ir, kad ši paklaida neįtakotų galutinio rezultato, t.y. prognozės.

Išorinių faktorių įvertinimas

Skambučių kiekis gali priklausyti nuo eilės įvairių faktorių: šventinių laikotarpių, vykstančių renginių, katalogų išsiuntimo, varžybų ar net oro temperatūros. Tarkime prognozuojamą objektą, šiuo atveju skambučių kiekį įtakoja M faktorių, tuomet AR-ABS modelį anksčiau apibrėžtą (2.4) formule galima modifikuoti, kiekvieną a koeficientą ir w reikšmę sudarys M komponenčių vektorius:

Tai yra bendresnis AR-ABS modelis, jį galima taikyti ir prognozavimui neįvertinant išorinių faktorių priimant, kad M=1. Siekiant supaprastint programinę tokios formulės realizaciją ją galima perrašyti taip:

 

Formulėse (2.12) ir (2.13) atitikmenys:

Algoritmo testavimo teorinis modelis

Pagal tam tikrą duomenų kiekį 1,….,t-1 tiesinio programavimo pagalba randami optimalūs a koeficientai, toliau laiko momentui t vykdomas prognozavimas. Jei priimame, kad ši diena yra t-1 laiko momentas, o rytdiena bus t, nors ištiestų turime realius duomenis t laiko momentui, o gal ir ilgesniam laikotarpiui į priekį t+n, galime apskaičiuoti prognozuojamą dydį w't laiko momentui t, pagal turimą laiko eilutę 1,…t-1. Skirtumas tarp prognozuojamos ir realios reikšmės |w't - wt| - reikš apsirikimą - nuokrypį absoliutiniu didumu. Tačiau viena reikšmė negali atspindėti algoritmo efektyvumo. Siekiant įvertinti efektyvumą visi duomenys dalinami į dvi dalis 1,…..,t-1 ir t,…,t*2+1. Su pirmąja duomenų intervalo dalimi bus atliekamas a koeficientų optimizavimas, o su antruoju duomenų intervalu bus atliekami skaičiavimai pagal formulę:

D vid - gaunama vidutinė paklaida.

Kartojant aukščiau aprašytus skaičiavimus su skirtingomis p reikšmėmis randamas optimalus p - dienų kiekis, kurį atsimenant gaunama mažiausia D vid vidutinė paklaida -nuokrypis.

  

 

1.     Programinė realizacija

ABSApplet - pagrindinė klasė apjungianti grafinę vartotojo sąsają su programos logine dalimi.

ARABS klasė praplečia (extends) pagrindinę klasę ABSApplet. Talpina duomenis apibrėžiančius AR-ABS modelį, reikalingus skaičiavimams bei gaunamus rezultatus. Ši klasė atlieka duomenų struktūros vaidmenį. struktūros vaidmenį atlieka ARABS klasė.

1.      Acoef - optimizuotų a koeficientų masyvas;

2.      class0 - AR-ABS modelio parametro M reikšmė;

3.      class1 - modelio parametro p reikšmė;

4.      class2 - modelio parametro T reikšmė;

5.      class3 - apibrėžia parametro p kitimą;

6.      class4 - apibrėžia parametro T kitimą;

7.      InputsNumber - nusako parametrų kiekį;

8.      past - praeities duomenys;

9.      Residuals - apskaičiuojami nuokrypiai tarp prognozuojamų ir praeities duomenų.

Vartotojas per grafinę sąsają gali pakeisti 2), 3), 4), 5), 6) kintamųjų reikšmes, taip pat 8) reikšmes pasirinkdamas duomenų failą; 1) ir 9) reikšmės pakeičiamos skaičiavimų eigoje.

PerformCount klasė yra pagrindinės klasės ABSApplet narys. Kuriant šios klasės objektą sukuriamas ir ReadDataFile objektas. PerformCount klasės metodai skirti skaičiavimų valdymui:

·         run metodas pagal vartotojo pasirinktus parametrus, valdo skaičiavimus - vykdo duomenų failo nuskaitymą ReadDataFile klasės metodo pagalba, sukuria OutpuFrame, MyLp, Prediction klasių objektus, kviečia dviejų pastarųjų klasių metodus, vykdo dalį skaičiavimų pvz.: vidurkio radimą bei rezultatų išvedimą į grafinę vartotojo sąsają;

·         StopCount metodas identifikuoja skaičiavimų nutraukimą;

·         Finish metodas atlieka apibrėžtus veiksmus skaičiavimų nutraukimo atveju;

·         Show metodas OutpuFrame objektą (tarpinių rezultatų langą) padaro aktyvų.

MyLp klasė praplečia pagrindinę klasę ABSApplet ir yra paveldėta PerformCount klasės. Jos metodas MyLpsolve generuoja TP uždavinį pagal duomenis esančius ARABS klasėje, sukuria Lp paketo objektą ir kreipiasi į metodus, kurie sprendžia TP uždavinį.

Prediction klasė praplečia pagrindinę klasę ABSApplet ir yra paveldėta PerformCount klasės. Jos metodai atlieka prognozavimo skaičiavimus:

·         Predict metodas prognozuoja reikšmę sekančiam laiko momentui;

·         PredictMulti metodas naudodamas Predict metodą prognozuoja tam tikrą kiekį kartų;

·         Residuals metodas skaičiuoja nuokrypius prognozuojamų reikšmių nuo atitinkamu realių duomenų su kuriais buvo atliktas AR-ABS modelio a koeficientų optimizavimas.

ReadDataFile klasė yra pagrindinės klasės ABSApplet narys. Jos metodai skirti duomenų iš failų skaitymui bei perdavimui kintamiesiems ar išvedimui į grafinę vartotojo sąsają :

·         ReadData metodas nuskaito duomenis iš duomenų failo armatest, call.data ar vartotojo parinkto failo, surašo į ARABS klasės kintamuosius;

·         ReadArea metodas skirtingai nei pastarieji duomenis nuskaito ne iš failo, o iš programos lange esančio lauko į kurį galima patalpinti duomenis. Taip pat vykdo duomenų analizę bei surašymą į ARABS klasės kintamuosius;

·         SimpleRead metodas skirtas failo turinio atvaizdavimui į kurį nors grafinės vartotojo sąsajos elementą.

OutputFrame klasė skirta vartotojo grafinės sąsajos funkcionalumui papildyti. Jos objektai - langai, kurie naudojami tiek detalių rezultatų išvedimui, tiek pagalbos (Hellp..) informacijos pateikimui.

MeCanvas klasė taip pat skirta grafinės sąsajos funkcionalumui papildyti. Jos metodų pagalba atskirame lange braižomas grafikas.

Reikalavimai duomenų failui

Rekomenduojama, kad duomenų failo struktūra būtų tokia:

Pavyzdys (failo fragmentas):

Praeities duomenys
 
1607 1.2 1.2

1431 1.1 1.1

Dabarties duomenys
 
1400 1.1 1.1

1194 1.1 1.1

 

1.     Programos naudojimas

Programos išorinis interfeisas nėra apkrautas grafiniais elementais, tad norint naudotis programa neprireiks ypatingų įgūdžių, čia svarbiau bus suprasti parametrų apibrėžiančių konkretų AR-ABS modelį, bei skaičiavimų atlikimo scenarijų esmę.

            Tik paleidus šią programą jūs išvysite tokį vaizdą:

Šiame lange dar kartą primenama jog programa taikys AR-ABS modelį.

Žemiau esančiame įvedimo lauke pagal nutylėjimą nurodytas armatest duomenų failas. Pasirinkus “Use data file “ opciją duomenys bus imami iš šio failo. Norint pasirinkti kitą duomenų failą įvedimo lauke reikia surinkti norimo failo, esančio tame pačiame kataloge kaip ir programa pavadinimą. Mygtuką "Browse…." Programą leidžiant naršyklėje neveiks.

Iškilus problemoms pasirenkant failą visada galima atstatyti failą kuris buvo nurodytas tik ką paleidus programą, tereikia paspausti mygtuką "Default". Patariama rinktis armatest failą skirtą "AR-ABS" testavimui arba call.data failą skirtą prognozuoti skambučių kiekį pagal realius "Call Center" duomenis pateiktus šiame faile.

Pasirinkus “Enter data in a field“ opciją duomenys turės būti patalpinti po failo įvedimo lauku esančiame lauke.

Toliau galima pereiti į sekantį langą "Parameters" (parametrai).

Nors iš pirmo žvilgsnio šiame lange tėra tik keletas įvedimo laukų, tačiau reikia nepamiršti jog įvesti skaitmenys šiuose laukuose turės lemiamą reikšmę AR-ABS modelio sudarymui, atliekamų skaičiavimų specifikai bei gautų rezultatų pateikimo formai.

1.      "Number of factors (M) :" - įvedimo lauke galima įvesti skaičių iš intervalo [1; 32767]. Įvestas skaičius apibrėš išorinių faktorių kiekį, kurie bus įvertinami tiek sudarant konkretų AR-ABS modelį tiek prognozuojant sekančiam laiko momentui. M= 1 reikš jog atsižvelgiama tik į patį prognozuojamą didį ir jo reikšmes praeities momentais. Rekomenduojama, kad išorinių faktorių kiekis nebūtų didesnis nei duomenų failo eilutės elementų kiekis, priešingu atveju duomenys apibrėšiantys išorinius faktorius bus imami iš sekančių failo eilučių.

2.      "AR parameter (p) :" - įvedimo lauke galima įvesti skaičių iš intervalo [0;32767], jis apibrėžia laiko momentų į praeitį kiekį, kuriuos mes atsimename.

3.      "Number of data entrees (T):" - įvedimo lauke galima įvesti skaičių iš intervalo [1;32767]. Įvesta reikšmė apibrėš tariamai turimų duomenų kiekį. Duomenų kiekis (T) turi būti didesnis už antrajame lauke įvestą dydį.

4.      "Indicator for one p evaluation (0), increasing p(1)" - įvedimo lauke gali būti įvesta reikšmė 0 arba 1.

"0" - reikš jog skaičiavimai bus atlikti vieną kartą su pasirinkta p reikšme.

"1" - reikš jog skaičiavimai bus atlikti p kartų, pirmą kartą p=1, antrą p=2 ir t.t. Bus rastas optimalus p parametras, tai yra toks su kuriuo gaunami mažiausi nuokrypai prognozuojamų dydžių nuo realių.

5.      "Indicator for one step evaluation (0), multistep (1)" - šiame įvedimo lauke taip pat gali būti įvestas tik 0 arba 1.

"0" - reikš jog prognozuosim tik vienam sekančiam laiko momentui T+1.

"1" - reikš jog prognozuosim tokiam pat kiekiui laiko momentų į ateitį kokia buvo duomenų imtis T, t.y prognozuosim T+1, T+2, T+3 …T+T laiko momentams. Bus rastas vidutinis nuokrypis absoliutiniu didumu prie tam tikro parametro p.

Programa vykdo griežtą šių parametrų įvedimo kontrolę, neteisingai įvesta reikšmė yra atstatoma į paskutinę teisingą. Apie neteisingai įvestas reikšmes praneša sekančios žinutės:              

Langas "Calculation" pavaizduotas sekančiame paveikslėlyje.

 

·         Paspaudus mygtuką "Calculate" vykdomi skaičiavimai;

·         Mygtuku "Stop" skaičiavimai nutraukiami. Skaičiavimai nutraukiami baigus loginį skaičiavimų vienetą, o ne iš karto.

·         Paspaudus mygtuką "Graphic" - atskirame lange bus pateiktas skaičiavimo rezultatų grafikas.

·         Paspaudus mygtuką "Data" lange bus išvestas visas pasirinkto duomenų failo turinys. Pasinaudojus šia opcija galima peržiūrėti bet kurį pasirinktą failą.

           

Šiame paveikslėlyje pavaizduota kaip pasikeičia Skaičiavimų lango vaizdas pradėjus skaičiavimus. Į langą pastoviai išvedami jau gauti skaičiavimų rezultatai, o trukmę kiek dar vyks skaičiavimai apytiksliai atspindi "Progresbarr" eilutė. Aktyvus tik vienas mygtukas "Stop", juo galima sustabdyti skaičiavimus. Sustabdžius skaičiavimus vėl visi mygtukai bus aktyvūs. Gauti skaičiavimo rezultatai analizuojami taip:

"p" - atsiminimo į praeitį momentų kiekis;

"Predicted" - sekantis prognozuojamas dydis;

"Should be" - koks iš tikrųjų dydis turėtų būti;

"Residuals" - nuokrypis prognozuojamo nuo tikrojo dydžio;

"Sum of all residuals" - suma visų nuokrypių absoliutiniu didumu;

"The average of residuals" - vidutinis nuokrypis;

"The optimal p parameter:" - optimali p parametro reikšmė.

Parinkus kitokius parametrus skaičiavimo kontrolei galimi šiek tiek kitokie rezultatų pateikimo atvejai, tačiau raktiniai žodžiai išlieka tokie patys.

Pasibaigus skaičiavimams automatiškai atidaromas "Rezults…" langas.

                                           

Šiame lange pateikiami detalesni skaičiavimų rezultatai. Nekintant p ir T reikšmėms, lange pateikiamas TP uždaviniosprendimo rezultatai, a - koeficientai, nuokrypiai tiems patiems duomenims su kuriais buvo atliktas a - koeficientų optimizavimas ir galiausiai prognozavimas sekančiai dienai.

·         Mygtuku "Close" - langas uždaromas;

Paspaudus "Calculation" lange esantį mygtuką "Graphic" (mygtukas bus aktyvus jei "Parameters" lange "Indicator for one p evaluation (0), increasing p(1)" įvedimo lauke buvo įvesta reikšmė -1) lange "Residuals graphic" bus pateiktas grafinis nuokrypio priklausomybės nuo parametro p atvaizdavimas.

   

Iškilus problemų naudojantis programa ar pamiršus esančių objektų (mygtukų, įvedimo laukų ir kt.) paskirtį galima iškviesti pagalbos langą "HELP Window…". Paspaudus dešinį pelės klavišą bet kuriame iš trijų pagrindinių langų ("Model", "Parameters", "Calculation") atsiranda mygtukas "Help..", jį paspaudus atsidaro "HELP Window…" langas.

 

 

 

AR-ABS modelio tyrimas

Modelio tyrimui buvo atliktas su armatest duomenų faile esančiais duomenimis. Atliekamam tyrimui pasirinktas imties dydis T=60.

Čia pateiktame esančiame grafike atvaizduotas realių duomenų bei prognozės (kai p=25) kitimas laike.

Optimalus AR-ABS modelio parametras p

Svarbiausias tyrimo aspektas yra AR-ABS modelio optimalaus p parametro radimas. Siekiant įvertinti šį parametrą kuo tiksliau neužtenka prognozuoti tik sekančiam laiko momentui, todėl naudojamos dvi duomenų imtys: pagal pirmąją optimizuojami a koeficientai, o su antros imties duomenimis atliekami prognozavimai, bei nuokrypių skaičiavimai.

 

Nuokrypio priklausomybė nuo parametro p

Kaip matyti pateiktame grafike optimalus duomenų atsiminimo kiekis p=25, tuomet gaunama bendra imties paklaida - 0,449 vidutinis absoliutinis nuokrypis (paklaida) - 0,4542 kai vidutinė imties reikšmė lygi 53,727. Procentinėje išraiškoje nuokrypis sudaro 0,845% vidutinės reikšmės.

Duomenų imties įvertinimas

Sunku vienareikšmiškai įvertinti optimalaus parametro p priklausomybę nuo duomenų imties.

T

Popt

e vid(p)

e min(p)

40

20

0,448

0,417

50

26

0,423

0,424

60

25

0,454

0,449

70

25

0,509

0,505

80

4

0,500

0,495

Pagal lentelėje pateiktus duomenis galima teigti, jog šiems duomenims optimalus parametras p svyruoja apie 25 (su kitais duomenimis jis bus kitoks). Didinat imtį T didėja tiek vidutinis nuokrypis tiek nuokrypis prie konkrečios optimalios p reikšmės, to būtų galima išvengti nekeičiant tos duomenų imties su kuria atliekamas prognozavimas, o didinant tik tą su kuria vykdomas a koeficientų optimizavimas.

Koeficientų įtaka prognozuojamoms reikšmėms

Didžiausią svorį turi pirmasis a koeficientas. Prognozuojant laiko momentui T+1 =61 didžiausią svorį turės koeficientas prie reikmės laiko momentui T=60, tai reiškia jog prognozuojant rytdienai mums bus labai svarbu kas buvo šiandien.

Koeficientų a įtaka prognozei

Įdomus yra prognozavimas tai pačiai duomenų imčiai kuri buvo panaudota optimizuojant AR-ABS modelio koeficientus įsimenant skirtingą laiko momentų kiekį. Skaičiuojant nuokrypį tarp prognozuojamų reikšmių ir imties duomenų tarsi patikrinamas rastų koeficientų efektyvumas. Pastebėta jog didinant parametrą p - nuokrypis mažėja beveik tiesiškai ( žiūr. Priedas 2).

Nuokrypių su neigiamu ženklu kiekis apylygis teigiamų kiekiui, tad AR-ABS modelis neturi tendencijos prognozuoti tik didesnes ar mažesnes reikšmes nei realios.

 

Tyrimas atliktas programa naudojančia lp_solver 2.0 C versija arabs_win.zip

Realizuojant programą pasinaudota Michael Berkelaar algoritmu lp_solver 2.0 bei jo Java kalbos realizacija. Jos aprašymas.

Darba atliko Janina Prokopčikaite. Janina.Prokopcikaite@vaidila.vdu.lt