Случайный лес (Random Forest)

Случайный лес — один из самых потрясающих алгоритмов машинного обучения, придуманные Лео Брейманом и Адель Катлер ещё в прошлом веке. Он дошёл до нас в «первозданном виде» (никакие эвристики не смогли его существенно улучшить) и является одним из немногих универсальных алгоритмов. Универсальность заключается, во-первых, в том, что он хорош во многих задачах (по моим оценкам, 70% из встречающихся на практике, если не учитывать задачи с изображениями), во-вторых, в том, что есть случайные леса для решения задач классификации, регрессии, кластеризации, поиска аномалий, селекции признаков и т.д.

Этот пост — краткое практическое руководство для новичков — путеводитель по основным параметрам алгоритма с картинками (которые, кстати, построены на данных последнего конкурса Сбербанка и одной модельной задачи). Под тестом здесь понимается результат на скользящем контроле (для построения графиков использовано 5 фолдов), хотя для отложенного контроля (hold out) выводы будут такими же. Графики лежат в коридорах: дисперсионном и (если есть второй коридор) макс-минном. Все выводы и рекомендации — общие — не для конкретной задачи.

RF (random forest) — это множество решающих деревьев. В задаче регрессии их ответы усредняются, в задаче классификации принимается решение голосованием по большинству. Все деревья строятся независимо по следующей схеме:

Выбирается подвыборка обучающей выборки размера samplesize (м.б. с возвращением) – по ней строится дерево (для каждого дерева — своя подвыборка).
Для построения каждого расщепления в дереве просматриваем max_features случайных признаков (для каждого нового расщепления — свои случайные признаки).
Выбираем наилучшие признак и расщепление по нему (по заранее заданному критерию). Дерево строится, как правило, до исчерпания выборки (пока в листьях не останутся представители только одного класса), но в современных реализациях есть параметры, которые ограничивают высоту дерева, число объектов в листьях и число объектов в подвыборке, при котором проводится расщепление.

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

В библиотеке scikit-learn есть такая реализация RF (привожу только для задачи классификации):

class sklearn.ensemble.RandomForestClassifier(n_estimators=10,
criterion='gini', max_depth=None, min_samples_split=2,
min_samples_leaf=1, min_weight_fraction_leaf=0.0,
max_features='auto', max_leaf_nodes=None, min_impurity_split=1e-07,
bootstrap=True, oob_score=False, n_jobs=1,
random_state=None, verbose=0, warm_start=False,
class_weight=None)

С алгоритмом работают по стандартной схеме, принятой в scikit-learn:

from sklearn.ensemble import RandomForestRegressor
from sklearn.metrics import roc_auc_score
# далее - (X, y) - обучение, (X2, y2) - контроль
# модель - здесь (для контраста) рассмотрим регрессор
model =  RandomForestRegressor(n_estimators=10 ,
                               oob_score=True,
                               random_state=1)
model.fit(X, y) # обучение
a = model.predict(X2) # предсказание

print ("AUC-ROC (oob) = ", roc_auc_score(y, model.oob_prediction_))
print ("AUC-ROC (test) = ", roc_auc_score(y2, a))

Опишем, что означают основные параметры:

Число деревьев — n_estimators

Чем больше деревьев, тем лучше качество, но время настройки и работы RF также пропорционально увеличиваются. Обратите внимание, что часто при увеличении n_estimators качество на обучающей выборке повышается (может даже доходить до 100%), а качество на тесте выходит на асимптоту (можно прикинуть, скольких деревьев Вам достаточно).

Число признаков для выбора расщепления — max_features

График качества на тесте от значения этого праметра унимодальный, на обучении он строго возрастает. При увеличении max_features увеличивается время построения леса, а деревья становятся «более однообразными». По умолчанию он равен sqrt(n) в задачах классификации и n/3 в задачах регрессии. Это самый важный параметр! Его настраивают в первую очередь (при достаточном числе деревьев в лесе).

Минимальное число объектов, при котором выполняется расщепление — min_samples_split

Этот параметр, как правило, не очень важный и можно оставить значение по умолчанию (2). График качества на контроле может быть похожим на «расчёску» (нет явного оптимума). При увеличении параметра качество на обучении падает, а время построения RF сокращается.

Ограничение на число объектов в листьях — min_samples_leaf

Всё, что было описано про min_samples_split, годится и для описания этого параметра. Часто можно оставить значение по умолчанию (1). Кстати, по классике, в задачах регрессии рекомендуется использовать значение 5 (в библиотеке randomForest для R так и реализовано, в sklearn — 1).

Максимальная глубина деревьев — max_depth

Ясно, что чем меньше глубина, тем быстрее строится и работает RF. При увеличении глубины резко возрастает качество на обучении, но и на контроле оно, как правило, увеличивается. Рекомендуется использовать максимальную глубину (кроме случаев, когда объектов слишком много и получаются очень глубокие деревья, построение которых занимает значительное время). При использовании неглубоких деревьев изменение параметров, связанных с ограничением числа объектов в листе и для деления, не приводит к значимому эффекту (листья и так получаются «большими»). Неглубокие деревья рекомендуют использовать в задачах с большим числом шумовых объектов (выбросов).

Критерий расщепления — criterion

По смыслу это очень важный параметр, но по факту здесь нет вариантов выбора. В библиотеке sklearn для регрессии реализованы два критерия: “mse” и “mae”, соответствуют функциям ошибки, которые они минимизируют. В большинстве задач используется mse. Сравнить их пока не берусь, т.к. mae появился совсем недавно — в версии 0.18 (и по-моему, реализован с ошибкой). Для классификации реализованы критерии “gini” и “entropy”, которые соответствуют классическим критериям расщепления: Джини и энтропийному. Простой перебор поможет Вам выбрать, что использовать в конкретной задаче (в авторской реализации алгоритма использовался Джини). Подробнее о критериях надо писать отдельный пост;)

В sklearn-реализации случайного леса нет параметра samplesize, который регламентирует, из скольких объектов делать подвыборку для построения каждого дерева. Такой параметр есть в R-реализации, но, по сути, часто оптимально выбирать из всей выборки. Также рекомендуется выбирать подвыборку с возвращением: bootstrap=True (это и есть бэггинг — bootstrap aggregating).

Совет

По умолчанию в sklearn-овских методах n_jobs=1, т.е. случайный лес строится на одном процессоре. Если Вы хотите существенно ускорить построение, используйте n_jobs=-1 (строить на максимально возможном числе процессоров). Для построения воспроизводимых экспериментов используйте предустановку генератора псевдослучайных чисел: random_state.

П.С. Метод RF хорош ещё тем, что при построении леса параллельно может вычисляться т.н. oob-оценка качества алгоритма (которая очень точная и получается не в ущерб разделения на обучение/тест), oob-ответы алгоритмы (ответы, которые выдавал бы алгоритм на обучающей выборке, если бы «обучался не на ней»), оцениваются важности признаков (но об этом, опять же, надо писать в отдельном посте). Ну, и не стоит забывать про полный перебор значений параметров (если объектов в задаче не очень много).