Как обучается дерево?

Как обучается дерево?

Фундаментальный процесс обучения дерева

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

Принцип работы: Жадный алгоритм (Greedy Algorithm)

Обучение дерева решений происходит сверху вниз (top-down) с использованием жадной стратегии (greedy approach):

1. Начинаем с корневого узла, содержащего все примеры
2. На каждом узле:
   - Для каждого признака проверяем все возможные значения разделения
   - Вычисляем информационный выигрыш (Information Gain) или уменьшение примеси
   - Выбираем лучшее разделение
3. Рекурсивно применяем процесс к левому и правому подузлам
4. Останавливаемся, когда достигнуты условия завершения

Критерии разделения

Для классификации:

1. Примесь Джини (Gini Impurity)

Gini(D) = 1 - Σ(p_i)^2

где p_i — доля класса i в узле D

Чем ниже Gini, тем чище узел (примеры больше принадлежат одному классу).

def gini_impurity(y):
    classes, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return 1 - np.sum(probabilities ** 2)

# Пример
y = [0, 0, 0, 1, 1]  # 3 нуля, 2 единицы
# p_0 = 0.6, p_1 = 0.4
# Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48

2. Энтропия и информационный выигрыш (Information Gain)

Entropy(D) = -Σ p_i * log2(p_i)

Information Gain = Entropy(parent) - Weighted Entropy(children)

Это мера уменьшения неопределённости после разделения.

def entropy(y):
    classes, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return -np.sum(probabilities * np.log2(probabilities + 1e-10))

def information_gain(parent, left, right):
    n = len(parent)
    n_left = len(left)
    n_right = len(right)
    
    parent_entropy = entropy(parent)
    left_entropy = entropy(left)
    right_entropy = entropy(right)
    
    weighted_child_entropy = (n_left / n) * left_entropy + (n_right / n) * right_entropy
    return parent_entropy - weighted_child_entropy

Для регрессии:

MSE reduction = MSE(parent) - Weighted MSE(children)

Алгоритм CART (Classification And Regression Trees)

Рекурсивный алгоритм построения дерева:

def build_decision_tree(X, y, depth=0, max_depth=5):
    # Условия остановки
    if (len(np.unique(y)) == 1 or  # Все примеры одного класса
        len(y) < 2 or              # Слишком мало примеров
        depth >= max_depth):       # Достигнута максимальная глубина
        return Leaf(np.argmax(np.bincount(y)))  # Возвращаем классический класс
    
    best_gain = 0
    best_feature = None
    best_threshold = None
    
    # Перебираем все признаки
    for feature_idx in range(X.shape[1]):
        feature_values = X[:, feature_idx]
        
        # Пытаемся разные пороги разделения
        for threshold in np.unique(feature_values):
            # Разделяем данные
            left_mask = feature_values <= threshold
            right_mask = ~left_mask
            
            if len(y[left_mask]) == 0 or len(y[right_mask]) == 0:
                continue
            
            # Вычисляем информационный выигрыш
            gain = information_gain(y, y[left_mask], y[right_mask])
            
            # Выбираем лучшее разделение
            if gain > best_gain:
                best_gain = gain
                best_feature = feature_idx
                best_threshold = threshold
    
    # Если не найдено хорошего разделения, возвращаем лист
    if best_feature is None:
        return Leaf(np.argmax(np.bincount(y)))
    
    # Рекурсивно строим левое и правое поддеревья
    left_mask = X[:, best_feature] <= best_threshold
    right_mask = ~left_mask
    
    left_subtree = build_decision_tree(X[left_mask], y[left_mask], depth + 1, max_depth)
    right_subtree = build_decision_tree(X[right_mask], y[right_mask], depth + 1, max_depth)
    
    return Node(best_feature, best_threshold, left_subtree, right_subtree)

Пример с реальными данными

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# Загружаем данные
iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# Создаём и обучаем дерево
dt = DecisionTreeClassifier(criterion='gini', max_depth=5, min_samples_split=5)
dt.fit(X_train, y_train)

# Оцениваем качество
accuracy = dt.score(X_test, y_test)
print(f'Accuracy: {accuracy:.3f}')

Сложность обучения

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

• В худшем случае: O(n² * m * log(n)), где n — количество примеров, m — количество признаков
• Обычно намного лучше из-за отсечений

Пространственная сложность:

• O(n) для хранения дерева в памяти

Ключевые отличия от других методов

Дерево решений НЕ использует:

• Градиентный спуск (как нейронные сети)
• Итеративную оптимизацию весов
• Функции активации

Дерево использует:

• Жадный поиск оптимальных разделений
• Информационно-теоретические метрики
• Рекурсивное разбиение пространства признаков

Заключение

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