ДЕРЕВЬЯ РЕШЕНИЙ презентация

каждому объекту соответствует единственный узел, дающий решение

ДЕРЕВЬЯ РЕШЕНИЙ

форме, вместо них мы можем хранить дерево решений, которое содержит точное описание объектов.
Классификация: Деревья решений отлично справляются с задачами классификации, т.е. отнесения объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения.
Регрессия: Если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от независимых(входных) переменных. Например, к этому классу относятся задачи численного прогнозирования(предсказания значений целевой переменной).

Пусть через {C1, C2, … Ck} обозначены классы (значения метки класса), тогда существуют 3 ситуации:
1. Множество T содержит один или более примеров, относящихся к одному классу Ck. Тогда дерево решений для Т – это лист, определяющий класс Ck;
2. Множество T не содержит ни одного примера, т.е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества отличного от T, скажем, из множества, ассоциированного с родителем;

случае следует разбить множество T на некоторые подмножества. Для этого выбирается один из признаков, имеющий два и более отличных друг от друга значений O1, O2, … On. T разбивается на подмножества T1, T2, … Tn, где каждое подмножество Ti содержит все примеры, имеющие значение Oi для выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу.

АЛГОРИТМЫ деревьев решений CART, C4.5, NewId, ITrule, CHAID, CN2 CART (Classification and Regression Tree) – это алгоритм построения бинарного дерева решений – дихотомической классификационной модели. Каждый узел дерева при разбиении имеет только двух потомков. Как видно из названия алгоритма, решает задачи классификации и регрессии.
C4.5 – алгоритм построения дерева решений, количество потомков у узла не ограничено. Не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации.

с конкретным классом, т.е. один из атрибутов должен быть выбран в качестве метки класса.
3. Дискретные классы. Классы должны быть дискретными, т.е. иметь конечное число значений.

- Пусть нам задано множество примеров T, где каждый элемент этого множества описывается m атрибутами.
Количество примеров в множестве T будем называть мощностью этого множества и будем обозначать |T|.
Пусть метка класса принимает следующие значения C1, C2 … Ck.

- Пусть мы имеем проверку X, которая принимает n значений A1, A2 … An.
Тогда разбиение T по проверке X даст нам подмножества T1, T2 … Tn, при X равном соответственно A1, A2 … An.

одному и тому же классу Cj. Тогда вероятность того, что случайно выбранный пример из множества S будет принадлежать к классу Cj

(1)

(2)

(3)

Обозначим их {v1, v2 … vn}.

{v1, v2 … vi}, {vi+1, vi+2 … vn}.

ПОРОГ

GAIN (X)=Info (T)- InfoX (T)

- [[ 9\27 * log(9\27)]+[18\27*log(18\27)]]=
=0.274

Info(T2)= 0

InfoX(T)= [27\37*0.274]+ 10\37*0 = 0.199

4. Критерий

GAIN (X)=Info (T)- InfoX (T)

атрибута. Выбирается условие для разбиения в узле, где GAIN = max

Идентично просчитываются все потенциальные пороговые значения других атрибутов.

Выбирается тот атрибут у которого найдено максимальное значение критерия GAIN и в качестве проверки в узле принимается это пороговое значение.

Долгота > 67.75

TROP, 27

BARO, 10

no

Долгота > 62.5

BARO, 9

TROP, 18

A. Обозначим через U количество неопределенных значений атрибута A. Изменим формулы (2) и (3) таким образом, чтобы учитывать только те примеры, у которых существуют значения по атрибуту A.

(7)

(8)

(9)

выбран на основе модифицированного критерия (8).

Если пример из множества T с известным выходом Oi ассоциирован с подмножеством Ti, вероятность того, что пример из множества Ti равна 1. Пусть тогда каждый пример из подмножества Ti имеет вес, указывающий вероятность того, что пример принадлежит Ti. Если пример имеет значение по атрибуту A, тогда вес равен 1, в противном случае пример ассоциируется со всеми множествами T1, T2 … Tn, с соответствующими весами