Decision Tree

Дерево решений — это модель обучения с учителем, которая делает предсказания, последовательно задавая вопросы «да или нет» о признаках входных данных, например «Доход превышает $50,000?», и проходя от корневого узла к листу с предсказанием согласно ответам. Деревья классификации предсказывают класс в каждом листе, а деревья регрессии — число. Каждое предсказание представляет собой понятную цепочку правил, поэтому деревья — стандартный инструмент для объяснимого ИИ (XAI). Деревья также служат строительными блоками случайных лесов и ансамблей градиентного бустинга, которые по-прежнему превосходят глубокое обучение на табличных наборах данных среднего размера. Алгоритм CART Брэймана, Фридмана, Олшена и Стоуна (1984), а также ID3 (1986) и C4.5 (1993) Росса Куинлана заложили основы обучения деревьев на данных.

Как строится дерево решений#

Деревья растут сверху вниз посредством рекурсивного разбиения. В каждом узле алгоритм оценивает возможные разбиения, каждое из которых представляет собой признак и порог для числовых признаков, выбирает разбиение, которое делает два дочерних узла наиболее однородными, и повторяет поиск в каждом дочернем узле. Однородность в деревьях классификации оценивают с помощью индекса Джини — вероятности ошибочно классифицировать случайную выборку из узла, если метки назначать случайным образом в пропорциях классов этого узла, — или с помощью энтропии, уменьшение которой называется приростом информации. В деревьях регрессии выбирают разбиение, сильнее всего уменьшающее квадратичную ошибку; каждый лист предсказывает среднее целевое значение обучающих выборок в нём. Рост прекращается, когда узел становится однородным, содержит слишком мало выборок или достигает максимальной глубины. При каждом разбиении алгоритм заглядывает только на один шаг вперёд, поэтому жадный поиск быстро строит хорошее дерево. Поиск гарантированно оптимального дерева — NP-трудная задача.

DecisionTreeClassifier из scikit-learn реализует оптимизированную версию CART. В этом примере на наборе данных об ирисах вырастает дерево глубиной 2 и выводятся найденные им правила:

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=42)

# A depth limit keeps the tree small enough to read and less prone to overfitting
clf = DecisionTreeClassifier(max_depth=2, random_state=42)
clf.fit(X_train, y_train)

print(export_text(clf, feature_names=iris.feature_names))
print(f"Test accuracy: {clf.score(X_test, y_test):.2f}")

Дерево использует только длину лепестка: цветы с длиной лепестка не более 2.45 см относятся к Setosa (класс 0), а второй порог — 4.75 см — отделяет Versicolor (класс 1) от Virginica (класс 2). По этим правилам правильно классифицируются 97% отложенных для проверки цветов.

Каждое разбиение — это пороговое правило такого вида: его можно обучить на данных, а можно задать вручную. В мониторе тренировок Ultralytics AIGym вручную задаются два таких правила для результата оценки позы YOLO26: кадр помечается как «вверх», когда угол локтя, вычисленный по ключевым точкам плеча, локтя и запястья, превышает 145°, и как «вниз», когда он становится меньше 90°. Повторение засчитывается при каждом переходе из положения «вверх» в положение «вниз».

Переобучение и обрезка дерева#

Дерево, которое растёт до тех пор, пока каждый лист не станет однородным, запоминает обучающие данные, включая шум. Это классический пример переобучения. Предварительная обрезка останавливает рост раньше, ограничивая, например, максимальную глубину или минимальное количество выборок на лист. При последующей обрезке сначала строится полное дерево, а затем удаляются ветви, которые дают небольшой прирост. В scikit-learn минимальная обрезка по критерию стоимости и сложности настраивается параметром ccp_alpha: чем он больше, тем сильнее обрезается дерево. Оба типа ограничений относятся к гиперпараметрам, которые выбирают с помощью перекрёстной проверки.

Даже обрезанное дерево обладает высокой дисперсией: небольшое изменение обучающих данных может изменить верхнее разбиение, а вместе с ним и все последующие. Ансамбли решают эту проблему, объединяя множество деревьев: можно усреднить деревья, обученные на бутстрэп-выборках, как в случайных лесах, или добавлять деревья по одному, чтобы исправлять ошибки предыдущих, как в градиентном бустинге.

Преимущества и ограничения#

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

Применение#

• Кредитные решения: Кредиторы используют неглубокие деревья и основанные на деревьях скоринговые карты для сортировки заявок по риску. Каждое решение можно проследить до пороговых значений дохода, кредитной истории и задолженности, на которых оно основано.
• Клиническая сортировка пациентов: Клинические правила принятия решений в форме деревьев распределяют пациентов по показателям жизнедеятельности и симптомам, например определяя, требуется ли пациенту срочная визуализация.
• Отток клиентов: Деревья делят клиентов на группы с высоким и низким риском отказа от услуг по интенсивности использования, сроку обслуживания и истории обращений в поддержку. Путь к каждой группе можно описать простыми словами.
• Прогнозное обслуживание: Деревья градиентного бустинга, обученные на признаках вибрации, температуры и времени работы, оценивают, какие машины могут выйти из строя до следующего обслуживания.

Деревья решений и родственные понятия#

• Случайные леса: Усредняют множество деревьев, обученных на бутстрэп-выборках и случайных подмножествах признаков. Это повышает точность и стабильность ценой снижения понятности по сравнению с отдельным деревом.
• XGBoost, LightGBM и CatBoost: Библиотеки градиентного бустинга, которые добавляют деревья по одному, чтобы исправлять ошибки предыдущих. LightGBM создан для быстрой работы на больших наборах данных, а CatBoost — для непосредственной обработки категориальных признаков.
• Глубокое обучение: Нейросети извлекают признаки из исходных изображений, аудио и текста, тогда как деревья выполняют разбиения по признакам, уже представленным в столбцах таблицы.
• Деревья анализа решений: В исследовании операций и бизнес-планировании деревом решений также называют схему, которую аналитик строит вручную. Она включает узлы решений, случайных событий и выплат, чтобы сравнивать варианты по ожидаемой ценности. Такая схема строится на основе оценённых вероятностей, а не обучается на данных.