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

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

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

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

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

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

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

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

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

1.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.2 Общее описание алгоритма

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

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