Python: Реализовать decision tree с нуля

Решение: Decision Tree классификатор с нуля

Структура: 2 класса (Node, DecisionTree)

1. Gini Index (критерий примеси)

Gini = 1 - sum(p_i^2)

• Минимум 0: чистый узел
• Максимум 0.5: 50/50 класс

2. Информационный прирост

IG = Gini(parent) - (N_left/N * Gini(left) + N_right/N * Gini(right))

Выше IG → лучше разбиение.

3. Алгоритм (рекурсивный)

Базовый случай (листовой узел):

• Достигнута max_depth
• Меньше min_samples_split объектов
• Чистый узел (один класс)
• IG = 0 (нет улучшения)

Рекурсивный случай:

1. Перебрать все признаки
2. Для каждого признака: перебрать все пороги
3. Вычислить IG для каждого разбиения
4. Выбрать разбиение с максимальным IG
5. Рекурсивно строить левое и правое поддеревья

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

Для каждого объекта:

1. Начать с корня
2. Если листовой узел → вернуть значение
3. Если x[feature] <= threshold → идти влево
4. Иначе → идти вправо

5. Оценка

Accuracy = количество правильных / общее количество

Ключевые методы

• gini(y): вычислить индекс Gini
• entropy(y): альтернатива (информационная энтропия)
• _best_split(X, y): найти лучшее разбиение
• _build_tree(X, y, depth): рекурсивное построение
• fit(X, y): обучение
• predict(X): предсказание
• score(X, y): точность

Временная сложность

• Обучение: O(n log n * d * k), где n=объекты, d=признаки, k=глубина
• Предсказание: O(k) для одного объекта

Пример

tree = DecisionTree(max_depth=5, criterion='gini')
tree.fit(X_train, y_train)
accuracy = tree.score(X_test, y_test)
predictions = tree.predict(X_test)