Resumen de Contributions to time series data mining departing from the problem of road travel time modeling
Usue Mori Carrascal 
Bidaiarientzako Informazio Sistema Aurreratuak (BISA) errepideetan sensoreenbidez bildutako datuak jaso, prozesatu eta jakitera ematen dituzte,erabiltzailei haien bidaietan lagunduz eta ibilbidea hasi baino lehen eta bideanhartu beharreko erabakiak erraztuz [5]. Helburu honetarako, BISA sistemektrafiko ereduak beharrezkoak dituzte, bidaiarientzat baliagarriak izandaitezkeen trafiko aldagaiak deskribatu, simulatu eta iragartzeko balio duelako.Zehazki, kontutan hartu daitezkeen trafiko aldagai guztietatik (fluxua,errepidearen okupazioa, abiadurak, etab.) bidai denbora da erabiltzaileentzatintuitiboena eta ulerterrazena den aldagaia eta, beraz, BISA sistemetan garrantziberezia hartzen duena [6]. Bidai denbora, aurrez zehaztutako puntubatetik bestera joateko ibilgailu batek behar duen denborari deritzo.Bidai denboren eredugintzan bi problema nagusi bereizten dira: estimazioaeta iragarpena. Nahiz eta literaturan batzuetan bi kontzeptu hauek baliokidetzatjo, berez, bi problema bereizi dira, ezaugarri eta helburu ezberdinekin,eta teknika ezberdinak eskatzen dituztenak.Alde batetik, bidai denboren estimazioaren helburua iada amaitutakobidaietan ibilgailuak bataz beste zenbat denbora igaro duten kalkulatzeada. Horretarako, ibilbidean zehar jasotako trafikoari buruzko informazioaedo/eta bestelako datuak (eguraldia, egutegiko informazioa, etab.) erabildaitezke [1]. Estimazio metodo ezberdinak eskuragarri dauden datu motaeta kantitatearen araberara sailka daitezke eta, a posteriori motako balorazioakegiteko balio dute. Bestalde, bidai denboren iragarpena, orainean edoetorkizunean hasiko diren bidaien denborak kalkulatzean datza. Honetarako,iragarpena egiten den momentuan jasotako eta iraganeko trafikoari buruzkodatuak eta testuinguruko informazioa erabiltzen da [8].Ibilgailu kopuru eta auto-ilaren ugaritzeen ondorioz, bidai denboren estimazioeta predikzio onak lortzea geroz eta beharrezkoagoa da, trafikoarenkudeaketa egokia ahalbidetzen duelako. Hau ikusirik, azken urteetan eredumota ezberdin andana proposatu eta argitaratu dira. Nolanahi ere, literaturarenberrikuspen eta analisi sakon bat egin dugu tesi honen lehenengoatalean. Bertan, ondorioztatu ahal izan dugu proposatutako eredu guztiakez direla egokiak errepide sare, trafiko egoera eta datu mota guztiekin erabiltzeko.Izan ere, atera dugun ondorio nabariena, argitaratutako eredu askokez dituztela BISA sistemen eskakizun praktikoak betetzen, da. Lehenik etabehin, eredu asko errepide zati txikietan soilik aplika daitezke, eta ez dagoargi errepide sare guztira nola hedatu daitezkeen. Bestalde, eredu gehienekdatu mota bakarra erabiltzen dute eta errealitatean ohikoa da datu mota batekinbaina gehiagorekin lan egin behar izatea. Azkenik, pilaketa ez-ohikoenaurrean malgutasun mugatua izatea ere desabantaila nabari eta ohikoa da.Hau honela, eredu konbinatu edo hibridoak proposamen hauetatik guztietatiketorkizun handiena dutenak direla dirudi, patroi ezberdinetara moldatzekogaitasuna dutelako, eta eredu eta datu mota ezberdinak nahastekoaukera ematen dutelako.Tesi honetan, bidai denborak iragartzeko eredu hibrido edo konbinatuakhartuko ditugu abiapuntutzat. Zehazki, hasieran datuak antzekotasunarenarabera multzokatzen dituenetan jarriko dugu arreta. Metodo hauek, datuakmultzokatu ondoren, multzo bakoitzari bidai denborak iragartzeko eredu ezberdinbat aplikatzen diote, zehatzagoa eta patroi espezifiko horrentzat espresukieraikia.Eredu talde honen kasu berezi bat, datuen multzokatzea denbora serieentaldekatzearen bitartez egiten duena da. Denbora serieen taldekatzea (clustering-a ingelesez) datu mehatzaritzako gainbegiratu gabeko ataza bat da, nonhelburua, denbora serie multzo, edo beste era batera esanda, denbora seriedatu base bat emanik, serie hauek talde homogeneoetan banatzea den [3]. Xedea,beraz, talde bereko serieen antzekotasuna ahalik eta handiena izatea etaaldiz, talde ezberdinetako serieak ahalik eta desberdinenak izatea da. Trafikodatuetan eta bidai denboretan, portaera ezberdinetako egunak aurkitzea osoohikoa da (adib. asteguna eta asteburuak). Hau honela, egun osoan zeharjasotako bidai denborez osatutako serie bat izanik, metodo mota honek lehenik,dagokion egun mota identifikatuko luke eta ondoren iragarpenak egunmota horretarako bereziki eraikitako eredu batekin lortuko lituzke.Denbora serieen clustering-an oinarritutako eredu mota hau ez da ia inoizerabili literaturan eta, ondorioz, bere onurak eta desabantailak ez dira ondoaztertu orain arte. Honegatik, tesi honen bigarren kapituluan, eredugintzaprozeduaren hasieran egun mota ezberdinak identifikatzea bidai denboreniragarpenak lortzeko lagungarria ote den aztertu dugu, emaitza positiboaklortuz. Hala ere, praktikan, honelako eredu konbinatuak eraikitzeak eta erabiltzeakzailtasun bat baino gehiago dakartza. Tesi honetan bi arazo nagusietanjarriko dugu arreta eta hauentzat soluzio bana proposatzea izango duguhelburu.Hasteko, denbora serieak multzokatzeko, erabaki ez tribial batzuk hartubehar dira, adibidez distantzia funtzio egoki bat aukeratzea. Literaturanbehin baino gehiagotan erakutsi da erabaki hau oso garrantzitsua dela etaasko baldintzatzen dituela lortuko diren emaitzak [7]. Trafikoko kasuan ere,hau honela dela demostratu dugu. Baina distantzia baten aukeraketa ez dabatere erraza. Azken urteotan hamaika distantzia ezberdin proposatu dituikerlari komunitateak denbora serieekin lan egiteko eta, dirudienez, datu basebakoitzaren ezaugarrien arabera, bat ala bestea izaten dela egokiena [3, 7].Guk dakigula, ez dago metodologia formalik erabiltzaileei aukeraketa hauegiten laguntzen dionik, ez batik bat denbora serieen clustering-aren testuinguruan.Metodologia ohikoena distantzia sorta bat probatzea eta lortutakoemaitzen arabera bat aukeratzea da. Zoritxarrez, distantzia batzuen kalkuluakonputazionalki oso garestia da, eta beraz, estrategia hau ez da batereeraginkorra praktikan.Ataza hau simplifikatzeko asmoarekin, tesiko hirugarren kapituluan etiketaanitzeko sailkatzaile bat (ingelesez multi-label classifier ) proposatzen dugudenbora serieen datu base bat multzokatzeko, distantzia egokiena modu automatikoanaukeratzen duena. Sailkatzaile hau eraikitzeko, hasteko, denboraserie datu base baten alderdi batzuk deskribatzeko ezaugarri sorta bat definitudugu. Besteak beste, datuetan dagoen zarata maila, autokorrelazio maila,serie atipikoen kopurua, periodizitatea eta beste hainbat ezaugarri neurtu etakuantifikatzeko metodoak proposatu ditugu. Ezaugarri hauek sailkatzaileakbehar duen input informazioa edo, bestela esanda, sailkatzailearen menpekoaldagaiak izango dira. Emaitza gisa, sailkatzaileak datu base batentzategokienak diren distantziak itzuliko dizkigu, kandidatu sorta batetik, noski.Sailkatzaile honen baliagarritasuna egiaztatzeko, esperimentu sorta zabalbat bideratu dugu, bai lan honetarako bereziki sortutako datu base sintetikoekineta bai UCR artxiboko [4] benetako datuak erabiliz. Lortutako emaitzapositiboak argi uzten dute proposatutako sailkatzaileak denbora serie batmultzokatzeko distantzia funtzio baten aukeraketa errazteko balio duela.Ekarpen hau azalduta, berriz bidai denboren iragarpenerako eredu kon-binatuetara itzuli eta bigarren problema bat identifikatzen dugu, tesiko bigarrenekarpen nagusira eramango gaituena. Gogoratu eredu konbinatu hauekhasiera batean datuak multzokatzen dituztela, clustering algoritmoak erabiliz.Talde bakoitzak patroi edo trafiko portaera ezberdin bat adieraziko du.Ondoren, talde bakoitzean iragarpenak egiteko, iragarpen eredu ezberdin bateraikiko dugu, soilik multzo horretako datu historikoak erabiliz. Gure kasuan,denbora serieen clustering-a aplikatu dugu eta beraz, egun mota ezberdinaklortuko ditugu. Ondoren, iragarpen berriak egin nahi ezkero, egun berri bathasten denean, zein multzokoa den asmatu beharko dugu, erabili behar duguneredua aukeratzeko.Ohartu, iragarpenak egiteko garaian, ez dugula egun osoko daturik izangoeskuragarri. Adibidez, goizeko hamarretan, eguerdiko hamabietan (2 ordugeroago) puntu batetik bestera joateko beharko dugun denbora iragarri nahibadugu, soilik egun horretan hamarrak arte jasotako informazioa izango dugueskuragarri, informazio historikoarekin batera, noski. Egoera honetan, egunhorretako informazio partzialarekin, seriearen lehen zatiarekin soilik, erabakibehar dugu zein multzotakoa den. Noski, ordurarte jasotako informazioa ezbada nahikoa adierazgarria, kalterako izan daiteke multzo eta eredu zehatzbat aukeratzea, eta ziurrenik hobe izango da eredu orokorrago bat erabiltzea,datu historiko guztiekin eraikia. Finean, egun berriak ahal bezain prontomultzo batera esleitu nahi ditugu, baina esleipen hauetan ahal bezain erroregutxien egin nahi dugu.Logikoa da pentsatzea esleipenak geroz eta lehenago eginez akatsak egitekoaukera handiagoa dela. Hau honela, helburua esleipenak ahal bezain azkaregitea da, baina zehaztasun maila onargarri bat bermatuz. Denbora serieenmehatzaritzan problema honi denbora serieen sailkapen goiztiarra (ingelesezearly classification of time series) deritzo [10].Denbora serieen sailkapena (ingelesez time series classification) [9, 10] datumehatzaritzako gainbegiratutako problema aski ezaguna da non, denboraserie multzo bat eta haietako bakoitzaren klasea jakinik, helburua sailkatzailebat eraikitzea den, serie berrien klaseak iragartzeko gai dena.Denbora serieen sailkapenaren azpi-problema gisa, sailkapen goiztiarra,denboran zehar iristen den datu zerrenda bat ahalik eta lasterren klase zehatzbatean sailkatzeko nahia edo beharra dagoenean agertzen da [10]. Adibide gisa,informatika medikoan, gaixoaren datu klinikoak denboran zehar monitorizatueta jasotzen dira, eta gaixotasun batzuen detekzio goiztiarra erabakigarriada pazientearen egoeran. Esaterako, arterien buxadura, fotopletismografia(PPG) serieen bidez detektatzen da errazen [2], baina diagnosian segunduhamarren baten atzerapenak, guztiz ondorio ezberdinak ekar ditzake.Honela, tesiaren 4. kapituluan, denbora serieen datu mehatzaritzari bigarrenekarpen garrantzitsu bezala, ECDIRE (Early Classification frameworkfor time series based on class DIscriminativeness and REliability ofpredictions) izeneko denbora serieen sailkatzaile goiztiarra aurkeztu dugu.Sailkatzaile hau eraikitzeko, entrenamendu fasean, metodoak klase bakoitzaanalizatzen du eta beste klaseengandik noiztik aurrera ezberdindu daitekeenkalkulatzen du, aurrez ezarritako zehaztasun maila bat mantenduz,noski. Zehaztasun maila hau erabiltzaileak finkatuko du haren interesen arabera.Entrenamentu fase honetan lortutako informazioak sailkapenak noizegin zehaztuko digu eta, beraz, serieak goizegi esleitzea saihesten lagundukodu. Bestalde, ECDIRE metodoak sailkatzaile probabilistikoak erabiltzen ditu,eta sailkatzaile mota hauengandik lortutako a-posteriori probabilitateak,lortutako sailkapenen zehaztasuna beste era batean kontrolatzen lagundukodigu.ECDIRE metodoa UCR artxiboko 45 datu baseei aplikatu diogu, literaturanorain arte lortutako emaitzak hobetuz. Bestalde, kasu erreal bateanmetodoaren aplikazioa nolakoa izango zen erakusteko, kantuen bidezko txoriendetekzio eta identifikazio problema baterako sortutako datu base batekinere burutu ditugu esperimentuak, emaitza egokiak lortuz.Azkenik, berriro ere bidai denboren iragarpenera itzuli gara eta aurrekobi ekarpenak problema honi aplikatu dizkiogu. Lortutako emaitzetatik,problema zehatz honetarako, proposatutako bi metodoetan egin beharrekomoldaketa batzuk identifikatu ditugu. Hasteko, distantzia aukeratzeaz gain,hauen parametroak ere aukeratu behar dira. Hau egiteko silhouette bezalakoindizeak erabili ditugu, baina argitzeke dago ea metodo hau ataza honetarakoonena den. Bestalde, datuen garbiketa eta aurre-prozesatze sakon bat beharrezkoadela ere ikusi dugu, serie atipikoak eta zaratak clustering soluzioetaneragin handia baitaukate. Azkenik, gure esperimentuak iragarpen eredu historikosimpleetan oinarritu ditugu. Eredu simple hauek ordu berdinean jasotakobidai denboren batez bestekoa kalkulatuz egiten dituzte iragarpenak,eta eredu konplexuagoak erabiltzea aukera interesgarria izan daiteke.Laburbilduz, tesi honetan bidai denboren eredugintzaren literaturarenanalisi batetik hasi gara eta, bertatik abiatuta, denbora serieen mehatzaritzaribi ekarpen egin dizkiogu: lehena, denbora serie multzo bat taldekatzekodistantzia automatikoki aukeratzeko metodo baten diseinua, eta bigarrena,sailkatzaile probabilistikoetan oinarritutako denbora serieen sailkatzaile goiztiarbat. Azkenik, berriro ere bidai denboren eredugintzaren problemara itzuligara eta aurreko bi ekarpenak testuinguru honetan aplikatuko ditugu, etorkizunerakoikerketa ildo berriak zabalduz.
