Päätöspuualgoritmit

Päätöspuualgoritmit ovat koneoppimisen menetelmiä, joita käytetään luokittelu- ja regressio-ongelmien ratkaisemiseen. Ne rakentavat puumaisen rakenteen, jossa jokainen sisäsolmu edustaa testausominaisuutta, jokainen haara edustaa testin tulosta ja jokainen lehtisolmu edustaa päätöstä eli luokkaa tai numeerista arvoa.

Algoritmin perusajatus on jakaa data rekursiivisesti pienempiin osajoukkoihin siten, että kukin jako perustuu johonkin ominaisuuteen. Jaoilla pyritään maksimoimaan samankaltaisuus kunkin osajoukon sisällä tai minimoimaan samankaltaisuus eri osajoukkojen välillä. Yleisiä kriteerejä jakojen tekemiselle ovat informaatiovoitto ja Gini-epäpuhtaus.

Yleisimpiä päätöspuualgoritmeja ovat CART (Classification and Regression Trees), ID3 (Iterative Dichotomiser 3) ja C4.5. CART luo binääripuita, kun taas ID3 ja C4.5 voivat luoda monihaaraisia puita. C4.5 on ID3:n jatkokehitys, joka käsittelee paremmin puuttuvia arvoja ja numeerisia ominaisuuksia.

Päätöspuut ovat helposti tulkittavia ja visuaalisesti esitettäviä, mikä tekee niistä suosittuja monissa sovelluksissa. Niillä on kuitenkin taipumus ylisovittua dataan, erityisesti jos puu kasvaa liian syväksi. Ylisovittumista voidaan ehkäistä menetelmillä kuten karsiminen (pruning) tai satunnaismetsien (random forests) käyttö, jotka yhdistävät useita päätöspuita paremman yleistyskyvyn saavuttamiseksi.