Hogyan zajlik a döntési fa építése? Milyen felosztási kritériumokat ismer?

A döntési fa az eredeti adathalmaz egymást követő felosztásával épül fel, amelyek a fa csomópontjaivá válnak. Minden lépésben kiválasztunk egy jellemzőt és egy küszöbértéket (számértékű jellemzők esetén), amelyek alapján az adatokat részekre osztjuk, hogy maximalizáljuk az eredményül kapott alhalmazok homogénségét (tisztaságát) a célszó változóhoz viszonyítva.

Fő felosztási kritériumok:

• Gini-index (Gini-impureitás) — méri annak a valószínűségét, hogy egy véletlenszerűen kiválasztott objektum tévesen lesz osztályozva, ha véletlenszerűen osztályozzuk a halmaz osztályeloszlása szerint. Minél alacsonyabb, annál jobb.

• Információs nyereség (Information Gain) — az entrópia különbsége a felosztás előtt és után. Minél nagyobb az információs nyereség, annál jobb a felosztás.

• Információs nyereség aránya (Information Gain Ratio) — az információs nyereség módosítása, amely figyelembe veszi az alhalmazok számát és méretét, hogy elkerülje a túlzott elfogultságot a sok értékkel rendelkező jellemzők irányába.

• Variancia csökkenés (Variance reduction) — regresszió esetén használják, minimalizálja a célszó változó értékeinek szórását az alhalmazokban.

Egyszerű felosztási példa jellemző szerint:

# Pszeudokód a legjobb felosztás kiválasztásához
best_gain = 0
best_feature = None
for feature in features:
    for threshold in possible_thresholds(feature):
        left, right = split(data, feature, threshold)
        gain = information_gain(data, left, right)
        if gain > best_gain:
            best_gain = gain
            best_feature = (feature, threshold)