Построение дерева решений
Построение дерева решений означает построение последовательности правил «если… то…», которая приводит к ответу максимально коротким путем. В машинном обучении эти правила называются тестами (tests).
Бинарные признаки — «да/нет?».
Непрерывные данные — «Признак i больше значения a?»
Этот рекурсивный процесс строит в итоге бинарное дерево решений, в котором каждый узел соответствует определенному тесту. Можно интерпретировать тест как разбиение части данных, рассматриваемое в данном случае вдоль одной оси.
Поскольку каждый тест рассматривает только один признак, области, получающиеся в результате разбиения, всегда имеют границы, параллельные осям.
Рекурсивное разбиение данных повторяется до тех пор, пока все точки данных в каждой области разбиения (каждом листе дерева решений) не будут принадлежать одному и тому же значению целевой переменной (классу или количественному значению). Лист дерева, который содержит точки данных, относящиеся к одному и тому же значению целевой переменной, называется чистым (pure).
Для решения задач регрессии обходится дерево на основе тестов в каждом узле и находится лист, в который попадает новая точка данных. Выходом для этой точки данных будет значение целевой переменной, усредненное по всем обучающим точкам в этом листе.
Контроль сложности
Как правило, построение дерева, продолжающееся до тех пор, пока все листья не станут чистыми, приводит к получению моделей, которые являются очень сложными и характеризуются сильным переобучением на обучающих данных. Наличие чистых листьев означает, что дерево имеет 100% правильность на обучающей выборке.
Две общераспространенные стратегии, позволяющие предотвратить переобучение.
- Ранняя остановка построения дерева (предварительная обрезка — pre-pruning). Возможные критерии предварительной обрезки включают в себя ограничение максимальной глубины дерева, ограничение максимального количества листьев или минимальное количество наблюдений в узле, необходимое для разбиения.
- Построение дерева с последующим удалением или сокращением малоинформативных узлов (пост-обрезка -post-pruning или просто обрезка — pruning).
В библиотеке scikit-learn деревья решений реализованы в классах DecisionTreeRegressor и DecisionTreeClassifier. В scikit-learn реализована лишь предварительная обрезка.
Если не ограничить глубину, дерево может быть сколь угодно глубоким и сложным. Поэтому необрезанные деревья склонны к переобучению и плохо обобщают результат на новые данные.
Один из вариантов – остановка процесса построения дерева по достижении определенной глубины. Это приводит к более низкой правильности на обучающем наборе, но улучшает правильность на тестовом наборе.
Ансамбли деревьев решений
Ансамбли (ensembles) – это методы, которые сочетают в себе множество моделей машинного обучения, чтобы в итоге получить более мощную модель.
- Случайный лес деревьев решений
- Градиентный бустинг деревьев решений.
Построение модели случайного леса
Для построения модели случайных лесов необходимо определиться с количеством деревьев (параметр n_estimators для RandomForestRegressor или RandomForestClassifier).
Деревья будут построены совершенно независимо друг от друга, и алгоритм будет случайным образом отбирать признаки для построения каждого дерева, чтобы получить непохожие друг на друга деревья.
Для построения дерева сформируется бутстреп-выборка (bootstrap sample) данных. То есть из n_samples примеров случайным образом выбирается пример с возвращением n_samples раз (поскольку отбор с возвращением, то один и тот же пример может быть выбран несколько раз). Получается выборка, которая имеет такой же размер, что и исходный набор данных, однако некоторые примеры будут отсутствовать в нем (примерно одна треть), а некоторые попадут в него несколько раз.
Например, [‘a’, ‘b’, ‘c’, ‘d’]. Возможная бутстреп выборка может выглядеть как [‘b’, ‘d’, ‘d’, ‘c’]. Другой возможной бутстреп-выборкой может быть [‘d’, ‘a’, ‘d’, ‘a’].
Далее на основе этой сформированной бутстреп-выборки строится дерево решений.
Количество отбираемых признаков контролируется параметром max_features.
Использование бутстрепа приводит к тому, что деревья решений в случайном лесе строятся на немного отличающихся между собой бутстреп-выборках.
Из-за случайного отбора признаков в каждом узле все расщепления в деревьях будут основано на отличающихся подмножествах признаков.
Вместе эти два механизма приводят к тому, что все деревья в случайном лесе отличаются друг от друга.
Если мы установим max_features равным n_features, это будет означать, что в каждом разбиении могут участвовать все признаки набора данных, и в отбор признаков не будет привнесена случайность (впрочем, случайность в силу использования бутстрепа остается). Если max_features равен 1, это означает, что при разбиении не будет никакого отбора признаков для тестирования вообще, будет осуществляться поиск с учетом различных пороговых значений для случайно выбранного признака.
Таким образом, высокое значение max_features означает, что деревья в случайном лесе будут весьма схожи между собой и они смогут легко аппроксимировать данные, используя наиболее дискриминирующие признаки. Низкое значение max_features означает, что деревья в случайном лесе будут сильно отличаться друг от друга и, возможно, каждое дерево будет иметь очень большую глубину, чтобы хорошо соответствовать данным.
В настоящее время случайные леса регрессии и классификации являются одним из наиболее широко используемых методов машинного обучения.
Они обладают высокой прогнозной силой, часто дают хорошее качество модели без утомительной настройки параметров и не требуют масштабирования данных.
Как правило, деревья в случайном лесе получаются более глубокими по сравнению с одиночными деревьями решений (из-за использования подмножеств признаков).
Построение случайных лесов на больших наборах данных можно распараллелить между несколькими ядрами процессора в компьютере — параметр n_jobs для настройки количества используемых ядер. Можно установить n_jobs=-1, чтобы использовать все ядра процессора.
Случайный лес по своей природе является рандомизированным алгоритмом, и установка различных стартовых значений генератора псевдослучайных чисел может кардинально изменить построение модели. Чем больше деревьев в лесу, тем более устойчивым он будет к изменению стартового значения.
Случайный лес плохо работает на данных очень высокой размерности, разреженных данных, например, на текстовых данных. Для подобного рода данных линейные модели подходят больше.
Важными параметрами настройки являются n_estimators, max_features и опции предварительной обрезки деревьев, например, max_depth.
Что касается n_estimators, большее значение всегда дает лучший результат только для обучающей выборки (?).
max_features случайным образом определяет признаки, использующиеся при разбиении в каждом дереве, а меньшее значение max_features уменьшает переобучение.
Значения, выставленные по умолчанию: max_features=sqrt(n_features) для классификации и max_features=n_features для регрессии. Увеличение значений max_features или max_leaf_nodes иногда может повысить качество модели.
Градиентный бустинг деревьев решений
В отличие от случайного леса, градиентный бустинг строит последовательность деревьев, в которой каждое дерево пытается исправить ошибки предыдущего. По умолчанию в градиентном бустинге деревьев регрессии отсутствует случайность, вместо этого используется строгая предварительная обрезка.
В градиентном бустинге деревьев часто используются деревья небольшой глубины, от одного до пяти уровней, что делает модель меньше с точки зрения памяти и ускоряет вычисление прогнозов.
Основная идея градиентного бустинга заключается в объединении множества простых моделей (в данном контексте известных под названием слабые ученики или weak learners), деревьев небольшой глубины. Каждое дерево может дать хорошие прогнозы только для части данных и таким образом для итеративного улучшения качества добавляется все большее количество деревьев.
Градиентный бустинг деревьев широко используется в коммерческих сферах. В отличие от случайного леса он, как правило, немного более чувствителен к настройке параметров, однако при правильно заданных параметрах может дать более высокое значение правильности.
Помимо предварительной обрезки и числа деревьев в ансамбле, еще один важный параметр градиентного бустинга – это learning_rate, который контролирует, насколько сильно каждое дерево будет пытаться исправить ошибки предыдущих деревьев. Более высокая скорость обучения означает, что каждое дерево может внести более сильные корректировки и это позволяет получить более сложную модель. Добавление большего количества деревьев в ансамбль, осуществляемое за счет увеличения значения n_estimators, также увеличивает сложность модели, поскольку модель имеет больше шансов исправить ошибки на обучающем наборе.
Градиентный бустинг деревьев решений – одна из самых мощных и широко используемых моделей обучения с учителем. Его основной недостаток заключается в том, что он требуют тщательной настройки параметров и для обучения может потребоваться много времени
В отличие от случайного леса, в котором более высокое значение n_estimators всегда дает лучшее качество, увеличение значения n_estimators в градиентном бустинге дает более сложную модель, что может привести к переобучению. Общепринятая практика – подгонять n_estimators в зависимости от бюджета времени и памяти, а затем подбирать различные значения learning_rate.
Другим важным параметром является параметр max_depth (или, как альтернатива, max_leaf_nodes), направленный на уменьшение сложности каждого дерева. Обычно для моделей градиентного бустинга значение max_depth устанавливается очень низким, как правило. не больше пяти уровней.
Источники
Андреас Мюллер, Сара Гвидо «Введение в машинное обучение с помощью Python. Руководство для специалистов по работе с данными.», Москва, 2016-17