Дерево регрессии с нуля с использованием Python

В этой статье я погружаюсь в тему дерева регрессии и его основных математических основ. Я постараюсь объяснить это как можно проще и создать рабочую модель с использованием python с нуля.

Я буду использовать рекурсию для создания узлов дерева, поэтому, если вы не знакомы с этим, я рекомендую посмотреть несколько примеров и пояснений в Интернете (хотя я все же кратко объясню его логику).

Импорт

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

Создание данных

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

где 𝜖 — шум.

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

Дерево регрессии

Древовидная структура

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

Учитывая набор данных, входное значение будет достигать листа. Все входные значения X, достигающие узла m, могут быть представлены подмножеством X. Математически представим эту ситуацию с помощью функции, которая дает 1, если заданное входное значение достигает узла m, и 0 в противном случае.

Нахождение порога для разделения данных

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

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

Синяя вертикальная линия представляет собой одно пороговое значение, где мы предполагаем, что это среднее значение любой заданной двух точек. Позже он будет использоваться для разделения данных.

Наш первый прогноз по проблеме — это среднее значение (по оси Y) для всех обучающих данных (зеленая горизонтальная линия). 2 красные линии — это прогнозы для создаваемого дочернего узла.

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

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

Внимание, спойлер:когда модель будет завершена, она не будет предсказывать какое-либо значение, используя корень или какие-либо промежуточные узлы; он будет прогнозировать, используя листья дерева регрессии (которые будут последними узлами дерева).

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

Давайте посмотрим в действии, как работает этот шаг.

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

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

Создание дочерних узлов

Теперь, когда мы разделили наши данные на две части, мы можем найти отдельные пороговые значения как для низких, так и для высоких значений. Хотя обратите внимание, что нам нужно условие остановки; поскольку с каждым узлом точки в наборе данных, принадлежащем узлу, становятся меньше, мы определяем минимальное количество точек данных для каждого узла. Если бы мы этого не сделали, каждый узел предсказывал бы, используя только одно обучающее значение, что приводило бы к переоснащению.

Мы можем создавать наши узлы рекурсивно. Для этого мы определяем класс с именем TreeNode, который будет хранить каждое значение, которое должен иметь узел. После этого мы сначала создаем корень, вычисляя его пороговые и прогнозные значения. Затем мы рекурсивно создаем дочерние узлы, где каждый класс дочерних узлов хранится как атрибут родительского класса с именем left или right.

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

Обратите внимание, что этот метод вносит свои изменения в первое предоставленное ему дерево, поэтому ему не требуется ничего возвращать.

Также обратите внимание, что, хотя обычно рекурсивная функция пишется не так (без возврата), мы не требуем возврата с тех пор, когда нет if оператор активирован, метод вернет сам себя.

Теперь мы можем проверить эту древовидную структуру, чтобы увидеть, созданы ли какие-либо узлы для лучшего соответствия данным. Я вручную выберу первые 2 узла и их прогнозы относительно порога корня.

Здесь мы видим 2 предсказания:

Прогнозы первого левого узла для высоких значений (выше его порога)
Предикации первого правого узла для низких значений (ниже его порога)

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

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

tree.left.right.left.left

Это, конечно, означает, что здесь есть ветвь, идущая вниз на 4 дочерних элемента, но она может идти намного глубже на другой ветке дерева.

Предсказание

Мы можем создать метод прогнозирования для прогнозирования любого заданного значения.

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

Тестируя с x = 3 (реальное значение можно вычислить с помощью функции, которую мы написали выше, при создании наших данных. -3**2+3+5 = -1, что является ожидаемым значением), мы получаем:

predict(3)

Расчетная ошибка

Мы можем использовать относительную квадратичную ошибку

и создайте данные проверки, как указано выше, используя ту же функцию.

что, возможно, является низкой ошибкой.

Обобщение шагов

Приложение

Лучше подходящие данные для модели дерева регрессии

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