Random Forest: прогулки по зимнему лесу
1. Вступление
Это небольшое практическое руководство по применению алгоритмов машинного обучения. Разумеется, существует немалое число алгоритмов машинного обучения и способов математического (статистического) анализа информации, однако, эта заметка посвящена именно Random Forest. В заметке показаны примеры использования этого алгоритма для задач классификации и регрессии, а также даны некоторые теоретические пояснения.
2. Несколько слов о деревьях
Прежде всего, рассмотрим некоторые базовые теоретические принципы работы этого алгоритма, а начнём с такого понятия, как деревья решений. Наша основная задача — принять решение на основе имеющейся информации. В самом простом случае у нас есть всего один признак (метрика, предиктор, регрессор) с хорошо различимыми границами между классов (максимальное значение для одного класса явно меньше минимального значения для другого). Например, зная массу тела нужно отличить кита от пчелы, если известно, что среди всех наблюдений нет ни одного кита, который бы имел массу тела как у пчелы. Следовательно, достаточно всего одного показателя (предиктора), чтобы дать точный ответ, предсказав тем самым верный класс.
Допустим, что точки одного класса (пусть они будут показаны красным цветом) во всех наблюдениях находятся выше точек синего цвета. Человек может провести между ними прямую линию и сказать, что это и будет граница классов. Следовательно, всё расположенное выше этой границы будет относиться к одному классу, а всё ниже линии — к другому.
Отобразим это в виде древовидной структуры. Если мы воспользуемся одним из алгоритмов (CART) для создания дерева решений по указанным ранее данным, то получим следующее условие классификации:
Следовательно, его визуальное представление будет таким:
Разумеется, каждый признак обладает разной степенью важности. Из следующего набора данных (формат LibSVM) видно, что первый признак (его индекс 1, так как нумерация начинается не с нуля) абсолютно идентичен у представителей всех классов. Фактически, этот показатель не имеет никакой ценности для классификации, следовательно, его можно назвать избыточной информацией, которая не несёт никакой практической пользы. Аналогичная ситуация и со вторым признаком (предиктором). Однако, третий из них отличается.
Именно третий признак (feature 2) и будет служить тем самым заветным различием, с помощью которого можно предсказывать класс по вектору. Логично предположить, что задача может быть решена одним единственным условием (If-Else). Действительно, каждое дерево в алгоритме машинного обучения правильно смогло понять различия. Далее показана отладочная информация (использован классификатор Random Forest из фреймворка Apache Spark 2.1.0) для нескольких деревьев ансамбля случайного леса.
Для более сложных задач необходимы более сложные деревья. В следующем примере закономерность перестала быть такой очевидной для человека. Нужно более внимательно посмотреть набор данных, чтобы заметить различия. Условие будет немного более сложным, так как нужна дополнительная проверка.
Вот такие дополнительные проверки требуют новых ветвлений (узлов) дерева. После каждого ветвления необходимо будет делать ещё проверки, т.е. новые ветвления. Это видно на отладочной информации. В целях экономии места я привожу только несколько деревьев:
А теперь представим себе набор данных из миллиона строк и из нескольких сотен (даже тысяч) столбцов. Согласитесь, что простыми условиями такие задачи будет сложно решить. Более того, при очень сложных условиях (глубокое дерево) оно может быть слишком специфично для конкретного набора данных (переобучено). Одно дерево стойко к масштабированию данных, но не стойко к шумам. Если объединить большое количество деревьев в одну композицию, то можно получить значительно более хорошие результаты. В итоге получается весьма эффективная и достаточно универсальная модель.
3. Random Forest
По сути, Random Forest является композицией (ансамблем) множества решающих деревьев, что позволяет снизить проблему переобучения и повысить точность в сравнении с одним деревом. Прогноз получается в результате агрегирования ответов множества деревьев. Тренировка деревьев происходит независимо друг от друга (на разных подмножествах), что не просто решает проблему построения одинаковых деревьев на одном и том же наборе данных, но и делает этот алгоритм весьма удобным для применения в системах распределённых вычислений. Вообще, идея бэггинга, предложенная Лео Брейманом, хорошо подходит для распределения вычислений.
Для бэггинга (независимого обучения алгоритмов классификации, где результат определяется голосованием) есть смысл использовать большое количество деревьев решений с достаточно большой глубиной. Во время классификации финальным результатом будет тот класс, за который проголосовало большинство деревьев, при условии, что одно дерево обладает одним голосом.
Так, например, если в задаче бинарной классификации была сформирована модель с 500 деревьями, среди которых 100 указывают на нулевой класс, а остальные 400 на первый класс, то в результате модель будет предсказывать именно первый класс. Если использовать Random Forest для задач регрессии, то подход выбора того решения, за которое проголосовало большинство деревьев будет неподходящим. Вместо этого происходит выбор среднего решения по всем деревьям.
Random Forest (по причине независимого построения глубоких деревьев) требует весьма много ресурсов, а ограничение на глубину повредит точности (для решения сложных задач нужно построить много глубоких деревьев). Можно заметить, что время обучения деревьев возрастает приблизительно линейно их количеству.
Естественно, увеличение высоты (глубины) деревьев не самым лучшим образом сказывается на производительности, но повышает эффективность этого алгоритма (хотя и вместе с этим повышается склонность к переобучению). Слишком сильно бояться переобучения не следует, так как это будет скомпенсировано числом деревьев. Но и увлекаться тоже не следует. Везде важны оптимально подобранные параметры (гиперпараметры).
Рассмотрим пример классификации на языке программирования R. Так как нам сейчас нужна классификационная модель, а не регрессионная, то в качестве первого параметра следует явно задать, что класс является именно фактором. Кроме количества деревьев уделим внимание числу признаков (mtry), которое будет использовать элементарная модель (дерево) для ветвлений. Фактически, это два основных параметра, которые есть смысл настраивать в первую очередь.
Убедимся, что это именно модель для классификации:
Ознакомимся с результатами confusion matrix:
Интересно увидеть предсказанные значения (на основе out-of-bag):
А функции varImpPlot и importance предназначены для отображения важности предикторов (ценности для точности работы классификатора).
Разумеется, для получения вероятного класса существует специальная функция. Она называется predict. В качестве первого аргумента требует модель, а в качестве второго — набор данных. Результатом будет вектор предсказанных классов. Для надёжной проверки необходимо выполнять тренировку на одном наборе данных, а проверку на другом наборе данных.
Ещё один пример. На этот раз используем Apache Spark 2.1.0 и язык программирования Scala. Информацию мы прочитаем из файла формата LibSVM. После этого необходимо будет явно разделить набор данных на две части. Одна из них будет учебная, а вторая — проверочная. Выполнять стандартизацию или нормализацию нет особого смысла. Наша модель устойчива к этому, равно как и достаточно устойчива к данным различной природы (вес, возраст, доход).
Повторюсь, что обучение необходимо производить только на учебной выборке. Количество классов в этом примере будет равно двум. Количество деревьев пусть будет 50. Оставим индекс Джинни в качестве критерия расщепления, так как теоретически применение энтропии не будет значительно более эффективным критерием. Глубину дерева ограничим девятью.
Теперь используем тестовый набор данных, чтобы проверить работу классификатора с указанными параметрами. Следует заметить, что порог точности (пригодность модели) определяется индивидуально в каждом конкретном случае.
Получив на вход вектор предикторов, система должна угадать (с допустимой вероятностью) класс объекта. Если в результате нескольких проверок на большом наборе данных это удалось сделать, то можно утверждать о точности модели. Однако, никакой человек и никакая система не смогут угадать с очень высокой точностью по росту человека его уровень образования. Следовательно, без правильно собранных и подготовленных данных сложно (или вообще невозможно) будет решить задачу.
4. Несколько мыслей о практическом применении
Бывают такие ситуации, когда простым условием или методами описательной статистики задачу сходу решить не получается. Как раз в задачах повышения эффективности интернет-проектов (анализ клиентов, выявление вероятности покупки, оптимальные стратегии рекламы, выбор товаров для показа в популярных блоках, рекомендации и персональные ранжирования, классификация записей в каталогах и справочниках) и встречаются подобные сложные наборы данных.
Помню, несколько лет назад впервые столкнулся с необходимостью применения ML-технологий. Была ситуация, когда мы с коллегами (группа разработчиков) пытались придумать метод классификации материалов подробного справочника на очень большом портале. Раньше классификация выполнялась вручную другими специалистами, что требовало огромного количества времени. А вот автоматизировать никак не получалось (правила и статистические методы не дали нужной точности). У нас уже был набор векторов, который ранее разметили специалисты.
Тогда меня удивило, что несколько строк кода (применение одной из популярных библиотек машинного обучения) смогли решить проблему буквально сразу. Естественно, что изучалась возможность применения различных моделей (включая нейронные сети) и продумывались рациональные гиперпараметры. Но так как эта заметка про случайный лес, то пример на языке программирования Python будет посвящён именно ему. Естественно, код примера написан с учётом новых версий готовых классификаторов, а не используемых тогда:
Таких примеров очень много. Расскажу ещё одну историю. Была задача повысить эффективность огромной системы управления рекламой. Её работа напрямую зависела от точности предсказания рейтинга товаров и услуг. У каждого из них был вектор из 64-ти признаков. Стратегически важно было заранее дать относительно точный прогноз значения рейтинга для каждого нового вектора признаков. До этого система управлялась нехитрыми правилами и описательной статистикой. Но, как известно, эффективности и точности в таких вопросах много не бывает. Для решения задачи повышения эффективности была использована регрессионная модель, похожая на указанную в примере:
В итоге мы получаем достаточно мощный инструментарий анализа информации, который способен прийти на помощь в тех задачах, где другие методы дают не самые лучшие результаты.
Как работает случайный лес?
Как и почему работает случайный лес? Разбираемся
Jan 9, 2020 · 7 min read
Важная часть машинного обучения — это классификация. Мы хотим знать, к какому классу (или группе) принадлежит значение. Возможность точно классифицировать значения чрезвычайно ценна для бизнес-приложений, таких как прогнозирование покупки продукта конкретным пользователем или прогнозирование платёжеспособности по кредиту.
Наука о данных предоставляет множество алгоритмов классификации, таких как логистическая регрессия, машина опорных векторов, наивный байесовский классификатор и деревья решений. Но на вершине иерархии классификаторов находится классификатор случайного леса.
Дерево решений
Давайте быстро перейдем к деревьям решений, поскольку они — строительные блоки случайного леса. К счастью, они довольно интуитивны. Готов спорить, что большинство людей использовали дерево решений — сознательно или нет — в какой-то момент своей жизни.
Представьте себе, что набор данных состоит из чисел в верхней части рисунка выше. У нас есть две единицы и пять нулей (1 и 0 — это наши классы) и мы хотим разделить классы, используя их признаки. Объекты имеют красный и синий цвета независимо от того, подчеркнуто ли значение.
Цвет кажется довольно очевидным признаком для разделения, поскольку все нули, кроме одного, синие. Поэтому мы можем использовать вопрос: “это красный?”, чтобы разделить наш первый узел. Вы можете представить себе узел в дереве как точку, в которой путь разделяется на два: значения, соответствующие критериям, идут вниз по ветке Yes, а не соответствующие критерию идут по ветке No.
У ветви No теперь все 0, но ветвь Yes все еще можно разделить. Теперь мы можем использовать вторую функцию и спросить: “это подчеркнуто?” для второго разделения.
Две подчёркнутые единицы идут вниз по стороне Yes, а неподчёркнутый 0 идет по правой стороне — и это всё. Наше дерево решений использовало эти два признака, чтобы идеально разделить данные.
Очевидно, что в реальной жизни наши данные не будут такими чистыми, но логика дерева решений остается прежней. На каждом узле оно будет спрашивать:
Какой признак позволит разделить значения таким образом, что результирующие группы будут максимально отличаться друг от друга, а члены каждой результирующей подгруппы будут максимально похожи друг на друга?
Классификатор случайного леса
Случайный лес, как и следует из его названия, состоит из большого количества отдельных деревьев решений, которые работают как ансамбль методов. Каждое дерево в случайном лесу возвращает прогноз класса, и класс с наибольшим количеством голосов становится прогнозом леса:
Фундаментальная концепция в основе случайного леса проста, но сильна — это мудрость толпы. Причина, по которой модель случайного леса работает так хорошо, заключается в том, что:
Большое число относительно некоррелированных деревьев, работающих совместно, будет превосходить любую из их отдельных составляющих.
Некоторые деревья могут быть неправильными, но многие другие будут правильными, а значит, группа деревьев способна двигаться в верном направлении. Таким образом, предпосылками успешного прогнозирования являются:
Почему это работает?
Эффект многих некоррелированных моделей так важен, что я хочу показать вам пример, который поможет понять это. Представьте себе, что мы играем в такую игру: у меня есть равномерно распределенный генератор случайных чисел для получения числа. Если число, которое я генерирую, больше или равно 40, вы выигрываете, то есть у вас 60% шанс на победу, и я плачу вам деньги. Если число меньше 40, я выигрываю — вы платите мне ту же сумму. Я предлагаю варианты. Мы играем так:
Что бы вы выбрали? Ожидаемая ценность каждой игры одинакова:
А как насчет распределений? Визуализируем результаты с помощью моделирования Монте-Карло: запустим 10 000 симуляций каждого типа игры. Например, имитируем 100 игр по первым условиям 10 000 раз. Взгляните на график ниже. Каков ваш выбор теперь?
Первый вариант, где мы играем 100 раз, предлагает лучший шанс заработать немного денег. На 10 000 симуляций вы зарабатываете деньги в 97% случаев! Во второй игре, где мы играем 10 раз, вы зарабатываете деньги в 63% симуляций. В третьей вы зарабатываете в 60% случаев, как и ожидалось.
Таким образом, хотя игры имеют одинаковое ожидаемое значение, распределение результатов совершенно различно. Чем больше мы делим нашу ставку в 100 долларов, тем больше мы можем быть уверены, что заработаем деньги. Как уже упоминалось, это работает, потому что каждая игра независима от других.
Случайный лес работает так же: каждое дерево похоже на одну игру. Мы только что видели, как наши шансы заработать деньги увеличивались в зависимости от количества игр. Аналогично при использовании модели случайного леса наши шансы на получение правильных прогнозов возрастают с увеличением числа некоррелированных деревьев. Если вы хотите запустить код для моделирования игры самостоятельно, вы можете найти его на моём GitHub.
Разнообразие моделей
Как случайный лес гарантирует, что поведение каждого отдельного дерева не слишком коррелирует с поведением любого другого дерева? Он использует два метода:
Обратите внимание, что при разбиении на пакеты мы не разбиваем обучающие данные на более мелкие фрагменты и не обучаем каждое дерево на другом фрагменте. Скорее, если у нас есть выборка размера N, мы подаём на вход каждого дерева обучающий набор размера N, если не указано иное.
Разбиение узлов в модели основано на случайном подмножестве объектов для каждого дерева.
Наглядный пример: на рисунке выше традиционное дерево решений синего цвета может выбрать из всех четырех признаков, принимая решение о разделении узла. Дерево решает использовать 1, черную и подчеркнутую, поскольку она разбивает данные на максимально разделённые группы.
Посмотрим на два дерева леса из примера. Когда мы проверяем первое дерево, то обнаруживаем, что оно может рассматривать только признаки 2 и 3, выбранные случайным образом. Мы знаем из нашего традиционного дерева решений, что признак 1 лучший для разбиения, но дерево 1 не может видеть его, поэтому оно вынуждено работать с признаком 2. Второе дерево, с другой стороны, может видеть только признаки 1 и 3, поэтому может выбрать признак 1.
Таким образом, в нашем случайном лесу мы получаем деревья, которые не только обучаются на разных наборах данных благодаря пакету, но и используют разные признаки для принятия решений.
И это создает некоррелированные деревья, которые и защищают друг друга от своих ошибок.
Вывод
Итак, случайный лес — это алгоритм классификации, состоящий из многих деревьев решений. Он использует бэггинг и случайность признаков при построении каждого отдельного дерева, чтобы попытаться создать некоррелированный лес, прогноз которого точнее, чем у любого отдельного дерева.
Что нам нужно, чтобы случайный лес прогнозировал точнее?
Введение в случайный лес
Дата публикации Dec 7, 2018
Последнее обновление: 2018–12–09
Случайные леса широко применяются как для соревнований по науке о данных, так и для практических задач. Они часто точны, не требуют масштабирования признаков, категориального кодирования признаков и требуют небольшой настройки параметров. Они также могут быть более интерпретируемыми, чем другие сложные модели, такие как нейронные сети.
Содержание организовано следующим образом.
Что такое случайный лес
Случайный лес состоит из нескольких деревьев случайных решений. Два типа случайностей встроены в деревья. Во-первых, каждое дерево строится на случайной выборке из исходных данных. Во-вторых, в каждом узле дерева случайным образом выбирается подмножество объектов для создания наилучшего разделения.
Мы используем набор данных ниже, чтобы проиллюстрировать, как построить случайное лесное дерево. Примечание Класс =XOR(X1, Х2). X3 сделан идентичным X2 (для иллюстративных целей в последующих разделах).
На рисунке ниже показано, как построить случайное лесное дерево.
Тот же процесс применяется для построения нескольких деревьев. На рисунке ниже показан процесс применения случайного леса с тремя деревьями к экземпляру данных тестирования.
Интерпретация случайного леса
Важность функции
Оценка важности функции измеряет вклад функции. Это основано на уменьшении примеси класса из-за особенности.
Давайте добавим не относящуюся к делу функцию X4 в иллюстративный набор данных. Показатели важности приведены ниже. Очевидно, что X1 и X4, соответственно, имеют самые большие и самые маленькие оценки. X2 и X3 идентичны и сортируют оценки важности.
Частичный график зависимости
Показатель важности функции не говорит о том, как соотносятся функция и класс. График частичной зависимости может визуализировать предельное влияние объекта на вероятность класса.
Когда объект соотносится с классом, график выглядит как левый рисунок ниже, показывая, что X1 ≤ 0,5 и X1> 0,5 связаны с различными классами.
Причина в том, что X1 должен взаимодействовать с X2 или X3, чтобы предвидеть класс. Один X1 не является прогностическим. Поэтому графики частичной зависимости могут вводить в заблуждение для этого случая.
inTrees
Ни оценки важности, ни графики частичной зависимости не показывают, как несколько объектов взаимодействуют с классом. Среду inTrees можно использовать для получения более четкой картины того, что происходит внутри случайного леса.
Уклон к особенностям с большим количеством категорий
Для иллюстративного набора данных добавим случайную функцию X5 с 30 категориями. Даже функция не имеет отношения к классу, показатель важности X5 больше, чем по-настоящему информативные функции X2 и X3, что указывает на неправильное смещение в сторону объектов с большим количеством категорий.
Обработка избыточных функций
Когда функции похожи друг на друга, оценки важности этих функций могут вводить в заблуждение. В иллюстративном наборе данных X2 и X3 идентичны, и они «разделяют» оценки важности (показано на левом рисунке ниже). Когда есть больше избыточных функций, важность каждой функции становится еще меньше.
Это может не повредить точности выполнения, но может ввести в заблуждение при интерпретации. Одним из решений будет регуляризованный случайный лес (RRF) В процессе построения дерева RRF запоминает функции, используемые в предыдущих узлах дерева, и предпочитает эти функции при разбиении будущих узлов дерева, что позволяет избежать избыточных объектов в деревьях. Правый рисунок ниже показывает оценки важности RRF.
Обнаружение выбросов со случайными лесами
Кластеризация со случайными лесами может избежать необходимости трансформации признаков (например, категориальных функций). Кроме того, некоторые другие функции случайного леса также могут быть использованы здесь, например, вероятность и интерпретация. Здесь мы демонстрируем метод с двумерным набором данных, изображенным на левом рисунке ниже.
Идея состоит в том, чтобы создать случайный набор данных, который контрастирует с исходными данными. Здесь мы случайным образом переставляем каждую функцию. Два набора данных помечены двумя классами (скажем, «нормальный» и «случайный») соответственно. Объединенный набор данных показан на правом рисунке ниже.
Случайный лес построен на наборе данных. Затем классификатор можно применять для проверки экземпляров данных. Если прогнозируемый класс является «случайным», то он определяется как выброс. Выявленные выбросы показаны на левом рисунке ниже.
Мы можем получить представление о том, какие функции способствуют обнаружению выбросов, взглянув на показатель важности. Для иллюстрации добавим случайную особенность X3, которая не имеет отношения к классам. Показатели важности показаны на правом рисунке ниже. X1 и X2 определены как важные функции, а X3 менее важен.
Кластеризация со случайными лесами
Подобно обнаружению выбросов, кластеризация со случайными лесами экономит усилия при предварительной обработке признаков.
Процедура аналогична обнаружению выбросов. Сначала создайте синтетический набор данных того же размера, что и исходные данные. Затем пометьте исходные данные и синтетический класс двумя разными классами. Затем для задачи классификации строится случайный лес.
Из построенного случайного леса извлекается оценка сходства между каждой парой экземпляров данных. Сходство двух экземпляров данных измеряется процентом деревьев, где два экземпляра данных появляются в одном и том же листовом узле.
С оценками сходства алгоритмы кластеризации, такие как иерархическая кластеризация, могут затем использоваться для кластеризации. На рисунках ниже показаны результаты кластеризации с числом кластеров, предварительно определенным как 2 и 4 соответственно.
Резюме
Случайные леса эффективны не только в классификации / регрессии, но и для таких целей, как обнаружение выбросов, кластеризация и интерпретация набора данных (например, выступая в качестве механизма правил с inTrees).
Однако ошибки могут быть легко сделаны при использовании случайных лесов. Во-первых, может иметь место смещение, когда в наборе данных существуют многоуровневые категориальные признаки. Во-вторых, оценки важности могут вводить в заблуждение, когда функции избыточны. Эта статья предоставляет решения для проблем.
Вы можете быть заинтересованы в чтении соответствующей статьи напочему случайные леса превосходят деревья решений,
Вы можете внести свой вклад вinTreesилиСБРпакет на github.