EASD - Experimental Algorithmics for Streaming Data

! ! ! ! CIplus Band 2/2016 EASD - Expe imen al Algo i hmics o S eaming Da a Thomas Ba z-Beiels ein ! ! ! ! ! ! ! ! ! EASD – Expe imen al Algo i hmics o S eaming Da a Thomas Ba z-Beiels ein SPOTSe en Lab Facul y o Compu e Science and Enginee ing Science TH K¨oln S einm¨ulle allee 1 51643 Gumme sbach, Ge many spo se en.de Ma ch 13, 2016 Abs ac This pape p oposes an expe imen al me hodology o on-line machine lea ning algo i hms, i.e., o algo i hms ha wo k on da a ha a e a ailable in a sequen ial o de . I is demons a ed how es ablished ools om expe imen al algo i hmics (EA) can be applied in he on-line o s eaming da a se ing. The massi e on-line analysis (MOA) amewo k is used o pe o m he expe imen s. Bene i s o a well-de ined epo s uc u e a e discussed. The applica ion o me hods om he EA communi y o on-line o s eaming da a is e e ed o as expe imen al algo i hmics o s eaming da a (EADS). 1 In oduc ion: Expe imen al Algo i hmics This a icle is de o ed o he ques ion “Why is an expe imen al me hodology necessa y o he analysis o on-line algo i hms?” We will men ion wo easons o mo i a e he app oach p esen ed in his pape . 1. Fi s , wi hou a sound me hodology, he e is he dange o gene a ing a bi a y esul s, i.e., esul s ha happened by chance; esul s ha a e no ep oducible; esul s ha depend on he seed o a andom numbe gene a o ; esul s ha a e s a is ically ques ionable; esul s ha a e s a is ically signi ican , bu scien i ically meaningless; esul s ha a e no gene alizable; e c. 2. Second, expe imen s a e he co ne s one o he scien i ic me hod. E en he disco e y o scien i ic highly ele an esul s is o no use, i hey emain unpublished o i hey a e published in an incomp ehensible manne . Discussion is he key ing edien o mode n science. Expe imen al algo i hmics (EA) uses empi ical me hods o analyze and unde s and he beha io o algo i hms. Me hods om expe imen al algo i hmics complemen heo e ical me hods o he analysis o algo i hms. S a is ics play a p ominen ole in EA and p o ide ools o gain a deep unde s anding o algo i hm beha io and e iciency. McGeoch (2012) desc ibes wo b anches o expe imen al algo i hmics: (EA-1) Empi ical analysis deals wi h he analysis and cha ac e iza ion o he beha io o algo i hms, and uses mos ly echniques and ools om s a is ics. (EA-2) Algo i hm design o algo i hm enginee ing is ocused on empi ical me hods o imp o ing he pe o mance o algo i hms, is based on app oaches om s a is ics, machine lea ning and op imiza ion. The s a is ical analysis o al- go i hm pa ame e s can esul in signi ican pe o mance imp o emen s. This p ocedu e is e e ed o as algo i hm uning. Expe imen al algo i hmics e ol ed o e he las h ee decades and p o ides ools o sound expe - imen al analysis o algo i hms. Main con ibu ions, which in luenced he ield o EA a e McGeoch’s hesis “Expe imen al Analysis o Algo i hms” (McGeoch,1986), he expe imen al e alua ion o sim- ula ed annealing by (Johnson e al.,1989,1991), and he a icle abou designing and epo ing compu a ional expe imen s wi h heu is ic me hods om (Ba e al.,1995). Cohen de ails ypical e o s in expe imen al esea ch, e.g., loo - and ceiling e ec s (Cohen,1995). And, Hooke ’s pape s 1 wi h he s iking i les “Needed: An empi ical science o algo i hms” and “Tes ing Heu is ics: We Ha e I All W ong” (Hooke ,1994,1996), which eally s uck a ne e. A he u n o he millennium, hese ideas eached mo e and mo e disciplines. Theo e icians ecognized ha hei me hods can bene i om expe imen al analysis and he discipline o algo i hm enginee ing was es ablished (Ca aneo and I aliano,1999). New s a is ical me hods, which had hei o igin in geos a is ics, become popula ools o he expe imen al analysis o algo i hms. San ne e al. (2003) made he e m design and analysis o compu e expe imen s (DACE) popula . Pa ame e uning me hods gained mo e and mo e a en ion in he machine lea ning (ML) and compu a ional in elligence (CI) communi ies. Eiben and Jelasi y’s “C i ical No e on Expe imen- al Resea ch Me hodology in EC” (Eiben and Jelasi y,2002) en o ced he discussion. The au ho s desc ibed hei discon en wi h he common p ac ice. They eques ed conc e e esea ch ques ions (and answe s), adequa e benchma ks, clea ly de ined pe o mance measu es, and ep oducibili y o he expe imen al indings. Ba z-Beiels ein (2003) combined classical design o expe imen me hods, ee-based me hods, and me hods om DACE o he analysis and he uning o algo i hms. This inc eased awa eness esul ed in se e al u o ials, wo kshops, and special sessions de o ed o expe - imen al esea ch in e olu iona y compu a ion. Resul s om hese e o s a e summa ized in he collec ion “Expe imen al Me hods o he Analysis o Op imiza ion Algo i hms” (Ba z-Beiels ein e al.,2010a). New so wa e ools o he expe imen al analysis and algo i hm uning we e de el- oped. The sequen ial pa ame e op imiza ion (SPO) was p oposed as (i) a me hodological ame- wo k o acili a e expe imen a ion wi h adequa e s a is ical me hods and (ii) a model-based uning echnique o de e mine imp o ed algo i hm ins ances and o in es iga e pa ame e e ec s and in e - ac ions (Ba z-Beiels ein e al.,2005). So SPO co e s bo h b anches, i.e., (EA-1) and (EA-2), o expe imen al algo i hmics as de ined by McGeoch. The idea o a sound expe imen al me hodology sp ead ou o e many sub-disciplines. Expe - imen al me hods we e e ined and specialized o many new ields, e.g., pa allel algo i hms (Ba and Hickman,1993), big da a applica ions, e.g., map educe by Ben a i (2012), mul imodal op- imiza ion (P euss,2015), o mul iobjec i e op imiza ion (Zae e e e al.,2013). Mul iobjec i e op imiza ion allows he combina ion o se e al goals, e.g., speed and accu acy. Exis ing benchma ks and s anda d es - unc ion se s we e econside ed (Whi ley e al.,1996). Two compe i ions we e es ablished in he con ex o CI: he CEC special session on pa ame e op imiza ion (Sugan han e al.,2005) and he black box op imiza ion benchma k (BBOB) compe i- ion (Hansen e al.,2009). This o e iew is by a no comple e, and se e al impo an publica ions a e missing. Howe e , i illus a es he de elopmen o an eme ging ield and i s impo ance. The s anda d app oach desc ibed so a ocuses on ela i ely small, s a ic da a se s ha can be analyzed o -line. We p opose an ex ension o EA o he ield o s eam da a, which will be e e ed o as expe imen al algo i hmics o s eaming da a (EASD). This ex ension is mo i a ed by he eno mous g ow h o da a in he las decades. The a ailabili y o da a aises he ques ion: how o ex ac in o ma ion om da a? Machine lea ning, i.e., au oma - ically ex ac in o ma ion om da a, was conside ed he solu ion o he immense inc ease o da a. His o ically, ML s a ed wi h small da a se s wi h limi ed aining se size: he en i e da a se can be s o ed in memo y. The ield o da a mining e ol ed o handle da a ha does no i in o wo king memo y: Da a mining became popula , because i p o ides ools o e y la ge, bu s a ic da a se s. Models canno be upda ed when new da a a i es. Nowadays, da a a e collec ed in nea ly e e y de ice. Senso s a e e e ywhe e—massi e, da a s eams a e ubiqui ous. Especially, indus ial p oduc ion p ocesses gene a e huge and dynamic da a. This leads o he de elopmen o he da a s eam pa adigm. Bi e e al. (2010) desc ibe co e assump ions o da a s eam p ocessing as ollows: (S-1) Vola ili y The aining examples can be b ie ly inspec ed a single ime only. (S-2) Speed The da a a i e in a high speed s eam. (S-3) Memo y Because he memo y is limi ed, da a mus be disca ded o p ocess he nex examples. (S-4) Bulk da a The o de o da a a i al is unknown. (S-5) On-line The model is upda ed inc emen ally, i.e., di ec ly when a new da a a i es. (S-6) Any ime p ope y The model can be applied a any poin be ween aining examples. 2 Inpu Requi emen R-1 Lea ning, T aining Requi emen s R-2 and R-3 Model Requi emen R-4 T aining da a Tes da a P edic ions Lea ning, T aining Model T aining da a Tes da a P edic ions Inpu Figu e 1: Le : The ba ch classi ica ion cycle. Righ : The s eam classi ica ion cycle. Do ed lines ep esen nonpe manen da a. Bo h classi ica ion cycles pa i ion he da a in o es and aining se . To keep he illus a ion simple, his spli is no shown. The igu e is based on he da a s eam classi ica ion cycle in Bi e e al. (2011). (S-7) E idence Las bu no leas : heo y is nice, bu empi ical e idence o algo i hm pe o mance is necessa y. Simila design c i e ia we e p oposed by Domingos and Hul en (2012). They add he equi emen ha a model, which is nea ly iden ical o he one ha would be gene a ed by a co esponding o dina y da a base mining algo i hm, should be p oduced. Al oge he , hese co e assump ions esul in a e y demanding e alua ion and pe o mance assessmen . We will de elop an expe imen al me hodology o on-line machine lea ning, i.e., o si ua ions in which da a becomes a ailable in a sequen ial o de . The da a is used o upda e he p edic o o u u e da a a each s ep. On-line lea ning di e s om adi ional ba ch lea ning echniques, which gene a e he p edic o by lea ning on he en i e aining da a se a once. The e ms “on-line” and “da a s eam” will be used synonymously in he ollowing. This pape is s uc u ed as ollows. Sec ion 2compa es he adi ional ba ch se ing wi h he s eam da a se ing. The gene a ion o da a s eam algo i hms is desc ibed in Sec. 3. Change and d i a e b ie ly in oduced in Sec. 4. How o assess model pe o mance is desc ibed in Sec. 5. En i onmen s o pe o ming he expe imen al analysis a e p esen ed in Sec. 6. A simple expe imen , which exempli ies he EASD app oach, is p esen ed in Sec. 7. This a icle concludes wi h a summa y in Sec. 8. 2 Ba ch Ve sus S eam Classi ica ion By compa ing he adi ional ba ch and he s eam classi ica ion, he ollowing obse a ions can be made: Bo h classi ica ion p ocedu es pa i ion he da a in o es and aining se . In con as o ba ch classi ica ion, s eam classi ica ion is a cyclic p ocess, which uses nonpe manen da a. The elemen a y s eps used in bo h se ings a e illus a ed in Fig. 1. 2.1 Ba ch Classi ica ion The ba ch classi ica ion cycle p ocesses da a as ollows: 1. Inpu The algo i hm ecei es he da a. 3 2. Lea n The algo i hm p ocesses he da a and gene a es i s own da a s uc u es (builds a model). 3. P edic The algo i hm p edic s he class o unseen da a using he es se . 2.2 S eam Classi ica ion Da a a ailabili y di e s in he s eam classi ica ion cycle. Addi ional es ic ions ha e o be consid- e ed (Bi e e al.,2011). F eely adap ed om Bi e e al. (2011), he da a s eam p ocessing can be desc ibed as ollows: 1. Inpu The algo i hm ecei es he nex da a om he s eam. A his s age o he p ocess, he ollowing equi emen has o be conside ed: (R-1) P ocess only once Da a s eam da a is accep ed as hey a i e. A e inspec ion, he da a is no a ailable any mo e. Howe e , he algo i hm i sel is allowed o se up an a chi e (memo y). Fo example, he algo i hm can s o e a ba ch o da a ha is used by adi ional, s a ic algo i hms. Due o he limi ed amoun o memo y, he algo i hm has o disca d he da a a e a ce ain ime pe iod. 2. Lea n The algo i hm p ocesses he da a and upda es i s own da a s uc u es (upda es he model). A his s age o he p ocess, he ollowing equi emen s ha e o be conside ed: (R-2) Limi ed Memo y Budge Da a s eam algo i hms allow p ocessing da a ha a e se e al imes bigge han he wo k- ing memo y. Memo y can be classi ied as memo y ha is used o s o e unning s a is ics and memo y ha is used o s o e he cu en model. (R-3) Limi ed Time Budge Run ime complexi y o he algo i hms should be linea in he amoun o da a, i.e., he numbe o examples. Real- ime p ocessing equi es ha he algo i hm p ocess he da a quickly (o e en as e ) han hey a i e. 3. P edic The algo i hm is able o ecei e he nex da a. I eques ed, i is also able o p edic he class o unseen da a. A his s age o he p ocess, he ollowing equi emen has o be conside ed: (R-4) P edic a any Poin The bes model should be gene a ed as e icien ly as possible. The model is gene a ed di ec ly in memo y by he algo i hm as i p ocesses incoming da a. 3 Gene a ing Da a S eam Algo i hms The p ocess o enabling ML algo i hms o p ocess la ge amoun o da a is called scaling (Die e ich, 1997). In da a mining, he w appe and he adap a ion app oach a e known o his ask. 3.1 W appe The maximum euse o exis ing schemes is e e ed o as he w appe app oach. The w appe app oach collec s and p e-p ocesses da a so ha adi ional ba ch lea ne s can be used o model building. Bi e e al. (2011) lis ypical implemen a ions o he w appe app oach: Chu and Zaniolo (2004) p opose a boos ing ensemble me hod, which is based on a dynamic sample-weigh assignmen scheme. They claim ha his me hod is as , makes ligh demands on memo y esou ces, and is able o adap o concep d i . Wang e al. (2010) in oduce a amewo k o mining concep -d i ing da a s eams. An ensemble o classi ica ion models, such as C4.5 (Quinlan,1993) o nai e Bayes, is ained om sequen ial chunks o he da a s eam. The classi ie s in he ensemble a e weigh ed based on hei es ima ed classi ica ion accu acy on he es da a unde he ime-e ol ing en i onmen . Thus, he ensemble app oach imp o es bo h he e iciency in lea ning he model and he accu acy in pe o ming classi ica ion. W appe app oaches su e om he ollowing di icul ies: (i) The selec ion o an app op ia e aining se sizes is p oblema ic. (ii) The aining ime canno be con olled. Only he ba ch sizes can be modi ied, which p o ides a mean o an indi ec con ol o he aining ime. 4 3.2 Adap a ion The adap a ion app oach de elops new me hods, which a e specially designed o he s eam da a analysis ask. Adap a ion comp ehends he ca e ul design o algo i hms especially designed o ul ill da a mining and ML asks on dynamic da a. Adap a ion algo i hms can implemen di ec s a egies o memo y managemen and a e usually mo e lexible han w appe app oaches. Bi e e al. (2011) lis examples o adap a ion algo i hms om he ollowing algo i hm classes: decision ees, associa- ion ules, nea es neighbo me hods, suppo ec o machines, neu al ne wo ks, and ensemble-based me hods. 4 Change and D i De ec ion Changes in he da a dis ibu ion play an impo an ole in da a s eam analysis. This mo i a ed he de elopmen o specialized echniques, e.g., change de ec ion s a egies (Lugho e and Sayed- Mouchaweh,2015). The a ge alue, which will be p edic ed by he model, is e e ed o as concep . Se e al changes o e ime may occu : A g adual concep change is e e ed o as a concep d i . A apid concep change o e ime is e e ed o as a concep shi , and a change in he da a dis ibu ion is e e ed o as a dis ibu ion o sample change. Es ablished me hods om s a is ical p ocess con ol, e.g., he cumula i e sum (CUSUM) algo- i hm, can be used o change de ec ion (Mon gome y,2008). Fu he me hods comp ehend he geome ic-mo ing-a e age (GMA) es o s a is ical hypo hesis es s. Hypo heses es s a e popula , because hey a e well-s udied and can be implemen ed easily. They compa e da a om wo s eams. The null hypo hesis H0 eads: bo h s eams come om he same dis ibu ion. Then a hypo hesis es , which is based on he di e ence o means µ1and µ2is pe o med, e.g., he Kolmogo o -Smi no (KS) es . Gama e al. (2004) de eloped a d i -de ec ion me hod, which is based on he on-line e o - a e. The aining examples a e p esen ed in sequence. New aining example a e classi ied using he ac ual model. As long as he dis ibu ion is s a iona y, he classi ica ion e o will dec ease. I a change in he dis ibu ion occu s, he e o will inc ease. The ace o he on-line e o o he algo i hm is obse ed. Fu he app oaches, e.g., based on he exponen ial-weigh ed-mo ing-a e age (EWMA) we e de- eloped (Ross e al.,2012). The eade is e e ed o Gus a sson (2001), who p esen s an o e iew o change de ec ion me hods. 5 Assessing Model Pe o mance This sec ion desc ibes an expe imen al se ing o he assessmen o model pe o mance. In Sec. 5.1 pe o mance c i e ia a e in oduced. The expe imen al e alua ion o he model pe o mance equi es da a. S a egies o ob aining es da a a e desc ibed in Sec. 5.2. 5.1 Pe o mance C i e ia Elemen a y pe o mance c i e ia o da a s eam algo i hms a e based on P-1 ime (speed) We conside he amoun o ime needed (i) o lea n and (ii) o p edic . I he ime limi is eached, con inuing he da a p ocessing will ake longe o esul s will loose p ecision. This consequence is no so ha d as he space limi , because o e iding he space limi will o ce he algo i hm o s op. P-2 space (memo y) A simple s a egy o he handling space budge is o s op once he limi is eached. To con inue p ocessing i he he space limi is eached is o o ce he algo i hm o disca d pa s o i s da a. P-3 e o a es (s a is ical measu es) The p edic ion e o is conside ed. Se e al e o measu es a e a ailable (Hyndman and Koehle , 2006;Willmo and Ma suu a,2005). Rega ding classi ica ion, he ollowing e o measu es a e es ablished. We will conside a bina y classi ica ion es , e.g., a es ha sc eens i ems o a ce ain ea u e. In his se ing, he e m “posi i e” co esponds wi h “iden i ied” ( he i em has he ea u e) and “nega i e” co esponds wi h “ ejec ed” ( he i em does no ha e he ea u e), i.e., •TP: ue posi i e = co ec ly iden i ied •FP: alse posi i e = inco ec ly iden i ied = αe o o he i s ype •TN: ue nega i e = co ec ly ejec ed 5 Table 1: Con usion ma ix. The e o o he i s kind, he so-called αe o ( alse posi i e) as well as he e o o he second kind, he so-called β-e o ( alse nega i e), a e deno ed as αand β, espec i ely. T ue alue Posi i e Nega i e Tes esul (p edic ion) Posi i e TP FP (α) PPV (p ecision) Nega i e FN (β) TN NPV TPR TNR •FN: alse nega i e = inco ec ly ejec ed = βe o o he second ype These ou alues can be a anged in a con ingency able o con usion ma ix as shown in Table 1. Based on he alues om he con usion ma ix, he ollowing s a is ical measu es can be de e - mined: •Accu acy is measu ed as he pe cen age o co ec classi ica ions, i.e., i is de ined as he sum o he numbe o ue posi i es and he numbe o ue nega i es di ided by he o al numbe o examples ( o al popula ion). Since accu acy can be misleading (conside he so-called accu acy pa adox), u he measu es a e commonly used (Zhu,2007). •The p ecision is de ined as he numbe o ue posi i es di ided by he numbe o ue posi i es and alse posi i es. P ecision is also e e ed o as he posi i e p edic i e alue (PPV). •The nega i e p edic i e alue (NPV) is de ined as he numbe o ue nega i es di ided by he numbe o ue nega i es and alse nega i es. •The speci i y (o ue nega i e a e, TNR) is de ined as he numbe o ue nega i es di ided by he numbe o ue nega i es and alse posi i es. •The sensi i i y (o ue posi i e a e (TPR) o ecall) is de ined as he numbe o ue posi i es di ided by he numbe o ue posi i es and he numbe o alse nega i es. •The adi ional F1sco e combines he sensi i i y (TPR) and he p ecision (PPV) measu es. I is de ined as he ha monic mean o sensi i i y and p ecison: F1= 2 ×((PPV ×TPR)/(PPV + TPR)). T aining da a can be used o de e mine hese s a is ical measu es. This can lead o o e i ing and esul in poo ly gene alizable models. The e o e, es ing da a, i.e., using unseen da a, should be used (Has ie,2009). 5.2 How o Gene a e Tes Da a Gene a ing es da a appea s o be i ial a he i s sigh . Howe e , simply spli ing he da a in o wo se s migh cause unwan ed e ec s, e.g., in oduce bias, o esul in an ine icien usage o he a ailable in o ma ion. The es da a gene a ion p ocess needs ca e ul conside a ions in o de o a oid hese allacies. Fi s , we will conside adi ional me hods, e.g., s a ic (s a iona y) da a se s wi h a ela i ely small amoun o da a. A se ing will be e e ed o as a ba ch se ing, i all he da a is a ailable ahead o ime. O he wise, he se ing will be e e ed o as an on-line se ing. I he da a dis ibu ion changes o e ime, he se ing is e e ed o as a non-s a iona y se ing. 5.2.1 Tes Da a in P e ious E alua ion Me hods P e ious ML me hods ocused on s a ic da a wi h a limi ed amoun o samples in he ba ch se ing. Bi e e al. (2011) lis he ollowing s a egies, which a e conside ed s anda d in ML. Holdou : Di ide he da a in wo subse s, he so-called aining se and he holdou o es ing se . The concep ual p oblem wi h he holdou me hod is ha i does no use he da a e icien ly, because many da a a e no used o aining. Random subsampling: To o e come he concep ual p oblem o he holdou app oach and o imp o e i s e iciency, andom subsampling and a e aging o he e o s om each subse can be used. Random subsampling also allows measu ing he accu acy es ima e’s a iance. 6 Random subsampling su e s om he ollowing disad an age: I he aining se con ains many da a om one class, han he es se na u ally con ains only a ew da a om his class. This bias esul s in andom subsampling iola ing he assump ion ha aining and es se s a e independen . C oss alida ion (CV): C oss alida ion (A lo and Celisse,2009) op imizes he use o da a o aining and es ing. E e y a ailable da a is used o aining and es ing. To a oid bias, s a i ied c oss- alida ion can be used. Lea e-one-ou CV: is a special case o c oss- alida ion, which is ela i ely expensi e o pe o m i he model i is complex. Lea e-one-ou CV is, in con as o CV, comple ely de e minis ic. Howe e , lea e- one-ou CV can ail, e.g., conside a classi ica ion si ua ion wi h wo classes, when da a is comple ely andom and 50 pe cen o he da a belong o each class. The lea e-one-ou CV ails, because he majo i y o e is always w ong on he hold-ou da a and lea e-one-ou CV will p edic an accu acy o ze o, al hough he expec ed accu acy is 50 pe cen . The boo s ap: The boo s ap me hod (E on and Tibshi ani,1993) gene a es a boo s ap sample by sampling wi h eplacemen a aining da a se , which has he same size as he o iginal da a. The da a ha a e no in he aining da a se a e used used o es ing. The boo s ap can gene a e w ong esul s (in his case, hey a e oo op imis ic) in se ings desc ibed o he lea e-one-ou CV. Recommenda ions o choosing a sui able e alua ion me hod a e gi en in Koha i (1995). Kleijnen (2008) discusses hese me hods in he con ex o simula ion expe imen s. 5.2.2 E alua ion P ocedu es o Dynamic Da a S eam Me hods In he dynamic da a s eam se ing, plen y o da a is a ailable. The simple holdou s a egy can be used wi hou causing he p oblems men ioned in he ba ch se ing. In con as o he ba ch se ings, la ge da a se s o exac accu acy es ima ions can be used o es ing wi hou p oblems. Holdou : The simples app oach is jus holding ou one (la ge) single e e ence da a se du ing he whole lea ning ( aining) phase. Using his holdou da a se , he model can be e alua ed pe iodically. This holdou da a se can be gene a ed using (i) old o (ii) new da a, i.e., look-ahead da a se s. The look-ahead me hod (Agga wal,2013) can gi e he model addi ional in o ma ion (addi ional aining da a) a e he i s es ing phase is comple ed. This me hod is use ul in si ua ion when concep d i occu s. In si ua ions wi hou any concep d i , a s a ic holdou da a se is adequa e and be e sui ed, because i does no in oduce an addi ional sou ce o andomness in he lea ning p ocess. In e lea ed Tes -Then-T ain In addi ion o he holdou me hod, he in e lea ed es - hen- ain me hod was p oposed o e alua ing da a s eam algo i hms (Bi e e al.,2010). Each new da a can be used o es he model be o e i is used o aining. Ad an ages o his me hod a e: (i) The model is es ed on unknown da a, (ii) each da um is used o es ing and aining, and (iii) he accu acy o e ime is smoo h, because each indi idual new da a will become less signi ican o he o e all a e age ( he sample size is inc easing). In e lea ed es - hen- ain me hods obscu e he di e ences be ween aining and es ing pe i- ods. The ue accu acy migh be biased, because algo i hms will be punished o ea ly mis akes. This e ec cancels ou o e ime. 5.3 Analysis A g aphical plo (accu acy e sus numbe o aining samples) is he mos common way p esen ing esul s. Ve y o en, he compa ison o wo algo i hms is based on g aphical compa isons by isualizing ends (e.g., accu acy) o e ime. Bi e e al. (2011) desc ibe he si ua ion as ollows: ”Mos o en his is de e mined om a single holdou un, and wi h an independen es se con aining 300 housand examples o less. I is a e o see a se ious a emp a quan i ying he signi icance o esul s wi h con idence in e als o simila checks.” This si ua ion appea s o be simila o he si ua ion o expe imen al algo i hmics a decade ago, which was desc ibed in Sec. 1. To ob ain eliable esul s, s a is ical measu es such as he s anda d e o o esul s, a e ecommended. Use ul app oaches we e desc ibed by Demˇsa (2006). Fo example, 7 McNema ’s es can be used o measu e he ag eemen be ween compe ing algo i hms on each es da a (Die e ich,1998). The s a is ical analysis should be accompanied by a comp ehensi e epo ing scheme, which includes he ele an de ails o unde s anding and possible eplica ion o he indings. The expe imen al analysis o da a s eam classi ica ion is subjec o cu en esea ch. Only a ew publica ions ha pe o m an ex ensi e s a is ical analyis a e a ailable. Bi e e al. (2011) claim ha pape Domingos and Hul en (2000) is he bes analysis so a . Fo una ely, he open sou ce amewo k o da a s eam mining MOA, which includes a collec ion o machine lea ning algo i hms (classi ica ion, eg ession, clus e ing, ou lie de ec ion, concep d i de ec ion and ecommende sys ems) and ools o e alua ion, is a ailable and p o ides ools o an ex ensi e expe imen al analysis (Holmes e al.,2010). 6 En i onmen s and Da a Sou ces 6.1 Real-wo ld Da a S eam Compu ing En i onmen s Compu ing en i onmen s can be classi ied as ollows: (i) Senso ne wo ks. In his se ing, only a ew hund ed kiloby es o memo y a e a ailable. (ii) Handheld compu e , which p o ide se e al megaby es o memo y, (iii) Single-boa d compu e s, i.e., compu e s ha a e buil on a single ci cui boa d. The componen s such as mic op ocesso (s), memo y, o inpu /ou pu a e loca ed on his boa d. Single- boa d compu e s can be used as embedded compu e con olle s, and (i ) se e s, which p o ide se e al gigaby es o RAM, e.g., 64 GB. 6.2 Simula o s o Da a S eam Analysis Random da a s eam simula o s a e a aluable ool o he expe imen al analysis o da a s eam algo i hms. Fo ou expe imen s in Sec. 7a s a ic da a se , which con ained p e-assigned class labels, was used o simula e a eal-wo ld da a s eam en i onmen . Conside a da a se o size n, which is pa i ioned in aining and es da a se s wi h n ain : numbe o examples used o aining be o e an e alua ion is pe o med on he es se . 2. n es : size o he es se . Using nai e Bayes o Hoe ding ees, a model is buil using he i s n ain ins ances o aining. P edic ion is pe o med on each o he emaining n es ins ances. The es da a is used o inc emen ally upda e he model buil . This on-line s eam se ing allows he es ima ion o he model accu acy on an ongoing basis, because he esul s (class labels) a e known in ad ance. The open sou ce amewo k o da a s eam mining MOA (Holmes e al.,2010) is able o gene a e a ew housand examples up o se e al hund ed housand examples pe second. Addi ional noise can slow down he speed, because i equi es he gene a ion o andom numbe s. 7 A Simple Expe imen in he EASD F amewo k 7.1 The Scien i ic Ques ion Be o e expe imen al uns a e pe o med, he scien i ic ques ion, which mo i a es he expe imen s, should be clea ly s a ed. To exempli y he EASD app oach, he ollowing ask is conside ed: Machine lea ning me hods, which combine mul iple models o imp o e p edic ion accu acy, a e called ensemble da a mining algo i hms. Di e si y o he di e en models is necessa y o each his pe o mance gain compa ed o indi idual models. I ensemble membe s always ag ee, he ensemble does no p o ide an ex a bene i . E o s o one ensemble membe can be co ec ed by o he membe s o he ensemble. Each indi idual ML algo i hm equi es he speci ica ion o some pa ame e s, e.g., he spli ing c i e ion o eg ession ees o he o de o linea models. Building ensembles equi es he speci- ica ion o addi ional algo i hm pa ame e s, e.g., he numbe o ensemble membe s. The scien i ic ques ion can be o mula ed as ollows: Scien i ic ques ion: How does he numbe o models o boos a ec he pe o mance o on-line lea ning algo i hms? To se up expe imen s, a speci ic algo i hm (o a se o algo i hms) has o be selec ed. Oza e al. p esen ed a simple on-line bagging and boos ing algo i hm, OzaBoos (Oza and Russell,2001b,a; Oza). OzaBoos combines mul iple lea ned base models wi h he aim o imp o ing gene aliza ion pe o mance. OzaBoos implemen s an on-line e sion o hese ensemble lea ne s, which ha e been used p ima ily in ba ch mode. The e ec o he numbe o models o boos on he algo i hm pe o mance is an impo an esea ch ques ion, which will be analyzed in he ollowing expe imen s. The e o e, he expe imen al se up as well as he implemen a ion de ails ha e o be speci ied u he . 8 G. Holmes, B. P ah inge , P. K anen, T. Jansen, T. Seidl, and A. Bi e . MOA: Massi e Online Analy- sis, a F amewo k o S eam Classi ica ion and Clus e ing. In In e na ional Wo kshop on Handling Concep D i in Adap i e In o ma ion Sys ems in conjunc ion wi h Eu opean Con e ence on Machine Lea ning and P inciples and P ac ice o Knowledge Disco e y in Da abases ECML PKDD, pages 3–16, 2010. J. N. Hooke . Needed: An empi ical science o algo i hms. Ope a ions esea ch, 42(2):201–212, 1994. J. N. Hooke . Tes ing Heu is ics: We Ha e I All W ong. Jou nal o heu is ics, 1(1):33–42, 1996. R. J. Hyndman and A. B. Koehle . Ano he look a measu es o o ecas accu acy. In e na ional Jou nal o Fo ecas ing, 22(4):679–688, Oc . 2006. D. S. Johnson, C. R. A agon, L. A. McGeoch, and C. Sche on. Op imiza ion by Simula ed Annealing: an Expe imen al E alua ion. Pa I, G aph Pa i ioning. Ope a ions esea ch, 37(6):865–892, 1989. D. S. Johnson, C. R. A agon, L. A. McGeoch, and C. Sche on. Op imiza ion by Simula ed Anneal- ing: an Expe imen al E alua ion. Pa II, G aph Colo ing and Numbe Pa i ioning. Ope a ions esea ch, 39(3):378–406, 1991. J. P. C. Kleijnen. Design and analysis o simula ion expe imen s. Sp inge , New Yo k NY, 2008. R. Koha i. A S udy o C oss-Valida ion and Boo s ap o Accu acy Es ima ion and Model Selec ion. pages 1–8, 1995. E. Lugho e and M. Sayed-Mouchaweh. Adap i e and on-line lea ning in non-s a iona y en i on- men s. E ol ing Sys ems, 6(2):75–77, Feb. 2015. C. C. McGeoch. Expe imen al Analysis o Algo i hms. PhD hesis, Ca negie Mellon Uni e si y, Pi sbu gh PA, 1986. C. C. McGeoch. A Guide o Expe imen al Algo i hmics. Camb idge Uni e si y P ess, New Yo k, NY, USA, 1s edi ion, 2012. D. C. Mon gome y. S a is ical Quali y Con ol. Wiley, 2008. N. C. Oza. Online Bagging and Boos ing. In 2005 IEEE In e na ional Con e ence on Sys ems, Man and Cybe ne ics. N. C. Oza and S. Russell. Online bagging and boos ing. In T. Jaakola and T. Richa dson, edi o s, 8 h Ins e na ional Wo kshop on A i icial In elligence and S a is ics, pages 105–112, 2001a. N. C. Oza and S. Russell. Expe imen al compa isons o online and ba ch e sions o bagging and boos ing. In he se en h ACM SIGKDD in e na ional con e ence, pages 359–364, New Yo k, New Yo k, USA, 2001b. ACM P ess. B. P ah inge , G. Holmes, and R. Ki kby. New Op ions o Hoe ding T ees. In AI 2007: Ad ances in A i icial In elligence, pages 90–99. Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, Dec. 2007. M. P euss. Mul imodal Op imiza ion by Means o E olu iona y Algo i hms. Na u al Compu ing Se ies. Sp inge In e na ional Publishing, Cham, 2015. J. R. Quinlan. C4.5: P og ams o Machine Lea ning. Mo gan Kau mann Publishe s Inc., San F an- cisco, CA, USA, 1993. R Co e Team. R: A Language and En i onmen o S a is ical Compu ing. R Founda ion o S a- is ical Compu ing, Vienna, Aus ia, 2015. G. J. Ross, N. M. Adams, D. K. Tasoulis, and D. J. Hand. Exponen ially weigh ed mo ing a e age cha s o de ec ing concep d i . 33(2):191–198, Jan. 2012. T. J. San ne , B. J. Williams, and W. I. No z. The Design and Analysis o Compu e Expe imen s. Sp inge , Be lin, Heidelbe g, New Yo k, 2003. A. Shake and E. H¨ulle meie . IBLS eams: a sys em o ins ance-based classi ica ion and eg ession on da a s eams. E ol ing Sys ems, 3(4):235–249, 2012. P. N. Sugan han, N. Hansen, J. J. Liang, K. Deb, Y. P. Chen, A. Auge , and S. Tiwa i. P oblem De i- ni ions and E alua ion C i e ia o he CEC 2005 Special Session on Real-Pa ame e Op imiza ion. Technical epo , Singapo e, 2005. 15 J. W. Tukey. Explo a i e da a analysis. Addison-Wesley, 1977. H. Wang, P. S. Yu, and J. Han. Mining Concep -D i ing Da a S eams. In Da a Mining and Knowledge Disco e y Handbook, pages 789–802. Sp inge US, Bos on, MA, July 2010. D. Whi ley, K. Ma hias, S. Rana, and J. Dzube a. E alua ing e olu iona y algo i hms. A i icial In elligence, 85(1–2):245–276, 1996. C. J. Willmo and K. Ma suu a. Ad an ages o he mean absolu e e o (MAE) o e he oo mean squa e e o (RMSE) in assessing a e age model pe o mance. Clim Res, pages 1–4, Dec. 2005. M. Zae e e , T. Ba z-Beiels ein, B. Naujoks, T. Wagne , and M. Emme ich. A Case S udy on Mul i- C i e ia Op imiza ion o an E en De ec ion So wa e unde Limi ed Budge s. In R. C. Pu shouse e al., edi o s, E olu iona y Mul i-C i e ion Op imiza ion 7 h In e na ional Con e ence, EMO, pages 756–770, Heidelbe g, 2013. Sp inge . X. Zhu. Knowledge Disco e y and Da a Mining: Challenges and Reali ies: Challenges and Reali ies. Gale i ual e e ence lib a y. In o ma ion Science Re e ence, 2007. 16 ! ! CIplus Band 2/2016 EASD - Expe imen al Algo i hmics o S eaming Da a P o . D . Thomas Ba z-Beiels ein Ins i u ü In o ma ik Fakul ä ü In o ma ik und Ingenieu wissenscha en Technische Hochschule Köln Mä z 2016 Die Ve an wo ung ü den Inhal diese Ve ö en lichung lieg beim Au o .