Как оценивается качество разделения в дереве решений?

Оценка качества разделения в дереве решений

Качество разделения (split quality) в дереве решений оценивается с помощью критериев примеси (impurity criteria), которые показывают, насколько хорошо разделение разделяет классы. Это ключевая часть алгоритма построения дерева.

Основные критерии примеси

1. Gini Index (коэффициент Джини)

Gini измеряет вероятность неправильной классификации при случайном выборе элемента:

Gini(D) = 1 - Σ(p_i)²

где p_i — доля примеров класса i в наборе D

Значение Gini от 0 до 1:

• 0 = идеальная чистота (все примеры одного класса)
• 0.5 = максимальная примесь (классы поровну)

Пример: узел с 8 положительными и 2 отрицательными примерами имеет Gini = 1 - (0.8² + 0.2²) = 0.32

2. Entropy (энтропия)

Entropy измеряет среднее количество информации (неопределённость):

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

Значение энтропии от 0 до 1:

• 0 = идеальная чистота
• 1 = максимальная неопределённость

Выбор лучшего разделения

Алгоритм выбирает разделение, которое максимизирует информационный прирост (Information Gain):

IG(D, A) = Entropy(D) - Σ(|D_v|/|D| * Entropy(D_v))

Для Gini: Gini_gain = Gini(D) - Σ(|D_v|/|D| * Gini(D_v))

Практический пример

Предположим, у нас есть 10 примеров: 6 положительных и 4 отрицательных.

Исходный Gini родителя = 1 - (0.6² + 0.4²) = 0.48

Разделение 1: age <= 30

• Левый узел (4 примера): 3 положительных, 1 отрицательный. Gini = 0.375
• Правый узел (6 примеров): 3 положительных, 3 отрицательных. Gini = 0.5
• Средний Gini = (4/10)*0.375 + (6/10)*0.5 = 0.45
• Information Gain = 0.48 - 0.45 = 0.03

Разделение 2: income <= 50000

• Левый узел (5 примеров): 1 положительный, 4 отрицательных. Gini = 0.32
• Правый узел (5 примеров): 5 положительных, 0 отрицательных. Gini = 0 (идеально!)
• Средний Gini = (5/10)*0.32 + (5/10)*0 = 0.16
• Information Gain = 0.48 - 0.16 = 0.32

Разделение 2 лучше, так как даёт больший Information Gain (0.32 > 0.03).

Сравнение критериев

Gini (вероятность неправильной классификации) более вычислительно эффективен, так как не требует логарифмов. Entropy (информационно-теоретический подход) дает идентичные или очень похожие результаты. На практике оба работают одинаково хорошо.

Применение в scikit-learn

Критерий выбирается параметром criterion='gini' (по умолчанию) или criterion='entropy'. Алгоритм автоматически оценивает все возможные разделения для каждого признака и выбирает то, которое максимизирует выбранный критерий.

Проблема переобучения

Деревья решений чувствительны к выбору порога и могут переобучаться. Решение: ограничивать глубину дерева (max_depth), минимальное количество примеров в узле (min_samples_split) или минимальное количество примеров в листе (min_samples_leaf).

На практике я использую Gini по умолчанию из-за скорости вычисления и переключаюсь на Entropy только при теоретическом обосновании.