4.5.3. Изрязване на клони.
Редица проблеми, генерирани от измерението на проблема, могат значително да намалят качеството на полученото решение. Една от тях е свързана с факта, че частта от дървото, която завършва с етикета на класа, може да бъде генерирана от примери, които са „шумни“ в смисъл, че елементът е избран по грешен начин.
Поради всички тези причини понякога е полезно да съкратите изграденото дърво, като отрежете някои клони. По принцип са възможни два подхода за резитба: онлайн интерактивна и последваща резитба. Онлайн подрязването предотвратява растежа на дървото, когато стойността на функцията за полезност, свързана с разделянето на набор от примери, падне под определен праг. Постредукция ви позволява да подрязвате някои клони на дървото, след като е завършено.
Един от най-известните редукционни подходи е разработен от И. Братко [35]. И. Братко предложи рязане на клони по такъв начин, че да се сведе до минимум общата очаквана класификационна грешка на нови примери. За тази цел се изчислява класификационната грешка за всеки възел в дървото. В листата на дървото се използват методи на теорията на вероятностите за оценка на грешката. Например, можете да използвате формулата на Лаплас.
За възли, които не са листа на дървото на решенията, класификационната грешка се изчислява като претеглената сума от класификационните грешки на поддърветата на всеки от възлите. Приема се, че теглото е равно на относителната честота на примерите, "предадени" от възела към съответните поддървета. След това класификационната грешка във възел "нелист" се оценява за случая на отрязване на клоните, произтичащи от него, така че той да стане лист. Ако тази оценка е по-малка от предишната, тогава съответните поддървета се съкращават. Този процес се разпространява от основата на дървото до листата му, докато оценките за грешка намалеят.
Ползи от постредукцияв сравнение с интерактивните методи, те са, че с последваща редукция могат да бъдат взети под внимание глобалните свойства на класификационното дърво, докато с интерактивно съкращаване минималната грешка може да се окаже локална. Възможни са и комбинирани подходи.