Как да се изгради дърво на решенията

Да предположим, че се дава обучение набор Т, съдържащ обекти (като примери), всеки от които се характеризира м атрибути (атрибути), една от които сочи към обект, който принадлежи към клас.

Идеята за изграждане на множество дървета на решения Т, изразена първо Хънт, Р. присъства на Kuinlenu (R. Quinlan).

Нека през 1. C2. Ck> означават клас (етикетите клас стойност), след което има 3 ситуации:

T комплект включва един или повече примери, принадлежащи към същия клас Ck. След това решение дървото за T - списък, който определя клас Ck;

множество T не съдържа един пример, че празен сет. Тогава е обратно лист, и класа, свързани с лист е избран от друг набор от отлично на Т, например, от множеството свързани с майка;

избран T съдържа примери от различни класове. В този случай, се прекъсне серия T до известна подгрупа. За тази цел се избира един от атрибутите, имащи два или повече различни стойности O1. O2. Включено. Т е разделена на подгрупи Т1. T2. Tn. Ti, където всеки подгрупа съдържа всички примери, които имат Oi стойност за избраната функция. Тази процедура се рекурсивно да продължи толкова дълго, колкото крайно множество ще се състои от примерите, отнасящи се до един и същи клас.

Горната процедура е в основата на много съвременни алгоритми за конструиране на дърво на решенията, това е познат метод все още се нарича отделяне и улавяне (разделяй и владей). Очевидно е, че с помощта на този метод, изграждане на дърво на решенията се случва от горе до долу.

Тъй като всички обекти са предварително определен с класовете, известни на нас, процесът на изграждане на дърво на решенията се нарича обучение с учител (под надзора обучение). Учебният процес се нарича още индуктивен обучение или индукция дърво (индукция дърво).

Днес има значителен брой алгоритми, които прилагат Решение КОШНИЦАТА дървета, C4.5, NewId, ITrule, CHAID, CN2 и т.н. Но най-широко популярни и получи следните два критерия:

КОШНИЦАТА (класификация и регресия Tree) - алгоритъм за построяване на двоично решение дърво - дихотомна модел класификация. Всеки възел на дървото в разделянето има само две деца. Както името на алгоритъма решава проблемите на класификация и регресия.

C4.5 - алгоритъм за изграждане на дърво на решенията, броят на наследници на възела не е ограничено. Не е в състояние да работи с цел поле непрекъснато, следователно, само решава проблема на класификация.

Повечето от известните алгоритми са "алчни алгоритъм". Ако времето е избран атрибут и разделяне на подмножества са направени по него, алгоритъмът не може да се върнете и да изберете друг атрибут, който ще даде най-доброто разделение. И така, на етапа на това дали избрания атрибут няма да се каже, в крайна сметка, оптималното дял.

Етапи на дърво на решенията

При изграждането на дърво на решенията се фокусира върху следните въпроси: Критерии за избор на атрибути, на които ще се разпределят, спират обучение и клони към крайния срок. Помислете за тези въпроси в ред.