Пошаговое руководство о том, что делает «случайный лес» случайным лесом.
TLDR.Случайные леса — это метод ансамблевого обучения на основе деревьев. Обучаются несколько деревьев решений, каждое из которых использует свои собственные начальные обучающие данные, и совокупность их прогнозов возвращается в качестве прогноза ансамбля. Метод агрегирования зависит от того, используем ли мы случайный лес для регрессии или классификации. Для регрессии мы обычно берем среднее значение предсказаний отдельных деревьев, а для классификации обычно берем большинство голосов меток классов. В этой статье используется простая задача регрессии, чтобы проиллюстрировать, как работают случайные леса.
Предварительные требования. В этой статье предполагается, что читатель имеет общее представление о задачах регрессии, включая такие понятия, как обучение модели, переобучение и выборка данных. Поскольку случайные леса основаны на деревьях, базовое понимание деревьев решений также будет полезно, особенно когда они используются для регрессии. Если вам нужно освежить это, не волнуйтесь. Скоро я расскажу о регрессии дерева решений в статье, так что следите за обновлениями! Мои коллеги-программисты Python могут ознакомиться с аннотацией Код ниже, а все остальные могут быть уверены, что эта статья не зависит от языка. Мы углубимся в алгоритмы и варианты дизайна, лежащие в основе случайных лесов, и попутно представим шаги в псевдокоде.
Код:код Python, который я написал для этой статьи, доступен на GitHub здесь. Не стесняйтесь клонировать репо и следуйте инструкциям! Обратите внимание, что этот код не является рецептом использования RandomForestRegressor Scikit-learn (хотя в конце приводится краткий пример на случай, если это то, что вы ищете). Вместо этого этот код использует DecisionTreeRegressor Scikit-learn для обучения отдельных деревьев, а затем мы шаг за шагом строим наши собственные ансамбли.
Ваш отзыв: если вам понравилась эта статья, похлопайте в ладоши и подпишитесь на меня! Если у вас есть какие-либо вопросы или комментарии, дайте мне знать в ответе ниже.
Теперь давайте начнем!
Мотивация
Предположим, мы хотим построить модель, соответствующую следующей кривой.
Наша модель будет учитывать только один атрибут, значения x, а нашей целью будут значения y. Понятно, что прямая линия не сможет отразить синусоидальный характер наших данных, поэтому мы решили, что линейная регрессия не подходит для этой задачи. Что нам нужно, так это модель, способная фиксировать изгибы и повороты наших данных. Что-то более или менее похожее на это:
Естественным выбором может быть использование дерева решений, потому что они способны изучать нелинейные закономерности. Это делает их надежным кандидатом для нашей задачи. Как вы, возможно, помните, одним из ключевых гиперпараметров дерева решений является его максимальная глубина (или количество разбиений дерева), поэтому мы будем обучать несколько деревьев решений на разной глубине, чтобы увидеть, насколько хорошо каждое из них подходит для нашей задачи. данные. Результаты представлены на графике ниже, где кривая, построенная деревом решений, представлена темно-синей линией.
Ясно, что каждое из этих деревьев лучше подходит для наших данных, чем простая прямая линия, но мы, кажется, очень быстро переходим от недообучения к переоснащению. В этом нет ничего удивительного, поскольку деревья решений печально известны своей склонностью к переоснащению. В этом случае кажется, что единственное дерево решений с глубиной 4 дает нам наилучшее соответствие. Мы будем использовать это, поскольку мы продолжим работать над нашей моделью в остальной части статьи.
Главный вывод здесь заключается в том, что, хотя отдельные деревья решений могут фиксировать сложные закономерности в данных, они склонны находить слишком сложные закономерности. Нам нужна красивая плавная кривая без всех неровных прыжков вверх и вниз по пути.
Здесь на помощь приходят случайные леса. Они позволяют нам использовать сильные стороны деревьев решений (находить сложные шаблоны в наших данных), а также минимизировать их недостатки (находить шаблон, который слишком сложно). На высоком уровне есть две основные особенности, которые определяют случайный лес:
- Это ансамблевый метод, в котором каждая отдельная модель представляет собой дерево решений. Мы можем думать об этом наборе деревьев как о «лесе».
- Деревья в этом ансамбле «случайны». То есть в обучении деревьев решений присутствует стохастический характер, и цель состоит в том, чтобы уменьшить корреляцию между деревьями.
Далее мы рассмотрим каждый из этих компонентов более подробно и увидим, как по отдельности они могут не сильно помочь нашим результатам, но вместе они могут многое сделать.
Часть «Лес».
Как упоминалось ранее, случайный лес представляет собой ансамбль деревьев решений, поэтому мы можем думать об этом наборе деревьев как о «лесе». В зависимости от задачи деревья будут построены либо для регрессии, либо для классификации. Каждое дерево выращивается¹ изолированно, а затем используется для создания прогноза для данного наблюдения. Ансамбль учитывает все эти прогнозы при определении своего окончательного прогноза. Для регрессии мы обычно используем средний прогноз по деревьям, а для классификации мы обычно возвращаем метку класса, определенную большинством голосов.
Вот псевдокод для создания ансамбля:
Algorithm: grow an ensemble
Input:
D, the set of data available for training
M, the decision tree modeling algorithm and its hyperparameters
Output: T, a collection of k decision trees (e.g. T_1, T_2, …, T_k)
SET T to be an empty collection
FOR i = 1 to k
CALL M using data set D to train a tree T_i
APPEND T_i to the collection of trees T
END FOR
А вот псевдокод для получения прогноза от ансамбля:
Algorithm: generate an ensemble prediction
Input:
X, the observation we want to get a prediction for
T, a collection of k decision trees (e.g. T_1, T_2, …, T_k)
Output: y_hat, the average prediction across the trees in T
SET prediction_sum to 0
FOR i = 1 to k
CALL T_i to get prediction for X
ADD prediction to prediction_sum
END FOR
SET y_hat = prediction_sum / k
Возвращаясь к нашей задаче моделирования, мы решаем построить ансамбль из 6 деревьев решений, каждое из которых имеет глубину 4 (наилучшая глубина из наших моделей с одним деревом выше). Результаты представлены на графике по отношению ко всему нашему набору обучающих данных ниже.
На первый взгляд может быть сложно сказать, но после небольшого изучения мы понимаем, что каждое из этих шести деревьев дало одинаковые результаты. Те, кто знаком с деревьями решений, могут вспомнить, что процесс выращивания дерева является детерминированным². То есть, учитывая набор данных для обучения и фиксированные гиперпараметры, результирующее дерево решений будет одинаковым каждый раз, когда мы обучаем модель.
Чтобы это было немного легче увидеть, мы можем нанести результаты всех 6 деревьев на один и тот же график и увидеть, что они полностью перекрываются. Кроме того, когда мы сравниваем результаты ансамбля, мы видим, что они также совпадают с результатами отдельных деревьев. Это неудивительно. В этом случае прогноз ансамбля представляет собой среднее значение группы повторяющихся значений из его составляющих деревьев.
Чтобы убедиться, что мы не отклонились от курса, мы должны сделать паузу и спросить себя, что мы получили, делая все это?
Ответ, кажется, абсолютно ничего! Мы усложнили наш подход и совсем не улучшили результаты. Получается, что использования ансамбля деревьев недостаточно, если они выращены детерминистически. По мере продвижения мы увидим, что именно сочетание этого ансамблевого подхода с добавлением стохастичности делает случайный лес более мощным, чем одиночное дерево решений.
«Случайная» часть
Как мы упоминали выше, деревья решений выращиваются детерминистически. То есть в алгоритме нет стохастического элемента (в отличие, например, от кластеризации k-средних), поэтому для любого данного набора обучающих данных и гиперпараметров³ можно вырастить ровно одно уникальное дерево решений.
Так как же мы можем добавить случайности в метод моделирования, который по своей природе является детерминированным?
Короче говоря, мы начинаем рандомизировать данные, используемые для обучения модели! Мы можем думать об обучающих данных двумя способами:
- Как набор наблюдений (или строк)
- Как набор атрибутов (или столбцов)
Если мы случайным образом выберем подмножества любого из них, мы можем добавить некоторую стохастичность в наши иначе детерминированные деревья решений. Случайные леса используют оба подхода, и далее мы рассмотрим каждый из них более подробно.
Случайная выборка наблюдений
Один из способов внедрить стохастичность в наш ансамбль — это обучить каждое дерево решений собственному случайно выбранному набору наблюдений. Случайные леса делают это путем равномерной выборки наблюдений исходного набора данных с заменой, чтобы создать подвыборку, которая будет использоваться для обучения одного дерева. Этот тип выборки называется «самозагрузкой» и является одной из ключевых особенностей случайных лесов. Обратите внимание, что начальную загрузку можно выполнять и для других типов моделей, даже для тех, которые не являются ансамблевыми методами. Когда мы используем самонастройку для ансамблевой модели, этот процесс называется «бэггингом», потому что мы загружаем обучающие данные для каждой отдельной модели, а затем агрегируем их результаты для формирования прогнозов, сделанных ансамблем (т. е. бэггинг = bootstrap + aggregating).
Чтобы включить начальную загрузку, нам нужно всего лишь внести два небольших изменения в наш предыдущий алгоритм роста ансамбля. Сначала мы загрузим образец данных, а затем воспользуемся им для обучения дерева. Псевдокод становится:
Algorithm: grow an ensemble with bootstrapping
Input:
D, the set of data available for training
M, the decision tree modeling algorithm and its hyperparameters
Output: T, a collection of k decision trees (e.g. T_1, T_2, …, T_k)
SET T to be an empty collection
FOR i = 1 to k
SET D_i to be a bootstrap sample of D
CALL M using data set D_i to train a tree T_i
APPEND T_i to the collection of trees T
END FOR
Возвращаясь к нашему примеру, мы рассмотрим эффекты использования начальной загрузки для обучения нового ансамбля из 6 деревьев, каждое из которых имеет глубину 4, как и раньше. Нанесение результатов на весь наш набор обучающих данных дает нам следующее.
Мы видим, что в отличие от прошлого раза, каждое из этих шести деревьев уникально. Однако ни одно из этих отдельных деревьев не кажется лучше того, что мы видели раньше, а некоторые из них, возможно, даже хуже! Начальная загрузка набора данных для роста каждого дерева, по-видимому, не помогает какому-либо отдельному дереву работать лучше, чем деревья, которые были выращены на всем исходном наборе данных.
Тем не менее, как ансамбль, бутстрапированные деревья могут соответствовать нашим данным лучше, чем любое из них по отдельности. Это видно по меньшим шагам и более гладкому внешнему виду ансамбля на крайнем правом графике ниже.
Подводя итог этим выводам, мы показали, что при изолированном использовании ансамбля деревьев или бутстрэппинг не дает никаких улучшений результатов нашей модели по сравнению с одним деревом решений. Но при совместном использовании мы можем получить лучшее приближение к кривой, чем то, что мы могли бы получить, используя одно дерево решений.
Выбор схемы
Прежде чем мы перейдем к другому обсуждению стохастичности и ансамблей деревьев, я хотел бы отметить сделанный здесь выбор схемы: равномерная выборка с замещением. Можно задаться вопросом, почему это было выбрано вместо выборки без замены. Основная причина использования выборки с заменой заключается в том, что она побуждает отдельные деревья в нашем ансамбле становиться более специализированными или лучше фиксировать определенные части лежащего в основе шаблона. Выборка с заменой означает, что некоторые наблюдения из нашего исходного набора данных могут повторяться при выращивании определенного дерева, тогда как другие наблюдения могут вообще не учитываться. Дерево, выращенное на такой выборке, с большей вероятностью станет лучше определять закономерности, связанные с его конкретным подмножеством наблюдений, поэтому оно может стать более специализированным.
Случайная выборка атрибутов
Теперь мы увидели улучшения, которые могут быть сделаны путем случайной выборки наблюдений в наших данных для каждого дерева в нашем ансамбле. Точно так же мы можем внедрить стохастичность в процесс построения дерева решений путем случайной выборки атрибутов наших данных в процессе обучения.
Случайные леса делают это, изменяя сам алгоритм построения дерева. Как правило, когда дерево решений растет, оно рассматривает все атрибуты наших данных при каждом разбиении, а затем выбирает лучший из них⁴. Подход со случайным лесом изменяет это так, что когда мы выращиваем деревья, из наших данных при каждом разбиении выбирается случайное подмножество атрибутов, а затем из этого подмножества делается наилучший выбор. В отличие от начальной загрузки для наблюдений (где выборка выбирается с заменой), случайные леса выбирают эти подмножества атрибутов без замены.
Мы не будем рассматривать здесь псевдокод для этого изменения, потому что на самом деле это изменение процесса роста дерева, и мы сосредоточились на нескольких частях этой задачи. Кроме того, данные, используемые в нашем примере, имеют только один атрибут, поэтому демонстрация не впечатляет. Если вам это интересно, следите за моей будущей статьей, где мы углубимся во внутреннюю работу деревьев решений!
Выбор дизайна
Как и в предыдущем разделе, давайте рассмотрим варианты дизайна, сделанные при таком подходе. В этом случае есть два варианта: выборка атрибутов без замены, а также выбор выборки атрибутов при каждом разбиении (а не только один раз перед обучением). заданное дерево).
Первый выбор кажется довольно ясным после небольшого размышления. Когда мы собирали наблюдения, мы надеялись вырастить специализированные деревья, поэтому выбор выборки наблюдений с заменой помогает нам выполнить эту задачу, как мы обсуждали ранее. Однако, когда задача состоит в выборке атрибутов, мы видим, что нет смысла позволять атрибуту повторяться. Это связано с тем, что дерево будет выбирать атрибут лучший из доступных вариантов, и количество раз, когда атрибут присутствует в этих параметрах, не изменится, является ли он лучшим или нет⁵. Таким образом, случайные леса выбирают атрибуты без замены, даже если они выбирают наблюдения с заменой.
Второй вариант мне не сразу ясен, и я еще не читал (или просто забыл) каких-либо объяснений, поддерживающих этот выбор. Почему создатели Random Forest выбрали выборку атрибутов при каждом разбиении? В конце концов,это требует от нас вмешательства в сам алгоритм выращивания дерева, тогда как кажется, что мы могли бы так же легко выбрать выборку атрибутов один раз, прежде чем мы начнем выращивать отдельное дерево, и затем дайте дереву решений идти своим естественным путем. Кроме того, я полагаю, что могло бы быть небольшое улучшение производительности, если бы мы производили выборку один раз для каждого дерева, а не один раз для разделения. Тем не менее, очевидно, что первоначальный выбор выборки при каждом разделении работает хорошо, поскольку случайные леса довольно популярны и эффективны. Если у вас есть какие-либо мысли или ресурсы относительно этого выбора дизайна, сообщите мне об этом в комментариях ниже!
Последние мысли
Прежде чем мы закончим эту статью, мы рассмотрим несколько заключительных мыслей. Во-первых, мы покажем, что, хотя случайные леса могут быть менее склонны к переоснащению, нам все равно нужно следить за этим. Затем мы быстро сравним результаты моей реализации алгоритма Random Forest с результатами реализации Scikit-learn, просто чтобы показать, что суть Random Forest действительно отражена в примерах, представленных в этой статье.
Переоснащение
Вспомним нашу мотивацию в начале этой статьи. Мы хотели подогнать модель к некоторым нелинейным данным, поэтому попытались построить несколько изолированных деревьев решений разной глубины. Мы увидели, что большинство этих деревьев были значительно недостаточны или переоснащены, и хотя дерево с глубиной 4 казалось лучшим, оно не было очень гладким приближением к нашей кривой. Итак, мы представили случайный лес как способ получить более плавную подгонку. Было бы несправедливо оставить кого-либо с впечатлением, что случайные леса также не способны к переоснащению.
Ключом к лучшему сочетанию случайных лесов является увеличение количества деревьев в ансамбле, а не не максимальная глубина деревьев. Настоящая сила ансамблевых методов заключается в большом количестве слабых учащихся⁶. Ниже мы построим три разных случайных леса, обученных с реализацией, которую я создал для наших примеров, с некоторыми изменениями гиперпараметров в каждом.
Крайний левый случайный лес — это тот же самый, который мы построили после введения в наш ансамбль концепции начальной загрузки. Мы будем использовать его в качестве основы для сравнения двух других графиков. Случайный лес в середине показывает нам, что произойдет, если мы зафиксируем максимальную глубину, но позволим увеличить количество деревьев в три раза. Мы видим, что увеличение количества деревьев позволяет получить более плавную аппроксимацию искомой кривой без переобучения. Напротив, крайний правый график показывает нам эффект увеличения максимальной глубины в три раза при фиксированном количестве деревьев. Этот случайный лес быстро соответствует данным, очень похоже на то, что мы видели ранее для отдельных деревьев решений.
Вывод здесь заключается в том, что случайные леса могут дать нам более плавное соответствие нелинейным данным, чем одно дерево решений, но они не застрахованы от переобучения. Мы должны продолжать следить за этим, обучая и оценивая наши модели!
Результаты «реальной» реализации
Надеемся, что примеры в этой статье помогли проиллюстрировать внутреннюю работу случайного леса и позволили нам лучше понять, что происходит под капотом. В качестве последней проверки работоспособности давайте посмотрим, как выглядят результаты RandomForestRegressor Scikit-learn по сравнению с моим подходом выше. Следующие три графика были созданы с использованием RandomForestRegressor Scikit-learn с теми же гиперпараметрами, что и предыдущий график.
Хорошая новость (для меня) заключается в том, что результаты известной реализации выглядят невероятно похожими на то, что было получено для примеров в этой статье! Таким образом, мы можем быть уверены, что нам действительно удалось уловить суть того, что происходит внутри Random Forest. Однако это не означает, что моя реализация почти так же хороша, как и то, что доступно во многих библиотеках с открытым исходным кодом. В нашем игрушечном примере было всего 100 наблюдений, и я подозреваю, что при наличии большого набора данных моя реализация будет ползать по сравнению с наиболее часто используемыми реализациями. Итак, если вы следовали моему коду, помните, что он был предназначен только для образовательных целей. Если вам нужно построить случайный лес по-настоящему, вы, вероятно, захотите вместо этого положиться на одну из установленных реализаций.
Краткое содержание
В этой статье мы рассмотрели много вопросов. Подводя итог, мы подготовили почву для того, почему кто-то может захотеть использовать случайный лес, пытаясь построить модель для некоторых нелинейных данных. Мы начали с построения серии изолированных деревьев решений с возрастающей глубиной и увидели, что они очень быстро перешли от недообучения к переоснащению. Это привело нас к концепции ансамбля, в котором мы пытались использовать результаты нескольких слабых учеников, чтобы улучшить нашу форму. Одного этого было недостаточно, чтобы изменить результаты, потому что наши обучающиеся (деревья решений) были детерминированы по своей природе. Итак, мы попытались внедрить стохастичность в обучение каждого ученика, загрузив данные, используемые для обучения каждой отдельной модели. Опять же, мы увидели, что одного этого недостаточно для улучшения наших результатов. В конце концов сработало сочетание этих двух тактик: набор слабых учеников, обученных стохастическим методом. Именно эта комбинация делает Random Forest отличным выбором для подбора нелинейных данных.
Мы также рассмотрели несколько вариантов дизайна, сделанных создателями алгоритма Random Forest, в частности
- Единообразная выборка наблюдений, используемая для обучения каждого дерева с заменой и
- Выборка атрибутов, учитываемых при каждом разбиении данного дерева, без замены перед выбором наилучшего.
Следует отметить, что именно эти варианты дизайна делают ансамбль деревьев «случайным лесом» и что существует множество других методов ансамбля на основе деревьев, которые следует учитывать. Например, существует алгоритм Extra Trees, который выбирает один случайный атрибут для использования при каждом разбиении в процессе роста дерева, а не рассматривает несколько случайных атрибутов и затем выбирает лучший, как Random Forest. Кроме того, есть Adaboost, который использует повышение⁷ вместо начальной загрузки при выборке наблюдений для использования для обучения данного дерева. В то время как равномерная выборка, используемая в Random Forests, дает ансамбль одинаково распределенных деревьев, бустинг, используемый Adaboost, этого не делает. Процесс повышения дает различные веса наблюдениям на основе производительности данного дерева. Затем эти веса используются при выборке данных для обучения последующих деревьев, что означает, что деревья в ансамбле больше не распределяются идентично⁸. Как и в большинстве вариантов дизайна, у каждого из этих подходов есть свои плюсы и минусы, и ни один из этих древовидных ансамблей не лучше других во всех обстоятельствах.
Хотя в этой статье я много сосредоточился на сильных сторонах Random Forests, я совсем не тратил много времени на их недостатки. Точно так же я лишь поверхностно сравнил Random Forests с другими древовидными ансамблями. Пожалуйста, дайте мне знать в комментариях ниже, если вы хотите, чтобы я коснулся какой-либо из этих тем в будущем.
Наконец, хотя некоторые из случайных лесов довольно хорошо справились с нашими данными, я думаю, мы все можем согласиться с тем, что мой плохой набросок по-прежнему является явным победителем. Удачи в следующий раз, машины!
Рецензенты
Примечания
1. Мило, правда? Для тех, кто не знаком с этой фразой, «вырастить» дерево решений означает то же самое, что и «обучить» дерево решений. Эта замена кажется уникальной для древовидных моделей и настолько распространена, что я никогда не обращал на нее внимания, пока не начал писать эту статью.
2. По крайней мере теоретически (Grus, 2015). Обратите внимание, что это поведение может различаться в зависимости от используемой реализации. Например, DecisionTreeRegressor от Scikit-learn по умолчанию включает случайные перестановки функций на каждом этапе, поэтому его реализация не дает детерминированного результата, если об этом явно не сказано. Подробности смотрите в документации.
3. Например: глубина узла или максимальное количество листьев.
4. Если вы не уверены в этом, не волнуйтесь. Я расскажу об этом процессе в следующей статье!
5. Мое утверждение справедливо не во всех случаях. Например, возможно, что выборка атрибутов, выбранных с заменой, действительно может изменить рейтинг атрибута среди других вариантов в выборке, потому что, если мы выбираем фиксированное количество атрибутов, повторение одного атрибута обязательно означает, что другой должны быть исключены. Однако это имеет тот же эффект, что и выбор меньшей выборки без замены, а размер выборки — это гиперпараметр, который мы можем настроить. Ради краткости я сделал широкое заявление выше!
6–7. Я расскажу об этом более подробно в следующей статье.
8. Подробнее см. страницы 587–588 книги Элементы статистического обучения.
Ссылки и ресурсы
Хасти, Тревор и др. (2009). Элементы статистического обучения. Спрингер Сайенс+Бизнес Медиа, ООО.
Грус, Джоэл. (2015). Наука о данных с нуля. О'Рейли Медиа, Инк.
ВандерПлас, Джейк. (2017). Руководство по науке о данных в Python. О'Рейли Медиа, Инк.
Хан, Цзявэй и др. (2012) Концепции и методы интеллектуального анализа данных (3-е изд.). Морган Кауфманн.
