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

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

random_forest.jpg

Этот пост — краткое практическое руководство для новичков — путеводитель по  основным параметрам алгоритма с картинками (которые, кстати, построены на данных последнего конкурса Сбербанка и одной модельной задачи). Под тестом здесь понимается результат на скользящем контроле (для построения графиков использовано 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%), а качество на тесте выходит на асимптоту (можно прикинуть, скольких деревьев Вам достаточно).

n_estimators

n_estimators_model

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

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

max_features

max_features_model

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

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

min_samples_split

min_samples_split_model

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

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

min_samples_leaf

min_samples_leaf_model.png

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

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

max_depth.png

max_depth_model.png

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

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

criterion

criterion_model

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

Совет

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

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

 

 

Реклама

Случайный лес (Random Forest): 20 комментариев

  1. Спасибо за руководство!
    Хотел бы добавить несколько наблюдений из своей практики:

    — стоит добавить, что методы, основанные на деревьях, помимо задач с изображениями, не так хорошо справляются с разреженными признаками, особенно когда их очень много. Это тексты и прочие задачи, где мы используем подход Bag of smth, например, есть посещенные пользователями сайты, их миллионы, и мы строим признаки из «мешка» сайтов
    — макс. глубину все равно лучше настраивать, хоть теория и говорит, что ее не надо ограничивать. Для «серьезных» выборок более осмысленно использовать RandomizedSearchCV, a не GridSearchCV, результат не сильно хуже, зато намного быстрее работает
    — RF умеет оценивать важности признаков (формального определения не видел, но интуитивно понятно). Как правило, лес устойчив к шумовым признакам, и поэтому кривая валидации по числу задействованных исходных признаков будет выходить на асимптоту. То есть если исходных признаков, скажем, 150, можно оценить важность признаков, построить кривые валидации для моделей, обученных на 50, 60, .. 150 признаках и отловить тот момент, когда добавление новых, менее важных признаков, уже не так повышает качество
    — gini/entropy можно вообще не настраивать — работают практически одинаково
    — в примере с классификацией a = model.predict(X2) лучше заменить на a = model.predict_proba(X2)[:,1]. при метрике AUC намного лучше вероятности прогнозировать (Вы это и так прекрасно знаете, просто уточнил)

    Пара интересующих меня вопросов:
    — всегда ди лучше Xgboost использовать или есть примеры, когда именно RF лучше работал?
    — не получаются ли на практике OOB-оценки слишком оптимистичными (у меня чаще — да)? типа того, что они все равно получены по тем же данным, на которых лес (или любой другой бэггинг) обучался.
    — Вы случайно не знаете статей, в которых теоретически обосновывалось бы использование метрик типа Джини или прироста информации? скажем, через VC-оценки или что-то более практичное типа сложности Радемахера? А то весь мир давно использует эти эвристики, но я нигде не видел объяснения, даже в оригинальной статье. И на Cross Validated игнорят 🙂 http://stats.stackexchange.com/questions/208749/gini-impurity-and-generalization-error

    • «методы, основанные на деревьях, помимо задач с изображениями, не так хорошо справляются с разреженными признаками…»

      Да, конечно. Хотя, в приведённых примерах главная проблема в том, что число признаков огромно, и потестить лес при достаточно большом max_features не получается. Были случаи, когда в таких задачах применялся что-то типа метода главных компонент, и потом леса работали на ура;)

      «макс. глубину все равно лучше настраивать…»

      У меня под рукой нет ни одного примера, где это было бы так… Вот в XGBoost это существенно, а в RF лично мне ещё ни разу не приходилось сокращать глубину, кроме описанных выше случаев.

      «RF умеет оценивать важности признаков…»

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

      «gini/entropy можно вообще не настраивать — работают практически одинаково»

      Согласен. Хотя на кэгле, где борьба за сотые – надо.

      «a = model.predict(X2) лучше заменить на a = model.predict_proba(X2)[:,1]»

      Нет, у меня там регрессор, если заменить будет ошибка;)

      «всегда ди лучше Xgboost использовать или есть примеры, когда именно RF лучше работал?»

      Да, сходу не вспомню, но на том же кэгле были задачки, в которых RF был лучше. Хотя, конечно, бустинг деревьев в 95% случаев лучше усреднения.

      «не получаются ли на практике OOB-оценки слишком оптимистичными»

      Возможно. В sklearn-реализации я их особо не использую. Применял в самописном RF, но там я по-особому считал, получались, вроде, нормальные – не завышенные.

      «Вы случайно не знаете статей, в которых теоретически обосновывалось бы использование метрик типа Джини или прироста информации?»

      Нет, надо бы поискать… Как Вы сами заметили, они почти одинаково работают. Я экспериментировал, туда какую эвристику не сунь, будет примерно также! В одной из серьёзных задач оптимально было вообще разбивать выборку пополам (каждый раз выбирался признак, на котором разбиение больше всего похоже на «поровну»).

  2. Спасибо за публикацию!

    А есть ли информация и примеры по использованию RF в задачах кластеризации и поиска аномалий? Особенно интересно было бы взглянуть на применеие даннго метода в таких задачах в связи с его способностью оценивать важность признаков и «нативной» поддержкой категориальных признаков.
    Из публикаций удалоьс найти вот эту статью http://www.nature.com/modpathol/journal/v18/n4/pdf/3800322a.pdf
    А также реализацию для R. Но ничего толкового для Python

    • По поводу аномалий: в sklearn уже всё реализовано, http://scikit-learn.org/stable/modules/outlier_detection.html (см. IsolationForest, там есть и нужные ссылки)

      Интересный способ предложен здесь:
      http://docs.salford-systems.com/AdeleCutler.pdf
      если есть какие-то объекты — объявим их первым классом, синтетически сгенерируем второй, будем их разделять — те объекты, которые «плохо разделяются» и есть «крайние объекты класса», т.е. нетипичные.

      В кластеризации RF используют редко. Что-то сходу не смог найти одну интересную диссертацию на эту тему. Идея как их можно использовать: когда строим лес (не важно на какой целевой признак настраиваемся), если объекты часто попадают в один лист, то они похожи, редко — нет. Поэтому можно придумать такую метрику — число непопаданий в один лист в деревьях леса. По ней уже можно кластеризовать (т.е. RF можно использовать для синтеза адекватной метрики 😉 , но ясно, что это не для Big Dat-ы.

      Да, в R очень много всего хорошего реализовано. Некоторые классные алгоритмы есть только в R. Например только там «правильный способ оценки важности признаков», тот что sklearn — не очень хороший, зато быстрый.

      • Большое спасибо за ответ и ссылки!
        Побольше бы таких хороших материалов 🙂
        Было бы очень здорово увидеть книгу за вашим авторством ориентированную на практику и аккумулирующую эмпирические находки и знания, учитывая ваше умение находить элегантные решения задач.

      • Спасибо за тёплые слова. Собственно, меня для этого в своё время просили начать блог вести: говорили, что займёт меньше времени, чем книга, и будет постоянная обратная связь.

  3. Спасибо!

    А есть ли принципиальная разница оценивать важность переменных по случайному лесу или по xgboost?
    Насколько я видел, результаты в одном тренде (плюс-минус), но в целом, есть ли практика?

    • Смотря для чего эту важность использовать. Если использовать «правильно», то нет. Я точно не знаю, как оценивается важность в xgboost, но судя по скорости, примерно также как в sklearn-овском лесе. А это не очень хороший метод! Правильно так, как писали «папа и мама RF»: http://docs.salford-systems.com/AdeleCutler.pdf
      Лучше написать свой shuffle-тест.

  4. Здравствуйте. Спасибо за интересную статью!

    Кстати, есть интересная статейка: http://www.jmlr.org/papers/volume15/delgado14a/delgado14a.pdf
    Авторы сравнили 179 классификаторов (xgboost’а, вроде, нет) на 121 датасете, и RF оказался «лучшим». Наверняка, там есть свои нюансы (настройка параметров, предобрабока), но все-таки интересный результат получился.

  5. Спасибо за материал. От себя добавлю.
    по поводу оптимистичности. вместо просто OOB лучше использовать out-of-time&out-of-sample
    по поводу «лес устойчив к шумовым признакам… отловить тот момент, когда добавление новых, менее важных признаков, уже не так повышает качество» это не признак леса. в любую модель можно перестать добавлять переменные и тем самым уменьшить вероятность перетренировки
    по определению и расчету важности можно посмотреть здесь http://www.slideshare.net/GewisstaLibrary/ss-52984378 61-я страница. там же можно прочесть про матрицу близостей — очень полезную вещь, использующуюся для импутации, детекции выбросов

  6. Здравсвуйте, Александр Геннадьевич!

    В первую очередь хочу Вас поблагодарить за эту статью и в целом за Ваш труд по просвещению в области анализа данных!

    С Вашего позволения пару вопросов Вам, а также всем, кому есть, что ответить. 🙂

    Есть задача по предсказанию выбора клиента, бинарная. В детали не буду опускаться, чтобы не нагружать, интересны общие моменты:
    1. В силу общности датасета с датасетами традиционными для скоринга, применяю модель случайного леса, но результат плохой (AUC = 0,56). После этого я вывожу важность признаков, и вижу, что признак, который алгоритм расценивает как самый важный, на мой взгляд, совершенно не важен.
    Я могу каким-то образом влиять на это?
    Например, я провожу такой эксперимент: создаю датасет с 5 признаками, 4 из них случайны, а 5 состоящий из случайных целых чисел влияет на целевой вектор(бинарный) таким образом, что если число четное, то соответствующее значение целевого вектора — 1, нечентое — 0. Применяю к этой модели random forest результат auc = 0.5. И опять же, модель не может понять, что самый важный признак — 5.
    2. Я запускаю на обучающей выборке сетку по трем фолдам по заданным спискам параметров, в результате bets_score у меня 0,82. При этом при обучении с best_parameters roc_auc_score = 0.5.
    Правильно я понимаю, что тут возможны два варианта —
    а. разная метрика у roc_auc_score и best_score, кстати, в документации, к сожалению не нашел какая метрика в best_score?
    b. некоторое локальное переобучение на фолдах, которое сказывается на полной обучающей выборке?

    Было бы здорово узнать от Вас об общих рекомендациях в вопросах борьбы с переобучением.

    Спасибо за внимание!

    • Здравствуйте, Борис!
      По поводу Вашего примера в п.1. Тут Вы делаете хитрую подмену понятий… да, 5й признак самый важный, но это не обнаружит ни одна модель! Все они (модели) построены по принципу разделения: строится (пусть неявно) некоторая поверхность, которая отделяет один класс от другого. Странно, если бы в классе поверхностей были бы такие, что отделяют чётные числа от нечётных. Вот если Вы добавите бинарный признак чётности — rf его сразу сделает важным (с помощью него и решит задачу, и не только rf). Ваш пример похож на то, что Вы бы были недовольны тем, что в классе полиномов что-то не удаётся хорошо аппроксимировать синус… ну просто это совсем разные классы функций. И есть вещи, которые сделать невозможно, в том числе, догадываться, что чётность значений признака что-то значит с помощью классических моделей алгоритмов классификации.
      Что касается вопроса в п.1, то важности признаков вообще странно доверять при таком низком АУК. Вы ведь задачу решили ну почти с точностью случайного угадывания, странно смотреть, какой признак при этом помог её Вам решить.

      По поводу п.2.
      a — может быть, да.
      b — сомнительно, ну только разве что у Вас в обучении повторяются объекты, из-за этого вне фолда есть представители самого фолда… ну или какой-то подобный эффект. Например, ещё если все объекты упорядочены по времени, тест «из будущего», а когда делите на фолды, то там случайно перемешанные объекты. Получается, что когда Вы настраиваете параметры модели, то просто учитесь общим зависимостям в датасете без привязки ко времени, а работать Ваш алгоритм будет предсказывая будущее… и качество тут может быть совсем плохим.

      Надеюсь, помог.

      • Большое спасибо за ответ и прошу прощения за опечатку в первом же слове 🙂
        Пример с синусом хороший. Понял, спасибо.

        Действительно, странно, тогда так — а могу ли я до fit’а указывать некие веса признаков, то есть существуют ли модели, в которые можно закладывать мнение эксперта?

        Я понял, повторения проверю, благодарю за идею, но вряд ли. Скорее всего разная метрика.

        Да, очень помогли, спасибо, мне тут пока не результат важен, но понимание 🙂

      • А это хороший вопрос… в современных реализациях моделей часто есть веса объектов (если есть экспертное мнение, что какие-то объекты важнее, то это можно учесть), а вот весов признаков нет… хотя их нетрудно реализовать самому. Скажем, если Вы сами пишете rf, то веса признаков — это вероятности по которым выбираются признаки для расщепления.

  7. Из этого и предыдущего ответов верно ли я понял, что учет весов объектов происходит с помощью добавления нового признака, как, например, «четность» в той игрушечной задаче, что я описывал выше?
    Да, спасибо, надо будет заняться. Кстати, у Вас же есть своя реализация rf, интересно , Вы закладывали туда такую возможность или на практике это не требуется?

    • Нет, как делается учёт объектов я не говорил. Не так, как Вы подумали.

      Где-то была своя на матлабе, но весов признаков я туда не закладывал.

      • Ясно.
        Спасибо за помощь! Буду разбираться)

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s