Machine Learning · Теория
Случайный лес из деревьев решений
Идея проста: вместо одного дерева — целая роща. Каждое дерево отвечает по-своему, а лес принимает решение большинством голосов. Получается алгоритм, который точнее, устойчивее и реже ошибается, чем любое отдельное дерево.
01Почему одного дерева мало
Одно дерево решений — мощный, но капризный алгоритм. Стоит немного изменить обучающую выборку — добавить пару объектов, убрать пару других — и дерево может перестроиться целиком. Один шумный пример сбивает выбор порога в верхнем узле, и за ним меняется вся структура. Из-за этого предсказания одного дерева сильно зависят от случайности — это называют высокой дисперсией.
Если такое дерево обучать без ограничений на глубину, оно зазубривает обучающие данные почти идеально, но на новых данных качество падает. Чтобы с этим бороться, его обрезают — но тогда теряется способность улавливать сложные закономерности. Получается замкнутый круг.
Идея в одной фразе
Если одна модель ошибается случайно, давайте обучим много разных моделей и усредним их ответы. Случайные ошибки погасятся, а правильные сигналы усилятся — лес окажется точнее любого своего дерева.
02Идея ансамбля
Представь врачебный консилиум. Один доктор может ошибиться: не заметить симптом, иметь предубеждение, переоценить редкий диагноз. Но если собрать пятерых врачей с разным опытом и спросить каждого по очереди, итоговое решение почти всегда будет надёжнее.
То же самое в машинном обучении. Если у нас есть много разных «экспертов» (деревьев) и каждое смотрит на данные немного со своей стороны, их совместный ответ обычно точнее любого отдельного.
Главное слово здесь — разных. Если все деревья выучили одно и то же, объединять их бессмысленно: они и ошибаться будут одинаково. Поэтому суть случайного леса не в количестве, а в том, как сделать деревья непохожими друг на друга.
Этого добиваются двумя источниками случайности:
- Бэггинг — каждое дерево учится на своей случайной подвыборке данных.
- Случайные признаки — в каждом разбиении дерево выбирает лучший признак не из всех, а из случайно отобранной горстки.
03Бэггинг: выборка с возвращением
Слово «бэггинг» (bagging) расшифровывается как Bootstrap Aggregating — «агрегация бутстрэп-выборок». Звучит сложно, на деле — школьный приём.
Допустим, в обучающей выборке 10 объектов. Чтобы получить бутстрэп-выборку, мы 10 раз случайно вытаскиваем объект с возвращением: вытащили — записали номер — положили обратно — снова тянем.
Получается набор из 10 объектов, но некоторые повторяются по 2–3 раза, а некоторые вообще не попали в выборку. Если повторить процедуру сто раз, получится 100 разных подвыборок — на каждой обучим своё дерево.
Любопытный факт
При размере выборки в несколько тысяч объектов в одну бутстрэп-выборку попадает примерно 63% уникальных объектов. Оставшиеся 37% не вошли в обучение этого дерева — это и есть его out-of-bag, на них можно бесплатно проверить, как оно работает. К этому вернёмся.
04Случайные признаки
Бэггинг ещё не делает лес случайным. Представь, что у тебя есть один очень сильный признак — например, «температура тела» в задаче распознать болезнь. Все деревья на бутстрэп-выборках начнут с одного и того же: разбиения по температуре. Дальше тоже пойдут похожими путями. В итоге получится сотня очень похожих деревьев — и пользы от их голосования будет мало.
Чтобы этого избежать, в случайном лесу применяют второй приём: при каждом разбиении в каждом узле дерево выбирает лучший признак не из всех, а из случайно отобранной горстки.
Сколько признаков рассматривать
Стандартный совет: если всего признаков $p$, для классификации берут $\sqrt{p}$, для регрессии — $p/3$. То есть из 100 признаков каждый узел смотрит примерно на 10 случайных.
Получается так: в одном узле дерево не увидит «температуру» вообще — и будет вынуждено искать сигнал в других признаках. Дерево уйдёт «в сторону» и заметит закономерности, которые более прямолинейный путь пропустил бы.
Это похоже на эффект мозгового штурма, где каждому участнику дают только часть карточек: даже если у группы есть очевидный лидер по знаниям, случайные ограничения заставляют остальных думать.
05Голосование большинством
Когда лес обучен, предсказание на новом объекте делается так:
- Объект прогоняют через каждое дерево по очереди.
- Каждое дерево возвращает свой ответ (класс или число).
- Итог — большинство голосов в задаче классификации или среднее в задаче регрессии.
Кроме самого ответа лес может вернуть вероятности: например, «за класс „выжил“ проголосовало 73 дерева из 100 — значит, вероятность выживания 73%». Это часто полезнее, чем простой ответ да/нет: можно оценить, насколько модель уверена.
06Почему деревья получаются разными
Скажем сразу: лес — это не одно «среднее» дерево. Каждое дерево обучается отдельно и имеет свою структуру. Разнообразие достигается тремя путями:
- Разные данные — бутстрэп-выборки никогда не совпадают.
- Разные точки зрения — в каждом узле дерево «не видит» большинство признаков и опирается на ту горстку, что выпала случайно.
- Жадный алгоритм — даже на одних и тех же данных дерево, начавшее с немного другого порога в корне, может прийти к совсем иной структуре.
В результате одно дерево может выучить, что «класс A — это там, где x₁ < 5 и x₂ > 3», другое — что «класс A — это там, где x₃ маленький». Каждое ошибается в своих местах. Когда они голосуют вместе, их ошибки взаимно компенсируются.
07OOB — бесплатная проверка
В обычном машинном обучении приходится разделять данные на train/test или использовать кросс-валидацию, чтобы оценить качество. Случайный лес даёт оценку бесплатно, прямо в процессе обучения.
Помнишь те 37% объектов, что не попадают в бутстрэп-выборку каждого дерева? Для каждого объекта x из обучающей выборки можно собрать предсказания только тех деревьев, в обучении которых x не участвовал. Эти деревья видят его «впервые», как настоящий тестовый. Усреднение их ответов даёт out-of-bag prediction.
Доля правильных OOB-предсказаний называется OOB-оценкой. Она хорошо приближает настоящее тестовое качество — и при этом нам не пришлось отрезать кусок данных.
08Важность признаков
В отличие от нейросетей и многих других алгоритмов, случайный лес даёт понятную картину: на какие признаки он опирается сильнее всего.
Идея простая. В каждом дереве в каждом разбиении мы знаем, насколько этот выбор уменьшил неопределённость (Gini или энтропию). Если признак часто используется и эти разбиения сильно «очищают» данные — он важный. Усредняем такой счёт по всем деревьям леса и получаем важность каждого признака.
Это огромный плюс: модель не «чёрный ящик», на её результаты можно посмотреть и понять, что на самом деле двигает предсказание. На медицинских данных так находят значимые показатели, на банковских — параметры, по которым модель решает, выдать ли кредит.
09Сильные и слабые стороны
| Плюсы |
Минусы |
| Высокая точность из коробки |
Тяжелее одного дерева — память, время |
| Почти не переобучается |
Хуже интерпретируется (нельзя нарисовать) |
| Не нужно масштабировать признаки |
Не умеет экстраполировать в регрессии |
| Даёт важность признаков |
На разреженных текстовых данных уступает другим |
| Бесплатная OOB-оценка |
Чувствителен к сильно несбалансированным классам |
| Легко распараллеливается |
Уступает градиентному бустингу на сложных табличных задачах |
Когда применять
Случайный лес — отличный базовый алгоритм для любой задачи с табличными данными. Его берут «из коробки», получают приличный результат, а потом уже решают, нужны ли более сложные модели. До эпохи градиентного бустинга он годами оставался победителем большинства Kaggle-соревнований.
10Что дальше
В Песочнице можно поиграть с лесом руками: поставить точки разных классов, посмотреть, как меняется граница при росте числа деревьев и глубины, сравнить лес с одним деревом.
В Реализации мы соберём лес из 30 строк кода и сравним со sklearn.
Куда расти после
- Градиентный бустинг — деревья учатся не независимо, а исправлять ошибки друг друга. Библиотеки: XGBoost, LightGBM, CatBoost. На большинстве табличных задач выигрывает у случайного леса.
- Стекинг и блендинг — комбинирование моделей разных типов (лес + линейная модель + бустинг + нейросеть) для дополнительного прироста точности.
- Изолирующий лес (Isolation Forest) — необычное применение той же идеи для поиска аномалий: чем «короче» путь объекта в случайных деревьях, тем подозрительнее он.
✦ ✦ ✦
Machine Learning · Теоретическое введение
Random Forest · Bagging · Random Subspace