Päätöspuu

Päätöspuu (kutsutaan myös luokituspuuksi tai regressiopuuksi) on päätöksenteon tukityökalu, jota käytetään koneoppimisessa , data-analyysissä ja tilastoissa . Puun rakenne on "lehdet" ja "oksat". Päätöspuun reunoihin ("haaroihin") kirjoitetaan ne ominaisuudet, joista tavoitefunktio riippuu, tavoitefunktion arvot kirjoitetaan "lehtiin" ja muissa solmuissa ominaisuudet, joilla tapaukset vaihtelevat. Uuden tapauksen luokittelemiseksi on mentävä alas puusta lehteen ja palautettava vastaava arvo.

Tällaisia ​​päätöspuita käytetään laajalti tiedon louhinnassa. Tavoitteena on luoda malli , joka ennustaa kohdemuuttujan arvon useiden syötemuuttujien perusteella.

Jokainen lehti edustaa kohdemuuttujan arvoa, kun se muuttuu juuresta puun reunoja pitkin lehteen. Jokainen sisäinen solmu on kartoitettu johonkin syöttömuuttujaan.

Puu voidaan "oppia" myös jakamalla alkuperäiset muuttujajoukot osajoukkoihin ominaisuusarvojen tarkistuksen perusteella. Tämä toiminto toistetaan jokaiselle tuloksena olevalle osajoukolle. Rekursio päättyy, kun solmun osajoukolla on samat kohdemuuttujien arvot, joten se ei lisää arvoa ennusteisiin. Ylhäältä alas -prosessi, päätöspuun induktio (TDIDT) [1] , on esimerkki absorboivasta ahneesta algoritmista, ja se on ylivoimaisesti yleisin datan päätöspuustrategia, mutta se ei ole ainoa mahdollinen strategia.

Tiedonlouhinnassa päätöspuita voidaan käyttää matemaattisina ja laskentatekniikoina auttamaan kuvaamaan, luokittelemaan ja yleistämään datajoukkoa, joka voidaan kirjoittaa seuraavasti:

Riippuva muuttuja Y on kohdemuuttuja, joka analysoidaan, luokitellaan ja tehdään yhteenveto. Vektori koostuu syötemuuttujista , jne ., joita käytetään tämän tehtävän suorittamiseen.

Perusmääritelmät

Päätöspuuanalyysi käyttää visuaalista ja analyyttistä päätöksentekotyökalua kilpailevien vaihtoehtojen odotettujen arvojen (tai odotettujen hyötyjen) laskemiseen.

Päätöspuu koostuu kolmen tyyppisistä solmuista:

• Päätössolmut - esitetään yleensä neliöinä
• Todennäköisyyssolmut - esitetty ympyränä
• Sulkevat solmut - esitetään kolmiona

Yllä olevassa kuvassa päätöspuuta tulee lukea vasemmalta oikealle. Päätöspuu ei voi sisältää syklisiä elementtejä, eli jokainen uusi lehti voi myöhemmin vain halkeilla, ei ole konvergoivia polkuja. Siten puuta manuaalisesti rakennettaessa voimme kohdata sen ulottuvuuden ongelman, joten pääsääntöisesti voimme saada päätöspuun käyttämällä erikoisohjelmistoa. Päätöspuu esitetään tyypillisesti kaavion muodossa, mikä helpottaa sen ymmärtämistä ja analysointia.

Puutypologia

Tiedonlouhinnassa käytettyjä päätöspuita on kahta päätyyppiä:

• Puu luokitellaan, kun ennustettu tulos on luokka, johon data kuuluu;
• Regression puu, kun ennustettua lopputulosta voidaan pitää reaalilukuna (esimerkiksi talon hinta tai potilaan sairaalassaoloaika).

Edellä mainitut termit esittelivät ensimmäisenä Breiman ym. [2] Listatuilla tyypeillä on joitain yhtäläisyyksiä (rekursiiviset rakennusalgoritmit) sekä joitain eroja, kuten kriteerit osion valintaan jokaisessa solmussa. [2]

Jotkin menetelmät mahdollistavat useamman kuin yhden päätöspuun rakentamisen (päätöspuuryhmien):

1. Päätöspuiden pussittaminen , aikaisin lähestymistapa . Rakentaa useita päätöspuita interpoloimalla dataa toistuvasti korvauksella ( bootstrap ) ja antaa konsensusvastauksena puiden äänen (niiden keskimääräisen ennusteen); [3]
2. Random Forest -luokitin perustuu pussitukseen , mutta sen lisäksi se valitsee satunnaisesti jokaisessa solmussa osan piirteitä tehdäkseen puista itsenäisempiä;
3. Puun tehostamista voidaan käyttää sekä regressio- että luokitteluongelmiin. [4] Tietojen analysointikilpailujen voittajat ovat käyttäneet toistuvasti yhtä puun tehostamisen toteutusta, XGBoost- algoritmia.
4. "Metsän kierto" - puut, joissa kukin päätöspuu analysoidaan soveltamalla ensimmäistä kertaa pääkomponenttianalyysiä (PCA) syöteominaisuuksien satunnaisille osajouksille. [5]

Puunrakennusalgoritmit

Seuraavan ominaisuuden valitsemiseen on useita tapoja:

• Algoritmi ID3 , jossa ominaisuuden valinta tapahtuu informaatiovahvistuksen ( eng.  Gain ) tai Gini-kriteerin perusteella .
• Algoritmi C4.5 (parannettu versio ID3:sta), jossa ominaisuuden valinta perustuu normalisoituun tiedon vahvistukseen ( Gain Ratio ) . 
• CART - algoritmi ja sen muunnelmat — IndCART, DB-CART.
• Automaattinen Chi-Square Interaction Detector (CHAID). Suorittaa monitasoisen erottelun puiden luokittelua laskettaessa; [6]
• MARS: laajentaa päätöspuita digitaalisen tiedonkäsittelyn parantamiseksi.

Käytännössä näiden algoritmien seurauksena puut ovat usein liian yksityiskohtaisia, mikä antaa jatkossa paljon virheitä. Tämä johtuu yliasennusilmiöstä . Puiden vähentämiseksi käytetään karsimista ( englanniksi  pruning ).

Menetelmän edut

Toisin kuin muut tiedonlouhintamenetelmät, päätöspuumenetelmällä on useita etuja:

• Helppo ymmärtää ja tulkita.
• Se ei vaadi erityistä tietojen valmistelua, kuten tietojen normalisointia, valemuuttujien lisäämistä ja puuttuvien tietojen poistamista.
• Pystyy työskentelemään sekä kategoristen että intervallimuuttujien kanssa. (Muut menetelmät toimivat vain datalla, jossa on vain yksi muuttujatyyppi. Esimerkiksi suhdemenetelmää voidaan soveltaa vain nimellismuuttujiin ja hermoverkkomenetelmää vain intervalliasteikolla mitattuihin muuttujiin.)
• Se käyttää "valkoisen laatikon" mallia, eli jos mallissa havaitaan tietty tilanne, niin se voidaan selittää Boolen logiikalla. Esimerkki "mustasta laatikosta" voi olla keinotekoinen hermoverkko , koska saatuja tuloksia on vaikea selittää.
• Mahdollistaa mallin arvioinnin tilastollisilla testeillä. Tämä mahdollistaa mallin luotettavuuden arvioinnin.
• Menetelmä toimii hyvin, vaikka malliin sisältyviä alkuperäisiä oletuksia on rikottu.
• Mahdollistaa suuren tiedon käsittelyn ilman erityisiä valmistelutoimenpiteitä. Tämä menetelmä ei vaadi erityisiä laitteita työskennelläkseen suurten tietokantojen kanssa.

Menetelmän haitat

• Optimaalisen päätöspuun saamisen ongelma on NP-täydellinen ongelma joidenkin optiminäkökohtien kannalta jopa yksinkertaisille ongelmille [7] [8] . Päätöspuualgoritmin käytännön soveltaminen perustuu siis heuristisiin algoritmeihin, kuten "ahne"-algoritmiin, jossa jokaisessa solmussa valitaan paikallisesti ainoa optimaalinen ratkaisu. Tällaiset algoritmit eivät voi taata koko puun optimaalisuutta kokonaisuutena.
• Päätöspuun rakentamisprosessi voi luoda liian monimutkaisia ​​rakenteita, jotka eivät täysin edusta tietoja. Tätä ongelmaa kutsutaan yliasovitukseksi [9] . Sen välttämiseksi on tarpeen käyttää menetelmää "puun syvyyden säätö".
• On käsitteitä, joita mallista on vaikea ymmärtää, koska malli kuvaa niitä monimutkaisesti. Tämä ilmiö voi johtua XOR-, pariteetti- tai multiplekseri-ongelmista. Tässä tapauksessa on kyse kohtuuttoman suurista puista. Tämän ongelman ratkaisemiseen on useita lähestymistapoja, esimerkiksi yritys muuttaa mallin käsitteen esitystapaa (uusien tuomioiden laatiminen) [10] tai käsitettä täydellisemmin kuvaavien ja edustavien algoritmien käyttö (esim. , tilastollisten suhteiden menetelmä, induktiivinen ohjelmointilogiikka).
• Datalle, joka sisältää kategorisia muuttujia suurella tasojoukolla (sulkemiset), niille ominaisuuksille, joilla on enemmän tasoja, annetaan enemmän informaatiopainoa [11] .

Puun syvyyssäätö

Puun syvyyden kuristus on tekniikka, jonka avulla voit pienentää päätöspuun kokoa poistamalla puusta vähän painoisia osia.

Yksi päätöspuualgoritmissa esiin nousevista kysymyksistä on lopullisen puun optimaalinen koko. Näin ollen pieni puu ei välttämättä tallenna yhtä tai toista tärkeää tietoa näytetilasta. On kuitenkin vaikea sanoa, milloin algoritmin tulisi pysähtyä, koska on mahdotonta ennustaa, mikä solmun lisäys vähentää merkittävästi virhettä. Tämä ongelma tunnetaan nimellä "horisonttiefekti". Kuitenkin yleinen puunrajoitusstrategia säilyy, eli solmujen poisto toteutetaan, jos ne eivät anna lisätietoa [12] .

Puun syvyyden säädön pitäisi pienentää harjoituspuumallin kokoa heikentämättä sen ennustetarkkuutta tai ristiinvalidoinnin kautta. Puun syvyyden säätämiseen on monia menetelmiä, jotka eroavat suorituskyvyn optimoinnin mittaamisesta.

Sääntelymenetelmät

Puiden karsiminen voidaan tehdä ylhäältä alas tai alhaalta ylös. Ylhäältä alas - karsiminen alkaa juuresta, alhaalta ylös - puun lehtien lukumäärä vähenee. Yksi yksinkertaisimmista ohjausmenetelmistä on puun rajoitusvirheen vähentäminen. Lehdistä alkaen jokainen solmu korvataan suosituimmalla luokalla. Jos muutos ei vaikuta ennusteen tarkkuuteen, se tallennetaan.

Esimerkki ongelmasta

Oletetaan, että olemme kiinnostuneita siitä, voittaako suosikkijalkapallojoukkueemme seuraavan ottelun. Tiedämme, että tämä riippuu useista parametreista; Niiden kaikkien luetteleminen on toivoton tehtävä, joten rajoitamme vain tärkeimpiin:

• onko vastustaja korkeammalla sijoituksessa;
• pelataanko ottelu kotona;
• jättääkö joku joukkueen johtajista väliin ottelun;
• sataako.

Meillä on tilastoja tästä:

Haluaisin ymmärtää, voittaako joukkueemme seuraavassa pelissä.

Katso myös

• Satunnainen metsä  - luokitin, joka perustuu komiteoiden käyttöön päätöspuista
• Uudelleenkoulutus
• Koneoppiminen  on tekoälymenetelmien luokka , jonka ominaispiirre ei ole ongelman suora ratkaisu, vaan oppiminen soveltamalla ratkaisuja moniin vastaaviin ongelmiin.
• Päätöstaulukko

Muistiinpanot

1. ↑ Quinlan, JR Päätöspuiden induktio  //  Koneoppiminen. - Kluwer Academic Publishers, 1986. - Ei. 1 . - s. 81-106 . Arkistoitu alkuperäisestä 20. tammikuuta 2022.
2. ↑ 1 2 Breiman, Leijona; Friedman, JH, Olshen, RA, & Stone, CJ Luokittelu- ja regressiopuut  . - Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. - ISBN 978-0-412-04841-8 .
3. ↑ Breiman, L. Bagging Predictors  //  Koneoppiminen. - 1996. - Ei. 24 . - s. 123-140 .
4. ↑ Friedman, JH Stokastinen gradientin tehostus  . - Stanfordin yliopisto, 1999.
5. ↑ Hastie, T., Tibshirani, R., Friedman, JH Tilastollisen oppimisen elementit : Tiedon louhinta, päättely ja ennustaminen  . – New York: Springer Verlag, 2001.
6. ↑ Kas ,  G.V. _  C-sarja (Applied Statistics). — Voi. 29 , ei. 2 . - s. 119-127 . - doi : 10.2307/2986296 . Arkistoitu alkuperäisestä 2. huhtikuuta 2022.
7. ↑ Hyafil, Laurent; Rivest, R.L. Optimaalisten binääripäätöspuiden rakentaminen on NP-täydellinen  //  Tietojenkäsittelykirjeet. - 1976. - Voi. 5 , ei. 1 . - s. 15-17 . - doi : 10.1016/0020-0190(76)90095-8 .
8. ↑ Murthy S. Automaattinen päätöspuiden rakentaminen tiedoista: Monitieteinen tutkimus  //  Data Mining and Knowledge Discovery. - 1998. - Ei. 2 . - s. 345-389 . Arkistoitu alkuperäisestä 2. huhtikuuta 2022.
9. ↑ Max Bramer. Tiedonlouhinnan periaatteet  . - Springer, 2007. - ISBN 978-1-84628-765-7 .
10. ↑ Induktiivinen logiikkaohjelmointi  / Horváth, Tamás; Yamamoto, Akihiro, toim. - Springer, 2003. - ISBN 978-3-540-20144-1 .
11. ↑ Deng, H., Runger, G., Tuv, E. Bias of Importance Measures for Multi-valued Attributes and Solutions // Artificial Neural Networks and Machine Learning - ICANN 2011. ICANN 2011. Lecture Notes in Computer Science, vol 6792  ( ( englanti) / Honkela, T., Duch, W., Girolami, M., Kaski, S. (toim.). - Berliini, Heidelberg: Springer, 2011. - ISBN 978-3-642-21737-1 .
12. ↑ Nopea, alhaalta ylöspäin suuntautuva päätöspuun karsiusalgoritmi

Linkit

• Luentomuistiinpanot päätöspuista
• Päätöspuusovelma tarjoaa useita esimerkkitietojoukkoja oppimista ja luokittelua varten

Kirjallisuus

• Levitin A. V. Luku 10. Algoritmien tehorajat: Päätöspuut // Algoritmit. Johdatus kehitykseen ja analyysiin - M .: Williams , 2006. - S. 409-417. — 576 s. — ISBN 978-5-8459-0987-9
• Paklin N.B., Oreshkov V.I. Luku 9. // Liiketoimintaanalytiikka: Datasta tietoon (+CD): Opetusohjelma. 2. painos - Pietari. : Peter, 2013. - S. 428-472. - ISBN 978-5-459-00717-6 .