Beslutningstræ

Et beslutningstræ opdeler feature-rummet i akseparallelle områder ved gentagen binær opsplitning. I hver knude gennemsøger algoritmen alle features og tærskler efter den opdeling, der mindsker et urenhedsmål mest: Gini-urenhed eller entropi (informationsgevinst) ved klassifikation og middelkvadratfejl ved regression. Bladene forudsiger flertalsklassen, klasseandelene eller gennemsnittet af målværdien for deres træningseksempler. At finde det optimale træ er NP-hårdt, så alle praktiske algoritmer er grådige og arbejder oppefra og ned.

De vigtigste algoritmefamilier er ID3 (Quinlan, 1986), der brugte informationsgevinst på kategoriske features; efterfølgeren C4.5, der håndterer numeriske features med tærskler og beskærer ud fra fejlskøn; og CART (Breiman, Friedman, Olshen og Stone, 1984), der bygger rent binære træer til både klassifikation og regression og beskærer efter omkostningskompleksitet. scikit-learn implementerer en optimeret udgave af CART.

Træer uden begrænsninger bliver ved med at dele, til bladene er rene, og lærer dermed træningssættet udenad, et skoleeksempel på overtilpasning med høj varians: Små ændringer i data kan give et helt andet træ. Midlerne er forhåndsbeskæring (maksimal dybde, mindste antal eksempler pr. blad eller opdeling, mindste fald i urenhed) og efterbeskæring som CART's minimal cost-complexity pruning, indstillet med krydsvalidering. Træer kræver ingen skalering af features, håndterer blandede datatyper og fanger naturligt samspil, men deres akseparallelle, trinvist konstante forudsigelser passer dårligt til bløde eller skrå grænser og kan ikke ekstrapolere ud over træningsområdet.

Et lavt træ er en af de få modeller, hvis fulde beslutningslogik et menneske kan læse, og derfor bruges det som fortolkelig model og som surrogat til at forklare black box-modeller. Urenhedsbaserede feature-vigtigheder fra træer er billige, men favoriserer features med mange forskellige værdier; permutationsvigtighed er den sædvanlige kontrol. Ustabiliteten er også grunden til, at ensembler virker så godt: Random forests tager gennemsnittet af mange dekorrelerede træer for at mindske variansen, og gradient boosting lægger mange lave træer til efter hinanden for at mindske bias.