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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 49: Строка 49:
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
−
Для математического описания алгоритма построения решающего дерева начнем с жадного алгоритма построения бинарного дерева решений. Пусть дана обучающая выборка <math>\mathbb{X} = (x_1, x_2, ..., x_n)</math>, найдем наиболее оптимальное разделение на две части <math>R_1(j, t) = \{x | x_j < 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<t]</math>. Объекты будут разделены на две части - одни попадут в левое поддерево, другие в правое. Для каждого из этих подмножеств рекурсивно повторяем процесс, создавая дочерние узлы для корневого узла и так далее. В каждом узле проверяем, выполнено ли условие остановки, и если да, прекращаем рекурсию и объявляем этот узел листом. После построения дерева каждому листу присваивается соответствующий ответ. В случае классификации это может быть класс с наибольшим количеством объектов в листе или вектор вероятностей (например, вероятность класса может быть равна доле его объектов в листе). Для регрессии это может быть среднее значение, медиана или другая функция от целевых переменных объектов в листе. Выбор конкретной функции зависит от критерия качества в исходной задаче.
+
Для математического описания алгоритма построения решающего дерева рассмотрим жадный алгоритм для построения бинарного дерева. Пусть дана обучающая выборка <math>\mathbb{X} = (x_1, x_2, ..., x_n)</math>, необходимо найти оптимальное разделение на две части <math>R_1(j, t) = \{x | x_j < 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<t]</math>. Объекты разделяются на две части - некоторые попадают в левое поддерево, остальные – в правое. Этот процесс рекурсивно повторяется для каждого подмножества, и создаются дочерние узлы для корневого узла. В каждом узле проверяется выполнение условия остановки, и при его выполнении рекурсия прекращается, и узел объявляется листом. Когда дерево построено, каждому листу присваивается соответствующий ответ. В случае классификации это может быть класс с наибольшим количеством объектов в листе или вектор вероятностей (например, вероятность принадлежности к классу, равная доле объектов данного класса в листе). В случае регрессии это может быть среднее значение, медиана или другая функция от целевых переменных объектов в листе. Выбор определенной функции зависит от функционала качества, используемого в задаче.
  
−
Решающие деревья могут обрабатывать пропущенные значения - ситуации, когда для некоторых объектов неизвестны значения одного или нескольких признаков. Для этого необходимо изменить процедуру разделения выборки в узле, что возможно несколькими способами.
+
Решающие деревья могут обрабатывать пропущенные значения - ситуации, когда для некоторых объектов неизвестны значения одного или нескольких признаков. Для этого необходимо изменить процедуру разделения выборки в узле, что возможно несколькими способами. После построения дерева, можно провести его стрижку (pruning) - удаление некоторых узлов с целью уменьшения сложности и повышения обобщающей способности.
−
 
 
−
После построения дерева, можно провести его стрижку (pruning) - удаление некоторых узлов с целью уменьшения сложности и повышения обобщающей способности. Существует несколько подходов к стрижке, которые мы кратко упомянем ниже.
 
  
 
Таким образом, конкретный метод построения дерева решений определяется:
 
Таким образом, конкретный метод построения дерева решений определяется:
Строка 63: Строка 61:
 
# Методом стрижки.
 
# Методом стрижки.
  
−
При построении дерева необходимо задать ''функционал качества'', на основе которого осуществляется разбиение выборки на каждом шаге. Обозначим через <math>R_m</math> множество объектов, попавших в вершину, разбиваемую на данном шаге, а через <math>R_\ell</math> и <math>R_r</math> - объекты, попадающие в левое и правое поддерево соответственно при заданном предикате.
+
При построении дерева необходимо задать ''функционал качества'', на основе которого осуществляется разбиение выборки на каждом шаге. Пусть <math>R_m</math> - множество объектов, попавших в вершину, разбиваемую на данном шаге, а <math>R_\ell</math> и <math>R_r</math> - объекты, попадающие в левое и правое поддерево соответственно при заданном предикате.
 
Будем использовать функционалы следующего вида:
 
Будем использовать функционалы следующего вида:
 
:<math>
 
:<math>
Строка 79: Строка 77:
 
</math>
 
</math>
  
−
Здесь <math>I(R)</math> - это ''критерий информативности''(impurity criterion), который оценивает качество распределения целевой переменной среди объектов множества <math>R</math>. Чем меньше разнообразие целевой переменной, тем меньше должно быть значение критерия информативности - и, соответственно, необходимо минимизировать его значение. Функционал качества <math>Q(R_m, j, s)</math> необходимо при этом максимизировать.
+
Здесь <math>I(R)</math> - ''критерий информативности''(impurity criterion), который оценивает качество распределения целевой переменной среди объектов множества <math>R</math>. Чем меньше разнообразие целевой переменной, тем меньше должно быть значение критерия информативности - и, соответственно, необходимо минимизировать его значение. Функционал качества <math>Q(R_m, j, s)</math> необходимо при этом максимизировать.
  
 
===== Классификация =====
 
===== Классификация =====
−
Обозначим через <math>p_k</math> долю объектов класса <math>k</math> (<math>k \in \{1, \dots, K\}</math>), попавших в вершину <math>R</math>:
+
Пусть <math>p_k</math> - доля объектов класса <math>k</math> (<math>k \in \{1, \dots, K\}</math>), попавших в вершину <math>R</math>:
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
Строка 92: Строка 90:
 
\end{align}
 
\end{align}
 
</math>
 
</math>
−
Через <math>k_*</math> обозначим класс, чьих представителей оказалось больше всего среди объектов, попавших в данную вершину: <math>k_* = \argmax_k p_{k}</math>.
+
<math>k_*</math> - класс, чьих представителей оказалось больше всего среди объектов, попавших в данную вершину: <math>k_* = \arg \max_k p_{k}</math>.
  
−
Рассмотрим '''индикатор ошибки''' как функцию потерь:
+
В качестве функции потерь рассмотрим '''индикатор ошибки''':
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
Строка 105: Строка 103:
 
\end{align}
 
\end{align}
 
</math>
 
</math>
−
Легко видеть, что оптимальным предсказанием тут будет наиболее популярный класс <math>k_*</math> - значит, критерий будет равен следующей доле ошибок:
+
Оптимальным предсказанием в данном критерии будет наиболее популярный класс <math>k_*</math> - значит, критерий будет равен следующей доле ошибок:
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
Строка 121: Строка 119:
  
 
'''Критерий Джини'''
 
'''Критерий Джини'''
−
Рассмотрим ситуацию, в которой мы выдаём в вершине не один класс, а распределение на всех классах <math>c = (c_1, \dots, c_K)</math>, <math>\sum_{k = 1}^{K} c_k = 1</math>. Если подставить эти вероятности в исходный критерия ''информативности Бриера''(Brier score) и провести ряд преобразований, то мы получим критерий Джини:
+
Рассмотрим ситуацию, в которой на каждом узле вместо единственного класса предоставляется распределение вероятностей для всех классов <math>c = (c_1, \dots, c_K)</math>, <math>\sum_{k = 1}^{K} c_k = 1</math>. Если подставить эти вероятности в исходный критерий ''информативности Бриера''(Brier score) и и выполнить ряд преобразований, то получим критерий Джини:
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
Строка 176: Строка 174:
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
−
Q(R, p(x)) = I(R) - \frac{n_l}{n} I(R_l) - \frac{n_r}{n} I(R_r),
+
    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}
 
\end{align}
 
</math>
 
</math>
  
−
где <math>R_l</math> и <math>R_r</math> - левое и правое подмножество разделения, <math>n_l</math> и <math>n_r</math> - их объемы.
+
Повторяя процесс разделения до достижения критерия остановки (максимальная глубина, минимальное количество объектов в листе, минимальное улучшение качества и т.д.), получаем дерево <math>T</math>. Затем для предсказания используем функцию <math>d_T(x)</math>, опуская объект от корня к листу с соответствующей меткой класса или прогнозируемым значением:
−
 
 
−
Повторяя процесс разделения до достижения критерия остановки (максимальная глубина, минимальное количество объектов в листе, минимальное улучшение качества и т.д.), мы получаем дерево <math>T</math>. Затем для предсказания используем функцию <math>d_T(x)</math>, опуская объект от корня к листу с соответствующей меткой класса или прогнозируемым значением:
 
  
 
:<math>
 
:<math>

Версия 13:55, 29 октября 2023

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

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

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

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

  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{или} \ \hat{y}. \end{align} [/math]



2 Литература

  1. ↑ Sociological Methods & Research 2011, Discrepancy Analysis of State Sequences, vol. 40, issue 3, p. 471–510
  2. ↑ Xindong Wu, Vipin Kumar, J. Ross Quinlan, Joydeep Ghosh, Qiang Yang, Hiroshi Motoda, Geoffrey J, McLachlan, Angus Ng, Bing Liu, Philip S. Yu, Zhi-Hua Zhou, Michael Steinbach, David J. Hand, Dan Steinberg,Knowledge and Information Systems 2008, Top 10 algorithms in data mining, vol. 14, issue 1, p. 1–37
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Matfu/Решающие_деревья&oldid=29359