Теперь соберём все части вместе и создадим полноценное дерево решений!
Дерево решений — это алгоритм машинного обучения, который:
1. Находит лучший признак для разделения данных (по информационной выгоде)
2. Рекурсивно строит поддеревья для каждой части
3. Останавливается, когда данные "чистые" или достигнута максимальная глубина
Пример работы на данных OR (логическое ИЛИ):
X = [[0,0], [0,1], [1,0], [1,1]]
y = [0, 1, 1, 1]
Дерево может выглядеть так:
[feature 0]
/ \
x[0]=0 x[0]=1
/ \
[feature 1] лист(1)
/ \
лист(0) лист(1)
Задача
Используйте класс
TreeNode, реализованный в предыдущем задании.
Реализуйте класс
DecisionTree с методами:
0.
__init__(self, max_depth=10)`
Инициализирует дерево решений.
Параметры:
-
max_depth: максимальная глубина дерева (по умолчанию 10)
Что нужно сделать:
- Сохранить
max_depth как атрибут объекта
- Создать атрибут
self.root и установить его в
None (корень дерева будет создан позже при вызове fit)
1.
entropy(self, labels)
Считает энтропию списка меток.
H = -p₀·log₂(p₀) - p₁·log₂(p₁)
Если список пустой, возвращает 0.
Если p=0, соответствующее слагаемое = 0.
2.
find_best_split(self, X, y)
Находит лучший признак для разделения.
- Для каждого признака считает информационную выгоду
- Возвращает кортеж: (индекс_лучшего_признака, информационная_выгода)
- Если все признаки дают нулевую выгоду, возвращает (0, 0)
3.
build_tree(self, X, y, depth=0)
Рекурсивно строит дерево. Возвращает
TreeNode.
Условия остановки (создать лист):
- Все метки одинаковые → лист с этой меткой
- Достигнута max_depth → лист с самым частым классом
- Нет признаков (X пустой или X[0] пустой) → лист с самым частым классом
- Лучшее разделение даёт нулевую выгоду → лист с самым частым классом
Иначе:
- Найти лучший признак
- Разделить данные: левая часть где x[feature]=0, правая где x[feature]=1
- Рекурсивно построить поддеревья
- Вернуть TreeNode с feature_index и поддеревьями
4.
fit(self, X, y) - берёт данные (примеры X и ответы y) и строит из них дерево решений, которое потом будет делать предсказания.
5.
predict(self, X) - берёт новые данные и для каждого примера спрашивает у дерева: "Какой ответ?"
Класс
TreeNode уже реализован в предыдущем задании. Скопируйте его здесь.
Примеры
Пример 1
X = [[0,0], [0,1], [1,0], [1,1]]
y = [0, 1, 1, 1]
tree = DecisionTree(max_depth=3)
tree.fit(X, y)
tree.predict(X) # [0, 1, 1, 1]
Пример 2
X = [[0,0], [0,1], [1,0], [1,1]]
y = [0, 0, 0, 1]
tree = DecisionTree(max_depth=3)
tree.fit(X, y)
tree.predict(X) # [0, 0, 0, 1]
Пример 3
X = [[0,0], [0,1], [1,0], [1,1]]
y = [1, 1, 1, 0]
tree = DecisionTree(max_depth=3)
tree.fit(X, y)
tree.predict(X) # [1, 1, 1, 0]