Решающие деревья
Логические методы классификации
Критерии качества для построения решающих деревьев
Построение решающих деревьев жадным алгоритмом ID3
Усечение (prunning) дерева, обработка пропусков и категориальных признаков
Решающие деревья в задачах регрессии. Алгоритм CART
Случайные деревья и случайный лес. Бутстрэп и бэггинг
Обучающие курсы
Python Python ООП Структуры данных Django C/C++
Телеграм-каналы
Канал selfedu_rus Python Django Машинное обучение Java и С++
Наш канал

Главная
ML
Решающие деревья

Случайные деревья и случайный лес. Бутстрэп и бэггинг

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

Идея алгоритма очень проста и была предложена Лео Брейманом в 1994 году. Этот подход оказался весьма эффективным и используется до сих пор.

Итак, предположим изначально у нас имеется некоторая обучающая выборка:

На ее основе мы хотим сформировать несколько разных и, в общем случае, независимых алгоритмов обработки входного вектора :

А, затем, усреднить ответы каждого алгоритма для формирования общего решения.

Наверное, здесь сразу возникает вопрос, зачем нам искусственно создавать несколько независимых алгоритмов, а потом усреднять их выходы? На самом деле, этому есть вполне логичное объяснение. Одна известная история гласит, как в 1906 году математик Фрэнсис Гальтон посетил рынок и увидел, как продавец быка предложил покупателям небольшую лотерею: угадать точный вес этого быка, который весил 1198 фунтов. От крестьян посыпались самые разные предположения. Но ни один не назвал точное значение. Однако, усреднив все ответы, получилось значение 1197 – очень близкое к истинному. Вот так «мудрость толпы» решила эту непростую задачу.

Эта же идея заложена в бэггинге, когда мы формируем множество независимых алгоритмов, каждый выдает свой вариант ответа, а затем, мы его усредняем, чтобы получить более точное значение.

Этот эффект уменьшения ошибки при усреднении ответов легко объяснить с позиции теории вероятностей. Предположим, что верное значение – вес быка – это величина θ. Тогда ответы крестьян можно представить в виде следующей аддитивной модели:

Здесь - случайная величина. Понятно, что ошибка в ответах каждого, составляет:

с дисперсиями ошибок:

Для простоты, я буду считать, что все ошибки имеют единую дисперсию (разброс значений):

Тогда, дисперсия усредненного ответа:

при условии независимости каждой СВ:

и несмещенности ошибки (нулевого среднего):

равна:

То есть, дисперсия одного отдельного ответа (алгоритма) после усреднения всех результатов, уменьшается в T раз. Это означает, что итоговая величина становится точнее T независимых ответов каждого алгоритма.

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

Бутстрэп (bootstrap)

Так как же нам сформировать T независимых алгоритмов, используя всего одну обучающую выборку? Здесь есть несколько идей, но в бэггинге используется очень простой подход, который носит название бутстрэп (bootstrap). Суть бутстрэпа заключается в формировании T новых обучающих выборок на основе одной исходной . Для этого случайным образом выбирается k-й элемент выборки и копируется в новую (в прежней он остается, не удаляется). Затем, эта операция повторяется m раз – по заданному размеру новой выборки. Так формируется новая обучающая выборка, состоящая из элементов исходной с некоторыми повторениями, так как вполне можно несколько раз случайно отобрать один и тот же элемент. После формирования одной выборки, переходят к формированию следующей и так T раз для T выборок, которые, очевидно, будут несколько отличаться друг от друга. Это идея бутстрэпа.

Можно показать, что формируя, таким образом, новую обучающую выборку длиной , она будет использовать, в среднем, образов из исходной выборки (остальные будут повторяться). Это значит, что оставшуюся часть выборки в 36,8% можно использовать в качестве отложенной для проверки качества алгоритма. И это нашло выражение в критерии под названием out-of bag, когда мы определяем число ошибок по объектам , не участвующих в обучении того или иного дерева:

Здесь - множества объектов, составляющих обучающую выборку для дерева t. В результате out-of bag – это несмещенная оценка обобщающей способности итогового алгоритма .

Бэггинг с решающими деревьями. Случайный лес

Собственно, само слово bagging произошло от сокращения двух английских слов: bootstrap aggregation. Итак, имея T случайных выборок длиной m элементов (), мы можем по ним получить T алгоритмов (классификации или регрессии). Например, используя линейную модель:

можно сформировать T наборов весовых векторов:

каждая для своей обучающей выборки. В результате получаем T различных алгоритмов:

А, затем, усредняя ответы от них, формируем общий результат:

Или, устраивая голосование, решаем задачу классификации:

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

Как ни странно, приверженность деревьев к переобучению играет положительную роль. Они, во-первых, получаются довольно разнообразными и, во-вторых, описывают самые разные исходы для входных векторов . Затем, при усреднении результатов, эффект переобучения естественным образом нивелируется (уменьшается) и итоговое выходное значение оказывается достаточно точным и устойчивым к отдельным выбросам. В ряде задач точность оказывается выше всех других подходов машинного обучения. Именно поэтому бутстрэп быстро завоевал свою популярность.

Чтобы решающие деревья получались еще более разнообразными и формировали менее зависимые ответы, предлагается при их обучении в каждой промежуточной вершине случайным образом отбирать некоторое количество признаков и уже среди них отбирать лучшие для ветвления. Наборы из таких деревьев называют случайным лесом (random forest). Причем, было показано, что в задачах классификации число, а в задачах регрессии . Есть теоретические выкладки почему это так (кому интересно, можно найти в литературе по машинному обучению). Сами же признаки и пороги для ветвления выбираются, как правило, по критерию Джини (он быстрее вычисляется, чем энтропийный и приводит к практически тем же результатам). А усечений деревьев уже не делают, они остаются переобученными. Как я уже отмечал, обобщение и устойчивость выходного значения будет определяться усреднением независимых ответов от каждого дерева. Причем, для случайного леса кривые качества на обучающей и проверочной выборках в среднем уменьшаются при увеличении числа деревьев T:

То есть, с ростом числа T решающих деревьев в случайном лесе итоговая модель не переобучается, а лишь достигает некоторого предельного уровня качества. Это очень хорошее свойство случайного леса, так как мы, фактически, получаем алгоритм, в котором нет сложно настраиваемых гиперпараметров. Единственный параметр T можно взять, например, 100, а затем, 500 и сравнить результаты на тестовой выборке. То есть, подобрать его очень просто. Остальные гиперпараметры для построения решающих деревьев можно выбирать с позиции некоего здравого смысла. Главное, чтобы деревья получались глубокими, гарантируя малые смещения в ответах. Напомню, что под смещением здесь понимается стремление к нулю (в среднем) ошибки прогноза:

Реализация случайного леса на Python

Вот идея бэггинга с применением случайного леса. Для ее реализации на языке Python в библиотеке Scikit-Learn имеются два класса:

RandomForestClassifier – случайный лес для задач классификации;
RandomForestRegressor – случайный лес для задач регрессии.

У каждого класса есть следующий набор основных параметров:

n_estimators – число используемых деревьев;
criterion – критерий разбиения выборки в промежуточных вершинах;
max_features – число признаков, по которым ищется разбиение;
min_samples_leaf – минимальное число объектов в листе;
max_depth – максимальная глубина дерева.

Подробнее о них можно почитать на странице русскоязычной документации:

https://scikit-learn.ru/1-11-ensemble-methods/

Ниже представлены результаты аппроксимации функции косинуса с небольшим гауссовским шумом случайными деревьями:

Программу можно скачать по ссылке:

machine_learning_41_regression.py

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

Преимущества и недостатки случайного леса

Как и любой алгоритм, случайные леса имеют свои преимущества и недостатки. К преимуществам можно отнести:

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

Недостатки случайного леса

в отличие от одного дерева, результаты случайного леса сложнее интерпретировать;
алгоритм работает хуже многих линейных методов, когда в выборке очень много разреженных признаков (тексты, Bag of words);
случайный лес не умеет экстраполировать, в отличие от той же линейной регрессии;
алгоритм склонен к переобучению на некоторых задачах, особенно на сильно зашумленных данных;
для данных, включающих категориальные переменные с различным количеством уровней, случайные леса предвзяты в пользу признаков с большим количеством уровней: когда у признака много уровней, дерево будет сильнее подстраиваться именно под эти признаки, так как на них можно получить более высокое значение оптимизируемого функционала (информационный выигрыш);
больший размер получающихся моделей. Требуется O(N∙K) памяти для хранения модели, где K – число деревьев.

На этом мы завершим данное занятие. Надеюсь, вы понял, что из себя представляет идея бэггинга вообще и как он работает для случайного леса.