Äärimmäisen nopea päätöspuu ja sen vertailu muihin Hoeffdingin puun sovelluksiin
Vanhala, Tuomas (2020)
2020
Tieto- ja sähkötekniikan kandidaattiohjelma - Degree Programme in Computing and Electrical Engineering, BSc (Tech)
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-05-08
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202004294589
https://urn.fi/URN:NBN:fi:tuni-202004294589
Tiivistelmä
Nykyisin voidaan datan valtaisan määrän vuoksi puhua massadatasta. Kertyneen datan hyödyntäminen edellyttää kuitenkin sen analysointia. Tiedonlouhinnassa datasta pyritään löytämään oleelliset tiedot tai mallit. Tietovirraksi kutsutaan jonkin prosessin synnyttämää jatkuvaa havaintojen sarjaa. Tietovirtojen tilastolliset ominaisuudet kuitenkin vaihtelevat ajan kuluessa. Tälle ilmiölle käytetään nimitystä käsitteen vaihtelu (concept drift).
Päätöspuut ovat tehokas luokittelumenetelmä. Hoeffdingin puuhun pohjautuvat päätöspuut kykenevät tekemään analytiikan reaaliaikaisesti suoraan tietovirrasta. Hoeffdingin puu tarjoaa Hoeffdingin rajan ansiosta tilastollisen takuun suorituskyvylleen. Hoeffdingin puun pohjalta kehitettyjä päätöspuita yhdistääkin niissä kaikissa esiintyvä Hoeffdingin raja. Näissä päätöspuissa hyödynnetään usein myös esimerkiksi rinnakkaisia alipuita. Manapragada, Webb ja Salehi esittivät vuonna 2018 äärimmäisen nopean päätöspuun (EFDT, Extremely Fast Decision Tree), joka oli huomattava parannus inkrementaalisen oppimisen standardeihin. Samassa julkaisussa esitettiin myös EFDT:n vertailu todella nopean päätöspuun (VFDT, Very Fast Decision Tree learner) kanssa usealla laajalla aineistolla.
Tässä työssä tutustutaan ongelman taustoihin, perehdytään Hoeffdingin puun teoriaan ja sovelluksiin, esitetään ja toistetaan vertailu VFDT:n ja EFDT:n välillä sekä laajennetaan vertailua satunnaisella aineistolla. Vertailu toistettiin virtuaalikoneessa olevalla Linux-alustalla käyttäen kokeiden toistoa varten saatavissa olevaa ohjelmakoodia. Tähän alkuperäiseen ohjelmakoodiin jouduttiin toteuttamaan uudelleen tulosdatan käsittely kuvaajan piirtoa varten. Työssä pystytään vahvistamaan Manapragadan, Webbin ja Salehin saamat tulokset. Näihin tuloksiin lukeutuu muun muassa se, että EFDT on useimmissa tapauksissa tarkempi, mutta suoritusajallisesti hitaampi. VFDT on EFDT:tä tarkempi ainoastaan laajoilla fysiikan simulaatioaineistoilla. Suoritusajallisesti VFDT on nopeampi niin ikään myös satunnaisella aineistolla, mutta tällä aineistolla on VFDT:n ja EFDT:n tarkkuuden välinen ero pieni ja kummankin päätöspuun tarkkuus lähellä 50 %:ia.
Päätöspuut ovat tehokas luokittelumenetelmä. Hoeffdingin puuhun pohjautuvat päätöspuut kykenevät tekemään analytiikan reaaliaikaisesti suoraan tietovirrasta. Hoeffdingin puu tarjoaa Hoeffdingin rajan ansiosta tilastollisen takuun suorituskyvylleen. Hoeffdingin puun pohjalta kehitettyjä päätöspuita yhdistääkin niissä kaikissa esiintyvä Hoeffdingin raja. Näissä päätöspuissa hyödynnetään usein myös esimerkiksi rinnakkaisia alipuita. Manapragada, Webb ja Salehi esittivät vuonna 2018 äärimmäisen nopean päätöspuun (EFDT, Extremely Fast Decision Tree), joka oli huomattava parannus inkrementaalisen oppimisen standardeihin. Samassa julkaisussa esitettiin myös EFDT:n vertailu todella nopean päätöspuun (VFDT, Very Fast Decision Tree learner) kanssa usealla laajalla aineistolla.
Tässä työssä tutustutaan ongelman taustoihin, perehdytään Hoeffdingin puun teoriaan ja sovelluksiin, esitetään ja toistetaan vertailu VFDT:n ja EFDT:n välillä sekä laajennetaan vertailua satunnaisella aineistolla. Vertailu toistettiin virtuaalikoneessa olevalla Linux-alustalla käyttäen kokeiden toistoa varten saatavissa olevaa ohjelmakoodia. Tähän alkuperäiseen ohjelmakoodiin jouduttiin toteuttamaan uudelleen tulosdatan käsittely kuvaajan piirtoa varten. Työssä pystytään vahvistamaan Manapragadan, Webbin ja Salehin saamat tulokset. Näihin tuloksiin lukeutuu muun muassa se, että EFDT on useimmissa tapauksissa tarkempi, mutta suoritusajallisesti hitaampi. VFDT on EFDT:tä tarkempi ainoastaan laajoilla fysiikan simulaatioaineistoilla. Suoritusajallisesti VFDT on nopeampi niin ikään myös satunnaisella aineistolla, mutta tällä aineistolla on VFDT:n ja EFDT:n tarkkuuden välinen ero pieni ja kummankin päätöspuun tarkkuus lähellä 50 %:ia.
Kokoelmat
- Kandidaatintutkielmat [10645]