PrepBro
← Назад к вопросам

Что минимизируем или максимизируем при построении дерева решений?

1.3 Junior🔥 181 комментариев
#Машинное обучение

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI29 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Что минимизируется в Decision Tree

При построении дерева решений мы минимизируем примесь (impurity) или эквивалентно максимизируем прирост информации (information gain). Это фундаментальный принцип алгоритма.

Концепция примеси (Impurity)

Что такое примесь?

Примесь показывает, насколько неоднородны классы в узле дерева.

Узел 1: все примеры класса A (чистый узел)
  Примесь = 0 (максимально информативен)

Узел 2: 50% класса A, 50% класса B (грязный узел)
  Примесь = 1 (максимальна неопределённость)

Узел 3: 90% класса A, 10% класса B (относительно чистый)
  Примесь = 0.19 (низкая примесь)

Метрика 1: Gini Impurity (наиболее распространена)

Формула

Gini = 1 - Σ(p_i)²

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

Пример расчёта

import numpy as np

# Узел с 4 примерами: 3 класса A, 1 класс B
p_A = 3/4  # 0.75
p_B = 1/4  # 0.25

gini = 1 - (p_A**2 + p_B**2)
gini = 1 - (0.75**2 + 0.25**2)
gini = 1 - (0.5625 + 0.0625)
gini = 1 - 0.625
gini = 0.375

print(f"Gini: {gini:.3f}")

# Интерпретация: 37.5% вероятность ошибки при случайной классификации

Gini для разных распределений

Идеально чистый узел (100% одного класса):
  Gini = 1 - (1² + 0²) = 0 ✓
  (максимум информации, минимум примеси)

Полностью смешанный узел (50-50):
  Gini = 1 - (0.5² + 0.5²) = 0.5
  (максимальная неопределённость)

Три класса поровну (33-33-33):
  Gini = 1 - 3*(0.33²) = 1 - 0.33 ≈ 0.67
  (высокая примесь)

Метрика 2: Entropy (Информационная энтропия)

Формула

Entropy = -Σ(p_i * log₂(p_i))

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

Пример расчёта

import numpy as np

# Узел: 3 класса A, 1 класс B
p_A = 3/4
p_B = 1/4

entropy = -(p_A * np.log2(p_A) + p_B * np.log2(p_B))
entropy = -(0.75 * np.log2(0.75) + 0.25 * np.log2(0.25))
entropy = -(0.75 * (-0.415) + 0.25 * (-2.0))
entropy = -(-0.311 - 0.5)
entropy = 0.811

print(f"Entropy: {entropy:.3f}")

# Интерпретация: в среднем 0.811 бит информации для классификации

Сравнение Gini и Entropy

import matplotlib.pyplot as plt
import numpy as np

# Для бинарной классификации
p = np.linspace(0, 1, 100)

gini = 1 - (p**2 + (1-p)**2)
entropy = -(p * np.log2(p + 1e-10) + (1-p) * np.log2(1-p + 1e-10))

plt.figure(figsize=(10, 6))
plt.plot(p, gini, label='Gini', linewidth=2)
plt.plot(p, entropy, label='Entropy', linewidth=2)
plt.xlabel('Доля класса 1')
plt.ylabel('Примесь')
plt.title('Gini vs Entropy')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

# Форма похожа, но Entropy более штрафует за несбалансированность

Информационный прирост (Information Gain)

Как дерево выбирает разбиение

Дерево ищет то разбиение, которое максимизирует информационный прирост:

IG = Impurity(parent) - Σ(weight_child * Impurity(child))

где weight_child = количество примеров в ребёнке / всего примеров

Пример: какое разбиение выбрать

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.tree import plot_tree
import matplotlib.pyplot as plt

# Загружаем данные
iris = load_iris()
X = iris.data[:, :2]  # используем только 2 признака
y = iris.target

# Строим дерево
dt = DecisionTreeClassifier(
    criterion='gini',  # или 'entropy'
    max_depth=3,
    random_state=42
)
dt.fit(X, y)

# Визуализируем
plt.figure(figsize=(20, 10))
plot_tree(dt, 
          feature_names=iris.feature_names[:2],
          class_names=iris.target_names,
          filled=True,
          fontsize=10)
plt.show()

# В каждом узле видно:
# - Условие разбиения (feature <= value)
# - Gini значение
# - Распределение классов
# - Решение (какой класс выбран)

Практический пример: ручной расчёт

Исходный узел:
  10 примеров класса A
  10 примеров класса B
  Gini = 1 - (0.5² + 0.5²) = 0.5

Вариант разбиения 1:
  Левое поддерево: 8 A, 2 B → Gini_left = 1 - (0.8² + 0.2²) = 0.32
  Правое поддерево: 2 A, 8 B → Gini_right = 1 - (0.2² + 0.8²) = 0.32
  
  Взвешенное значение:
  Gini_weighted = (10/20) * 0.32 + (10/20) * 0.32 = 0.32
  
  IG = 0.5 - 0.32 = 0.18 ✓

Вариант разбиения 2:
  Левое поддерево: 7 A, 3 B → Gini_left = 1 - (0.7² + 0.3²) = 0.42
  Правое поддерево: 3 A, 7 B → Gini_right = 1 - (0.3² + 0.7²) = 0.42
  
  Gini_weighted = (10/20) * 0.42 + (10/20) * 0.42 = 0.42
  
  IG = 0.5 - 0.42 = 0.08 ✗

Вывод: Вариант 1 лучше (больший прирост информации)

Алгоритм построения дерева (ID3/CART)

def build_decision_tree(node, data, labels):
    """
    Рекурсивное построение дерева путём минимизации примеси
    """
    # Базовые условия остановки
    if len(set(labels)) == 1:  # Все примеры одного класса
        return Leaf(class=labels[0])
    
    if len(data) < min_samples_split:
        return Leaf(class=most_common(labels))
    
    # Поиск оптимального разбиения
    best_feature = None
    best_threshold = None
    best_information_gain = 0
    
    current_impurity = calculate_gini(labels)
    
    for feature in range(n_features):
        for threshold in unique_values(data[:, feature]):
            # Разбиваем данные
            left_mask = data[:, feature] <= threshold
            right_mask = ~left_mask
            
            # Считаем примесь после разбиения
            left_impurity = calculate_gini(labels[left_mask])
            right_impurity = calculate_gini(labels[right_mask])
            
            n_left = sum(left_mask)
            n_right = sum(right_mask)
            n_total = len(labels)
            
            weighted_impurity = (
                (n_left / n_total) * left_impurity + 
                (n_right / n_total) * right_impurity
            )
            
            # Считаем информационный прирост
            information_gain = current_impurity - weighted_impurity
            
            # Обновляем лучшее разбиение
            if information_gain > best_information_gain:
                best_information_gain = information_gain
                best_feature = feature
                best_threshold = threshold
    
    # Если информационного прироста нет, создаём лист
    if best_information_gain == 0:
        return Leaf(class=most_common(labels))
    
    # Рекурсивно строим поддеревья
    left_child = build_decision_tree(
        node,
        data[data[:, best_feature] <= best_threshold],
        labels[data[:, best_feature] <= best_threshold]
    )
    
    right_child = build_decision_tree(
        node,
        data[data[:, best_feature] > best_threshold],
        labels[data[:, best_feature] > best_threshold]
    )
    
    return Node(
        feature=best_feature,
        threshold=best_threshold,
        left=left_child,
        right=right_child
    )

Гиперпараметры для контроля примеси

from sklearn.tree import DecisionTreeClassifier

dt = DecisionTreeClassifier(
    # Выбор критерия
    criterion='gini',  # или 'entropy'
    
    # Остановка роста
    max_depth=10,  # Максимальная глубина
    min_samples_split=20,  # Минимум примеров для разбиения
    min_samples_leaf=10,  # Минимум примеров в листе
    min_impurity_decrease=0.01,  # Минимальный прирост информации для разбиения
    
    random_state=42
)

Вывод

При построении дерева решений минимизируется:

  1. Примесь (Impurity) — Gini или Entropy
  2. Эквивалентно максимизируется информационный прирост (Information Gain)

Процесс:

  • На каждом узле дерево ищет разбиение, которое лучше всего разделяет классы
  • Чем больше информационный прирост — тем чище получатся поддеревья
  • Алгоритм жадный (greedy): выбирает локально лучшее разбиение на каждом шаге

Важно помнить: это может привести к переобучению, поэтому используются ограничения (max_depth, min_samples_split, min_impurity_decrease).