Как делается сплит в вершине дерева?

Как делается сплит в вершине дерева решений

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

1. Процесс выбора оптимального сплита

Для каждого признака дерево ищет точку разделения, которая максимизирует информационный выигрыш (Information Gain).

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

# Создаём простой датасет
X = np.array([
    [1.0],
    [2.0],
    [3.0],
    [4.0],
    [5.0],
    [6.0]
])
y = np.array([0, 0, 0, 1, 1, 1])

# Дерево автоматически найдёт оптимальный сплит
dt = DecisionTreeClassifier(max_depth=1)  # Только корень + один сплит
dt.fit(X, y)

# Проверить параметры сплита
print(f"Признак для сплита: {dt.tree_.feature[0]}")
print(f"Значение сплита: {dt.tree_.threshold[0]}")
# Признак для сплита: 0
# Значение сплита: 3.5  (делит на [0,0,0] и [1,1,1])

2. Критерии выбора сплита

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

Gini измеряет загрязненность узла (насколько в нём смешаны классы):

Gini = 1 - Σ(p_i)^2

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

Пример вычисления:

def gini(y):
    """Вычислить Gini индекс"""
    classes = np.unique(y)
    gini_val = 1.0
    
    for cls in classes:
        prob = np.sum(y == cls) / len(y)
        gini_val -= prob ** 2
    
    return gini_val

# Пример
y_pure = np.array([0, 0, 0, 0])      # Только класс 0
print(f"Gini (чистый): {gini(y_pure)}")
# Gini (чистый): 0.0

y_mixed = np.array([0, 0, 1, 1])     # 50% класс 0, 50% класс 1
print(f"Gini (смешанный): {gini(y_mixed)}")
# Gini (смешанный): 0.5

y_chaos = np.array([0, 1, 2, 3])     # По одному от каждого класса
print(f"Gini (максимальный): {gini(y_chaos)}")
# Gini (максимальный): 0.75

Информационный выигрыш (Information Gain)

Информационный выигрыш — уменьшение примеси после сплита:

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

Где:

• Gini(parent) — Gini родительского узла
• N_left, N_right — количество образцов слева и справа
• Gini(left), Gini(right) — Gini дочерних узлов

3. Алгоритм поиска оптимального сплита

def find_best_split(X, y, feature_idx):
    """Найти лучший сплит для одного признака"""
    
    best_gain = -1
    best_threshold = None
    
    # Сортируем уникальные значения
    thresholds = np.sort(np.unique(X[:, feature_idx]))
    
    # Вычислить Gini родителя
    gini_parent = gini(y)
    n_total = len(y)
    
    # Пробуем каждый возможный порог
    for threshold in thresholds:
        # Разделить выборку
        mask_left = X[:, feature_idx] <= threshold
        mask_right = ~mask_left
        
        y_left = y[mask_left]
        y_right = y[mask_right]
        
        # Пропустить если одна из сторон пуста
        if len(y_left) == 0 or len(y_right) == 0:
            continue
        
        # Вычислить Gini дочерних узлов
        gini_left = gini(y_left)
        gini_right = gini(y_right)
        
        # Информационный выигрыш
        n_left = len(y_left)
        n_right = len(y_right)
        gini_child = (n_left / n_total * gini_left + 
                      n_right / n_total * gini_right)
        
        gain = gini_parent - gini_child
        
        # Выбрать лучший сплит
        if gain > best_gain:
            best_gain = gain
            best_threshold = threshold
    
    return best_threshold, best_gain

# Пример
X = np.array([[1], [2], [3], [4], [5], [6]])
y = np.array([0, 0, 0, 1, 1, 1])

threshold, gain = find_best_split(X, y, feature_idx=0)
print(f"Лучший сплит: X[0] <= {threshold}, выигрыш = {gain:.3f}")
# Лучший сплит: X[0] <= 3, выигрыш = 0.500

4. Энтропия (альтернатива Gini)

Вместо Gini можно использовать энтропию:

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

def entropy(y):
    """Вычислить энтропию"""
    classes = np.unique(y)
    ent = 0.0
    
    for cls in classes:
        prob = np.sum(y == cls) / len(y)
        if prob > 0:
            ent -= prob * np.log2(prob)
    
    return ent

# Пример
y_pure = np.array([0, 0, 0, 0])
print(f"Entropy (чистый): {entropy(y_pure):.3f}")  # 0.0

y_mixed = np.array([0, 0, 1, 1])
print(f"Entropy (смешанный): {entropy(y_mixed):.3f}")  # 1.0

y_chaos = np.array([0, 1, 2, 3])
print(f"Entropy (максимальный): {entropy(y_chaos):.3f}")  # 2.0

5. Трёхуровневый пример сплита

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

# Датасет
X = np.array([
    [25, 50000],
    [30, 60000],
    [35, 75000],
    [45, 90000],
    [22, 40000],
    [40, 85000]
])
y = np.array([0, 0, 1, 1, 0, 1])  # 0 = не покупает, 1 = покупает

# Дерево с max_depth=2
dt = DecisionTreeClassifier(max_depth=2, criterion='gini')
dt.fit(X, y)

# Визуализировать дерево
plot_tree(dt, feature_names=['Age', 'Income'], class_names=['No', 'Yes'])
plt.show()

# Проверить параметры сплита
print("Узел 0 (корень):")
print(f"  Признак: {dt.tree_.feature[0]} (Age)")
print(f"  Порог: {dt.tree_.threshold[0]:.1f}")
print(f"  Gini: {dt.tree_.impurity[0]:.3f}")

print("\nУзел 1 (левый):")
print(f"  Признак: {dt.tree_.feature[1]} (Income)")
print(f"  Порог: {dt.tree_.threshold[1]:.1f}")
print(f"  Gini: {dt.tree_.impurity[1]:.3f}")

6. Полный алгоритм построения дерева (CART)

class SimpleDecisionTree:
    def __init__(self, max_depth=5, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.tree = None
    
    def fit(self, X, y):
        self.tree = self._build_tree(X, y, depth=0)
        return self
    
    def _build_tree(self, X, y, depth):
        n_samples, n_features = X.shape
        n_classes = len(np.unique(y))
        
        # Критерий остановки
        if (depth >= self.max_depth or 
            n_samples < self.min_samples_split or 
            n_classes == 1):  # Узел чистый
            return {'leaf': True, 'class': np.bincount(y).argmax()}
        
        best_gain = -1
        best_split = None
        
        # Пробуем все признаки и пороги
        for feature_idx in range(n_features):
            threshold, gain = find_best_split(X, y, feature_idx)
            
            if gain > best_gain:
                best_gain = gain
                best_split = (feature_idx, threshold)
        
        # Если нет хорошего сплита
        if best_split is None:
            return {'leaf': True, 'class': np.bincount(y).argmax()}
        
        # Разделить выборку
        feature_idx, threshold = best_split
        mask = X[:, feature_idx] <= threshold
        
        # Рекурсивно построить поддеревья
        return {
            'leaf': False,
            'feature': feature_idx,
            'threshold': threshold,
            'gain': best_gain,
            'left': self._build_tree(X[mask], y[mask], depth + 1),
            'right': self._build_tree(X[~mask], y[~mask], depth + 1)
        }

7. Практические советы

Использование sklearn

from sklearn.tree import DecisionTreeClassifier

# Использовать Gini (быстрее)
dt_gini = DecisionTreeClassifier(criterion='gini', max_depth=5)

# Использовать Entropy (более информативно)
dt_entropy = DecisionTreeClassifier(criterion='entropy', max_depth=5)

# Контролировать сложность
dt = DecisionTreeClassifier(
    max_depth=5,              # Максимальная глубина
    min_samples_split=10,     # Минимум образцов для сплита
    min_samples_leaf=5,       # Минимум образцов в листе
    min_impurity_decrease=0.01  # Минимальный выигрыш
)

Визуализация сплитов

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

dt = DecisionTreeClassifier(max_depth=3)
dt.fit(X, y)

fig, ax = plt.subplots(figsize=(20, 10))
plot_tree(dt, ax=ax, feature_names=['Age', 'Income'], 
          class_names=['No', 'Yes'], filled=True)
plt.show()

Выводы

Как делается сплит в вершине дерева:

1. Вычисляется Gini родительского узла — мера загрязненности
2. Для каждого признака и порога считается Information Gain — выигрыш от разделения
3. Выбирается сплит с максимальным выигрышем — разделение, которое лучше всего очищает узлы
4. Выборка разделяется на левую (<=порог) и правую (>порог) части
5. Процесс рекурсивно повторяется для каждого дочернего узла до остановки

Ключевые формулы:

• Gini = 1 - Σ(p_i)^2
• IG = Gini(parent) - (N_left/N * Gini(left) + N_right/N * Gini(right))

Это фундамент алгоритма CART (Classification and Regression Trees), используемого во всех популярных библиотеках (sklearn, XGBoost, LightGBM, CatBoost).