Редактирование: Решающее дерево (Decision tree)

'''Решающее дерево (Decision tree) ''' &mdash; решение задачи [[Обучение с учителем (Supervised learning)|обучения с учителем]], основанный на том, как решает задачи прогнозирования человек. В общем случае &mdash; это k-ичное дерево с ''решающими правилами'' в нелистовых вершинах (узлах) и некотором заключении о целевой функции в листовых вершинах (''прогнозом''). ''Решающее правило'' &mdash; некоторая функция от объекта, позволяющее определить, в какую из дочерних вершин нужно поместить рассматриваемый объект. В листовых вершинах могут находиться разные объекты: класс, который нужно присвоить попавшему туда объекту (в задаче классификации), вероятности классов (в задаче классификации), непосредственно значение целевой функции (задача регрессии).

Чаще всего на практике используются '''двоичные решающие деревья'''.

[[Файл:Decision_tree.png|thumb|center|348px]]

== Алгоритм построения ==
В корне дерева &mdash; рассматриваем всю [[Анализ данных|обучающую выборку]].
# Проверить критерий останова алгоритма. Если он выполняется, выбрать для узла выдаваемый прогноз, что можно сделать несколькими способами.
# Иначе требуется разбить множество на несколько не пересекающихся. В общем случае в вершине <math>t</math> задаётся решающее правило <math>Q_t(x)</math>, принимающее некоторый диапазон значений. Этот диапазон разбивается на <math>R_t</math> непересекающихся множеств объектов, <math>S_1, S_2, \dots, S_{R_t}</math>, где <math>R_t</math> &mdash; количество потомков у вершины, а каждое <math>S_i</math> &mdash; это множество объектов, попавших в <math>i</math>-го потомка.
# Множество в узле разбивается согласно выбранному правилу, для каждого узла алгоритм запускается рекурсивно.

== Решающие правила ==
<nowiki> </nowiki>Чаще всего в качестве <math>Q_t(x)</math> берут просто один из признаков, то есть <math>x^{i(t)}</math>.

Традиционные разбиения на диапазоны:

* <math>S_t(j) = \left \{x \in \mathbb{X}: h_j \le x^{i(t)} \le h_{j+1}\right \}</math> для выбранных <math>h_1, \dots, h_{j+1}</math>
* <math>S_t(1) = \left \{x \in \mathbb{X}: \langle x,v \rangle \le 0\right \}; S_t(2) = \left \{x \in \mathbb{X}: \langle x,v \rangle > 0\right \}</math> &mdash; по сути проверка угла.
* <math>S_t(1) = \left \{x \in \mathbb{X}: \rho (x, x_0) \le h\right \}; S_t(2) = \left\{x \in \mathbb{X}: \rho (x, x_0) > h\right \}</math>, где расстояние <math>\rho</math> определено в некотором метрическом пространстве (например,<math>\rho (x, y) = |x - y|</math>).
* <math>S_t(1) = \left \{x \in \mathbb{X}: x^{i(t)} \le h\right \}; S_t(2) = \left \{x \in \mathbb{X}: x^{i(t)} > h\right \}</math> &mdash; '''предикаты''', <math>\langle x, v \rangle </math> &mdash; скалярное произведение векторов.

В целом, взять можно любые решающие правила, но лучше &mdash; [[Интерпретируемость|интерпретируемые]], поскольку их легче настраивать. Особого смысла брать что-то сложнее предикатов нет, так как уже с их помощью можно получить дерево со 100%-й точностью на обучающейся выборке (но при этом и скорее всего переобучиться).

=== Выбор оптимального решающего правила ===
Считаем, что решаем задачу многоклассовой классификации или регрессии в <math>R</math>-ичном дереве.

Обычно для построения дерева выбирается целое семейство решающих правил. Чтобы найти среди них оптимальное для каждого конкретного узла, требуется ввести некоторый критерий оптимальности. Для этого вводят некоторую меру <math>\Iota(t)</math> измерения того, насколько разбросаны объекты (регрессия) или перемешаны классы (классификация) в некотором узле <math>t</math>. Эта мера называется [[Критерий информативности (Impurity function)|критерием информативности]].

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

<math>\Delta\Iota(X_t, t) = \Iota(X_t, t) - \sum_{i=1}^R \Iota(X_{t_i}, t_i)\frac{N(t_i)}{N(t)}</math>, где <math>R</math> &mdash; на сколько узлов разбивается узел, <math>t</math> &mdash; текущий узел, <math>t_1, \dots, t_R</math> &mdash; узлы-потомки, получающиеся при выбранном разбиении, <math>N(t_i)</math> &mdash; количество объектов обучающей выборки, попадающие в потомок <math>i</math>, <math>N(t)</math> &mdash; попавших в текущий узел, <math>X_{t_i}</math> &mdash; объекты, попавшие в <math>t_i</math>-ую вершину.

<math>\Delta\Iota(X_t, t)</math> также называется '''Information gain''', то есть сколько информации мы получим при таком разбиении. Для выбора решающего правила требуется взять argmax от неё по всевозможным признакам и параметрам семейства решающих правил. При таком взятии мы как раз и получим оптимальное разбиение множества объектов в текущей вершине.

== Критерии останова ==
[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem04_trees.pdf Семинары Соколова], стр. 6

* Ограничение максимальной глубины дерева.
* Ограничение минимального числа объектов в листе.
* Ограничение максимального количества листьев в дереве.
* Останов в случае, если все объекты в вершине относятся к одному классу.
* Требование, что Information gain при дроблении улучшался как минимум на <math>s</math> процентов.

== Стрижка ==
Для любой обучающей выборки существует дерево, которое не будет допускать на нём ни одной ошибки. Подобрать правильный критерий останова бывает затруднительно, поэтому прибегают к стрижке &mdash; строят дерево целиком, а затем начинают обрубать узлы с листов.
=== Стрижка по валидационной выборке ===
[https://yandexdataschool.ru/edu-process/courses/machine-learning#item-3 Лекции Воронцова], 63-я минута.

Рассмотрим бинарное решающее дерево на примере задачи классификации.

Выделим валидационной выборку порядка половины размера всей выборки (или можно, например, разделить выборку на 2 части следующим образом: <math>\tfrac{2}{3}</math> всей выборки оставить в качестве тренировочной, <math>\tfrac{1}{3}</math> &mdash; в качестве валидационной)

Построим дерево по тренировочной выборке. Пропустим через построенное дерево валидационную выборку и рассмотрим любую внутреннюю вершину <math>t</math> и её левую и правую вершины <math>L_t, R_t</math>. Если до <math>t</math> не дошло ни одного объекта из валидационной выборки, то говорим, что эта вершина (и все её поддеревья) незначимые и делаем из <math>t</math> листовую (ставим в качестве предиката мажоритарный класс в этой вершине по тренировочной выборке). Если до <math>t</math>
дошли объекты из валидационной выборки, то рассмотрим следующие 3 величины:

# [[Критерий информативности (Impurity function)#Ошибка классификации|Число ошибок классификации]] поддеревом из вершины <math>t</math>
# [[Критерий информативности (Impurity function)#Ошибка классификации|Число ошибок классификации]] поддеревом из вершины <math>L_t</math>
# [[Критерий информативности (Impurity function)#Ошибка классификации|Число ошибок классификации]] поддеревом из вершины <math>R_t</math>

Если в 1) [[Критерий информативности (Impurity function)#Ошибка классификации|Число ошибок классификации]] поддеревом из вершины <math>t</math> равно 0, то значит делаем из <math>t</math> листовую с соответствующим прогнозом для класса.

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

# Ничего не делать
# Заменить дерево из вершины <math>t</math> деревом из вершины <math>L_t</math>
# Заменить дерево из вершины <math>t</math> деревом из вершины <math>R_t</math>

=== Cost-complexity pruning ===
[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem04_trees.pdf Семинары Соколова], стр. 6 &ndash; 7.

Обозначим дерево, полученное в результате работы жадного алгоритма, через <math>T_0</math>. Поскольку в
каждом из листьев находятся объекты только одного класса, значение функционала <math>R(T)</math> будет минимально на самом дереве <math>T_0</math> (среди всех поддеревьев). Однако данный функционал характеризует лишь качество дерева на обучающей выборке, и
чрезмерная подгонка под нее может привести к переобучению. Чтобы преодолеть эту
проблему, введем новый функционал <math>R_\alpha(T)</math>, представляющий собой сумму исходного функционала <math>R(T)</math> и штрафа за размер дерева:

<math>
\begin{array}{lr}
R_\alpha(T) = R(T) + \alpha|T| & (*) \\
\end{array}
</math>

где <math>|T |</math> &mdash; число листьев в поддереве <math>T</math> , а <math>\alpha > 0</math> &mdash; параметр. Это один из примеров [[ссылка на статью про регуляризацию|регуляризованных]] критериев качества , которые ищут баланс между качеством
классификации обучающей выборки и сложностью построенной модели. В дальнейшем мы много раз будем сталкиваться с такими критериями.
Можно показать, что существует последовательность вложенных деревьев с
одинаковыми корнями:
<math>T_K \subset T_{K-1} \subset \dots \subset T_0</math> ,
(здесь <math>T_K</math> &mdash; тривиальное дерево, состоящее из корня дерева <math>T_0</math>), в которой каждое
дерево <math>T_i</math> минимизирует критерий <math>(*)</math> для <math>\alpha</math> из интервала <math>\alpha \in [\alpha_i , \alpha_{i + 1})</math>, причем
<math>0 = \alpha_0 < \alpha_1 < \dots < \alpha_K < +\infty</math>.
Эту последовательность можно достаточно эффективно найти путем обхода дерева.
Далее из нее выбирается оптимальное дерево по отложенной выборке или с помощью
кросс-валидации.

== Выбор прогноза в листе ==
* Самый простой способ &mdash; взять самый часто встречающийся класс среди объектов обучающей выборки, попавших в этот лист, для классификации или среднее целевых функций этих объектов для регрессии.

* В задачах классификации c <math>k</math> классами в листе <math>t</math> также можно хранить вероятности классов &mdash; например, по классической вероятности: <math>\mathbb{P}(y=y_i|x) = \dfrac{\#{X_t}}{N(t)}</math>, где <math>\mathbb{Y} = \{y_1, y_2, \dots, y_k\}</math> &mdash; классы. Более подробно, как в таком случае выбирать класс, описано в [[Решающее дерево (Decision tree)#Метод обработки пропущенных значений|обработке пропусков]]

* Если задана [[Матрица штрафов (Сost matrix)|матрица штрафов]], то есть в случае несимметричных потерь, можно минимизировать штраф и взять в качестве класса в листе <math> \hat{y} </math>:
<math>\hat{y} = \underset{y \in \mathbb{Y}}{\operatorname{argmin}} \sum_{i} \lambda_{y_{i}y}</math>, где <math>\lambda_{y_iy}</math> &mdash; элементы матрицы штрафов.

* В регрессии &mdash; использовать [[Функция потерь (Loss function)|функцию потерь]], то есть:

<math>\hat y = \underset{y \in \mathbb{Y}}{\operatorname{argmin}}\sum_{i} L(y, y_i) </math>

Выбор функции потерь в общем случае является параметром алгоритма.

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

Сложность прогнозирования для одного объекта для полностью построенного дерева &mdash; <math>O(h)</math>, где <math>h</math> &mdash; высота дерева. Вообще говоря, дерево может быть несбалансированным, поэтому оценка в <math>O(\log N)</math>, где <math>N</math> &mdash; размер тренировочной выборки, не гарантируется.

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

=== Пропуск пропущенных значений ===
[https://yandexdataschool.ru/edu-process/courses/machine-learning#item-3 Лекции Воронцова], 59-я минута.

{{Рецензия|Имя = Сергей Иванов|Комментарий = Вроде в билетах этого нет, но вполне вопрос.}}

При обучении дерева объекты с пропущенными значениями у признака, по которому идет разбиение, игнорируются: <math>\Delta\Iota(X_t, t) \approx \dfrac{\#\{x \in X_t: x_{i(t)} \mbox{not missing}\}}{N(t)} \cdot \Delta\Iota(\{x \in X_t : x_{i(t)} \mbox{not missing}\}, t) </math>

При построении прогноза при необходимости разбить подвыборку в вершине <math>t</math> по отсутствующему признаку происходит следующая процедура: будем как бы предполагать, что этот признак принимает случайное значение. Определим по обучающей выборке вероятности, с которой новый объект попадёт к каждому потомку &mdash; <math>w_1, w_2, \dots, w_R, w_i = \dfrac{N(t_i)}{N(t)}</math>. Затем отправим объект независимо к каждому потомку, получим прогнозы <math>y_1, y_2, \dots, y_R</math>. В случае регрессии это будут непосредственно значения целевой функции, в случае классификации &mdash; вероятности принадлежности какому-то зафиксированному классу <math>y</math>(который, как будет видно ниже, надо перебирать): <math>y_i = \mathbb{P}(y|x, t_i)</math>

Дальше можно поступать образом, схожим с выбором прогноза в листе: так, для регрессии можно просто объединить отклики с вероятностями в качестве весов, <math>\hat{y} = w_{1}y_{1} + \dots + w_{R}y_{R}</math>.

Пусть <math>t_0</math> &mdash; корень дерева.
В случае классификации <math>\hat{y} = \underset{y \in \mathbb{Y}}{\operatorname{argmax}}  \mathbb{P}(y|x, t_0) \overset{\mbox{def}}{=} \underset{y \in \mathbb{Y}}{\operatorname{argmax}} \sum_{i = 1}^R w_{i}\mathbb{P}(y|x, t_i)</math>

Такой алгоритм работы с пропущенными значениями используется в [[какая-то ссылка|ID3]], [[какая-то ссылка|C4.5]].

=== Суррогатные разбиения ===

Находим другой признак, по которому разбиение будет максимально похожим.
Выкидываем те объекты, по которому по данному признаку есть пропущенные значения, делаем разбиение. Ищем другой признак (видимо, предполагаем, что по нему нет пропущенных значений, либо сразу выкидывать объекты с пропущенными значениями и по первому приведенному признаку и по второму), берем максимально похожее разбиение на изначальное. Например, можно сравнивать как можно большее пересечение левых и правых поддеревьев (в случае бинарного дерева).

Такой алгоритм работы с пропущенными значениями используется в [[CART (Classification and regression tree)|CART]]

== Работа с категориальными признаками ==
{{Кластеризовать}}{{Рецензия|Имя = Сергей Иванов|Комментарий = Возможно, часть информации здесь не относится к деревьям; следует вынести в отдельную статью по работе с категориальными признаками}}

=== One-hot кодирование ===

Из вершины <math>t</math> делаем столько детей, сколько уникальных значений у категориального признака.

При таком подходе размер дерева увеличивается <math>\Rightarrow</math> увеличивается риск переобучения.

=== Перевод категориальных в вещественные ===

[https://github.com/esokolov/ml-course-msu/blob/master/ML16/lecture-notes/Sem04_trees.pdf Семинары Соколова], стр. 8

Пусть категориальный признак <math>x_j</math> имеет
множество значений <math>Q = \{u_1, \dots, u_q\}, |Q| = q</math>. Разобьем множество значений на два непересекающихся подмножества: <math>Q = Q_1 \bigsqcup Q_2</math> , и определим предикат как индикатор
попадания в первое подмножество: <math>\beta(x) = \mathbb{I}[x_j \in Q_1 ]</math>. Таким образом, объект будет попадать в левое поддерево, если признак <math>x_j</math> попадает в множество <math>Q_1</math> , и в правое поддерево в противном случае. Основная проблема заключается в том, что для построения оптимального предиката нужно перебрать <math>2^{q-1} - 1</math> вариантов разбиения,что может быть не вполне возможным.

Оказывается, можно обойтись без полного перебора в случаях с бинарной классификацией и регрессией. Обозначим через<math> R_m (u)</math> множество объектов, которые
попали в вершину <math>m</math> и у которых <math>j</math>-й признак имеет значение <math>u</math>; через <math>N_m(u)</math> обозначим количество таких объектов.
В случае с бинарной классификацией упорядочим все значения категориального признака на основе того, какая доля объектов с таким значением имеет класс <math>+1</math>:

<math>
\dfrac{1}{N_m(u_{(1)})} \sum_{x_i \in R_m(u_{(1)})} \mathbb{I}[y_i = +1] \le \dots \le \dfrac{1}{N_m(u_{(q)})} \sum_{x_i \in R_m(u_{(q)})} \mathbb{I}[y_i = +1]
</math>

после чего заменим категорию <math>u_{(i)}</math> на число <math>i</math>, и будем искать разбиение как для вещественного признака. Можно показать, что если искать оптимальное разбиение по
[[Критерий информативности (Impurity function)#Критерий Джини|критерию Джини]] или [[Критерий информативности (Impurity function)#Энтропия|энтропийному критерию]], то мы получим такое же разбиение,
как и при переборе по всем возможным <math>2^{q-1} - 1</math> вариантам.
Для задачи регрессии с MSE-функционалом это тоже будет верно, если упорядочивать значения признака по среднему ответу объектов с таким значением:

<math>
\dfrac{1}{N_m(u_{(1)})} \sum_{x_i \in R_m(u_{(1)})} y_i \le \dots \le \dfrac{1}{N_m(u_{(q)})} \sum_{x_i \in R_m(u_{(q)})} y_i 
</math>

== CART-деревья ==
Реализация решающего дерева &mdash; за подробностями [[CART (Classification and regression tree)|милости просим сюда]].

== Обобщающая способность деревьев ==
Для любой обучающей выборки существует дерево, которое не будет допускать на нём ни одной ошибки. Подобрать правильный критерий останова бывает затруднительно, поэтому прибегают к стрижке &mdash; строят дерево целиком, а затем начинают обрубать узлы с листов. [[CART (Classification and regression tree)#Стрижка|Подробнее]].