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

Модель Random Forest, разработанная сначала Тином Кам Хо, а затем расширенная Лео Брейманом и Адель Катлер, является своего рода швейцарским армейским ножом, который подходит для множества применений, но может быть не лучшим для данной конкретной проблемы. Так что в большинстве случаев это может быть отличная базовая модель, выводы из которой затем могут быть использованы для разработки других продвинутых моделей. Алгоритм случайного леса - это моя отправная точка (в большинстве случаев), когда я перехожу к фазе моделирования анализа. Итак, приступим к изучению!

В этом посте мы рассмотрим следующие темы:

  • Деревья решений
  • Как случайный лес работает под капотом?
  • Функции затрат
  • Важность функции

Деревья решений

Случайный лес - это не что иное, как набор деревьев решений. Чтобы понять основы алгоритма, нам сначала нужно понять деревья решений.

Допустим, я даю вам 3 фрукта (яблоко, апельсин и банан) и прошу вас назвать каждый. Сначала вы можете подумать, что я идиот из-за того, что дала вам глупое задание, но давайте предположим, что вы насмехаетесь надо мной и участвуете. Конечно, вы можете идентифицировать красный круглый фрукт как яблоко, длинный желтый фрукт как банан, а оставшийся как апельсин. Простой! Чтобы прийти к такому выводу, вам понадобится не меньше секунды. Но сделайте паузу на минуту и ​​подумайте, как вы пришли к решению.

Верно! Вы приняли решение, основываясь на характеристиках или «характеристиках» каждого фрукта. Яблоко круглое (характеристика 1) и красного цвета (характеристика 2). Банан длинный (характеристика 1) и желтого цвета (характеристика 2). И по этим признакам вы сгруппировали плоды. Именно это и делает дерево решений! Он разделяет данные по функциям в каждой ветви, чтобы прийти к окончательному выводу.

А теперь представьте, что вас 10 попросили определить плоды. Каждый из вас пройдет один и тот же процесс и присвоит фрукту ярлык. То есть у нас есть 10 деревьев решений! И если бы я был инопланетянином и понятия не имел, как выглядят фрукты, разумно было бы провести голосование, основанное на всеобщем решении, и назвать круглый красный фрукт яблоком. Вуаля! У нас есть случайный лес.

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

Как под капотом работает случайный лес

Теперь, когда у нас есть понимание о деревьях решений, мы немного углубимся в модели случайного леса.

Алгоритм основан на теореме жюри Кондорсе:

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

Итак, как Random Forest обеспечивает соответствие вышеуказанным критериям? Вот тут-то и появляется «случайность» в Random Forest, и это можно сделать двумя способами:

  • не все данные отображаются для всех деревьев (бэггинг)
  • Для каждого дерева доступна только часть функций (Выбор критериев)

Давайте подробно рассмотрим два вышеупомянутых момента.

Сборка: сборка или начальная агрегация - это метод создания дополнительных наборов данных из исходного набора данных путем выборки с заменой. Непонятно, правда? Мы разберем это дальше.

Допустим, у нас есть список чисел - [1,2,4,9,10,15]. Я хотел бы создать новый список того же размера путем случайной выборки с заменой из исходного списка, чтобы получить другой список того же размера. Предположим, сначала мы выбрали «2», мы добавляем это в наш новый список [2] и сохраняем «2» обратно в исходный список. Теперь мы случайным образом выбираем другой номер из списка. По всей вероятности, мы снова получим «2» или какое-то другое число. Мы будем повторять это 6 раз (размер исходного списка), каждый раз выбирая и заменяя выбранное число на исходное, пока мы не получим новый список. Наш новый список может выглядеть так - [2,2,9,9,15,4]. Мы можем делать это любое количество раз, чтобы получить целую кучу списков.

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

Быстрый вопрос: поскольку образцы могут повторяться, какой процент исходного набора данных доступен в каждом дереве. Ответ составляет примерно 63% и основан на приведенной ниже формуле, где N - размер выборки. Вы можете решить это и увидите, что для больших размеров выборки значение сходится к 63,2%.

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

Так что это значит? Скажем, для задачи классификации фруктов у нас есть 4 характеристики: размер, цвет, форма, вес. Из 4 функций только часть функций доступна в ветви для разделения. В этом случае он может получить только размер и цвет ветки для разделения. А другая ветка получит только цвет и форму. Учитывая подмножество функций, он решит, какую функцию разделить, на основе «сбора информации», который мы обсудим в следующем разделе. Обычно количество функций, доступных в ветви, равно sqrt (p), где p - общее количество функций в наборе данных.

Функции затрат

Теперь, когда мы хорошо понимаем, как работает модель случайного леса, давайте поговорим о том, как случайный лес принимает решение о разбиении или определяет качество каждого разбиения. Решение исходит из «теории информации» и является отдельной областью исследования. Двумя наиболее распространенными решениями являются «Индекс Джини» и «Энтропийный критерий».

Индекс Джини:

По умолчанию в Python используется индекс Джини, и давайте сначала разберемся с этим. Уравнение для индекса Джини приведено ниже. Проще говоря, это мера примеси в каждой отрасли. Лучшее значение - 0, что означает, что в ветке есть только класс и он отлично классифицирован. Чем выше значение Джини, тем грязнее ветка.

P - это вероятность каждого класса в ветви, а j - индекс для класса. Например, у нас есть ветка со следующей структурой:

  • Яблоки: 10
  • Апельсины: 6
  • Виноград: 4 шт.

Вероятность каждого класса следующая:

  • Яблоки: 0,5
  • Апельсины: 0,3
  • Виноград: 0,2

На основе формулы Джини можно рассчитать следующим образом: 1 - (0,5 ** 2 + 0,3 ** 2 + 0,2 ** 2) = 0,62.

Теперь дерево решений может быть разделено на две ветви и имеет несколько вариантов. Давайте рассмотрим следующие два сценария.

Первый вариант выглядит хорошо на первый взгляд, так как все яблоки отделены от винограда. А как насчет второго? Как дерево решений узнает, какое разбиение является лучшим?

Идея состоит в том, чтобы рассчитать индекс Джини для обоих сплитов и посмотреть, какой из них ниже. Мы видим, что для варианта 1 у ветви 1 индекс Джини равен 0,444, а у ветви 2 - 0,32. Взвешенный коэффициент Джини равен (15 * 0,444 + 5 * 0,32) / 20 = 0,413. Применяя ту же логику, взвешенный индекс Джини составляет 0,447 для варианта 2. Поскольку он выше, для разделения будет выбран вариант 1. «Информационный выигрыш» - это просто разница между индексом Джини до и после разделения. В данном случае для Варианта 1 информационный прирост составляет 0,62–0,413 = 0,207. Цель алгоритма - максимизировать получение информации при каждом разбиении.

Критерии энтропии

Другой вариант определения разделения - критерий энтропии. Уравнение для энтропии приведено ниже.

И здесь чем ниже значение, тем чище ветка. Поскольку мы умножаем вероятность на логарифм вероятности, это всегда будет иметь отрицательное число. Знак минус в уравнении учитывает это и дает положительное число для суммирования энтропии.

Продолжая приведенный выше пример, общая энтропия, основанная на приведенной выше формуле, составляет 1,485. Обратите внимание, что энтропия может быть больше 1, если классов больше 2. И используя те же два варианта разбиения, которые мы использовали для индекса Джини, мы получаем общую энтропию 0,869 для варианта 1 и энтропию 1,038 для варианта 2. Здесь снова общий выигрыш информации для варианта 1 (1,485–0,869 = 0,616) больше, чем для варианта 2.

Обратите внимание, что мы должны указать параметр для алгоритма, и, следовательно, это гиперпараметр. Исследования и эксперименты показали, что нет существенной разницы в результатах при использовании того или другого. Я обычно придерживаюсь индекса Джини (по умолчанию) для своих моделей.

Важность функции

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

Так как же Random Forest рассчитывает эту относительную важность? Это делается двумя способами. Первый метод заключается в использовании прироста информации на каждом разбиении. Поскольку каждая ветвь в каждом дереве случайного леса разбита только на одну функцию, мы можем оценить информационный прирост для конкретной функции для данного дерева. Полученная информация затем умножается на количество точек данных, достигающих этой ветви. Это значение рассчитывается для всех таких разбиений для одного объекта, где бы он ни использовался в дереве, и суммировался. После того, как значение вычислено для всех функций, значения нормализуются для этого дерева. Окончательное значение важности для каждой функции - это среднее значение по всем деревьям. Обратите внимание, что это вычисление выполняется параллельно при создании деревьев.

Другой метод расчета важности функции - использование ошибки OOB (вне сумки). Модель случайного леса способна генерировать ошибку OOB, которая является ошибкой при классификации точек данных, которые не были доступны в дереве (помните, что только 63% обучающих данных отображаются для каждого дерева!). Для каждого дерева мы можем случайным образом переставить значения отдельных функций и измерить разницу между новой ошибкой OOB и исходной ошибкой OOB. Новая ошибка OOB, скорее всего, будет больше, чем базовое (исходное) значение. Особенность, вызывающая максимальную разницу, - самая важная. Обратите внимание, что каждая функция должна переставляться индивидуально. После вычисления разницы ошибок OOB значения необходимо сбросить до исходных, прежде чем повторять процесс для следующей функции.

Резюме

Это базовое введение в модель случайного леса, чтобы понять, как она работает изнутри. Это по-прежнему очень надежная модель для начинающих, учитывая, что в вашем распоряжении другие продвинутые модели, такие как XGBOOST и LightGBM. Преимущество модели случайного леса в том, что ее легко понять, настроить и реализовать без особых усилий. Я напишу другой пост о том, как реализовать случайный лес в Scikit-Learn на конкретном примере. Так что остерегайтесь этого!

Надеюсь, вам понравилось читать так же, как я любил писать этот пост!