НазваниеОписание ОбъектПример, шаблон, наблюдение АтрибутПризнак, независимая переменная, свойство Метка класса Зависимая переменная, целевая переменная, признак определяющий класс объекта УзелВнутренний узел дерева, узел проверки ЛистКонечный узел дерева, узел решения Проверка (test) Условие в узле Деревья решений – это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение ДЕРЕВЬЯ РЕШЕНИЙ

Описание данных: Деревья решений позволяют хранить информацию о данных в компактной форме, вместо них мы можем хранить дерево решений, которое содержит точное описание объектов. Классификация: Деревья решений отлично справляются с задачами классификации, т.е. отнесения объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения. Регрессия: Если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от независимых(входных) переменных. Например, к этому классу относятся задачи численного прогнозирования(предсказания значений целевой переменной). Пусть через {C 1, C 2, … C k } обозначены классы (значения метки класса), тогда существуют 3 ситуации: 1. Множество T содержит один или более примеров, относящихся к одному классу C k. Тогда дерево решений для Т – это лист, определяющий класс C k ; 2. Множество T не содержит ни одного примера, т.е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества отличного от T, скажем, из множества, ассоциированного с родителем;

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

ДЕРЕВЬЯ РЕШЕНИЙ (CART) 1.Описание атрибутов. 2.Определенные классы. Каждый пример должен быть ассоциирован с конкретным классом, т.е. один из атрибутов должен быть выбран в качестве метки класса. 3. Дискретные классы. Классы должны быть дискретными, т.е. иметь конечное число значений. - Пусть нам задано множество примеров T, где каждый элемент этого множества описывается m атрибутами. -Количество примеров в множестве T будем называть мощностью этого множества и будем обозначать |T|. -Пусть метка класса принимает следующие значения C 1, C 2 … C k. - Пусть мы имеем проверку X, которая принимает n значений A 1, A 2 … A n. Тогда разбиение T по проверке X даст нам подмножества T 1, T 2 … T n, при X равном соответственно A 1, A 2 … A n.

Пусть freq(C j, S) – количество примеров из некоторого множества S, относящихся к одному и тому же классу C j. Тогда вероятность того, что случайно выбранный пример из множества S будет принадлежать к классу C j называется энтропией множества T.энтропией (1) (2) (3)

(4) Критерий для выбора атрибута Пусть числовой атрибут имеет конечное число значений. Обозначим их {v 1, v 2 … v n }. {v 1, v 2 … v i }, {v i+1, v i+2 … v n }. ПОРОГ GAIN (X)=Info (T)- Info X (T)

ДАННЫЕ: Barotrop.sta 3v LONGITUDLATITUDECLASS BARO BARO BARO BARO BARO BARO BARO BARO BARO TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP TROP BARO BARO BARO BARO BARO BARO BARO BARO BARO BARO 1.Выбираю точку разрыва = (67,50+68,00)/2=67,75 2. Ищу = - [[(19/37)*log(19/37)]+[(18/37)*log(18/37)]]= Ищем Info X (T)= [|T 1 |\|T|*info(T 1 )]+[|T 2 \|T|*info(T 2 )|] Info(T 1 )= - [[ 9\27 * log(9\27)]+[18\27*log(18\27)]]= =0.274 Info(T 2 )= 0 Info X (T)= [27\37*0.274]+ 10\37*0 = Критерий GAIN (X)=Info (T)- Info X (T)

GAIN (X)=0,299-0,199=0,1 Далее такой же подход ко всем потенциальным пороговым значениям 1 атрибута. Выбирается условие для разбиения в узле, где GAIN = max Идентично просчитываются все потенциальные пороговые значения других атрибутов. Выбирается тот атрибут у которого найдено максимальное значение критерия GAIN и в качестве проверки в узле принимается это пороговое значение. Долгота > TROP, 27BARO, 10 no Долгота > 62.5 BARO, 9 TROP, 18

(5) (6)

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

Пусть теперь проверка X с выходными значениями O 1, O 2 … O n выбран на основе модифицированного критерия (8). Если пример из множества T с известным выходом O i ассоциирован с подмножеством T i, вероятность того, что пример из множества T i равна 1. Пусть тогда каждый пример из подмножества T i имеет вес, указывающий вероятность того, что пример принадлежит T i. Если пример имеет значение по атрибуту A, тогда вес равен 1, в противном случае пример ассоциируется со всеми множествами T 1, T 2 … T n, с соответствующими весами