Oppiminen Päätös puu on menetelmä, joka perustuu käytön päätöspuumallia ennustemallina. Sitä käytetään erityisesti tiedonlouhinnassa ja koneoppimisessa .
Näissä puurakenteissa lehdet edustavat kohdemuuttujan arvoja ja oksat vastaavat syötemuuttujien yhdistelmiä, jotka johtavat näihin arvoihin. Päätösanalyysissä päätöksentekopuuta voidaan käyttää nimenomaisesti edustamaan tehtyjä päätöksiä ja niihin johtavia prosesseja. Oppimisessa ja tiedonlouhinnassa päätöspuu kuvaa tietoja, mutta ei itse päätöksiä. Puuta käytettäisiin lähtökohtana päätöksentekoprosessille.
Se on valvottu oppimistekniikka : käytämme joukkoa tietoja, joille tiedämme kohdemuuttujan arvon rakentaaksemme puun (ns. Leimatut tiedot), sitten ekstrapoloimme tulokset tietokokoon. Päätöspuut ovat koneoppimisen suosituimpia algoritmeja .
Päätöspuun oppiminen on klassinen menetelmä koneoppimisessa . Sen tarkoituksena on luoda malli, joka ennustaa kohdemuuttujan arvon useiden syötemuuttujien arvosta.
Yksi tulomuuttujista valitaan puun jokaisessa sisäsolmussa (tai sisäisessä solmussa, joka ei ole pääte) algoritmista riippuvan menetelmän mukaisesti, josta keskustellaan myöhemmin. Kukin alisolmun reuna vastaa syötemuuttujan arvoja, joten alisolmujen reunaryhmä peittää kaikki mahdolliset tulomuuttujan arvot.
Jokainen lehti (tai puun päätesolmu) edustaa joko kohdemuuttujan arvoa tai kohdemuuttujan eri mahdollisten arvojen todennäköisyysjakaumaa. Tulomuuttujien arvojen yhdistelmää edustaa polku juuresta lehteen.
Puu rakennetaan yleensä erottamalla tietojoukko alajoukoiksi syöttöominaisuuksien arvon perusteella. Tämä prosessi toistetaan jokaisella rekursiivisesti saadulla osajoukolla, joten se on rekursiivinen osiointi .
Rekursio suoritetaan solmussa joko silloin, kun kaikilla osajoukoilla on sama kohdeominaisuuden arvo, tai kun erottaminen ei enää paranna ennustusta. Tätä prosessia kutsutaan päätöksentekopuiden ylhäältä alas induktioksi (TDIDT), se on ahne algoritmi, koska etsimme puun jokaisesta solmusta optimaalista jakamista saadaksemme parhaan mahdollisen jakamisen koko päätöspuulle. Tämä on yleisin strategia päätöksentekopuiden oppimiseksi datasta.
Tiedon louhinnassa päätöspuista voi olla apua kiinteän tietojoukon kuvauksessa, luokittelussa tai yleistämisessä .
Harjoittelupaketti toimitetaan yleensä tämän tyyppisten tietueiden muodossa:
Muuttuja osoittaa kohdemuuttujan, jota pyritään ennustamaan, luokittelemaan tai yleistämään. Vektori koostuu syöttömuuttujista jne. joita käytetään tähän tarkoitukseen.
Tiedon louhinnassa on kahta päätyyppiä:
Termi Classification and Regression Tree Analysis ( CART , lyhenteen jälkeen) on yleinen termi, joka viittaa Breimanin ym. Aiemmin kuvaamiin ja käyttöön ottamiin menettelyihin. Regressiotapauksessa ja luokittelussa käytetyillä puilla on yhtäläisyyksiä mutta myös eroja , erityisesti haarojen erottelujen määrittämiseksi käytetyn menettelyn suhteen.
Päätöksentekokaavio oppiminen koostuu rakentaa puusta oppimisen joukko koostuu leimatun tuplat . Päätöspuuta voidaan kuvata datavuokaaviona (tai vuokaaviona ), jossa kukin sisäinen solmu kuvaa oppimuuttujan testiä, kukin haara edustaa testin tulosta ja jokainen lehti sisältää kohdemuuttujan arvon. (Luokka luokituspuiden tunniste, regressiopuiden numeerinen arvo).
Yleensä algoritmit päätöksentekopuiden rakentamiseksi rakennetaan jakamalla puu ylhäältä lehtiin valitsemalla jokaisessa vaiheessa tulomuuttuja, jolla saavutetaan paras joukko objektijoukkoja, kuten aiemmin on kuvattu. Jos haluat valita solmun erotusmuuttujan, algoritmit testaavat erilaisia mahdollisia tulomuuttujia ja valitsevat yhden, joka maksimoi tietyn kriteerin.
Luokittelupuiden tapausLuokittelupuiden tapauksessa tämä on automaattinen luokitteluongelma . Osioiden arviointikriteeri luonnehtii joukon jakamalla saadun osajoukon homogeenisuutta (tai homogeenisuuden kasvua). Näitä mittareita sovelletaan kuhunkin ehdokasosajoukkoon ja tulokset yhdistetään (esim. Keskiarvoksi) erottelun laadun mittaamiseksi.
Tällaisia kriteereitä on paljon, yleisimmin käytettyjä ovat Shannonin entropia , Gini-monimuotoisuusindeksi ja niiden muunnokset.
Regressiopuiden tapaus
Regressiopuiden tapauksessa voidaan käyttää samaa erotusmenetelmää, mutta luokitteluvirheiden minimoimisen sijaan pyrimme maksimoimaan luokkien välisen varianssin (jotta saataisiin osajoukkoja, joiden kohdemuuttujan arvot ovat hajallaan yhtä laajalti mahdollisimman). Yleensä kriteerissä käytetään chi-neliötestiä .
HuomautuksetTiettyjen kriteerien avulla voidaan ottaa huomioon se, että kohdemuuttuja ottaa järjestetyt arvot käyttämällä asianmukaisia mittareita tai heuristiikkaa.
Jokainen segmenttimuuttujan arvojoukko tuottaa alisolmun. Oppimisalgoritmit voivat vaihdella tuotettujen lapsisolmujen lukumäärän suhteen: jotkut (kuten CART ) tuottavat järjestelmällisesti binäärisiä puita ja etsivät siksi binääristä osiota, joka optimoi segmentointikriteerin. Toiset (kuten CHAID ) pyrkivät muodostamaan osuvimmat ryhmittelyt tilastollisten kriteerien perusteella. Tekniikasta riippuen saamme enemmän tai vähemmän leveitä puita. Menetelmän tehokkuuden varmistamiseksi on huolehdittava siitä, että tietoja ei jaeta liikaa, jotta ei syntyisi liian pieniä henkilöstöryhmiä, jotka eivät vastaa mitään tilastollista todellisuutta.
Jatkuvien segmenttimuuttujien osalta valitun segmentointikriteerin on oltava riittävä. Yleensä tiedot lajitellaan käsiteltävän muuttujan mukaan, sitten testataan mahdolliset eri raja-arvot arvioimalla kunkin tapauksen kriteeri. Optimaalinen raja-arvo on se, joka maksimoi segmentointikriteerin.
Käytännössä ei ole aina toivottavaa rakentaa puuta, jonka lehdet vastaavat kohdemuuttujan kannalta täysin homogeenisia osajoukkoja. Itse asiassa koulutus toteutetaan otoksella, jonka toivotaan edustavan väestöä. Minkä tahansa oppimistekniikan haasteena on kerätä hyödyllistä tietoa väestön tilastollisesta rakenteesta lukuun ottamatta tutkittavaan aineistoon liittyviä erityispiirteitä. Mitä monimutkaisempi malli on (mitä suurempi puu, sitä enemmän oksia siinä on, sitä enemmän lehtiä sillä on), sitä enemmän olemme vaarassa, että tätä mallia ei voida ekstrapoloida uusiin tietoihin. todellisuudesta, jota yritetään tarttua.
Erityisesti äärimmäisessä tapauksessa, jossa puulla on niin monta lehtiä kuin populaatiossa on yksilöitä (tietojoukon tietueet), puu ei tee virhettä tässä otoksessa, koska se täyttää kaikki ominaisuutensa, mutta sitä ei voida yleistetty toiseen otokseen. Tämä ongelma, jota kutsutaan ylikoulutukseksi tai ylitys ( overfitting ), on klassinen koneoppimisen ja tiedonlouhinnan aihe.
Siksi pyrimme rakentamaan mahdollisimman pienen puun ja samalla varmistamaan parhaan mahdollisen suorituskyvyn. Parsimonian periaatetta noudattaen , mitä pienempi puu, sitä vakaampi se on tulevissa ennusteissaan. Käytettyjen mallien suorituskyvyn ja monimutkaisuuden välillä on tehtävä kompromissi. Vertailukelpoisuuden saavuttamiseksi suosimme aina yksinkertaisinta mallia, jos haluamme pystyä käyttämään tätä mallia uusissa näytteissä.
Mallien yliasennuksen ongelmaKäytettyjen mallien suorituskykyä / monimutkaisuutta koskevan välimiesmenettelyn suorittamiseksi yhden tai useamman mallin suorituskyky arvioidaan sen rakentamiseen käytettyjen tietojen perusteella (koulutusnäyte (t)), mutta myös yhdellä (tai useammalla) validointinäytteellä : merkitty tieto saatavilla, mutta jota vapaaehtoisesti päätetään olla käyttämättä mallien rakentamisessa.
Näitä tietoja käsitellään kuten testituloksia, mallien suorituskyvyn vakaus näissä kahdessa näytetyypissä tekee mahdolliseksi arvioida sen ylikuntoisuuden ja siten sen kyvyn käyttää hallitulla virheriskillä todellisissa olosuhteissa, joissa tiedot ei tiedetä etukäteen.
Vastakkaisessa kaaviossa havainnoidaan päätöksentekopuun säätövirheen evoluutiota puun lehtien lukumäärän funktiona (mikä mittaa tässä monimutkaisuutta). Havaitsemme, että jos virhe pienenee jatkuvasti oppimisnäytteessä tietystä monimutkaisuudesta, malli siirtyy pois todellisuudesta, todellisuudesta, jota yritämme arvioida validointinäytteellä (kutsutaan kaaviossa testinäytteeksi). ).
Päätöspuiden tapauksessa on harkittu useita erityyppisiä algoritmisia ratkaisuja, joilla pyritään välttämään mahdollisimman paljon mallien ylikuormitusta: puiden esi- tai jälkileikkaustekniikat.
Jotkut tilastoteoriat pyrkivät löytämään optimaalisen koulutuksen otokseen tehdyn virheen ja testinäytteeseen tehdyn virheen välillä. Teoria Vapnik-Chervonenkis Structured riskin minimointiin (tai SRM), käyttää muuttujan nimeltään ulottuvuus VC, määrittää optimaalisen mallin. Siksi sitä voidaan käyttää sellaisten mallien luomiseen, jotka takaavat parhaan kompromissin mallin laadun ja kestävyyden välillä.
Nämä algoritmiset ratkaisut täydentävät koulutus- ja validointinäytteille suoritettuja vertailevia suorituskyky- ja vakausanalyysejä.
EsileikkausEnsimmäinen strategia, jota voidaan käyttää päätöksentekopuiden liiallisen oppimisen välttämiseen, on pysäytyskriteerien ehdottaminen laajennusvaiheessa. Tämä on karsinnan periaate. Kun ryhmä on liian pieni tai kun osajoukon homogeenisuus on saavuttanut riittävän tason, otoksen erottaminen ei ole enää tarpeen. Toinen tässä yhteydessä usein havaittu kriteeri on tilastollisen testin käyttäminen sen arvioimiseksi, tuottaako segmentointi merkittävän informaation kohdemuuttujan ennustamiseen.
JälkileikkausToinen strategia koostuu puun rakentamisesta kahdessa vaiheessa: ensin tuotetaan puu, jonka lehdet ovat mahdollisimman homogeeniset laajenemisvaiheessa, käyttäen ensimmäistä murto-osaa datanäytteestä (näyte d, jota ei pidä sekoittaa koko näytteeseen) , jota kutsutaan englanniksi kasvavaksi joukoksi epäselvyyden poistamiseksi), sitten puu pienenee, tukeutuen toiseen murto-osaan tiedoista puun suorituskyvyn optimoimiseksi on karsimisen jälkeinen vaihe. Tapauskohtaisesti tämä toinen osa tiedoista on merkitty termillä validointinäyte tai testinäyte, mikä sekoittaa mallin suorituskyvyn mittaamiseen käytetyn näytteen. Termi karsimisnäyte sallii sen osoittamisen ilman epäselvyyttä, se on suora käännös englanninkielisestä nimestä karsimisjoukko .
Käytettävissä olevat tiedot ovat usein puutteellisia siinä mielessä, että vain osa syötemuuttujista on käytettävissä tietueelle. Tässä tapauksessa on mahdollista käyttää useita mahdollisuuksia:
Luokittelupuiden kohdalla tehtäväsääntö on määritettävä taulukoissa, kun puu on rakennettu. Jos lehdet ovat homogeenisia, ei ole epäselvyyttä. Jos näin ei ole, yksinkertainen sääntö on päättää taulukon luokasta eniten edustetun luokan enemmistöluokan mukaan.
Tämä hyvin yksinkertainen tekniikka on optimaalinen siinä tapauksessa, että tiedot ovat peräisin puolueettomasta satunnaisvalinnasta populaatiossa; väärin kohdistettujen kustannusten matriisi on yhtenäinen (symmetrinen): kohdentaminen asianmukaisesti nollakustannuksilla ja kustannusten kohdentaminen väärin tapauksesta riippumatta. Tämän kehyksen ulkopuolella enemmistösääntö ei ole välttämättä perusteltu, mutta sitä on helppo käyttää käytännössä.
Jotkut tekniikat, joita kutsutaan sarjamenetelmiksi ( kaikki menetelmät ), parantavat ennusteen laatua tai luotettavuutta rakentamalla tiedoista useita päätöspuita:
Päätöspuut yhdistetään toisinaan toistensa kanssa tai muiden oppimistekniikoiden kanssa: diskriminanttianalyysi, logistiset regressiot, lineaariset regressiot, hermoverkot ( monikerroksinen perceptroni , säteittäisen perustoiminnon verkko ) tai muut.
Menettelyt eri käytettyjen mallien suorituskyvyn yhdistämiseksi (kuten konsensuspäätökset) otetaan käyttöön maksimaalisen suorituskyvyn saavuttamiseksi, samalla kun hallitaan käytettyjen mallien monimutkaisuutta.
Verrattuna muihin tiedonlouhintamenetelmiin päätöspuilla on useita etuja:
Toisaalta sillä on tiettyjä haittoja:
Päätöspuussa kaikki polut juuresta lehtiin käyttävät AND- liitintä . Päätöskaaviossa voimme myös käyttää OR- liitintä useiden polkujen yhdistämiseen käyttämällä viestin vähimmäispituutta (MML). Yleensä päätöskaaviot tuottavat kaavioita, joissa on vähemmän lehtiä kuin päätöspuita.
Ja Evoluutioalgoritmien välttämiseksi käytetään erottamiseen johtaa paikalliseen optimaalinen.
Puusta voidaan myös ottaa näytteitä MCMC- menetelmillä Bayesin paradigmassa .
Puu voidaan rakentaa käyttäen alhaalta ylöspäin (bottom-up) lähestymistapaa.
Päätöspuiden rakentamiseen on useita algoritmeja, mukaan lukien:
ID3 ja CART keksittiin itsenäisesti vuosikymmeninä 1970-1980, mutta käyttävät samankaltaisia lähestymistapoja oppia päätöksentekopuita oppimisjoukosta.
Kaikki nämä algoritmit erotetaan käytetyillä segmentointikriteereillä tai toteutetuilla karsimismenetelmillä niiden tavoin puuttuvien tietojen käsittelemiseksi ennustimissa.
Monet tiedonlouhintaohjelmistot tarjoavat kirjastoja yhden tai useamman päätöksentekopuun oppimisalgoritmin toteuttamiseen. Esimerkiksi avoimen lähdekoodin R- ohjelmisto sisältää useita CART-sovelluksia, kuten rpart, party ja randomForest, ilmaisen ohjelmiston Weka ja Orange (ja sen orngTree-moduulin) tai ilmaisen Python-kirjaston scikit-learn ; mutta myös Salford Systems CART, IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, KNIME, Microsoft SQL Server [1] .