Как отбираются значения признаков в дереве?

Отбор значений признаков в дереве решений

Дерево решений рекурсивно выбирает лучший признак и его пороговое значение для разбиения (split) данных. Это ключевой механизм работы алгоритма.

1. Общая стратегия: жадный (Greedy) алгоритм

Дерево решений использует жадный алгоритм (greedy algorithm) для выбора разбиений:

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

Хотя это не гарантирует глобально оптимальное дерево, на практике работает очень хорошо.

2. Критерии качества разбиения

2.1 Gini Impurity (для классификации)

Самый популярный критерий. Измеряет чистоту (purity) узла:

import numpy as np
from sklearn.tree import DecisionTreeClassifier

# Gini Index вычисляется как:
# Gini(p) = 1 - sum(p_i^2)
# где p_i - вероятность класса i

def compute_gini(y):
    """
    Вычислить Gini Index для набора y
    """
    # Посчитать долю каждого класса
    classes, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    
    # Gini = 1 - sum(p^2)
    gini = 1 - np.sum(probabilities ** 2)
    return gini

# Примеры
y_pure = np.array([1, 1, 1, 1])  # Только класс 1
print(f"Pure node (all class 1): Gini = {compute_gini(y_pure):.3f}")
# Gini = 0 (идеально чистый)

y_mixed = np.array([1, 1, 0, 0])  # Поровну классов
print(f"Mixed node (50-50): Gini = {compute_gini(y_mixed):.3f}")
# Gini = 0.5 (максимальная неопределённость)

y_imbalanced = np.array([1, 1, 1, 0])  # Дисбалансированные
print(f"Imbalanced node (75-25): Gini = {compute_gini(y_imbalanced):.3f}")
# Gini = 0.375

Интерпретация:

• Gini = 0: Идеально чистый узел (только один класс)
• Gini = 0.5: Максимальная неопределённость (50-50 для двух классов)
• Меньше Gini → лучше разбиение

2.2 Information Gain (Entropy-based)

Альтернативный критерий, основанный на информационной энтропии:

def compute_entropy(y):
    """
    Вычислить Shannon entropy
    """
    classes, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    
    # Entropy = -sum(p_i * log2(p_i))
    entropy = -np.sum(probabilities * np.log2(probabilities + 1e-10))
    return entropy

def compute_information_gain(parent, left_child, right_child):
    """
    Information Gain = Entropy(parent) - WeightedAvg(Entropy(children))
    """
    n = len(parent)
    n_left = len(left_child)
    n_right = len(right_child)
    
    entropy_parent = compute_entropy(parent)
    entropy_left = compute_entropy(left_child)
    entropy_right = compute_entropy(right_child)
    
    # Взвешенное среднее энтропии детей
    weighted_entropy = (n_left / n) * entropy_left + (n_right / n) * entropy_right
    
    # Information Gain
    info_gain = entropy_parent - weighted_entropy
    return info_gain

# Пример
parent = np.array([0, 0, 1, 1, 1])  # 2 нуля, 3 единицы
left = np.array([0, 0, 1])  # Один вариант разбиения
right = np.array([1, 1])

info_gain = compute_information_gain(parent, left, right)
print(f"Information Gain: {info_gain:.3f}")
print(f"Более высокий Information Gain = лучшее разбиение")

3. Алгоритм выбора разбиения

Пошаговый процесс для одного узла:

from sklearn.tree import DecisionTreeClassifier
import numpy as np
from sklearn.datasets import load_iris

iris = load_iris()
X = iris.data
y = iris.target

# Вручную реализовать процесс выбора разбиения
feature_index = 0  # Рассмотрим первый признак (sepal length)
feature_values = X[:, feature_index]

print(f"Feature: {iris.feature_names[feature_index]}")
print(f"Value range: [{feature_values.min():.2f}, {feature_values.max():.2f}]")
print()

# Для дерева нужно проверить все возможные пороги
# Оптимальные пороги - это значения признака в данных
unique_values = np.unique(feature_values)
print(f"Количество уникальных значений: {len(unique_values)}")
print()

best_gini = float("inf")
best_threshold = None
best_split_idx = None

for i in range(len(unique_values) - 1):
    # Пороговое значение между двумя последовательными значениями
    threshold = (unique_values[i] + unique_values[i+1]) / 2
    
    # Разбить данные
    left_mask = feature_values <= threshold
    right_mask = ~left_mask
    
    # Пропустить если разбиение тривиально
    if len(y[left_mask]) == 0 or len(y[right_mask]) == 0:
        continue
    
    # Вычислить Gini
    def gini_split(y_parent, y_left, y_right):
        n = len(y_parent)
        gini_left = 1 - np.sum((np.bincount(y_left) / len(y_left)) ** 2)
        gini_right = 1 - np.sum((np.bincount(y_right) / len(y_right)) ** 2)
        weighted_gini = (len(y_left) / n) * gini_left + (len(y_right) / n) * gini_right
        return weighted_gini
    
    weighted_gini = gini_split(y, y[left_mask], y[right_mask])
    
    if weighted_gini < best_gini:
        best_gini = weighted_gini
        best_threshold = threshold
        best_split_idx = i

print(f"Лучший порог разбиения: {best_threshold:.2f}")
print(f"Лучший взвешенный Gini: {best_gini:.3f}")

4. Рассмотрение всех признаков

def find_best_split_all_features(X, y):
    """
    Найти лучшее разбиение среди всех признаков
    """
    best_gini = float("inf")
    best_feature = None
    best_threshold = None
    
    # Для каждого признака
    for feature_idx in range(X.shape[1]):
        feature_values = X[:, feature_idx]
        unique_values = np.unique(feature_values)
        
        # Для каждого порога
        for i in range(len(unique_values) - 1):
            threshold = (unique_values[i] + unique_values[i+1]) / 2
            
            # Разбить
            left_mask = feature_values <= threshold
            right_mask = ~left_mask
            
            if len(y[left_mask]) == 0 or len(y[right_mask]) == 0:
                continue
            
            # Вычислить Gini
            n = len(y)
            gini_left = 1 - np.sum((np.bincount(y[left_mask]) / len(y[left_mask])) ** 2)
            gini_right = 1 - np.sum((np.bincount(y[right_mask]) / len(y[right_mask])) ** 2)
            weighted_gini = (len(y[left_mask]) / n) * gini_left + (len(y[right_mask]) / n) * gini_right
            
            if weighted_gini < best_gini:
                best_gini = weighted_gini
                best_feature = feature_idx
                best_threshold = threshold
    
    return best_feature, best_threshold, best_gini

# Найти лучшее разбиение
best_feature, best_threshold, best_gini = find_best_split_all_features(X[:100], y[:100])
print(f"\nЛучший признак: {iris.feature_names[best_feature]}")
print(f"Лучший порог: {best_threshold:.2f}")
print(f"Лучший Gini: {best_gini:.3f}")

5. Сложность алгоритма

# Сложность выбора одного разбиения:
# O(d * n log n) где d - количество признаков, n - количество samples

# Объяснение:
# - d признаков: проверить каждый
# - Для каждого признака: отсортировать значения O(n log n)
# - Для каждого порога: вычислить метрику O(n)
# - Общее: O(d * n log n) для одного разбиения

# На каждом уровне дерева число узлов удваивается
# Глубина дерева: O(log n) в лучшем случае
# Общая сложность обучения: O(d * n * log²(n))

6. Практический пример с scikit-learn

from sklearn.tree import DecisionTreeClassifier, plot_tree
import matplotlib.pyplot as plt

# Обучить дерево
dt = DecisionTreeClassifier(
    max_depth=3,
    random_state=42
)

dt.fit(X, y)

# Визуализировать
plt.figure(figsize=(20, 10))
plot_tree(
    dt,
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    filled=True,
    rounded=True,
    fontsize=10
)
plt.title("Decision Tree с выбранными разбиениями")
plt.tight_layout()
plt.show()

# Получить информацию о разбиениях
feature = dt.tree_.feature  # Индекс признака каждого узла
threshold = dt.tree_.threshold  # Пороговое значение каждого узла

print("\nЛучшие разбиения (в порядке создания узлов):")
for node_id in range(dt.tree_.node_count):
    if feature[node_id] != -2:  # -2 означает листовой узел
        feature_name = iris.feature_names[feature[node_id]]
        threshold_val = threshold[node_id]
        print(f"Node {node_id}: {feature_name} <= {threshold_val:.2f}")

7. Влияние параметров на выбор разбиений

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score

# min_samples_split: минимальное число samples для разбиения
print("Влияние min_samples_split:")
for min_split in [2, 5, 10, 20]:
    dt = DecisionTreeClassifier(
        min_samples_split=min_split,
        random_state=42
    )
    scores = cross_val_score(dt, X, y, cv=5)
    print(f"  min_samples_split={min_split}: accuracy={scores.mean():.3f}")

print()

# criterion: критерий выбора разбиения
print("Влияние criterion (критерия качества):")
for criterion in ["gini", "entropy", "log_loss"]:
    dt = DecisionTreeClassifier(
        criterion=criterion,
        random_state=42
    )
    scores = cross_val_score(dt, X, y, cv=5)
    print(f"  criterion={criterion}: accuracy={scores.mean():.3f}")

8. Оптимизации при выборе разбиений

Оптимизация 1: Presort (deprecated в новых версиях)

# В старых версиях scikit-learn
# presort=True значительно ускорял выбор разбиений
# Теперь это встроено и обычно игнорируется

Оптимизация 2: Случайные пороги (Random Tree)

from sklearn.tree import ExtraTreeClassifier

# ExtraTree (Extremely Randomized Tree)
# Выбирает случайные пороги вместо оптимальных
dt_extreme = ExtraTreeClassifier(random_state=42)
dt_extreme.fit(X, y)

print("ExtraTree: более быстро, часто почти такая же точность")

9. Пошаговая визуализация процесса

import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier

# Создать простой 2D dataset для визуализации
from sklearn.datasets import make_blobs

X_2d, y_2d = make_blobs(
    n_samples=200,
    centers=3,
    n_features=2,
    random_state=42
)

fig, axes = plt.subplots(1, 3, figsize=(15, 4))

# Разные глубины дерева
for idx, max_depth in enumerate([1, 2, 5]):
    dt = DecisionTreeClassifier(max_depth=max_depth, random_state=42)
    dt.fit(X_2d, y_2d)
    
    # Сделать сетку для визуализации
    x_min, x_max = X_2d[:, 0].min() - 1, X_2d[:, 0].max() + 1
    y_min, y_max = X_2d[:, 1].min() - 1, X_2d[:, 1].max() + 1
    xx, yy = np.meshgrid(
        np.linspace(x_min, x_max, 100),
        np.linspace(y_min, y_max, 100)
    )
    
    # Предсказать на сетке
    Z = dt.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    # Визуализировать
    axes[idx].contourf(xx, yy, Z, alpha=0.3)
    axes[idx].scatter(X_2d[:, 0], X_2d[:, 1], c=y_2d, edgecolors="k")
    axes[idx].set_title(f"Max Depth = {max_depth}")
    axes[idx].set_xlim(x_min, x_max)
    axes[idx].set_ylim(y_min, y_max)

plt.tight_layout()
plt.show()

print("Границы решения становятся более сложными с увеличением depth")
print("потому что дерево выбирает больше разбиений")

10. Итоговый алгоритм

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

1. Начать с корневого узла, содержащего все данные

2. Для каждого узла:
   a) Если условие остановки (max_depth, min_samples_split, etc):
      - Создать листовой узел
      - Выход
   
   b) Для каждого признака f = 1..d:
      i) Для каждого порога t в значениях признака f:
         - Разбить данные: left = X[f] <= t, right = X[f] > t
         - Вычислить метрику качества (Gini или Entropy)
      ii) Найти лучший порог t* с максимальным Information Gain
   
   c) Выбрать признак f* и порог t* с наибольшим улучшением
   
   d) Создать два дочерних узла:
      - Левый узел (f* <= t*)
      - Правый узел (f* > t*)
   
   e) Рекурсивно вызвать алгоритм для левого и правого узлов

3. Вернуть построенное дерево

Выводы

Как отбираются значения признаков:

1. Жадный алгоритм: проверить все признаки и пороги
2. Критерий качества: Gini (чистота) или Information Gain (энтропия)
3. Пороги: значения между уникальными значениями признака
4. Выбор: разбиение с максимальным улучшением качества
5. Рекурсия: повторить для каждого дочернего узла

Сложность: O(d * n * log²(n)) для обучения

Оптимизации: современные реализации используют histograms для ускорения