Деревья решений

Три родословные дерева решений

Современные деревья решений выросли из трёх разных корней. В 1963 году социологи Джеймс Морган и Джон Сонквист создали AID (Automatic Interaction Detection) - одну из первых программ, разбивавших данные опросов на подгруппы для изучения социальных закономерностей. В 1984 году статистики Лео Брейман, Джером Фридман, Ричард Олшен и Чарльз Стоун опубликовали CART (Classification and Regression Trees), дав направлению строгую статистическую основу с бинарными разбиениями и cost-complexity pruning. Параллельно специалист по ИИ Росс Куинлан шёл со стороны искусственного интеллекта: его алгоритм ID3 (1986) выбирал разбиения по приросту информации, а преемник C4.5 (1993) добавил работу с непрерывными признаками, пропусками и обрезкой. Вместе эти линии определяют то, как деревья строят сегодня.

Когда врач ставит диагноз, он задаёт серию вопросов: есть ли температура? Если да - выше 38? Есть ли кашель? Сухой или влажный? Каждый ответ сужает список возможных диагнозов. Деревья решений работают точно так же - разбивают данные серией вопросов, от общего к частному. Но как алгоритм выбирает, какой вопрос задать первым? Почему спросить про температуру полезнее, чем про цвет глаз? За этим стоит математика - Information Gain и Gini Impurity - метрики, которые измеряют, насколько каждый вопрос уменьшает неопределённость.

• **Банковский скоринг:** дерево решений в Сбере и Тинькофф определяет, одобрить ли кредит - и в отличие от нейросети, может объяснить почему: «отказ, потому что доход < 30k и просрочки > 2 за год». Регуляторы требуют именно такую прозрачность
• **Медицинская диагностика:** дерево-классификатор в приёмном отделении сортирует пациентов по срочности: если пульс > 120 и давление < 90 - немедленная помощь. Простота интерпретации спасает жизни, когда некогда ждать сложную модель
• **Kaggle и production ML:** XGBoost и LightGBM - ансамбли из тысяч деревьев решений - выигрывают большинство соревнований на табличных данных и используются в рекомендательных системах Uber, Airbnb, Netflix

Предварительные знания

• Metrics and Model Evaluation

Энтропия: мера неопределённости

Представьте два мешка с шарами. В первом - 10 красных шаров. Во втором - 5 красных и 5 синих. Из какого мешка вы с большей уверенностью предскажете цвет случайно вытянутого шара? Из первого, разумеется - там нет неопределённости. Второй мешок максимально непредсказуем. Именно эту идею формализует **энтропия** - мера «беспорядка» или неопределённости в наборе данных.

Клод Шеннон в 1948 году ввёл формулу энтропии в теории информации: **Entropy(S) = -sum(p_i * log2(p_i))**, где p_i - доля элементов класса i. Эта формула измеряет среднее количество бит, необходимых для кодирования случайного исхода. Чем больше «сюрприза» несёт каждый исход - тем выше энтропия.

**Почему log2, а не ln?** Потому что энтропия измеряется в **битах** - минимальных единицах информации. Entropy = 1 означает, что для кодирования одного исхода нужен ровно 1 бит (как один ответ «да/нет»). Entropy = 0 означает, что исход полностью предсказуем - не нужно ни одного бита.

Для деревьев решений энтропия - это инструмент оценки «качества» узла. Дерево стремится создавать такие разбиения, чтобы дочерние узлы были как можно **чище** (энтропия ближе к нулю). Если после разбиения по признаку один дочерний узел содержит только «да», а другой только «нет» - это идеальное разбиение с нулевой энтропией в обоих потомках.

**Граничный случай:** когда p_i = 0, формула содержит log2(0) = -infinity. По соглашению 0 * log2(0) = 0, потому что lim(x -> 0) x * log2(x) = 0. В коде это обрабатывается проверкой `if count == 0: continue`.

Information Gain: выбор лучшего вопроса

Теперь у нас есть способ измерить «беспорядок» в данных. Следующий вопрос: **по какому признаку лучше всего разбить данные?** Information Gain (IG) - это разница между энтропией до разбиения и средневзвешенной энтропией после. Дерево решений на каждом шаге выбирает признак с **максимальным** Information Gain - тот, который сильнее всего уменьшает неопределённость.

Классический пример: вы решаете, играть ли в теннис, на основе погоды. У вас 14 наблюдений: 9 раз играли (Yes), 5 раз не играли (No). Какой признак лучше всего разделит данные - Outlook (погода), Temperature, Humidity или Wind?

**Варианты алгоритмов построения деревьев:** - **ID3** (Quinlan, 1986) - использует Information Gain, работает только с категориальными признаками - **C4.5** (Quinlan, 1993) - использует Gain Ratio (нормализованный IG), обрабатывает числовые признаки и пропуски - **CART** (Breiman, 1984) - использует Gini Impurity, строит только бинарные деревья, sklearn использует именно CART

Рекурсивное разбиение продолжается, пока не выполнится одно из условий остановки: все примеры в узле принадлежат одному классу (чистый лист), не осталось признаков для разбиения, или достигнута заданная глубина дерева. Каждый путь от корня к листу - это **правило**: например, «Если Outlook = Sunny И Humidity = Normal, то играем».

У Information Gain есть слабость: он **предпочитает признаки с большим количеством уникальных значений**. Представьте признак «ID клиента» - у каждого уникальное значение, разбиение по нему даст идеально чистые листья (по одному примеру в каждом). IG будет максимальным, но такое дерево бесполезно. Именно поэтому C4.5 использует **Gain Ratio** - Information Gain, делённый на собственную энтропию признака.

Gini Impurity: альтернатива энтропии

Information Gain основан на энтропии и операции логарифма. Но есть альтернативная метрика, которая проще в вычислении и даёт почти такие же результаты: **Gini Impurity**. Формула: **Gini(S) = 1 - sum(p_i^2)**, где p_i - доля класса i в узле. Gini Impurity измеряет вероятность **неправильной** классификации случайно выбранного элемента, если мы назначаем ему класс случайно, пропорционально распределению классов в узле.

**Почему sklearn использует Gini по умолчанию?** Алгоритм CART (Classification And Regression Trees), реализованный в sklearn, исторически использует Gini. Gini не требует вычисления логарифма - только умножение и сложение - что делает его чуть быстрее. На практике деревья, построенные с Gini и с Entropy, совпадают в **99% случаев**. Разница заметна только на крайне специфичных данных.

**Regression Trees: MSE вместо Gini/Entropy** Деревья решений работают не только для классификации. Для задач регрессии (предсказание числа) используется другая метрика разбиения: - **MSE (Mean Squared Error):** среднеквадратичная ошибка в узле - Предсказание в листе = среднее значение всех примеров в этом листе - Дерево выбирает разбиение, минимизирующее суммарную MSE потомков В sklearn: `DecisionTreeRegressor(criterion='squared_error')`

Подведём итог: Gini Impurity и Entropy - это два способа измерить одно и то же: насколько «нечист» узел дерева. Gini проще вычислительно, Entropy имеет информационно-теоретическую интерпретацию. На практике выбор между ними - вопрос вкуса, а не качества модели. Гораздо важнее правильно настроить **глубину дерева и другие ограничения** - а это тема следующего концепта.

Pruning: борьба с overfitting

Если дерево решений не ограничивать, оно будет расти до тех пор, пока каждый лист не станет чистым - по одному примеру в каждом. Такое дерево запоминает обучающую выборку с **точностью 100%**, но на новых данных работает отвратительно. Это классический **overfitting** - модель выучила шум вместо закономерностей. Дерево глубиной 30 для 1000 примеров создаст уникальное «правило» для каждого обучающего примера, включая аномалии и ошибки в данных.

Есть два подхода к pruning (обрезке дерева). **Pre-pruning** (ранняя остановка) - ограничить рост дерева *до* его полного построения. **Post-pruning** - сначала вырастить полное дерево, а потом обрезать ветки, которые не улучшают качество на валидационной выборке.

**Плюсы деревьев решений:** - **Интерпретируемость** - дерево можно визуализировать и объяснить бизнесу: «клиент получит кредит, потому что доход > 50k И стаж > 2 года» - **Не нужна нормализация** - деревья работают с raw features, не нужен scaling - **Работают с категориальными признаками** - не нужен one-hot encoding (для CART в sklearn всё же нужен, но ID3/C4.5 работают напрямую) - **Feature importance бесплатно** - дерево автоматически ранжирует признаки по полезности

**Минусы деревьев решений:** - **Нестабильность** - маленькое изменение в данных (убрать 1 пример) может полностью перестроить дерево. Это следствие жадного алгоритма: изменив корневой split, вы меняете всё дерево - **Axis-aligned splits** - дерево разбивает пространство только параллельно осям (x1 < 5, x2 < 3). Диагональные границы аппроксимируются «лесенкой» из множества разбиений - **Bias к признакам с большим числом значений** - Information Gain предпочитает признаки с многими уникальными значениями Именно из-за нестабильности были изобретены **Random Forest** (ансамбль случайных деревьев) и **Gradient Boosting** - они решают главные проблемы одиночного дерева.

Ключевые идеи

• **Энтропия** = -sum(p_i * log2(p_i)) измеряет неопределённость в узле: 0 = чистый узел, 1 = максимальный хаос (для двух классов)
• **Information Gain** = Entropy(parent) - Weighted_Avg(Entropy(children)) - дерево жадно выбирает признак с максимальным IG, чтобы каждый вопрос максимально сужал неопределённость
• **Gini Impurity** = 1 - sum(p_i^2) - вычислительно проще энтропии и даёт почти такие же деревья; sklearn использует Gini по умолчанию (CART)
• **Pruning** - ключевая защита от overfitting: max_depth, min_samples_leaf (pre-pruning) или ccp_alpha (post-pruning) не дают дереву запомнить каждый обучающий пример
• Деревья решений интерпретируемы и не требуют нормализации, но нестабильны - и именно поэтому врач ставит диагноз серией вопросов, а не одним, а ансамбли деревьев (Random Forest, XGBoost) комбинируют сотни деревьев для стабильности и точности

Связанные темы

Деревья решений - фундамент для ансамблевых методов, и их понимание связано с метриками качества и другими алгоритмами классификации:

• Метрики оценки моделей — Accuracy, Precision, Recall, F1 - метрики, которые мы используем для оценки дерева и подбора гиперпараметров pruning
• Random Forest — Ансамбль из сотен случайных деревьев - решает проблему нестабильности одиночного дерева через bagging и случайный выбор признаков
• Gradient Boosting — Последовательность деревьев, где каждое следующее исправляет ошибки предыдущего - XGBoost, LightGBM, CatBoost базируются на этой идее
• Naive Bayes — Альтернативный подход к классификации через теорему Байеса - использует вероятности вместо деревьев разбиений

Вопросы для размышления

• Дерево решений жадно выбирает лучший признак на каждом шаге. Может ли случиться, что «плохой» первый split приведёт к лучшему дереву в итоге? Почему деревья не перебирают все возможные комбинации?
• Feature importance показывает, что один признак отвечает за 80% решений дерева. Значит ли это, что остальные признаки бесполезны и их можно удалить?
• Почему в задачах, где важна интерпретируемость (медицина, финансы, право), деревья решений иногда предпочитают более точным моделям вроде нейросетей?

Связанные уроки

• ml-12-random-forest — Random Forest - ансамбль деревьев решений
• ml-05-evaluation — Gini impurity и information gain - метрики качества разбиения
• it-02 — Information gain = H(Y) - H(Y|X) из information theory
• prob-04-bayes
• alg-20-greedy