Участник: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] является одним из объектов выборки любой точкой признакового пространства.

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

Метод случайного леса (англ. random forest) — алгоритм машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев. Алгоритм сочетает в себе две основные идеи: метод бэггинга Бреймана и метод случайных подпространств, предложенный Тин Кам Хо. Алгоритм применяется для задач классификации, регрессии и кластеризации. Основная идея заключается в использовании большого ансамбля решающих деревьев, каждое из которых само по себе даёт очень невысокое качество классификации, но за счёт их большого количества результат получается хорошим.

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]

1.3 Вычислительное ядро алгоритма

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

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

1.4 Макроструктура алгоритма

Для построения случайного леса и последующего получения предсказания для решения задачи классификации и регрессии необходимо первоначально научиться строить решающее дерево. Макроструктура алгоритма построения CART включает следующие этапы:

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

Макроструктура алгоритма случайного леса для задач классификации и регрессии включает следующие этапы:

1. Инициализация: выбор параметров ансамбля, таких как количество деревьев в лесу и максимальная глубина деревьев.
2. Построение ансамбля решающих деревьев:
   1. Создание бутстрапированной выборки (bootstrap sample) из исходного набора данных для обучения. Бутстрап-выборка содержит N объектов, выбранных случайным образом с возвращением (то есть один объект может быть выбран несколько раз, а некоторые объекты могут быть пропущены).
   2. Построение решающего дерева на основе полученной бутстрап-выборки с использованием метода CART. При выборе предиката для разделения узлов дерева, алгоритм случайного леса рассматривает только подмножество случайно выбранных предикатов для каждого узла (подпространство признаков).
   3. Повторение пунктов 1 и 2 заданное количество раз, чтобы построить необходимое число решающих деревьев.
3. Обучение: каждое дерево обучается на соответствующей ему бутстрап-выборке без обрезки или других процедур, устраняющих переобучение.
4. Предсказание:
   • Для задачи классификации: каждое дерево выполняет предсказание класса, а решение ансамбля принимается путем голосования большинства среди всех деревьев. Класс, получивший наибольшее число голосов от деревьев, принимается в качестве итогового предсказания.
   • Для задачи регрессии: каждое дерево выполняет предсказание числового значения, а решение ансамбля принимается путем усреднения предсказаний всех деревьев. Полученное среднее значение принимается в качестве итогового предсказания.
5. Оценка качества ансамбля: качество предсказания случайного леса оценивается посредством кросс-валидации, Out-of-Bag-оценки или других подходящих методов.

1.9 Входные и выходные данные алгоритма

Входные данные:

Объём входных данных: [math][/math]

Выходные данные:

Объём выходных данных: [math][/math]

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

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

Первый набор данных Sonar, Mines vs. Rocks предназначен для решения задачи классификации гидроакустических сигналов. Сонары (гидролокаторы) посылают звук высокой частоты в определенном направлении и получают отраженную звуковую волну. По характеристике этой волны можно сделать вывод, от чего именно она отразилась – от морской мины или же от подводного камня, скалы. Используемый для решения задачи набор данных был разработан сотрудником аэрокосмического технологического центра Полом Горманом в разгар холодной войны. Для получения данных металлический цилиндр и цилиндрическая горная порода, длиной около 1,5 метров, размещались на песчаном дне океана.

База данных о гидроакустических сигналах содержит 208 экземпляров и 60 атрибутов. Файл "sonar.mines" содержит 111 экземпляров, полученных путем отскакивания сигналов от мины под разными углами и при различных условиях. Файл "sonar.rocks" содержит 97 экземпляров, полученных от камней или скал в аналогичных условиях. Переданный сигнал гидролокатора представляет собой частотно-модулированный ЛЧМ, повышающийся по частоте. Каждый экземпляр представляет собой набор из 60 чисел в диапазоне от 0,0 до 1,0. Каждое число представляет энергию в пределах определенной полосы частот, полученной за определенный период времени. Метка, связанная с каждой записью, содержит букву «R» ("Rocks"), если объект представляет собой камень/скалу, и «M» ("Mines"), если это мина. Оба файла с представлением данных были интегрированы в один csv-файл "sonar.all-data.csv".

Также был использован набор данных The Home Equity dataset (HMEQ), которые представляет информацию о долевом участии в строительстве жилья (HMEQ) содержит исходную информацию и информацию об эффективности кредитования для 5 960 недавних займов на строительство жилья. Целевой показатель - это бинарная переменная, указывающая, был ли заявитель в конечном итоге неплатежеспособен или имел серьезные просрочки. Этот неблагоприятный исход имел место в 1189 случаях. Для каждого заявителя было зарегистрировано 12 входных признаков.

2.7 Существующие реализации алгоритма

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

1. Scikit-learn (Python) - наиболее известная библиотека для машинного обучения в Python, которая включает различные модели деревьев решений, такие как DecisionTreeClassifier и DecisionTreeRegressor.

2. WEKA (Java) - популярная библиотека для машинного обучения и анализа данных, которая содержит несколько реализаций деревьев решений, например, J48 Algorithm for Decision Tree.

3. MATLAB - математический программный пакет, который также оснащен инструментами для создания деревьев решений, таких как fitсtree и fitrtree для классификации и регрессии соответственно.