Решающее дерево

Реша́ющее де́рево (также дерево классификации и регрессии; англ. decision tree) — модель машинного обучения, использующая древовидный граф для принятия решений и представления их возможных последствий. Оно относится к обучению с учителем и применяется для решения задач классификации и регрессии. Решающее дерево строится рекурсивным разбиением исходного множества объектов на подмножества (ветви) на основании значений их признаков. Благодаря наглядности представления правил и интерпретируемости получаемых результатов деревья являются одним из наиболее популярных методов интеллектуального анализа данных.

Основные определения и простейший алгоритм синтеза дерева

Формально решающее дерево — это ориентированный ациклический граф, имеющий одну корневую вершину и множество конечных вершин (листьев). Каждая внутренняя вершина $v$ содержит логическое условие (предикат) над значением одного из признаков $X_i$ , а рёбра, исходящие из неё, соответствуют исходам проверки. Листья содержат прогнозируемое значение целевой переменной — класс в задачах классификации или число в задачах регрессии.

Жадный алгоритм синтеза дерева (TDIDT — англ. Top-Down Induction of Decision Trees) строит модель сверху вниз:

Корню дерева ставится в соответствие вся обучающая выборка.
Выбирается признак и пороговое значение (для непрерывного признака) либо подмножество категорий (для номинального), которые наилучшим образом разделяют выборку с точки зрения заданного функционала качества.
Выборка разбивается на части по выбранному предикату, и для каждой дочерней вершины процесс повторяется рекурсивно.
Рост ветви прекращается при выполнении критерия останова; текущая вершина объявляется листом.

Процесс является «жадным», поскольку на каждом шаге выбирается локально оптимальное разбиение без учёта последующих шагов.

Разновидности: тип задачи

В зависимости от типа целевой переменной выделяют:

Деревья классификации (англ. classification trees) — целевая переменная дискретна. Лист предсказывает наиболее частый класс или распределение вероятностей классов.
Деревья регрессии (англ. regression trees) — целевая переменная непрерывна. Лист содержит константу (обычно среднее арифметическое или медиану значений целевой переменной попавших в лист наблюдений).

Иногда выделяют деревья выживаемости (англ. survival trees) для цензурированных данных, но они представляют собой расширение двух основных типов.

Критерии ветвления и критерии останова

Критерии ветвления

Критерий ветвления измеряет, насколько «чище» становятся дочерние подмножества после разбиения. Чем выше однородность целевой переменной в узле, тем лучше.

Энтропийный критерий (прирост информации) использует понятие информационной энтропии Шеннона. Для узла $S$ с распределением классов $p_i$ энтропия определяется как

$H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i.$ Тогда информационный выигрыш (англ. information gain) при разбиении $S$ по признаку $A$ равен $IG(S, A) = H(S) - \sum_{v \in \mathrm{Values}(A)} \frac{|S_v|}{|S|} H(S_v),$ где $S_v$ — подмножество объектов, для которых признак $A$ принял значение $v$ . Выбирается разбиение, максимизирующее $IG$ . Недостаток — критерий предпочитает признаки с большим числом значений.

Критерий Джини (англ. Gini impurity) измеряет вероятность неверной классификации случайного объекта, если относить его к классу с вероятностью, равной доле класса в узле:

$Gini(S) = 1 - \sum_{i=1}^{c} p_i^2.$ Разбиение, минимизирующее средневзвешенный индекс Джини дочерних узлов, считается оптимальным. В отличие от энтропийного критерия, индекс Джини не использует логарифм, что делает вычисления быстрее.

Критерии для регрессионных деревьев основаны на снижении дисперсии. В узле $S$ вычисляется среднеквадратическая ошибка (MSE) относительно среднего значения $\bar{y}$ :

$MSE(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar{y})^2.$ При разбиении по признаку $A$ минимизируют взвешенную сумму MSE дочерних узлов.

В алгоритме CART дополнительно применяется критерий Twoing, основанный на сравнении распределений классов в левой и правой ветвях, что полезно для задач с большим числом классов.

Критерии остановки

Критерии останова предотвращают бесконечное дробление дерева. Типичные условия:

Глубина дерева достигла заданного предела.
Число объектов в узле меньше порога $N_{\min}$ .
Узел содержит объекты только одного класса (или дисперсия в регрессионном узле близка к нулю).
Улучшение критерия ветвления меньше заданного порога.
Исчерпаны все признаки.

Ранняя остановка роста дерева относится к методам предредукции (см. ниже).

Что находится во внутренних вершинах и в листьях

Внутренняя вершина хранит:

Условие расщепления: для номинального признака — подмножество значений, отправляемых в каждую дочернюю ветвь; для порядкового или непрерывного — правило вида « $X_j \leq t$ » (в случае бинарного дерева). Для многозначных расщеплений (ID3, C4.5) внутренняя вершина может иметь более двух дочерних вершин.
Ссылки на дочерние вершины.
Дополнительную служебную информацию (число объектов, распределение классов).

Лист (терминальная вершина) содержит прогноз:

Для классификации: метку класса (голосованием большинства) и, как правило, вектор оценённых вероятностей $\hat{p}_i$ .
Для регрессии: число — среднее или медиана значений целевой переменной попавших в лист наблюдений. Иногда сохраняется вся модель линейной регрессии (в деревьях моделей, таких как M5).

Передача информации между вершинами (alternating decision tree)

Чередующееся решающее дерево (англ. alternating decision tree, ADTree) представляет собой обобщение классической модели, в котором информация передаётся между вершинами специальным образом ^[1]. Граф ADTree состоит из чередующихся слоёв:

Узлы-предикаты (англ. prediction nodes), содержащие значение вклада в итоговый счёт.
Узлы-расщепители (англ. splitter nodes), задающие условие над признаком (предикат).

Проход по дереву суммирует значения всех узлов-предикатов, достижимых из корня при соблюдении соответствующих условий расщепления. Знак итоговой суммы определяет предсказываемый класс, а модуль — степень уверенности. Такая архитектура может рассматриваться как бустинг над деревьями малой глубины, компактно представленный в виде одного графа. ADTree примечательны тем, что промежуточные предсказания накапливаются по мере движения по дереву, реализуя «передачу информации» от корня к листьям.

Редукция решающих деревьев

Склонность решающих деревьев к переобучению — порождению излишне сложных структур, точно воспроизводящих шум в обучающих данных — требует обязательного применения процедур редукции.

Предредукция (pre-pruning)

Предредукция (англ. pre-pruning) останавливает рост дерева досрочно на основании критериев останова (минимальное число объектов в узле, минимальный прирост качества, ограничение глубины). Метод вычислительно эффективен, однако существует риск остановки на «плато» перед значимым расщеплением.

Постредукция (post-pruning)

Постредукция (англ. post-pruning) сначала выращивает полное (избыточное) дерево, а затем последовательно заменяет поддеревья листьями или более простыми поддеревьями, если это не ухудшает (или несущественно ухудшает) обобщающую способность. Основные алгоритмы:

REP (англ. Reduced Error Pruning) — использует отдельную отложенную выборку для оценки ошибки.
PEP (англ. Pessimistic Error Pruning) — оценивает ошибку на обучающей выборке с поправкой на непрерывность (псевдоправдоподобие), применяется в C4.5.
Cost-complexity pruning (минимальная стоимость-сложность) — метод, введённый в алгоритме CART. Минимизирует взвешенную сумму ошибки дерева и штрафа за количество листьев:

$R_\alpha(T) = R(T) + \alpha |T_{\text{leaf}}|,$ где $\alpha$ — параметр, подбираемый кросс-валидацией.

Оценивание вероятностей и полужадный синтез

Оценивание вероятностей классов в листе обычно выполняется на основе частот: $\hat{p}_i = \frac{n_i}{n},$ где $n_i$ — число объектов класса $i$ в листе, $n$ — общее число объектов. Во избежание нулевых вероятностей применяют сглаживание Лапласа или m-оценку: $\hat{p}_i = \frac{n_i + m \cdot p_{i0}}{n + m},$ где $p_{i0}$ — априорная вероятность класса, а $m$ — параметр эквивалентного объёма выборки.

Полужадный синтез (англ. semi-greedy induction) объединяет стратегии выбора разбиений, не сводящиеся строго к максимизации локального критерия. Например:

Выбор не лучшего признака, а одного из $k$ лучших с некоторой вероятностью (рандомизированные деревья).
Использование ограниченного просмотра вперёд (англ. lookahead).
Байесовский подход, усредняющий неопределённость относительно параметров расщепления.

Такие методы часто улучшают итоговое качество в композициях, где разнообразие базовых деревьев играет ключевую роль.

Алгоритмы построения

ID3

ID3 (Iterative Dichotomiser 3; Quinlan, 1986)^[1] — жадный алгоритм для номинальных признаков и классификации. На каждом шаге выбирает атрибут, максимизирующий информационный выигрыш. Не обрабатывает пропуски и непрерывные признаки, не содержит постредукции.

C4.5

C4.5 (Quinlan, 1993)^[1] — развитие ID3. Основные улучшения:

Использование коэффициента Gain Ratio для устранения смещения в сторону многозначных признаков:

$GainRatio(S, A) = \frac{IG(S, A)}{-\sum_{v} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}}.$

Обработка непрерывных признаков через бинарные пороги.
Встроенная обработка пропусков (объект с пропуском распределяется по ветвям с весом, пропорциональным доле объектов в каждой ветви).
Постредукция методом пессимистической оценки ошибки.

C5.0

C5.0 — коммерческая версия, развивающая идеи C4.5. Отличается более высокой скоростью, эффективным использованием памяти, генерацией наборов правил и встроенной поддержкой бустинга. Детали алгоритма являются закрытыми.

CART

CART (Classification and Regression Trees; Breiman, Friedman, Olshen, Stone, 1984)^[1] строит строго бинарные деревья. Для классификации по умолчанию используется критерий Джини, для регрессии — снижение среднеквадратической ошибки. CART осуществляет постредукцию cost-complexity pruning с выбором параметра $\alpha$ по кросс-валидации. Модель обрабатывает как непрерывные, так и категориальные предикторы.

LISTBB

LISTBB (List-Based Branch-and-Bound; Rymon, 1993)^[1] — алгоритм, использующий списочную организацию данных и метод ветвей и границ для эффективного поиска оптимальных разбиений. Все объекты, удовлетворяющие определённому предикату, образуют линейный список, что позволяет быстро перебирать пороговые значения и вычислять критерии качества без повторного сканирования всей выборки. Идеи применения списочных структур в дальнейшем нашли независимое развитие в алгоритмах SLIQ, SPRINT и RainForest для больших данных.

Другие алгоритмы построения

Перечисленные выше алгоритмы (ID3, C4.5, C5.0, CART, LISTBB) представляют собой лишь наиболее известные и исторически значимые представители обширного семейства решающих деревьев. За десятилетия исследований было разработано более пятидесяти различных алгоритмов, отличающихся стратегией выбора разбиений, критериями ветвления, методами обработки пропусков, способами редукции и областями применения.

Среди них можно выделить:

CHAID (Chi-squared Automatic Interaction Detection) и QUEST (Quick, Unbiased, Efficient Statistical Tree) — алгоритмы, использующие статистические критерии для уменьшения смещения при выборе признака;
CTREE (Conditional Inference Trees) — алгоритм, основанный на условной инференции и применяющий статистические тесты для принятия решений о разбиении;
M5 — алгоритм для построения регрессионных деревьев с линейными моделями в листьях;
NBTree — гибридный подход, совмещающий дерево решений с наивным байесовским классификатором;
REPTree (Reduced Error Pruning Tree) — быстрый алгоритм, использующий сокращение ошибок для упрощения дерева;
эволюционные и генетические алгоритмы, которые ищут оптимальную структуру дерева без жадных ограничений;
алгоритмы построения оптимальных разреженных деревьев, такие как OSDT (Optimal Sparse Decision Trees);
метод альтернативной оптимизации деревьев (TAO, Tree Alternating Optimization).

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

Обобщающая способность решающих деревьев

Решающие деревья являются непараметрическим методом и обладают низким смещением, но высокой дисперсией: небольшие изменения обучающей выборки могут приводить к существенно различающимся структурам. Нередуцированные деревья почти всегда переобучены. Правильная постредукция, а также задание ограничений (минимальное число объектов в листе, максимальная глубина) значительно улучшают обобщающую способность. Деревья хорошо работают с пропущенными данными, не требуют масштабирования признаков и могут улавливать нелинейные зависимости, однако уступают современным ансамблевым методам по точности.

Оценка неопределённости прогнозов и измерение ошибки классификации

Нестабильность и бутстрэп-оценка разброса

Дискретная природа решающих деревьев и высокая чувствительность к данным приводят к тому, что структура дерева может радикально меняться даже при незначительных изменениях обучающей выборки — свойство, известное как нестабильность модели. Это ограничивает прямое использование единственного дерева в задачах, требующих оценки надёжности прогнозов.

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

Измерение ошибки классификации

Выбор метрики качества принципиально влияет на процесс обучения и оценку деревьев. Помимо стандартной доли верных ответов (accuracy), вводят следующие подходы.

Кросс-энтропия и нормализованное отрицательное логарифмическое правдоподобие

Для вероятностной постановки, когда дерево оценивает вероятности $\hat{p}_i$ принадлежности к классам, качество часто измеряют с помощью средней логарифмической функции потерь: $-\frac{1}{N} \sum_{n=1}^{N} \log \hat{p}_{y_n}(x_n),$ где $y_n$ — истинный класс объекта $x_n$ . Эта метрика, называемая кросс-энтропией или нормализованным отрицательным логарифмическим правдоподобием, оценивает не только долю ошибок, но и уверенность прогнозов: уверенная ошибка (прогноз высокой вероятности для неверного класса) штрафуется логарифмически сильнее, чем неуверенная. Минимизация кросс-энтропии эквивалентна максимизации правдоподобия, что теоретически обосновывает использование таких критериев, как информационный выигрыш при построении дерева.

Матрица стоимостей

В задачах с асимметричной ценой ошибок (например, медицинская диагностика, обнаружение мошенничества) вводится матрица стоимостей $C$ , где $C_{ij}$ — потери от предсказания класса $j$ , когда истинный класс есть $i$ . Для бинарного случая решение о назначении класса принимается путём сравнения ожидаемых потерь. В листе порог вероятности сдвигается: объект относится к положительному классу, если $\hat{p}_1 > \frac{C_{01}}{C_{01}+C_{10}}$ (при нулевых потерях за правильные решения). Это смещение порога позволяет контролировать компромисс между чувствительностью и специфичностью. Метод детально разработан в области cost-sensitive learning ^[1].

Подход Неймана–Пирсона

В ситуациях, когда необходимо строго ограничить долю ложноположительных срабатываний (вероятность ошибки первого рода) и затем минимизировать долю ложноотрицательных ошибок, применяют подход Неймана–Пирсона в контексте машинного обучения ^[1]. Вместо подбора весов матрицы стоимостей исследователь фиксирует допустимый верхний предел $\alpha$ на вероятность ложного положительного решения (уровень значимости), после чего выбирается классификатор, минимизирующий вероятность ложноотрицательного пропуска (максимизирующий мощность). Дерево решений в этой парадигме обучается или калибруется таким образом, чтобы на отложенной выборке доля false positive не превышала $\alpha$ , а метрикой качества выступает true positive rate. Главное преимущество подхода — отсутствие необходимости в явном задании стоимостей ошибок и устойчивость к изменению априорной вероятности классов в эксплуатационных данных: решающее правило определяется только условными распределениями признаков, а не пропорциями классов в обучающей выборке.

Композиции решающих деревьев

Одиночное дерево редко является лучшей моделью по точности, поэтому широко применяют композиции:

Случайный лес (англ. random forest; Breiman, 2001) — строится путём бэггинга (усреднения результатов большого числа деревьев, обученных на бутстрап-выборках) с добавлением случайного подпространства признаков: в каждом узле разбиение выбирается не из всех признаков, а из случайно отобранного их подмножества. Это увеличивает декорреляцию деревьев и существенно снижает дисперсию.

Бустинг над деревьями — последовательное построение ансамбля, в котором каждое следующее дерево исправляет ошибки предыдущих. Алгоритмы:
- AdaBoost — на каждой итерации перевзвешивает объекты, увеличивая штраф за ошибки.
- Градиентный бустинг над решающими деревьями (англ. gradient boosting machines) — каждое новое дерево аппроксимирует антиградиент функции потерь. Реализации: XGBoost, LightGBM, CatBoost, которые доминируют на соревнованиях по машинному обучению благодаря высокой точности и скорости.

История

Ранние прообразы деревьев решений восходят к статистическим методам автоматического обнаружения взаимодействий. Алгоритм AID (Automatic Interaction Detection; Morgan, Sonquist, 1963) использовал бинарное разбиение для регрессии. Метод THAID (Morgan, Messenger, 1973) применил многомерный анализ для классификации. В 1984 году Лео Брейман, Джером Фридман, Ричард Олшен и Чарльз Стоун опубликовали монографию «Classification and Regression Trees», в которой детально описали алгоритм CART и его теоретические обоснования, что стало поворотным моментом. Параллельно Джон Росс Куинлан разработал семейство алгоритмов, начиная с ID3 (1986), который привнёс энтропийный критерий, и его преемник C4.5 (1993), ставший де-факто стандартом в академической среде. В 1999 году Фрейнд и Мейсон предложили чередующиеся деревья (ADTree). Развитие ансамблевых методов в 1990–2000-е годы (случайный лес Бреймана, AdaBoost Фрейнд и Шапире, градиентный бустинг Фридмана) вывело деревья на новый уровень, сделав их фундаментальными строительными блоками в самых мощных современных моделях.

См. также

Ссылки

Classification and Regression Trees — лекция Cosma Shalizi (CMU) по деревьям классификации и регрессии.
Статистическое машинное обучение — курс 36-350, Университет Карнеги — Меллон.

Литература

Breiman L., Friedman J. H., Olshen R. A., Stone C. J. Classification and Regression Trees. — Wadsworth, 1984. — 368 p.
Quinlan J. R. Induction of decision trees // Machine Learning. — 1986. — Vol. 1, no. 1. — P. 81–106.
Quinlan J. R. C4.5: Programs for Machine Learning. — Morgan Kaufmann, 1993. — 302 p.
Freund Y., Mason L. The alternating decision tree learning algorithm // Proceedings of the Sixteenth International Conference on Machine Learning (ICML). — 1999. — P. 124–133.
Rymon R. An SE-tree-based characterization of the induction problem // Proceedings of the Tenth International Conference on Machine Learning (ICML). — 1993. — P. 268–275.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — 2nd ed. — Springer, 2009. — Глава 9.
Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — Глава 14.
Elkan C. The foundations of cost-sensitive learning // Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI). — 2001. — P. 973–978.
Scott C., Nowak R. D. A Neyman-Pearson approach to statistical learning // IEEE Transactions on Information Theory. — 2005. — Vol. 51, no. 11. — P. 3806–3819.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B5%D1%88%D0%B0%D1%8E%D1%89%D0%B5%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE»

Категории: Энциклопедия анализа данных | Популярные и обзорные статьи | Решающие деревья

@@ Строка 196: / Строка 196: @@
 * Elkan C. The foundations of cost-sensitive learning // Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI). — 2001. — P. 973–978.
 * Scott C., Nowak R. D. A Neyman-Pearson approach to statistical learning // IEEE Transactions on Information Theory. — 2005. — Vol. 51, no. 11. — P. 3806–3819.
+[[Категория:Энциклопедия анализа данных]]
+[[Категория:Популярные и обзорные статьи]]
+[[Категория:Решающие деревья]]

Решающее дерево

Материал из MachineLearning.

Текущая версия

Содержание