Алгоритм дерева решений – это жадный рекурсивный алгоритм построения модели, основанной на разбиении пространства признаков на подпространства с одинаковым значением целевой переменной.
Результатом работы алгоритма является бинарное дерево (как правило, бинарное), состоящего из определенного числа разбиений всей исходной выборки данных по разным критериям (предикатам).
Дерево решений очень похоже на игру, в которой нужно отгадать имя музыканта или число, задавая разные вопросы типа: мужчина или женщина, жив или нет, гитарист или нет, рок-музыкант или нет, число больше 2 или меньше и т.д. С каждым вопросом мы получаем новую информацию и отсекаем большой пласт неподходящих вариантов.
Алгоритм дерева решений используется как для задач классификации, так и для задач регрессии.
Как работает алгоритм
- Берется вся выборка данных и все ее признаки.
- Для каждого признака берется условие (предикат), по которому происходит разбиение.
- Для каждого разбиения вычисляются метрики разбиения (для задачи классификации – критерий Джини или энтропия Шэннона, для задачи регрессии – MSE или другие метрики регрессии).
- Находится такой признак и такое разбиение, для которых метрика минимальна.
- Вся выборка разбивается по этому предикату на две части. Так получаются две новые ветви дерева.
- Далее для каждой части повторяется та же последовательность подбора предиката. И т.д.
В итоге получается структура в виде бинарного дерева, в которой на концах находятся “листья” с выборкой, относящейся преимущественно к одному классу. При этом все расчеты для каждого шага сохраняются.
Дерево может быть очень большим (глубоким), если не ограничить его.
Алгоритм дерева решений:
- ищет признаки, которые наиболее эффективно уменьшают неопределенность (энтропию или индекс Джини, или метрику регрессии),
- делит выборку на все более “чистые” подгруппы,
- работает жадно, т.е. локально оптимизирует разбиение на каждом шаге, не возвращаясь назад.
Функции оценки чистоты разбиения – критерий Джини и энтропия Шэннона
Критерий Джини – для задачи классификации
Gini(t) = 1 - \sum_{i=1}^{C} p_i^2
Где:
- p_i — доля объектов класса i в узле t
- CCC — число классов
Энтропия Шеннона – для задачи классификации
Entropy(t) = - \sum_{i=1}^{C} p_i \log_2(p_i)
Где:
- p_i — вероятность (доля) появления класса i в узле t
- Энтропия измеряет уровень неопределенности — чем она выше, тем более “смешанным” является узел.
График показывает, как зависит значение критерия от вероятности наличия объектов определенного класса в выборке. Также виден взаимный масштаб изменения критерия Джини и энтропии Шеннона.
Пример:
Если в узле представлены оба класса с вероятностями 50% на 50%:
Entropy = − (0.5⋅log2(0.5) + 0.5⋅log2(0.5)) = 1
Если только один класс: Entropy = 0
MSE – для задачи регрессии
mse = \sum_{i=1}^{n} \frac {(y_i - y)^2}{n}
Нюансы работы дерева решений
Как выбираются пороги для разбиения?
Все уникальные значения признака сортируются по возрастанию, и рассматриваются середины между соседними значениями как возможные пороги. Например, если x = [1,3,4,5,6], то возможные пороги: t ∈ {2,3.5,4.5,5.5}.
Последовательность разбиений имеет значение
В дереве решений имеет значение последовательность задавания вопросов.
Разделение, созданное первым вопросом, может создать полезную ситуацию для второго вопроса.
И он окажется удачным по разделению. Если бы второй вопрос был задан до первого, он был бы
бесполезным.
Ограничение дерева
Ограничение дерева по глубине – это, по сути, ограничение дерева в числе заданных вопросов.
Мы словно просим дерево задать всего несколько самых важных и продуктивных вопроса.
Есть ли функция потерь у дерева решений?
Это частый вопрос на собеседованиях! Ответ – нет никаких функций потерь и градиентного спуска в деревьях!
Они обучаются другим способом – проход по сэмплам и их разбиение по признакам.
И так на каждой итерации – алгоритм старается максимизировать метрику прироста информации.
Строго говоря, эти метрики не являются функциями потерь!
Какова временная сложность построения дерева решений?
Какова будет сложность построения дерева в нотации О большое, если размер выборки равен N,
а количество признаков равно M?
Ответ: O(M⋅NlogN)
Объяснение смотри здесь.
Реализация дерева решений для задач классификации и регрессии с помощью Scikit Learn
Задача классификации – минимальный код
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# Загрузка данных
X, y = load_iris(return_X_y=True)
# Разбиение данных на обучающие и тестовые
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
# Инициализация модели и её обучение
model = DecisionTreeClassifier()
model.fit(X_train, y_train)
# Предсказания модели
y_pred = model.predict(X_test)
# Оценка качества прогноза
acc = accuracy_score(y_test, y_pred)
print(f"Accuracy: {acc:.2f}")Задача регрессии – минимальный код
from sklearn.datasets import load_diabetes
from sklearn.tree import DecisionTreeRegressor
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error
# Загрузка модели
X, y = load_diabetes(return_X_y=True)
# Разбиение данных на тренировочные и тестовые
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
# Инициализация модели и ее обучение
model = DecisionTreeRegressor()
model.fit(X_train, y_train)
# Предсказания
y_pred = model.predict(X_test)
# Оценка качества
mse = mean_squared_error(y_test, y_pred)
print(f"MSE: {mse:.2f}")