Участник:Matfu/Решающие деревья

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

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

Деревья решений являются одним из самых популярных алгоритмов машинного обучения благодаря их понятности и простоте.

Решающие деревья хорошо описывают процесс принятия решения во многих ситуациях. Например, когда клиент приходит в банк и просит выдать ему кредит, то сотрудник банка начинает проверять условия:

1. Какой возраст у клиента? Если меньше 18, то отказываем в кредите, иначе продолжаем.
2. Какая зарплата у клиента? Если меньше 50 тысяч рублей, то переходим к шагу 3, иначе к шагу 4.
3. Какой стаж у клиента? Если меньше 10 лет, то не выдаем кредит, иначе выдаем.
4. Есть ли у клиента другие кредиты? Если есть, то отказываем, иначе выдаем.

Такой алгоритм, как и многие другие, хорошо описывается решающим деревом.

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

1 Свойства и структура алгоритмов

Определение решающего дерева. Рассмотрим бинарное дерево, в котором:

1. каждой внутренней вершине [math]v[/math] приписана функция (или предикат) [math]\beta_v: \mathbb{X} \to \{0, 1\}[/math];
2. каждой листовой вершине [math]v[/math] приписан прогноз [math]c_v \in Y[/math](в случае с классификацией листу также может быть приписан вектор вероятностей).

Рассмотрим теперь алгоритм [math]a(x)[/math], который стартует из корневой вершины [math]v_0[/math] и вычисляет значение функции [math]\beta_{v_0}[/math]. Если оно равно нулю, то алгоритм переходит в левую дочернюю вершину, иначе в правую, вычисляет значение предиката в новой вершине и делает переход или влево, или вправо. Процесс продолжается, пока не будет достигнута листовая вершина; алгоритм возвращает тот класс, который приписан этой вершине. Такой алгоритм называется бинарным решающим деревом.

На практике в большинстве случаев используются одномерные предикаты [math]\beta_v[/math], которые сравнивают значение одного из признаков с порогом:

[math] \begin{align} \beta_v(x; j, t) = [x_j \lt t]. \end{align} [/math]

Существуют и многомерные предикаты, например:

1. линейные [math]\beta_v(x) = [\langle w, x \rangle \lt t][/math];
2. метрические [math]\beta_v(x) = [\rho(x, x_v) \lt t][/math], где точка [math]x_v[/math] является одним из объектов выборки любой точкой признакового пространства.

Многомерные предикаты позволяют строить ещё более сложные разделяющие поверхности, но очень редко используются на практике, например, из-за того, что усиливают и без того выдающиеся способности деревьев к переобучению.

1.1 Общее описание алгоритма

Процесс построения решающего дерева состоит из нескольких этапов:

1. Инициализация: сначала создается корень дерева, представляющий весь набор данных.
2. Рекурсивное разделение: на каждом уровне дерева происходит разделение данных на основе определенного критерия. Критерии разделения могут основываться на различных метриках, таких как индекс Джини, энтропия или средняя квадратическая ошибка. Таким образом, выбирается пороговое значение наиболее значимого признака, по которому будет осуществляться разделение.
3. Прекращение разделения: когда процесс разделения достигает определенной глубины или не остается данных для дальнейшего разделения, остановка создания потомков и создание листа с меткой класса или прогнозируемым значением для регрессии.
4. Отсечение: в некоторых случаях, для борьбы с переобучением, может использоваться стратегия отсечения ветвей дерева. Это может включать удаление ветвей, не улучшающих характеристики дерева, создание деревьев с ограниченной глубиной или обрезание деревьев в соответствии с минимальным порогом улучшения критерия разделения.
5. Предсказание: после построения дерева оно может использоваться для предсказания меток классов или значений функции на новых данных. Для этого каждый объект пропускается через дерево по соответствующим условиям разделения, начиная с корня и заканчивая листом.

1.2 Математическое описание алгоритма

Для математического описания алгоритма построения решающего дерева рассмотрим жадный алгоритм для построения бинарного дерева. Пусть дана обучающая выборка [math]\mathbb{X} = (x_1, x_2, ..., x_n)[/math], необходимо найти оптимальное разделение на две части [math]R_1(j, t) = \{x | x_j \lt t\}[/math] и [math]R_2(j, t) = \{x | x_j \geq t\}[/math] с учетом заранее заданного критерия качества [math]Q(X, j, t)[/math]. После определения наилучших значений [math]j[/math] и [math]t[/math] создается корневой узел дерева, соответствующий предикату [math][x_j\lt t][/math]. Объекты разделяются на две части - некоторые попадают в левое поддерево, остальные – в правое. Этот процесс рекурсивно повторяется для каждого подмножества, и создаются дочерние узлы для корневого узла. В каждом узле проверяется выполнение условия остановки, и при его выполнении рекурсия прекращается, и узел объявляется листом. Когда дерево построено, каждому листу присваивается соответствующий ответ. В случае классификации это может быть класс с наибольшим количеством объектов в листе или вектор вероятностей (например, вероятность принадлежности к классу, равная доле объектов данного класса в листе). В случае регрессии это может быть среднее значение, медиана или другая функция от целевых переменных объектов в листе. Выбор определенной функции зависит от функционала качества, используемого в задаче.

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

Таким образом, конкретный метод построения дерева решений определяется:

1. Типом предикатов в узлах;
2. Критерием качества [math]Q(X, j, t)[/math];
3. Условием остановки;
4. Методом обработки пропущенных значений;
5. Методом стрижки.

При построении дерева необходимо задать функционал качества, на основе которого осуществляется разбиение выборки на каждом шаге. Пусть [math]R_m[/math] - множество объектов, попавших в вершину, разбиваемую на данном шаге, а [math]R_\ell[/math] и [math]R_r[/math] - объекты, попадающие в левое и правое поддерево соответственно при заданном предикате. Будем использовать функционалы следующего вида:

[math] \begin{align} Q(R_m, j, s) = I(R_m) - \frac{|R_\ell|}{|R_m|} I(R_\ell) - \frac{|R_r|}{|R_m|} I(R_r). \end{align} [/math]

Здесь [math]I(R)[/math] - критерий информативности(impurity criterion), который оценивает качество распределения целевой переменной среди объектов множества [math]R[/math]. Чем меньше разнообразие целевой переменной, тем меньше должно быть значение критерия информативности - и, соответственно, необходимо минимизировать его значение. Функционал качества [math]Q(R_m, j, s)[/math] необходимо при этом максимизировать.

1.2.1 Классификация

Пусть [math]p_k[/math] - доля объектов класса [math]k[/math] ([math]k \in \{1, \dots, K\}[/math]), попавших в вершину [math]R[/math]:

[math] \begin{align} p_{k} = \frac{1}{|R|} \sum_{(x_i, y_i) \in R} [y_i = k]. \end{align} [/math]

[math]k_*[/math] - класс, чьих представителей оказалось больше всего среди объектов, попавших в данную вершину: [math]k_* = \arg \max_k p_{k}[/math].

В качестве функции потерь рассмотрим индикатор ошибки:

[math] \begin{align} I(R) = \min_{c \in \mathbb{Y}} \frac{1}{|R|} \sum_{(x_i, y_i) \in R} [y_i \neq c]. \end{align} [/math]

Оптимальным предсказанием в данном критерии будет наиболее популярный класс [math]k_*[/math] - значит, критерий будет равен следующей доле ошибок:

[math] \begin{align} I(R) = \frac{1}{|R|} \sum_{(x_i, y_i) \in R} [y_i \neq k_*] = 1 - p_{k_*}. \end{align} [/math]

Данный критерий является достаточно грубым, поскольку учитывает частоту [math]p_{k_*}[/math] лишь одного класса.

Критерий Джини Рассмотрим ситуацию, в которой на каждом узле вместо единственного класса предоставляется распределение вероятностей для всех классов [math]c = (c_1, \dots, c_K)[/math], [math]\sum_{k = 1}^{K} c_k = 1[/math]. Если подставить эти вероятности в исходный критерий информативности Бриера(Brier score) и и выполнить ряд преобразований, то получим критерий Джини:

[math] \begin{align} I(R) = \sum_{k = 1}^{K} p_k (1 - p_k). \end{align} [/math]

Другой популярный критерий - энтропия:

[math] \begin{align} I(R) = - \sum_{k = 1}^{K} p_k \log p_k. \end{align} [/math]

1.2.2 Регрессия

Для регрессии используется среднеквадратическая ошибка:

[math] \begin{align} I(R) = \min_{c \in \mathbb{Y}} \frac{1}{|R|} \sum_{(x_i, y_i) \in R} (y_i - c)^2. \end{align} [/math]

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

[math] \begin{align} I(R) = \frac{1}{|R|} \sum_{(x_i, y_i) \in R} \left( y_i - \frac{1}{|R|} \sum_{(x_j, y_j) \in R} y_j \right)^2. \end{align} [/math]

Функционал качества разделения выбирает предикат, который обеспечивает наибольшее улучшение качества:

[math] \begin{align} Q(R_m, j, s) = I(R_m) - \frac{|R_\ell|}{|R_m|} I(R_\ell) - \frac{|R_r|}{|R_m|} I(R_r). \end{align} [/math]

Повторяя процесс разделения до достижения критерия остановки (максимальная глубина, минимальное количество объектов в листе, минимальное улучшение качества и т.д.), получаем дерево [math]T[/math]. Затем для предсказания используем функцию [math]d_T(x)[/math], опуская объект от корня к листу с соответствующей меткой класса или прогнозируемым значением:

[math] \begin{align} d_T(x) = C_j \ \text{или} \ \widehat{y}. \end{align} [/math]