Этапы построения деревьев решений

При построении деревьев решений особое внимание уделяется следующим вопросам: выбору критерия признака, по которому пойдет разбиение и остановки обучения.

Правило разбиения. Каким образом следует выбрать признак?

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

Были разработаны различные критерии, рассмотрим один из них:

Статистический критерий

Алгоритм CART использует так называемый индекс Gini (в честь итальянского экономиста Corrado Gini), который оценивает "расстояние" между распределениями классов.

(3)

где c – текущий узел, а p_j – вероятность класса j в узле c.

Функции Matlab для работы с деревьями решений

Расчет бинарного дерева классификации наблюдений

T = treefit(X,y) функция предназначена для расчета структуры Т, определяющей параметры бинарного дерева классификации наблюдений для матрицы независимых переменных Х и вектора значений зависимой переменной y. Размерность матрицы Х - n×m, где n - число наблюдений, m - количество независимых переменных. Строки Х соответствуют наблюдениям, столбцы Х - независимым переменным. Число элементов вектора y должно быть равно n. Вектор y может быть задан как вектор строк Выходная переменная T определяет бинарное дерево решений, в котором промежуточные узлы делятся ветвями на 2 возможных решения. В качестве условия выбора направления перехода выступает ограничение на значение независимой переменной.

T = treefit(X,y,'param1',val1,'param2',val2,...) дополнительные параметры 'param1', 'param2',… задаются в виде пары "название параметра, значение" и позволяют задать:

Название параметра - 'param'	Назначение и возможные значения val
'cost'	Параметр позволяет задать погрешность классификации точки -го класса в i-й класс. Значение 'cost' задается в виде матрицы С с размерностью р×р, где р - количество значений (классов) зависимой переменной. По умолчанию C(i,j)=1 если i≠j, и C(i,j)=0 если i=j. Значение 'cost' может быть также задано в виде структуры S с двумя полями: S.group -названия групп; S.cost -матрица погрешностей классификации.
'splitcriterion'	Критерий формирования бинарного дерева решений. Возможные значения 'splitcriterion': 'gdi' - формирование узлов дерева решений выполняется на основе индексов различия Джини; 'twoing' - используется правило максимального соответствия пар значений; 'deviance' - деление выполняется по правилу минимизации максимальной дисперсии. Значение по умолчанию 'splitcriterion'='gdi'.
'priorprob'	Параметр задает априорные вероятности для каждого класса по зависимой переменной y. Значения параметра 'priorprob' определяются вектором. Каждый элемент вектора значений 'priorprob' соответствует априорной вероятности для отдельного класса по y. Значение 'priorprob' может быть задано как структура S с двумя полями: S.group - названия классов по y; S.prob -вектор соответствующих вероятностей.

Пример использования функции treefit

Задача классификации для 4 независимых переменных meas, заданных на числовой шкале, и зависимой переменной species, элементы вектора которой заданы как 3 значения по категориальной шкале.

>> load fisheriris

>> t = treefit(meas,species);

>> treedisp(t);

Графическое представление бинарного дерева классификации наблюдений

treedisp(T) функция позволяет получить графическое представление бинарного дерева для классификации наблюдений на основе входного аргумента T. Параметр Т определяет вид дерева решений и задается как структура. Т является выходным аргументом функции treefit. Результат отображается в графическом окне. Промежуточные узлы дерева решений отмечены метками с условиями выбора относительно значения какой либо независимой переменной. Каждый из конечных узлов дерева решений имеет метку со значением зависимой переменной. Для выбора одной из двух возможных ветвей дерева решений исходящих из промежуточного узла действует правило: левая ветвь соответствует выполнению условия относительно независимой переменной, правая - невыполнению этого условия. Определение значения зависимой переменной начинается с первого промежуточного узла, далее, следуя заданному условию, выбирается правая или левая исходящая ветвь. Аналогично просматриваются последующие узлы до тех пор, пока не будет достигнут последний конечный узел. Символьная метка, соответствующая последнему узлу, является значением зависимой переменной.

Графическое окно бинарного дерева решений.

treedisp(T,'param1',val1,'param2',val2,...) дополнительные параметры 'param1', 'param2',: задаются в виде пары "название параметра, значение" и позволяют определить:

Название параметра 'param'	Назначение и возможные значения val
'names'	Определяет метки независимых переменных в графическом окне. Значения 'names' задаются в виде массива ячеек. Порядок элементов в массиве ячеек должен соответствовать последовательности независимых переменных (столбцов) матрицы Х, передаваемой как входной аргумент функции treefit.
'prunelevel'	Начальный уровень при формировании сокращенного дерева решений. Задается как целое число.

Пример использования функции treedisp

Графическое отображение бинарного дерева при решении задачи классификации. Зависимая переменная задана на категориальной шкале при помощи вектора строк.

load fisheriris

t = treefit(meas,species);

treedisp(t);

Расчет погрешности классификации на основе дерева решений

cost = treetest(T,'resubstitution') функция позволяет рассчитать погрешность классификации, определяемой бинарным деревом решений Т методом обратной подстановки исходных значений зависимой и независимых переменных. Входной аргумент Т формируется с помощью функции treefit. Вероятностью p(i) является отношение числа неверных классификаций по i-му значению зависимой переменной из начального множества данных к объему исходной выборки. Выходная переменная cost является вектором погрешностей для последовательности классификаций, полученных в процессе совращения уровней в исходном бинарном дереве решений Т. Поскольку расчет вектора ошибок основан на исходной выборке по которой была рассчитана структура Т, то элементы вектора cost будут представлять нижнюю границу доверительного интервала погрешности при использовании новой выборки.

cost = treetest(T,'test',X,y) функция предназначена для расчета вектора погрешностей cost классификации, определяемой структурой Т по тестовой выборке X, y. Х матица значений независимых переменных. Столбцы Х соответствуют независимым переменным, строки - наблюдениям. y - вектор значений зависимой переменой. Тестовая выборка и исходная выборка, использованная в treefit при расчете Т, должны быть различны. Количество и порядок независимых переменных, столбцов матриц Х в исходной и тестовой выборках, должно быть одинаковым.

[cost,secost,ntnodes,bestsize] = treetest(...) функция позволяет рассчитать: 1. cost - вектор погрешностей классификации; 2. secost - вектор стандартных ошибок для элементов вектора cost; 3. ntnodes - вектор чисел конечных узлов последовательности сокращенных бинарных деревьев решений; 4. bestsize - скаляр, определяющий оптимальный уровень сокращения полного дерева решений Т. Если bestsize=0, то оптимальным будет полное бинарное дерево решений Т. Величина bestsize должна соответствовать наименьшему бинарному дереву решений, обеспечивающему погрешность классификации, равной минимальной погрешности плюс ее стандартная ошибка.

Пример использования функции treetest

Рассматривается задача классификации. Зависимая переменная задана на категориальной шкале при помощи вектора строк. Погрешность классификации рассчитывается методом обратной подстановки.

load fisheriris

t = treefit(meas,species);

treedisp(t);

cost = treetest(t,'resubstitution')

Расчет зависимой переменной по дереву классификации

YFIT = treeval(T,X) функция позволяет определить значения зависимой переменной YFIT по дереву классификации, параметры которого задаются структурой T, для значений независимых переменных Х. Структура Т формируется как выходной аргумент функции treefit. Х задается как матрица с размерностью n×m, где n - число наблюдений, m - количество независимых переменных. Строки Х соответствуют наблюдениям, столбцы Х - независимым переменным. Выходная переменная YFIT является вектором значений с числом элементов равным n. Значение YFIT(j) рассчитывается согласно строкам X(j,:). YFIT(j) является номером класса, к которому принадлежит точка с координатами X(j,:) в пространстве независимых переменных. Для определения названия класса соответствующего номеру YFIT(j) используется третий выходной аргумент cname.

[YFIT,NODE] = treeval(...) кроме значений зависимой переменной функция возвращает массив номеров узлов NODE соотнесенных c каждой строкой матрицы независимых переменных Х(j,:). Размерность YFIT и NODE будет совпадать. С помощью функции treedisp в интерактивном режиме можно определить номер каждого выделенного в графическом окне узла в бинарном дереве решений.

Пример использования функции treeval

Задача классификации для 4 независимых переменных meas, заданных на числовой шкале, и зависимой переменной species, элементы вектора которой заданы по 3-м классам на категориальной шкале. Определение классов по зависимой переменной определяется для матрицы new_meas.

load fisheriris

t = treefit(meas,species);

new_meas=[5 3.1 1.35 0.32; 4 5.1 2.35 1.32; 2 0.1 3.35 0.22;]

YFIT = treeval(t, new_meas)

Пример совместного использования функций работы с деревом решений:

load fisheriris;

t1 = treefit(meas,species, 'names',{'SL' 'SW' 'PL' 'PW'});

treedisp(t1)

pr=t1(meas(55,:))

Расчет параметров сокращенного бинарного дерева решений

Синтаксис

T2 = treeprune(T1,'level',level)

Описание

T2 = treeprune(T1,'level',level) функция предназначена для получения сокращенной до уровня 'level' иерархической регрессионной модели T2 из начального бинарного дерева решений T1. T1 является выходной переменной функции treefit. Значение параметра 'level' - level должно быть целым положительным числом. Если level=0 то T2 будет получено без сокращения T1. Исходное бинарное дерево решений T1 сокращается по оптимальной схеме, т.е. в первую очередь удаляются промежуточные узлы соответствующие наименьшему уменьшению погрешности иерархической регрессионной модели.