Решающее дерево (Decision tree)

Это незавершённая статья Автор, вероятно, переобучился и отправился спать. Вы можете помочь, экстраполировав местную информацию.

Решающее дерево (Decision tree) - решение задачи обучения с учителем, основанный на том, как решает задачи прогнозирования человек.

Идея

немного Соколовщины и интуиции

Алгоритм построения

Корень дерева - вся обучающая выборка.

1. Проверить критерий останова алгоритма. Если он выполняется, выбрать для узла выдаваемый прогноз, что можно сделать несколькими способами.
2. Иначе требуется разбить множество на несколько не пересекающихся. В общем случае задаётся решающее правило $Q_t(x)$, принимающее некоторый диапазон значений. Этот диапазон разбивается на R_t непересекающихся множеств, S_1, S_2...S_{R_t}.
3. Множество в узле разбивается согласно выбранному правилу, для каждого узла алгоритм запускается рекурсивно.

Решающие правила

пояснения

• $Q_{t}(x)=x^{i(t)}$
• $S_{t}(j)=\left\{h_{j}\leq x^{i(t)}\leq h_{j+1}\right\}$ для выбранных $h_{1}...h_{j+1}$
• $S_{t}(1)=\left\{(x,v)\leq 0\right\};S_{t}(2)=\left\{(x,v)>0\right\}$ - по сути проверка угла
• $S_{t}(1)=\left\{|x|\leq h\right\};S_{t}(2)=\left\{|x|>h\right\}$

В целом, взять можно любые, но лучше - интерпретируемые, поскольку их легче настраивать.

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

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

$\Delta \mathrm {I} (t)=\mathrm {I} (t)-\sum _{i=1}^{R}\mathrm {I} (t_{i}){\frac {N(t_{i})}{N(t)}}$, где $R$ - на сколько узлов разбивается узел, $t$ - текущий узел, $t_{1}...t_{R}$ - узлы-потомки, получающиеся при выбранном разбиении, $N(t_{i})$ - количество объектов обучающей выборки, попадающие в потомок $i$, $N(t)$ - попавших в текущий узел.

$\Delta \mathrm {I} (t)$ также называется Information gain, ну то есть сколько информации мы получим при таком разбиении. Ну а для выбора решающего правила требуется взять argmax от неё по всевозможным признакам и параметрам семейства решающих правил.

Критерии останова

Выбор прогноза в листе

Методы обработки пропущенных значений

CART-деревья

Реализация решающего дерева - за подробностями милости просим сюда.

Обобщающая способность деревьев

Для любой обучающей выборки существует дерево, которое не будет допускать на нём ни одной ошибки. Подобрать правильный критерий останова бывает затруднительно, поэтому прибегают к стрижке - строят дерево целиком, а затем начинают обрубать узлы с листов. Подробнее.