UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO Finančna matematika – 2. stopnja
Teja Rupnik
NAPOVED ŠIRJENJA GRIPE Z UPORABO ALGORITMOV PODATKOVNEGA RUDARJENJA
Magistrsko delo
Mentorica: prof. dr. Marjetka Knez
Zahvala
Svoji mentorici prof. dr. Marjetki Knez se zahvaljujem za strokovno pomoč, nasvete in čas, ki mi ga je naklonila.
Najlepša hvala mojim staršem za vso pomoč, spodbudo in zaupanje skozi celoten študij. Hvala, da verjameta vame!
Hvala moji sestri Sandri, ker mi vedno stojiš ob strani in mi pomagaš skozi življenje.
Kazalo
1. Uvod 1
2. Pregled literature 2
3. Gripa 3
4. Podatki 5
4.1. CDC 6
4.2. Vreme 9
4.3. Twitter 12
4.4. Google Trends 15
4.5. Končna podatkovna baza 17
5. Metode 18
5.1. Standardna napoved 18
5.2. Tekoča napoved 18
6. Model 20
6.1. LASSO 20
6.2. LASSO: standardna napoved 30
6.3. LASSO: tekoča napoved 35
6.4. Naključni gozd 37
6.5. Naključni gozd: standardna napoved 46
6.6. Naključni gozd: tekoča napoved 49
6.7. Primerjava modelov 50
7. Omejitve in nadaljnje študije 51
8. Zaključek 52
Slovar strokovnih izrazov 53
Literatura 54
Program dela
Razvoj in uporaba algoritmov za strojno učenje in analizo podatkov je v zadnjih de- setletjih v velikem porastu. Eden od pomembnih problemov, pri katerem se izkažejo ti algoritmi kot zelo uporabni, je napoved širjenja sezonske gripe. V magistrskem delu predstavite več različnih modelov, ki naj vključujejo zgodovinske in vremenske podatke kot tudi podatke, ki jih lahko pridobimo iz socialnih omrežij (npr. Twitter) in iskalnega omrežja Google.
Osnovna literatura
[12] S. Raimi in F. Ren, Flu trend prediction in the world of big data, Big Data Analytics 452 (2016).
[8] N. Gauraha,Introduction to the LASSO, Resonance23 (2018), strani 439-464.
[3] L. Breiman, Random Forests, Machine Learning 45 (2001), strani 5-32.
Podpis mentorja:
NAPOVED ŠIRJENJA GRIPE Z UPORABO ALGORITMOV PODATKOVNEGA RUDARJENJA
Povzetek
Natančna napoved širjenja gripe lahko izdatno pripomore tako pri preventivi kot pri zajezitvi ob izbruhu. V magistrski nalogi si bomo ogledali algoritme podat- kovnega rudarjenja na primeru napovedi širjenja gripe. Predstavili bomo modela LASSO in naključni gozd ter na obeh uporabili standardno napoved in tekočo na- poved. Za napoved bomo uporabili podatke iz socialnega omrežja Twitter, podatke zbrane v spletnem brskalniku Google, vremenske podatke in zgodovinske podatke o številu pacientov okušenih z gripo. Ugotovili bomo, kako različni nabori podatkov vplivajo na napoved in kateri model nam da najboljšo napoved.
FLU SPREADING PREDICTION USING DATA MINING ALGORITHMS
Abstract
Exact flu spreading prediction can be helpfull in prevention and intervention in case of influenza outbreak. In this work we will describe algorithms of data mining on the case of flu spreading prediction. We will present two models: LASSO and random forest. For each model we will observe a regular forecast and a rolling forecast. For prediction we will use data from social network Twitter, data gathered in Google search queries, history of total number of influence patients and weather data, in- cluding temperature and humidity. We will find optimal model for flu spreading prediction and show which set of data gives the best results.
Math. Subj. Class. (2010): 62-07, 62C05, 62J07
1. Uvod
Sezonska gripa se pojavi predvsem v zimskem obdobju. To je virusna bolezen, ki prizadene respiratorni sistem v lažjih ali težjih oblikah, lahko pa povzroči celo smrt. Center za nadzor in preprečitev bolezni (angl. Center for Disease Control and Prevention, CDC) v Združenih državah Amerike je ocenil, da se je število smrti povezanih z gripo na sezono v Združenih državah Amerike povzpelo iz nizkih 3000 v sezoni 1976−1977 do visokih 49000 v sezoni 2006−2007 ([20]).
Z napovedjo širjenja gripe bi lahko izdatno pomagali k zajezitvi števila okuženih in zmanjševanju števila smrti povezanih z gripo. Napoved širjenja gripe v realnem času bi lahko pomagala pri pripravi ključnih nalog, kot so opisane v viru [5]:
• Pravočasna dobava protivirusnih zdravil in cepiv.
• Večji nadzor v javnem zdravstvu.
• Optimizacija obdobja za preventivna cepljenja.
• Pravočasna preskrba z bolnišničnimi posteljami in zdravstvenim osebjem.
Nekaj modelov za napoved širjenja gripe že poznamo in se uporabljajo vsakoletno za pripravo na sezono gripe. Dva glavna taka model sta:
(1) Model z zgodovino nivojev gripe.
(2) Google Flu Trends model.
Omenjena modela pa nista prinesla zadostnih rezultatov. Ogledali si bomo, kako bi lahko z uporabo socialnih omrežij (Google Trends in Twitter) ter podatkovnega rudarjenja napovedali izbruhe gripe.
Čeprav uporabniki socialnih omrežji vidijo socialna omrežja kot prostor za komuni- kacijo s prijatelji in znanci ali za spremljanje znanih osebnosti, so informacije, ki jih delijo na socialnih omrežjih, zelo uporabne za podatkovno analizo. V nadaljevanju bomo pokazali, da obstaja pozitivna korelacija med objavami na socialnem omrežju Twitter povezanimi z gripo in dejanskim širjenjem gripe v Združenih državah Ame- rike.
V nadaljevanju naloge bomo najprej na kratko pregledali že obstoječo literaturo na področju napovedi gripe. Potem bomo opisali, kakšno podatkovno bazo smo upora- bili, iz kje so bili podatki pridobljeni ter na kakšen način smo jih vključili v modele.
Po predstavitvi obeh modelov, LASSO in naključni gozd, ki bosta uporabljena na realnih podatkih, bomo povedali, kateri model je boljši ter rezultate primerjali z že opravljenimi raziskavami. Na koncu bomo navedli še omejitve, s katerimi smo se tekom raziskave srečali in podali morebitne predloge za nadaljnje študije.
2. Pregled literature
CDC poroča tedenske podatke o številu okuženih z gripo, zato dobimo podatke o realnem številu okuženih z enotedenskim zamikom. V preteklosti so študije poka- zale, da je dovolj uporabiti zamik časovne vrste, kar nam da zadovoljive rezultate.
Ker ima vse več ljudi dostop do interneta, je uporaba interneta in iskalne vrstice v spletnih brskalnikih postalo uporabno orodje za CDC pri predvidevanju širjenja gripe. Leta2009je Google izdal spletno orodje za nadzor izbruhov bolezni v realnem času ([4]). Pokazali so, da obstajajo zelo podobni vzorci med pogostostjo iskanja informacij o gripi na spletu in CDC tedenskimi poročili. Na ta način so pravilno predvidevali, kakšne podatke bo pokazalo CDC poročilo z enotedenskim zamikom.
Leta 2013 je Gary King podvomil v natančnost Google Flu Trends (GFT), saj je bila njihova napoved dvakrat večja od tedenskih poročil CDC dejanskega stanja [9].
Naštel je dva razloga, zakaj prihaja do razlike:
(1) Velike podatkovne baze ne morejo nadomestiti tradicionalnega zbiranja po- datkov.
(2) Napake v algoritmu. Najpomembnejša faktorja pri širjenju gripe sta tempe- ratura in vlažnost ([10]).
V istem časovnem obdobju sta avtorja članka [11] uporabila podatke iz social- nega omrežja Twitter in iskalne vrstice ter ugotovila, da se s tem napoved izboljša v primerjavi z uporabo samo CDC podatkov. Ocenjena vrednost je imela Pearsonov korelacijski koeficient z dejanskimi podatki enak 0,89.
V nalogi smo poleg CDC poročil uporabili podatke iz socialnega omrežja Twit- ter, Google Trends in zgodovino vremenskih podatkov. Poleg standardne napovedi (angl. regular-forecasting) smo uporabili tekočo napoved (angl. rolling-forecasting).
Z uporabo različnih naborov podatkov smo poiskali najboljšo metodo za napoved širjenja gripe.
3. Gripa
Gripa aliinfluencaje akutna virusna bolezen, ki prizadene dihala in se hitro širi.
Pojavi se v zimskem obdobju na severni polobli in ogroža vse prebivalstvo, najbolj starejše ljudi, bolnike s kroničnimi boleznimi in majhne otroke.
Izvor. Poznamo tri vrste virusov povzročiteljev gripe:
• Virus influence A: Povzroči epidemijo ali celo pandemijo.
• Virus influence B: Povzroči srednje velike, vendar omejene izbruhe (npr.
šole in vrtci).
• Virus influence C:Okuži zgolj posameznika.
Virus influence A ima nadaljnjo delitev na podtipe na podlagi dveh površinskih antigenov:
• Površinski antigen hemaglutin:
– H1, – H2, – H3.
• Površinski antigen nevraminida:
– N1, – N2.
Obe skupini podtipov virusa influence A povzročijo tako imenovano sezonsko gripo pri ljudeh. Občasno se pojavijo novi podtipi virusa, ki povzročijo pandemije. Ti so običajno kombinacija človeških in živalskih virusov. Za vsakoletno sezonsko gripo poskrbijo postopne spremembe in prilagajanja virusov na njihovo okolje.
Dovzetnost. Za gripo smo dovzetni vsi, potek pa je odvisen od zdravstvenega stanja, starosti, imunskega sistema in preteklosti okužb z gripo. Pri zdravih osebah okužba poteka brez simptomov, pri starejših in kroničnih bolnikih pa lahko pride do zaple- tov. V času sezonske gripe zato opazimo povečanje obolelih z gripo v bolnišnicah in povečano umrljivost.
Znaki in simptomi. Simptomi in znaki bolezni se pojavijo 1−3 dni po okužbi. Ti so:
• mrazenje,
• izčrpanost,
• visoka temperatura,
• glavobol,
• bolečine v mišicah in kosteh,
• dražeč občutek v žrelu,
• suh kašelj.
Simptomi izginejo v 2−7 dneh.
Virus poškoduje sluznico dihal in s tem omogoči prodor bakterij v pljučno tkivo.
Pri težjih primerih se lahko pojavi bakterijska pljučnica in poslabšanje osnovnih bolezni pri kroničnih bolnikih.
Prenos. Virus se prenaša preko kužnih kapljic in preko površin. Kužne kapljice na- stanejo pri kihanju, kašljanju in glasnem govorjenju ter se po zraku prenašajo en meter. Do prenosa pride ob tesnem stiku z obolelim največkrat v zaprtem pro- storu. Na površinah virus preživi več ur. Če se ga v tem času dotaknemo, ga lahko prenesemo na sluznico nosu ali ust in se tako okužimo.
Inkubacijska doba. Inkubacijska doba je čas med okužbo in prvimi znaki bolezni ter pri gripi traja 1−3dni.
Zdravljenje. Pri večini bolnikov se ne uporablja protivirusna zdravila, ampak se počaka, da bolezen sama izzveni, medtem pa si sami lajšamo simptome. V primeru visoke temperature je priporočljiva uporaba zdravil za nižanje temperature. Poleg tega pa se priporoča tudi uporaba kapljic za nos, ki olajšajo dihanje. Protivirusna zdravila se predpišejo le bolnikom, ki se zdravijo v bolnišnicah. V času simptomov je pomembno, da si redno umivamo roke, zračimo prostor in poskrbimo, da okužbe ne prenesemo na svoje bližnje.
Preventiva. Najbolj učinkovita preventivna zaščita pred gripo je cepljenje. Ceplje- nje je še posebej priporočljivo za starejše osebe, bolnike s kroničnimi obolenji, osebe s slabšim imunskim sistemom ter majhne otroke. Cepljenje se običajno izvaja jeseni pred izbruhom gripe. Ker se virusi neprestano prilagajajo in spreminjajo, se cepivo izdela vsako leto znova za viruse, za katere se predvideva, da bodo v prihajajoči sezoni prisotni.
Povzetu po viru [29].
4. Podatki
Raziskava je bila narejena na podlagi zbranih podatkov iz Združenih držav Ame- rike. Vsi podatki zajemajo območje celotnih Združenih držav Amerike in časovno obdobje od leta2009 do leta2015. Podatke med leti2009in2014smo uporabili kot učno množico ter naredili napoved za leto 2015. Napovedi smo potem primerjali z dejanskimi podatki iz leta 2015.
V raziskavo so bili vključeni podatki iz štirih virov:
(1) podatki o številu okuženih, ki jih poroča CDC, (2) podatki o vremenskih razmerah,
(3) podatki iz socialnega omrežja Twitter, (4) podatki iz Google Trends.
V tem vrstnem redu si jih bomo v nadaljevanju ogledali. Pogledali si bomo, iz kje so bili podatki pridobljeni, kakšni so in kako smo jih pretvorili za naš model. Na koncu poglavja bomo pogledali, kako smo podatke združili in jih uporabili.
Predvidevamo, da bo število okuženih skozi leto v posameznih tednih sledilo vzorcu števila okuženih v posameznih tednih iz preteklih let. Tako bo naša napoved po- kazala najvišje število okuženih v tednih, ko je bilo število okuženih najvišje tudi v učni množici. Kot vremenske podatke bomo uporabili podatke o temperaturi in vlažnosti. Predvidevamo, da bosta imela temperatura in vlažnost negativno korela- cijo s številom okuženih. Za objave na socialnem omrežju Twitter in poizvedbah v spletnem brskalniku Google pa pričakujemo pozitivno korelacijo.
4.1. CDC.
4.1.1. Vir. Podatke o številu oseb z gripo in gripi podobnimi boleznimi zbira center za nadzor in preprečitev bolezni (angl. Center for Disease Control and Prevention, CDC). Vsi podatki so dostopni na spletni strani [37].
4.1.2. Opis podatkov. CDC poroča število okuženih enkrat na teden, z začetkom tedna v nedeljo in koncem v soboto. Zbrani podatki o številu pacientov pozitivnih na gripo so razdeljeni na 10 regij znotraj Združenih držav Amerike.
Razdelitev zveznih držav v regije:
• Regija 1: Connecticut, Maine, Massachusetts, New Hampshire, Rhode Is- land in Vermont.
• Regija 2: New Jersey, New York, Puerto Rico in Deviški otoki Združenih držav.
• Regija 3: Delaware, Zvezno okrožje Kolumbija, Maryland, Pensilvanija, Virginija in Zahodnja Virginija.
• Regija 4: Alabama, Florida, Georgia, Kentucky, Mississippi, Severna Ka- rolina, Južna Karolina in Tennessee.
• Regija 5: Illinois, Indiana, Michigan, Minnesota, Ohio in Wisconsin.
• Regija 6: Arkansas, Louisiana, Nova Mehika, Oklahoma in Teksas.
• Regija 7: Iowa, Kansas, Misuri in Nebraska.
• Regija 8: Kolorado, Montana, Severna Dakota, Južna Dakota, Utah in Wyoming.
• Regija 9: Arizona, Kalifornija, Havaji in Nevada.
• Regija 10: Aljaska, Idaho, Oregon in Washington.
Na sliki 1 je prikazana delitev zveznih držav po regijah.
Slika 1. Prikaz delitve zveznih držav po regijah.
CDC nato regije klasificira z enim izmed razredov:
• Brez aktivnosti: Ni nobene laboratorijsko potrjene okužbe z gripo.
• Razpršeno: Manjše število laboratorijsko potrjenih okužb ali en laborato- rijsko potrjen izbruh gripe.
• Lokalno: Več laboratorijsko potrjenih izbruhov gripe omejenih na eno regijo.
• Regionalno: Več laboratorijsko potrjenih izbruhov gripe v vsaj dveh, ven- dar v manj kot polovici regij.
• Široka razširjenost: Laboratorijsko potrjeni izbruhi gripe v več kot polovici vseh regij.
Primer 4.1. Na sliki 2 vidimo primer tedenskega poročila z zgornjimi klasifikacijami
iz dne 4.4.2020. ♦
Slika 2. CDC tedensko poročilo iz dne 4.4.2020 ([25]).
CDC prav tako vodi evidenco okuženih po starostnih skupinah, kjer so pacienti razdeljeni v starostne skupine: 0−4let,5−24let,25−49let,50−64let in≥65let.
Nas je zanimalo natančno število okuženih, ki smo ga uporabili kot enega izmed vhodnih podatkov za napoved (število okuženih v preteklem obdobju) in kot izid v učni množici. Predvidevamo, da bomo iz podatkov o številu okuženih v enakem obdobju v preteklih letih, lahko sklepali o številu okuženih v tekočem letu ([36, 12]).
V nadaljevanju si bomo pogledali, če naše predvidevanje drži.
4.1.3. Obdelava podatkov. Podatki, ki smo jih pridobili iz spletne strani CDC, pri- kazujejo število obolelih z gripo. Ti podatki so lahko zavajajoči, saj imajo nekatere regije veliko več prebivalcev od drugih. V resnici je lahko le majhen delež popula- cije v večji regiji okužen, a bo število obolelih z gripo večje od drugih regij, kjer je skupna populacija manjša. Zato smo podatke o številu obolelih z gripo pretvorili v lažje primerljivo spremenljivko. Nova spremenljivka meri število obolelih z gripo na milijon prebivalcev. Potrebovali smo še zamik za zbrane podatke. Novi pacienti z gripo se v podatkih pojavijo v tedenskem poročilu s tedenskim zamikom. Generirali smo še drugi in tretji zamik ter zanemarili prvi zamik. Drugi in tretji zamik sta neodvisni spremenljivki v našem modelu.
Slika 3. Graf števila obolelih z gripo na milijon prebivalcev po tednih ([12]).
Na sliki 3 vidimo krivuljo prisotnosti gripe. Ker je krivulja vsako leto zelo podobna in ker je skupno število okuženih vsako leto podobno, sklepamo, da se da širjenje gripe na podlagi zgodovine podatkov zanesljivo napovedati ([12]).
4.2. Vreme.
4.2.1. Vir. Vremenske podatke smo pridobili iz spletne strani Weather Wundergro- und ([31]).
Na žalost pa iz omenjene spletne strani ni mogoče naenkrat prenesti vseh podatkov, ki jih potrebujemo, saj je na tak način možno prenesti le podatke za eno leto za en okraj. Zato smo za vsako zvezno državo izbrali le največji okraj glede na število pre- bivalcev. Podatki iz teh okrajev predstavljajo celotno zvezno državo. Tem okrajem smo dodali štirimestne kode. V nadaljevanju si bomo ogledali, kako smo podatke preuredili.
4.2.2. Opis podatkov. Na viru so zbrani naslednji vremenski podatki:
• temperatura (◦F),
• rosišče (◦F),
• vlažnost (%),
• hitrost vetra (mph),
• zračni tlak (Hg),
• padavine (in - inches).
Za vse spremenljivke razen padavin so zabeležene minimalne, maksimalne in pov- prečne dnevne vrednosti. Pri padavinah imamo zabeleženo skupno dnevno vsoto padavin.
Primer 4.2. Na sliki 4 vidimo primer vremenskih podatkov za prvih pet dni v
mesecu maju leta 2009. ♦
Slika 4. Primer vremenskih podatkov za mesec maj 2009 iz spletne strani Weather Wunderground ([39]).
V naši raziskavi smo uporabili le dve spremenljivki:
(1) povprečna temperatura (◦F), (2) povprečna vlažnost (%).
Predvidevamo, da ima spremenljivka povprečna temperatura obratno korelacijo s številom okuženih z gripo, saj so nizke temperature bolj ugodne za preživetje virusa izven gostitelja. Na preživetje virusa prav tako ugodno vpliva nizka vlažnost zraka, kar je pokazala študija CDC ([30]), zato ima tudi spremenljivka vlažnosti zraka obratno korelacijo s številom okuženih z gripo.
Tako kot podatke o številu okuženih, smo tudi vremenske podatke zbrali za obdo- bje med letoma2009in2015. Podatke za vsako zvezno državo predstavljajo podatki iz njihovih največjih okrajev ([12]).
4.2.3. Obdelava podatkov. Iz spletne strani Weather Wunderground smo dobili 540 CSV datotek, ki smo jih morali združiti v eno končno CSV datoteko. Okraje ozi- roma zvezne države smo razvrstili v 10 regij, kot smo opisali v poglavju o CDC podatkih. Spremenljivki leto in teden smo že dobili v prenesenih vremenskih podat- kih. Spremenljivki, ki nas zanimata, povprečna temperatura in povprečna vlažnost, smo združili na nivoju regije in tedna. Za vsako regijo smo za vsako leto in vsak teden vzeli podatke iz vseh zveznih držav v regiji in izračunali povprečno vrednost.
Tako kot pri CDC podatkih se teden začne z nedeljo in konča s soboto. Primer 4.3 je povzet po viru [35].
Primer 4.3. Oglejmo si primer obdelave podatkov za regijo 9, v katero spadajo zvezne države Arizona, Kalifornija, Havaji in Nevada. Najprej si poglejmo, katera so njihova največja okrožja:
• Arizona: okraj Maricopa,
• Kalifornija: okraj Los Angelesa,
• Havaji: okraj Honolulu,
• Nevada: okraj Clark.
Podatki o temperaturi in vlažnosti iz teh okrajev predstavljajo celotne zvezne države.
Iz spletne strani smo pridobili povprečne dnevne podatke, mi pa smo za vsako zvezno državo izračunali povprečne tedenske podatke in nato povprečne tedenske podatke v celotni regiji9. V primeru imamo podatke za prvi teden v letu2009, torej od nedelje 4.1.2009do sobote10.1.2009. Podatki o temperaturi so v stopinjah Fahrenheit (◦F), podatki o vlažnosti pa v procentih (%).
ned, 4.1. pon, 5.1. tor, 6.1. sre, 7.1. cet, 8.1. pet, 9.1. sob, 10.1. povprečje
temperatura: 52,8 49,5 50,0 50,8 52,8 55,5 55,5 52,4
vlažnost: 78,1 53,0 47,5 53,6 59,0 49,4 25,9 52,4
temperatura: 50,1 47,2 50,1 54,6 54,3 56,4 58,7 53,1
vlažnost: 41,2 42,8 65,9 61,4 73,2 62,8 25,5 53,3
temperatura: 75,0 74,1 72,7 74,5 73,8 72,3 72,8 73,6
vlažnost: 67,4 69,0 74,4 69,1 69,5 76,9 78,8 72,2
temperatura: 25,9 39,3 44,7 42,0 43,8 32,2 32,4 37,2
vlažnost: 58,3 57,1 62,2 65,3 53,5 58,5 54,7 58,5
54,06 59,07 skupno povprečje vlažnosti:
Arizona California
Hawaii Nevada
skupno povprečje temperature:
Slika 5. Vremenski podatki za regijo 9iz spletne strani [39].
Iz slike 5 vidimo, da je povprečna temperatura v regiji 9 v prvem tednu januarja 2009 od 4.1. do 10.1. enaka 54,06 ◦F, kar je 12,26 ◦C. Povprečna vlažnost v tem
tednu v regiji 9 je enaka 59,07%. ♦
Podobno kot v primeru 4.3 smo za regijo 9 za vsak teden izračunali povprečno vrednost obeh spremenljivk temperature in vlažnosti. Enako smo naredili s preosta- limi regijami. Tako smo dobili vremenski spremenljivki temperaturo in vlažnost na enakem nivoju, kot so CDC podatki. Ko smo imeli podatke v ustrezni obliki, smo generirali še prve tri zamike za obe spremenljivki ([12]).
Slika 6. Vremenski podatki po tednih ([12]).
Ko so bili podatki v ustrezni obliki, smo narisali grafe, da bi videli, če so krivulje v skladu z našim predvidevanjem o vplivu vremena na širjenje gripe. Grafi so prikazani na sliki 6. Rdeče krivulje na grafu predstavljajo povprečno temperaturo, modre krivulje predstavljajo povprečno vlažnost v regijah. Temperatura je očitno nižja v zimskih mesecih, ko je okužba z gripo najvišja, vendar pa tega ne vidimo tako očitno na krivuljah povprečne vlažnosti. V nadaljevanju bomo ugotovili, če so bila naša predvidevanja pravilna.
4.3. Twitter.
4.3.1. Vir. Vsi Twitter podatki, ki smo jih uporabili, so zbrani iz spletne strani Crimson Hexagon ([26]). Crimson Hexagon je podjetje, ki se ukvarja z analizo socialnih omrežij. Zbranih imajo več kot 500 bilijonov objav iz socialnih omrežij kot sta Twitter in Facebook. Podjetje posameznikom dovoljuje dostop do podatkov povezanih z določeno temo iz določenega obdobja. Predvidevamo, da ima količina objav, ki vsebujejo besede povezane z gripo, močno pozitivno korelacijo s številom okuženih z gripo ([12]).
4.3.2. Opis podatkov. Osredotočili smo se na objave iz socialnega omrežja Twitter.
Podjetje je bilo ustanovljeno leta 2006 in je do danes eno največjih spletno družab- nih omrežij. Na njem uporabniki objavljajo sporočila, ki jih imenujemo "tweets".
V raziskavi smo uporabili objave, ki so bile objavljene med leti 2009 in 2015 ter so bile povezane z gripo. Uporabili smo samo objave v angleškem jeziku iz območja Združenih držav Amerike, Puerto Rico in Deviški otoki Združenih držav. Da bi pridobili ustrezen nabor objav z besedami povezanimi z gripo, smo morali narediti poizvedbo v Crimson Hexagonu, ki jo imenujemo monitor.
Izbrali smo nabor besed, ki so povezane z gripo. Na podlagi teh besed smo poi- skali objave za raziskavo. Besede v naboru so:
(1) gripa (angl. flu),
(2) Tamiflu - zdravilo za zdravljenje gripe, (3) pljučnica (angl. pneumonia),
(4) bolniška (angl. sickday), (5) influenca (angl. influenza), (6) prašičja gripa (angl. swineflu), (7) nahod (angl. runnynose),
(8) bolečine v mišicah (angl. muscleache), (9) boleče grlo (angl. sorethroat),
(10) cepivo za gripo (angl. flushot), (11) bolečine v telesu (angl. bodyache).
Primer 4.4. Na sliki 9 vidimo primer objave na socialnem omrežju Twitter, ki
vsebuje iskano besedo "gripa" (angl. flu). ♦
Slika 7. Primer objave, ki vsebuje besedo "gripa" (angl. flu).
Izbrane besede smo pridobili iz preteklih študij, ki so pokazale, da so te besede najbolj povezane z gripo. Nekatere besede, ki smo jih prvotno želeli vključiti v na- bor iskanih besed, smo morali izključiti zaradi dvojnega pomena besede. Ena izmed teh besed je bila beseda "bolan" (angl. ill). Pojavi se v zelo pogosti besedni zvezi
"jaz bom" (angl. "I will"), ki pa ni povezana z gripo. Drug primer je še en prevod besede "bolan" (angl. sick), ki v slengu pomeni "kul", "mega" ali "noro". Podobno se zgodi z besedo "mrzlica" (angl. chills).
Izbrali smo tudi nabor besed, za katere smo objave, ki jih vsebujejo, namensko izključili. To so bile besede:
• bieber,
• RT,
• game,
• jobs,
• job,
• jordan.
Socialno omrežje Twitter omogoča poleg objav tudi deljenje že obstoječih objav.
Takšnim objavam pravimo "re-tweets" in dobijo predpono "RT". Ker smo želeli upoštevati samo prvotne objave brez ponovnih delitev, smo v nabor besed za izklju- čitev objav dodali besedo "RT". Poskusili smo ugotoviti, katere besede se pojavijo v besednih zvezah, ki za nas niso pomembne. Ugotovili smo, da pri iskanju objav, ki vsebujejo besedo "vročina" (angl. fever), dobili ogromno objav, ki se navezujejo na besedno zvezo "Bieber fever". Besedna zveza se navezuje na zveznika Justina Bieberja in ni povezana z gripo. Zato smo v nabor besed za izključitev objav dodali besedo "bieber". Na podoben način smo poiskali vse ostale besede.
4.3.3. Obdelava podatkov. Tudi Twitter podatke smo morali združiti po regijah in po tednih, kot pri CDC podatkih. Na spletni strani Crimson Hexagon obstaja funkcija, ki jo imenujemo podfilter, s pomočjo katere je mogoče podatke agregirati po tednih in regijah. Ker imamo 10 regij in iščemo objave po 11−ih ključnih besedah smo naredili 110 podfiltrov:
11 iskanih besed∗10 regij= 110 podfiltrov
V oblikovanju podfiltrov smo najprej dodali vse zvezne države iz določene regije in mu dodelili ime. Določili smo ključno besedo, po kateri smo filtrirali objave in omejili parameter vpliva avtorja objave na vrednosti med 0 in 50. S tem smo uporabili le objave običajnih uporabnikov in izločili objave televizijskih programov in časopisov.
Ko smo podfilter dokončali, smo dobili podatke o številu objav za vsako iskano besedo po regijah in tednih.
Primer 4.5. Poglejmo si primer podflitra. Izbrali smo regijo 4, v katero spadajo zvezne države: Alabama, Florida, Georgia, Kentucky, Mississippi, Severna Karolina, Južna Karolina in Tennessee. Ključna beseda v primeru je "gripa" (angl. flu). V spodnjem grafu smo prikazali število objav s ključno besedo na teden med leti 2009 in 2015.
Slika 8. Število objav z besedno "gripa" v regiji 4 ([12]).
Na sliki 8 je mogoče opaziti večje število objav v času zimskih mesecev, kar potr-
juje naša predvidevanja. ♦
Prenesli smo 110 csv datotek, ki smo jih v nadaljevanju združili v eno. Nazadnje smo generirali prve tri zamike, podobno kot v ostalih skupinah podatkov.
4.4. Google Trends.
4.4.1. Vir. Kot zadnji vir podatkov smo uporabili spletni brskalnik Google, kjer nas je zanimala pogostost iskanja podatkov o gripi. Podatki o vseh iskanjih v spletnem brskalniku Google so zbrani na spletni strani Google Trends ([28]). Predvidevamo, da je korelacija med količino iskanja informacij povezanih z gripo in številom okuže- nih z gripo podobna korelaciji števila objav povezanih z gripo na socialnem omrežju Twitter in številom okuženih z gripo, torej močno pozitivna korelacija. V nadalje- vanju si bomo ogledali, če naše predvidevanje drži.
4.4.2. Opis podatkov. Rezultati prikazani na spletni strani Google Trends so agre- girane poizvedbe v spletnem brskalniku Google. Podobno kot pri Twitter podatkih, smo v poizvedbah iskali določene besede povezane z gripo. Izbrali smo 8 ključnih besed, ki so nas zanimale. Te besede so:
(1) gripa (angl. flu),
(2) influenca (angl. influenza), (3) pljučnica (angl. pneumonia), (4) nahod (angl. runnynose), (5) boleče grlo (angl. sorethroat),
(6) Tamiflu - zdravilo za zdravljenje gripe, (7) cepivo (angl. vaccine),
(8) simptomi gripe (angl. flu symptom).
Spletna stran Google Trends ima določene omejitve, zaradi katerih nismo mogli dobiti podatkov, kot smo si želeli. Podatki, ki jih spletna stran prikazuje za določeno zvezno državo, prikazujejo količino iskanj relativno glede na količino iskanj v drugih zveznih državah. To pomeni, da ima zvezna država, v kateri je količina iskanja dolo- čene ključne besede največja, vrednost 100, preostale zvezne države imajo vrednost med 0 in 100. Vrednost 50 pomeni, da ima zvezna država polovico količine iskanj zvezne države z vrednostjo100. Poleg tega je možno hkrati prenesti podatke le za 5 zveznih držav. Odločili smo se, da bomo za vsako regijo uporabili le podatke iz zve- zne države z največ prebivalci. Največje zvezne države glede na število prebivalcev v posameznih regijah ([38]), ki smo jih uporabili, so:
• Regija 1: Massachusetts,
• Regija 2: New York,
• Regija 3: Pensilvanija,
• Regija 4: Florida,
• Regija 5: Illinois,
• Regija 6: Teksas,
• Regija 7: Misuri,
• Regija 8: Kolorado,
• Regija 9: Kalifornija,
• Regija 10: Washington.
4.4.3. Obdelava podatkov. Na spletni strani je mogoče pridobiti le relativne podatke.
Pogledamo lahko primerjavo frekvence iskanja določenega izraza znotraj ene zvezne države skozi leto. Teden, v katerem je bil iskani izraz poizveden največkrat, ima vrednost 100. Ostali tedni v letu imajo vrednost, ki predstavlja delež poizvedb v primerjavi z tednom, ko je bila količina poizvedb najvišja. Druga možnost pa je, da primerjamo zvezne države med seboj. Primerjava je narejena znotraj zahtevanega časovnega obdobja. Tista zvezna država, ki je imela v celotnem časovnem obdobju največ poizvedb, ima vrednost 100, preostale imajo vrednost, ki predstavlja delež poizvedb glede na vodilno zvezno državo. Pomanjkljivost teh analiz je, da primer- jamo število poizvedb ne glede na število prebivalstva v zvezni državi. Tako bo, na primer, lahko imela zvezna država z nižjim številom prebivalstva nižjo vrednost od zvezne države z višjim številom prebivalstva kljub temu, da ima višje število poizvedb na prebivalca.
Izbrali smo zvezno državo Massachusetts in jo uporabili kot osnovno zvezno dr- žavo, s katero smo primerjali vse ostale. Massachusetts je dobila vrednost 100, vse ostale zvezne države pa relativno vrednost glede na osnovno zvezno državo. Iz sple- tne strani smo pridobili tedenske podatke. Ločili smo podatka o tednu in letu v dve spremenljivki. Združili smo podatke o vseh iskanih besedah in nazadnje dodali še prve tri zamike.
Primer 4.6. Na sliki 9 vidimo končne podatke za regijo4 v letu 2013. ♦
Slika 9. Google Trends podatki za regijo 4 v letu 2013 ([12]).
4.5. Končna podatkovna baza. Vse opisane tipe podatkov smo združili v končno podatkovno množico, ki je za vsako regijo in vsak teden v časovnem obdobju med leti 2009 in 2015 vsebovala podatke:
• število obolelih z gripo na milijon prebivalcev,
• povprečna temperatura,
• povprečna vlažnost,
• število Twitter objav povezanih z gripo,
• število Google poizvedb povezanih z gripo.
V vseh modelih, ki jih bomo uporabili, bo odvisna spremenljivka število obolelih z gripo na milijon prebivalcev na regijo in teden. Neodvisne spremenljivke vsebujejo različne kombinacije:
• drugi in tretji zamik števila obolelih z gripo na milijon prebivalcev,
• prvi trije zamiki vremenskih spremenljivk,
• prvi trije zamiki Twitter objav,
• prvi trije zamiki Google poizvedb.
Ker imamo vse podatke agregirane za celoten teden, se ti izračunajo na koncu tedna. Imenujemo jih prvi zamik, saj predstavljajo podatke preteklega tedna. Drugi zamik predstavlja podatke za dva tedna nazaj, tretji zamik pa podatke iz treh tednov nazaj. Pri CDC podatkih bomo v učni množici uporabili le drugi in tretji zamik, prvi zamik pa bo služil kot izid testne množice.
5. Metode
Za napoved širjenja gripe v našem primeru, bomo uporabili dva modela: LASSO in naključni gozd. Obstaja več načinov, kako vključujemo podatke v analizo za napoved pričakovanih vrednosti. Mi si bomo ogledali in uporabili dve metodi:
(1) standardna napoved (angl. Regular forecasting), (2) tekoča napoved (angl. Rolling forecasting).
5.1. Standardna napoved. Pri standardni napovedi vzamemo celotno množico podatkov iz učne množice in naredimo napoved za celotno časovno obdobje, ki ga želimo predvideti.
Primer 5.1. Slika 10 ponazarja standardno napoved, kjer je bila narejena napoved na podlagi podatkov iz celotnega leta 2017 za celotno leto 2018. ♦
Slika 10. Primer uporabe standardne napovedi ([33]).
5.2. Tekoča napoved. Pri tekoči napovedi izberemo dolžino časovnega intervala, ki jo želimo uporabiti kot učno množico, na primer 12 mesecev. Nato pa za vsak mesec, ki ga želimo napovedati, vzamemo za učno množico 12 mesecev pred njim.
Za napoved januarja 2018 vzamemo celotno leto 2017, za napoved februarja 2018 vzamemo podatke od februarja 2017 do januarja 2018 in tako dalje.
Primer 5.2. Slika 11 ponazarja oceno s pomočjo tekoče napovedi. ♦
Slika 11. Primer uporabe tekoče napovedi ([33]).
Za oba modela bomo uporabili obe metodi in naredili primerjavo med dobljenimi rezultati ter povedali, katera metoda je prinesla najboljše rezultate. V nadaljevanju si bomo podrobneje ogledali LASSO model in obe metodi, ki smo ju uporabili na LASSO modelu ter model naključnega gozda z obema metodama:
(1) LASSO: standardna napoved, (2) LASSO: tekoča napoved,
(3) naključni gozd: standardna napoved, (4) naključni gozd: tekoča napoved.
6. Model 6.1. LASSO.
6.1.1. Motivacija. Oglejmo si običajni model regresije. Dane imamo podatke(xi, yi), i = 1,2, . . . , n, kjer so xi = (xi1, xi2, . . . , xip) spremenljivke in yi izid i−tega opazo- vanja. Naj bo X ∈ Rnxp matrika sestavljena iz vrstic xi in naj bo Y ∈ Rn vektor izidov. Izid sestavlja le eno vrednost, ki jo želimo oceniti, to je število okuženih.
Koeficiente regresijskega modela označimo z β = (β1, β2, . . . , βp)T. S strešico bomo označili ocene, ki jih bomo naredili. Definicija 6.1 je povzeta po viru [24].
Definicija 6.1. Naj bosta dani množici X in Y ter funkcija f : X →Y. Potem je arg min na neki podmnožiciS ⊂X definiran kot
arg min
x∈S
f(x) ={x∈S | ∀y∈S:f(y)≥f(x)}
in vrne vrednosti x, pri katerih ima funkcijaf najmanjšo vrednost.
Pri metodi najmanjših kvadratov (MNK, angl. Ordinary least squares) ocene pa- rametrov β poiščemo z minimiziranjem skupne vsote kvadratov slučajne napake:
βˆM N K = arg min
β∈Rp
1
n||Y−Xβ||22
.
Če ima matrika X polni rang in je p ≤ n, dobimo enolično rešitev tega problema preko rešitve normalnega sistema XTXβ =XTY:
βˆM N K = (XTX)−1XTY.
Pojavita se dve pomanjkljivosti, zaradi katerih rezultati študije niso zadovoljivi.
(1) Natančnost predvidevanja: Ocena na podlagi metode najmanjših kva- dratov ima pogosto nizko pristranskost in visoko varianco. Natančnost pred- videvanja lahko izboljšamo tako, da utežimo vrednosti koeficientov in po po- trebi kakšne od uteži nastavimo na0. S tem nekoliko povečamo pristranskost, vendar dobimo manjšo varianco ocene vrednosti ter s tem večjo natančnost predvidevanja ([2]).
(2) Interpretacija modela: Pri velikem številu parametrov bi radi določili podmnožico tistih, ki imajo največji vpliv.
Oceno po metodi najmanjših kvadratov lahko izboljšamo na dva načina.
(1) Izbor podmnožice spremenljivk: S tem dobimo model, ki je lažji za interpretacijo, vendar je lahko zelo variabilen. Z majhnimi spremembami podatkov lahko dobimo povsem drugačen model, kar zmanjša natančnost predvidevanja.
(2) Grebenska regresija (angl. Ridge regression): To je zvezni proces, ki uteži koeficiente, s čimer dobimo večjo stabilnost, vendar nobenemu koefici-
S kombinacijo obeh omenjenih načinov izboljšave dobimo operator najmanj- šega absolutnega krčenja in selekcijealiLASSOmetodo (angl. Least absolute shrinkage and selection operator). Metoda koeficientom doda uteži, nekaterim iz- med koeficientov pa določi vrednost0. S tem ohranimo dobre lastnosti metod izbora podmnožice spremenljivk in grebenske regresije. Definicija 6.2 je povzeta po viru [14].
Definicija 6.2. Naj bodo dani podatki (xi, yi), i= 1,2, . . . , n, kjer so
xi = (xi1, xi2, . . . , xip) spremenljivke in yi izid i−tega opazovanja. Opazovanja naj bodo med seboj neodvisna. Predpostavimo, da so xij standardizirani, torej da velja
n
X
i=1
xij
n = 0,
n
X
i=1
x2ij
n = 1 za vsak j = 1,2, . . . , p.
Označimo regresijske koeficiente z β = (β1, β2, . . . , βp)T in prosti člen v regresijski enačbi z α. Oceno po metodi LASSO definiramo kot
( ˆα,β) = arg minˆ
α∈R,β∈Rp
n X
i=1
yi−α−
p
X
j=1
βjxij
2
, (1)
p.p.
p
X
j=1
|βj| ≤γ.
Iskanje rešitve enačbe (1) je kvadratični optimizacijski problem z linearnimi po- goji. S parametromγ ≥0nadzorujemo, kakšne uteži bomo pripisali koeficientom in ga imenujemo regulacijski parameter. Naj bo y¯= n1 Pn
i=1yi povprečna vrednost spremenljivke y. Za vsak γ je rešitev za α enaka αˆ = ¯y. Po viru [14] lahko brez škode za splošnost predpostavimo, da jey¯= 0, torej lahkoαzanemarimo in problem zapišemo kot
βˆ= arg min
β∈Rp
n
X
i=1
yi−
p
X
j=1
βjxij 2
,
p.p.
p
X
j=1
|βj| ≤γ.
Ta optimizacijski problem pa lahko zapišemo s pomočjo norm kot βˆ=β(γ) = arg minˆ
β∈Rp
1
n||Y−Xβ||22
,
p.p. ||β||1 ≤γ.
Z upoštevanjem pogoja |β||1 ≤γ, lahko zapišemo βˆ=β(γ) = arg minˆ
β∈Rp
1
n||Y−Xβ||22+γ||β||1
, (2)
kjer s parametrom γ ≥ 0 nadzorujemo velikosti uteži, ki jih želimo dodati oceni.
Če je γ ≥ ||βˆM N K||1, je ocena po metodi LASSO enaka MNK oceni. Če je γ <
||βˆM N K||1, metoda LASSO zmanjša regresijske koeficiente proti 0. Več o tem v virih [8, 14, 21].
6.1.2. Notacija in ozadje. Metodi najmanjših kvadratov za iskanje optimalne rešitve kvadratičnega optimizacijskega problema bomo dodali pragovno funkcijo, da dobimo LASSO metodo. Definicija pragovne funkcije je povzeta po virih [8, 21].
Definicija 6.3. Definirajmo pragovno funkcijo, ki jo uporabimo za krčenje:
Sγ(x) =
x+γ , če x <−γ, 0 , če |x| ≤γ, x−γ , če x > γ.
−6 −4 −2 0 2 4 6
−6
−4
−2 0 2 4 6
x S1(x)
Slika 12. Primer pragovne funkcije s pragom γ = 1.
Primer 6.4. Na sliki 12 vidimo primer uporabe pragovne funkcije s pragom γ = 1.
Rdeča krivulja prikazuje graf funkcije y(x) =x, modra pa pragovno funkcijo s pra-
gom γ = 1. ♦
Definiciji 6.5 in 6.6 ter izrek 6.7 so povzeti po viru [19], kjer je zapisan tudi dokaz izreka, ki ga v tem delu izpustimo.
Definicija 6.5. Naj boV končno razsežen vektorski prostor nad obsegomO,U < V vektorski podprostor in a ∈ V. Množico A = a+U = {a+x|x ∈ U} imenujemo afin podprostorvV. MnožicaA jeafin prostor, če je afin podprostor v kakšnem vektorskem prostoru.
Definicija 6.6. Naj bostaU inV vektorska prostora nad obsegomO. PreslikavaM: U → V je semilinearna, če obstaja avtomorfizem f ∈ Aut(O), da je M aditivna in semihomogena; t.j.
• za vsakx∈U iny ∈U je M(x+y) =M(x) +M(y),
• za vsakx∈U inλ ∈ O je M(λx) = f(λ)M(x).
Izrek 6.7. Naj boV vektorski prostor nad obsegomO inA, B ⊂V afina podprostora razsežnosti dimA = dimB ≥ 2. Preslikava τ : A → B, je afina transformacija oz.
afina funkcija, ki ohranja vzporednost, natanko tedaj, ko obstajajo a, b ∈ V in obrnljiva semilinearna preslikava M, da je τ(x) = M(x−a) +b.
Definicija 6.8 je povzeta po viru [32].
Definicija 6.8. Naj bo dana funkcija f :Rn →R. Definicijsko območje funkcijef je množica
Df ={x∈Rn|f(x) je dobro definirana}.
Funkcija f je konveksna funkcija, če velja
(1) Definicijsko območje Df je konveksna množica na Rn. (2) Za vsak x1,x2 ∈ Df in λ∈(0,1)velja
f(λx1+ (1−λ)x2)≤λf(x1) + (1−λ)f(x2).
Primer 6.9. Slika 13 prikazuje primer konveksne funkcije ene spremenljivke. Kar pomeni, da graf funkcije na intervalu [x1, x2] leži pod premico, ki gre skozi točki (x1, f(x1))in(x2, f(x2)).
a x1 λx1+ (1−λ)x2 x2 b f(λx1+ (1−λ)x2)
λf(x1) + (1−λ)f(x2)
x y
Slika 13. Primer konveksne funkcije.
♦
Definiciji 6.10 in 6.11 sta povzeti po viru [8].
Definicija 6.10. Konveksni optimizacijski problem je optimizacijski problem oblike
x∈minRp
f(x),
p.p. qi(x)≤0 za vsaki= 1,2, . . . , m, hi(x) = 0 za vsaki= 1,2, . . . , r,
kjer so f in qi konveksne funkcije za vsak i = 1,2, . . . , m, hi afine funkcije za vsak i= 1,2, . . . , r ter x∈Rp.
Definicija 6.11. Naj bo dan konveksni optimizacijski problem kot v definiciji 6.10.
Njegovo pripadajočo posplošeno Lagrangevo funkcijodefiniramo kot L(x,u,v) =f(x) +
m
X
i=1
uiqi(x) +
r
X
i=1
vihi(x),
kjer so ui ≥ 0za vsak i = 1,2, . . . , m. Konstante u1, u2, . . . , um in v1, v2, . . . , vr imenujemo Lagrangevi multiplikatorji.
Naj bo dan konveksni optimizacijski problem kot v definiciji 6.10 in naj bo Df konveksna množica. Za vsak x ∈ Df, ki zadošča pogojem iz definicije 6.10, in za vsako izbiro para (u,v)∈Rm×Rr velja
f(x)≥L(x,u,v).
Rešitev Lagrangevega optimizacijskega problema poiščemo tako, da Lagrangevo funkcijo maksimiziramo glede na Lagrangeve multiplikatorje u = (u1, u2, . . . , um) in v= (v1, v2, . . . , ur):
θp(x) = max
u∈Rm, v∈Rr, ui≥0
L(x,u,v).
Nato rezultat minimiziramo glede na x:
x∈minRp u∈maxRm,
v∈Rr, ui≥0
L(x,u,v) = min
x∈Rp
θp(x).
Temu optimizacijskemu problemu pravimo primarni optimizacijski problem.
Primarnemu optimizacijskemu problemu pa lahko priredimodualni optimizacijski problem ([8], [23]). Definicija 6.12 je povzeta po viru [8].
Definicija 6.12. Za dano posplošeno Lagrangevo funkcijo L(x,u,v) definirano v 6.11, definiramo Lagrangevo dualno funkcijo kot minimum posplošene Lagran- geve funkcije glede na x∈Rp:
`(u,v) = minL(x,u,v),
Naj box∗rešitev primarnega optimizacijskega problem inf(x∗)njegova optimalna vrednost. Potem z minimiziranjem L(x,u,v) po vseh x∈Rp dobimo spodnjo mejo za f(x∗):
f(x∗)≥ min
x∈DfL(x,u,v)≥ min
x∈Rp
L(x,u,v) =`(u,v). (3)
Najboljšo spodnjo mejo dobimo, ko je Lagrangeva dualna funkcija `(u,v) ma- ksimizirana po paru (u,v). To imenujemo dualni optimizacijski problem in ga definiramo kot
u∈maxRm, v∈Rr
`(u,v),
p.p. ui ≥0 za vsaki= 1,2, . . . , m.
(4) Dualni optimizacijski problem je vedno konveksen neodvisno od tega, če je konve- ksen tudi njegov primarni optimizacijski problem. Definiciji 6.13 in trditev 6.14 sta povzeti po viru [8].
Definicija 6.13. Če je x∗ optimalna rešitev za primarni optimizacijski problem in je(u∗,v∗)optimalna rešitev pripadajočega dualnega optimizacijskega problema, po- tem po (3) neenakost
f(x∗)≥`(u∗,v∗)
vedno drži, kar imenujemo šibka dualnost. Kadar v zgornji enačbi velja enakost f(x∗) = `(u∗,v∗),
pa to imenujemo krepka dualnost.
Trditev 6.14. Če za konveksni primarni optimizacijski problem obstaja tak x∈Rp, da velja
• q1(x)<0, q2(x)<0, . . . , qm(x)<0 in
• h1(x) = 0, h2(x) = 0, . . . , hr(x) = 0,
potem krepka dualnost vedno drži. Ta pogoj imenujemo Slaterjev pogoj.
Pokazali bomo, kako s pomočjo Karush Kuhn Tucker-jevih pogojev (krajše KKT) pridemo do rešitve primarnega optimizacijskega problema. Definicije 6.15, 6.17 in 6.19 so povzete po virih [8] in [22].
Definicija 6.15. Naj bo f : C → R konveksna funkcija, C ⊂ Rp. Vektorju g =g(x)∈Rp rečemosubgradient(angl. sub-gradients) funkcije f v točki x∈C, če za vsak y∈C velja
f(y)≥f(x) +gT(y−x).
Primer 6.16. Naj bo dana funkcija f(x) = |x|. Pripadajoči subgradient je pri x>0enakg(x) = +1, prix<0enakg(x) =−1, prix= 0pa je enak kateremukoli
Definicija 6.17. Množico vseh subgradientov konveksne funkcijef v točkiximenu- jemosubdiferencial(angl. sub-differentials) funkcijef v točkix. Označimo ga kot
δf(x) = {g(x)∈Rp :g(x) je subgradient funkcijef v točkix}.
Primer 6.18. Subdiferencial funkcije f(x) = |x| v točki x = 0 je enak δf(0) =
[−1,1]. ♦
Slika 14 prikazuje funkcijo f(x) = |x| (levo) in njen subdiferencial (desno) iz primera 6.18.
−3 −2 −1 1 2 3
−3
−2
−1 1 2 3
x
|x|
−3 −2 −1 1 2 3
−3
−2
−1 1 2 3
x δf(x)
Slika 14. Funkcija f(x) = |x|in njen subdiferencial iz primera 6.18.
Definicija 6.19. Naj bodo dani primarni optimizacijski problem iz definicije 6.10, pripadajoča posplošena Lagrangeva funkcija L(x,u,v) in pripadajoč dualni opti- mizacijski problem definiran v (4). Naj bo x∗ optimalna rešitev primarnega op- timizacijskega problema ter (u∗,v∗) optimalna rešitev dualnega optimizacijskega problema. Potem Karush Kuhn Tucker-jeve pogoje definiramo kot
• Pogoj stacionarnosti (angl. stationarity condition): subdiferencial funkcije L(x,u,v) pri točki (x∗,u∗,v∗) mora vsebovati ničlo:
0∈δf(x∗) +
m
X
i=1
u∗iδqi(x∗) +
r
X
i=1
v∗iδhi(x∗).
• Komplementarna ohlapnost (angl. Complementary Slackness):
u∗iqi(x∗) = 0 za vsak i= 1,2, . . . , m.
• Pogoj izvedljivosti za primarni optimizacijski problem (angl. Primal Feasi- bility Condition):
qi(x∗)≤0za vsak i= 1,2, . . . , m inhi(x∗) = 0 za vsak i= 1,2, . . . , r.
• Pogoj izvedljivosti za dualni optimizacijski problem (angl. Dual Feasibility
S temi pogoji dobimo sistem enačb, preko katerega dobimo optimalno rešitev x∗ primarnega optimizacijskega problema.
KKT pogoji so potrebni pogoji za iskanje optimalne rešitve optimizacijskega pro- blema, vendar niso nujno zadostni. Če pa imamo konveksni optimizacijski problem, ki zadostuje Slaterjevemu pogoju 6.14, so KKT pogoji zadostni za iskanje optimalne rešitve.
6.1.3. Uporaba. Primeri 6.20, 6.21 in 6.22 so povzeti po viru [8].
Primer 6.20. Oglejmo si preprost primer uporabe LASSO metode na modelu z eno spremenljivko. Ker imamo samo eno spremenljivko, je naša matrika X sestavljena le iz enega stolpca X1 in β1 je edini regresijski koeficient. Naj bo torej p = 1 in Y = X1β1+ enačba preproste linearne regresije. Optimizacijski problem, ki nas zanima, je podan kot
min
β1∈R
1
n||Y−X1β1||22+γ|β1|
.
Predpostavimo, da je βˆ1 rešitev tega optimizacijskega problema. Potem iz prvega KKT pogoja stacionarnosti, ki pravi, da mora subdiferencial vsebovati ničlo, dobimo
−2
nXT1(Y−X1βˆ1) +γ sign( ˆβ1) = 0.
Preoblikujemo in dobimo 1
nXT1(Y−X1βˆ1) = γ
2sign( ˆβ1)
1
nXT1Y− 1
nXT1X1βˆ1 = γ
2sign( ˆβ1).
Ker je X1 po predpostavki standardizirana, je 1nXT1X1 = 1, kar implicira 1
nXT1Y−βˆ1 = γ
2sign( ˆβ1),
oziroma
βˆ1 = 1
nXT1Y− γ
2sign( ˆβ1),
kar je ekvivalentno
βˆ1 =
1
nXT1Y+γ2 , če 1nXT1Y <−γ2, 0 , če 1n|XT1Y|= γ2,
1
nXT1Y− γ2 , če 1nXT1Y > γ2.
Enako rešitev dobimo, če uporabimo pragovno funkcijoSiz definicije 6.3 s pragom
γ
2 na oceni, ki jo dobimo z metodo najmanjših kvadratov βˆM N K = n1XT1Y, kot je opisano na začetku tega poglavja:
βˆ1 =Sγ
2( ˆβM N K).
♦ Primer 6.21. Oglejmo si sedaj primer uporabe metode LASSO z več spremenljiv- kami. Videli bomo, da v splošnem LASSO ocena nima tako enostavne rešitve kot v primeru ene spremenljivke. Ponovno imamo matriko spremenljivk X ∈ Rnxp. V tem primeru označimo stolpce matrike X z x1,x2, . . . ,xp. Če ima matrika X poln stolpični rang, tedaj je XTX obrnljiva. S X−j označimo matriko X brez j−tega stolpca xj:
X−j = (x1,x2, . . . ,xj−1,xj+1, . . . ,xn).
Podobno z β−j označimo vektor parametrov brez parametra βj: β−j = (β1, β2, . . . , βj−1, βj+1, . . . , βp)T.
Naj bo βˆj rešitev za parameterβj. Iz KKT pogoja stacionarnosti dobimo
−2
nxTj(Y−X−jβ−j −βˆjxj) +γ sign( ˆβj) = 0
in dalje
−2
nxTjY+ 2
nxTjX−jβ−j+ 2
nxTjβˆjxj +γ sign( ˆβj) = 0.
Ponovno uporabimo lastnost standardizirane matrike n1xTjxj = 1 in dobimo
−2
nxTjY+ 2
nxTjX−jβ−j+ 2 ˆβj+γ sign( ˆβj) = 0.
Enačbo delimo z 2in izrazimo βˆj: βˆj = 1
nxTjY− 1
nxTjX−jβ−j −γ
2 sign( ˆβj).
Rezultat lahko preoblikujemo v βˆj = 1
nxTj(Y−X−jβ−j)− γ
2 sign( ˆβj).
Vidimo, da je rešitev β odvisna od ostalih komponent β, i6=j, zato nimamo eno-
Enostavno rešitev dobimo v primeru, ko ima matrika X ∈ Rnxp ortonormirane stolpce. Da ima matrika ortonormirane stolpce pomeni, da pri množenju s transpo- nirano matriko XT dobimo enotsko matriko:
XTX =I.
Zato lahko odstranimo člen XTjX−j, podobno kot v primeru 6.20.
Primer 6.22. Oglejmo si še uporabo LASSO metode na ortogonalnem primeru.
Naj bo X matrika velikosti n ×p. Tudi v tem primeru označimo stolpce matrike X zx1,x2, . . . ,xp. Predpostavimo, da so spremenljivke med seboj nekorelirane, da torej veljaxTi xj = 0 za vsaki6=j in 1nXTX =Ip. Naj boβˆrešitev optimizacijskega problema (2). Potem iz KKT pogoja stacionarnosti dobimo
−2
nXT(Y−X ˆβ) +γ sign(β) = 0ˆ oziroma
1
nXTY− 1
nXTX ˆβ = γ
2sign(β).ˆ Iz n1XTX=Ip sledi
1
nXTY−βˆ= γ
2sign(β).ˆ Izrazimo β,ˆ
βˆ= 1
nXTY− γ
2sign(β),ˆ kar je ekvivalentno
βˆj =
1
n(XTY)j +γ2 , če n1(XTY)j <−γ2, 0 , če n1|(XTY)j|= γ2,
1
n(XTY)j −γ2 , če n1(XTY)j > γ2, pri čemer z (XTY)j označimo j-ti element vektorja XTY.
Podobno kot v primeru 6.20, kjer smo metodo LASSO uporabili na primeru z eno spremenljivko, lahko koeficient βˆj izračunamo s pragovno funkcijo S s pragom γ2 uporabljeno na j−ti komponenti ocene po metodi najmanjših kvadratov ( ˆβM N K)j:
βˆj =Sγ
2
βˆM N K
j
=Sγ
2
1 nXTY
j
.
♦
6.2. LASSO: standardna napoved.
6.2.1. Uporaba. Kot smo že razložili, je metoda LASSO ali operator najmanjšega absolutnega krčenja in selekcij regresijska metoda, ki se uporablja tudi za izbiro spremenljivk. Spremenljivke, ki jih bomo uporabili, izberemo tako, da bo statisti- čen model čim bolj natančen. Za uporabo LASSO metode namesto klasične metode najmanjših kvadratov smo se odločili zato, da bi se izognili naslednjima težavama:
• natančnost predvidevanja,
• interpretacija modela.
6.2.2. Model. V tem poglavju si bomo ogledali uporabo LASSO modela za napoved odvisne spremenljivke "število obolelih z gripo na milijon prebivalcev na regijo" za leto 2015. Podatke med leti 2009 in 2014smo uporabili kot učno množico. Podatki iz leta 2015 pa so nam služili kot testna množica. Uporabili smo prečno preverjanje (angl. cross-validation) ([7]), kjer naredimo več delitev na učno in validacijsko mno- žico. Naredili smo torej več iteracij na zbranih podatkih, le da smo vsakič uporabili druge primere v učni in validacijski množici. Pomembno je, da se vsi primeri pojavijo v validacijski množici natanko enkrat. Primere razdelimo tako, da so validacijske množice med seboj disjunktne in skupaj sestavljajo celotno množico primerov.
Primer 6.23. Oglejmo si primer delitev pri prečnem preverjanju. Narediti želimo 10−kratno prečno preverjanje. V vsakem izmed poskusov uporabimo90% primerov za učenje in 10% za testiranje. Skozi vse poskuse so kot testni uporabljeni vsi primeri, vsak natanko enkrat. Slika 15 prikazuje primer takšne delitve primerov pri 10 poskusih in 10iteracijah, z odebeljeno so označene validacijske množice. ♦
Primeri
Iteracija 1 x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 Iteracija 2 x1,x2, x3, x4, x5, x6, x7, x8, x9, x10 Iteracija 3 x1, x2,x3, x4, x5, x6, x7, x8, x9, x10
. . . .
. . . .
Iteracija10 x1, x2, x3, x4, x5, x6, x7, x8, x9,x10
Slika 15. Primer delitve primerov pri prečnem preverjanju.
Spomnimo se ocene po metodi LASSO:
βˆ=β(γ) = minˆ
β∈Rp
1
n||Y−Xβ||22+γ||β||1
Ko se utež γ približuje vrednosti 0, se vrednost funkcije izgube našega modela pri- bližuje funkciji izgube MNK modela.
Primer 6.24. Na sliki 16 vidimo, kakšne vrednosti dobijo koeficienti v LASSO modelu v odvisnosti od parametraγ. Različne barve na grafu prikazujejo vrednosti, ki jih zavzamejo različni koeficienti v našem modelu. Os x prikazuje vrednosti parametraγ. Ko se parameterγpribližuje vrednosti0, so tudi vsi koeficienti modela
enaki 0. ♦
Slika 16. Različne barve na grafu prikazujejo različne koeficiente in kako se njihove vrednosti spreminjajo glede na parameter γ ([12]).
Kot je opisano v poglavju o LASSO modelu, bomo s to metodo nekaterim koe- ficientom pripisali vrednost 0. LASSO model s standardno napovedjo je izpustil 7 parametrov oziroma jim je določil vrednost 0. Spuščeni parametri so:
• Google Trends podatki o iskanju besede "Tamiflu" dva tedna nazaj glede na zvezno državo Massachusetts.
• Google Trends podatki o iskanju besedne zveze "simptomi gripe" dva tedna nazaj glede na zvezno državo Massachusetts.
• Število Twitter objav z besede "plučnica" en teden nazaj.
• Število Twitter objav z besedo "plučnica" tri tedne nazaj.
• Število Twitter objav z besedno zvezo "prašičja gripa" en teden nazaj.
• Število Twitter objav z besedno zvezo "cepivo za gripo" tri tedne nazaj.
• Poprečna vlažnost v regiji en teden nazaj.
Naslednji parametri so imeli zelo nizke koeficiente, torej nizko utež v modelu, a vseeno niso bili izpuščeni:
• Google Trends podatki o iskanju besede "influenca" en teden nazaj glede na zvezno državo Massachusetts.
• Google Trends podatki o iskanju besede "influenca" dva tedna nazaj glede na zvezno državo Massachusetts.
• Google Trends podatki o iskanju besede "influenca" tri tedne nazaj glede na zvezno državo Massachusetts.
Ker v učni množici nismo upoštevali podatkov iz leta 2015, je imel tudi parame- ter, ki določa 2015, vrednost 0. Ti podatki so bili uporabljeni kot testna množica podatkov, s katerimi smo primerjali dobljeno napoved s LASSO modelom.
Slika 17. Število obolelih z gripo na milijon glede na posamezno regijo (napoved in dejanska vrednost) ([12]).
Napovedi števila obolelih z gripo na milijon prebivalcev na regijo v letu 2015 so bile precej točne. Primerjavo med napovedanimi in dejanskimi vrednostmi vidimo na sliki 17. Z modro barvo so prikazane opazovane vrednosti, z rdečo barvo pa ocenjene vrednosti za vsako regijo posebej.
6.2.3. Ocena. S prečnim preverjanjem smo izboljšali naš model, ki smo ga zgradili na podatkih iz leta 2009, 2010, 2011, 2012, 2013 in 2014. Rezultati so bili zadovoljivi, v naslednjem primeru 6.25 pa si bomo ogledali primerjavo med napovedanimi in dejanskimi vrednost v regiji 1.
Primer 6.25. Na sliki 18 vidimo korelacijo med napovedanimi in dejanskimi vre- dnostmi za regijo 1. Odebeljena črta na grafu ponazarja funkcijo y =x. Bližje kot so točke na grafu funkciji y = x, bolj natančna je naša napoved. Naša ocena po metodi LASSO s standardno napovedjo je torej precej natančna in zadovoljiva. ♦
Slika 18. Primerjava ocenjenih in dejanskih vrednosti za regijo1 ([12]).
Primerjali smo še, kako dobre ocene dobimo z različnimi nabori spremenljivk.
Želeli smo ugotoviti, če podatki pridobljeni iz Twitterja, podatki Google Trends in vremenski podatki res izboljšajo napoved. Pogledali smo, kako natančna je napoved z uporabo le zgodovinskih CDC podatkov. Nato smo pogledali, kakšno napoved dobimo, če CDC podatkom dodamo en sklop podatkov (Twitter, Google Trends ali vremenski podatki). Nazadnje smo v napoved vključili vse zbrane podatke.
Primerjali smo standardni odklon. Definicija 6.26 je povzeta po viru [34]
Definicija 6.26. Oceno odvisnega regresijskega koeficientaytoznačimo zyˆt. Stan- dardni odklonoceneyˆtsT ponovitvami je izračunan zaT različnih ocen kot koren povprečne kvadratne napake:
σ = s
PT
t=1( ˆyt−yt)2
T .
