Вступление

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

Предпосылки

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

  1. Деревья решений: мы также будем создавать это с нуля для нашего случайного леса, но я не буду объяснять его теорию и рабочий механизм, для краткости упрощает рассуждения, таким образом, все смешано в одном посте только сделает это неразумным.
  2. Ансамблевое обучение: случайный лес - это лишь подмножество этого обширного набора методов машинного обучения, вы лучше поймете этот пост, если у вас есть базовые знания об этом (не вдавайтесь в подробности только ради этого поста)
  3. Библиотека numpy и pandas: Хороший плотник должен хорошо разбираться в своих инструментах. Эти две библиотеки - наши инструменты.

Теория

Прежде чем приступить к написанию нашего кода, нам нужно понять некоторую базовую теорию:

  1. Функция упаковки: b ootstrap agg regating или упаковка - это метод выбора случайного количества образцов из исходного набора с заменой. При упаковке функций исходный набор функций выбирается случайным образом и передается в разные деревья (без замены, поскольку наличие избыточных функций не имеет смысла). Это сделано для уменьшения корреляции между деревьями. Функция, имеющая непревзойденно большую важность, заставит каждое дерево решений выбирать ее для первого и возможных последующих разбиений, это приведет к тому, что все деревья будут вести себя одинаково и, в конечном итоге, более коррелированы, что нежелательно. Наша цель здесь - создать сильно некоррелированные деревья решений.

Почему нужно сделать причину принятия решения очень некоррелированной?

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

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

Код Python

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

Случайный лесной класс

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

  1. x: независимые переменные обучающей выборки. Чтобы все было минимальным и простым, я не создаю отдельный метод подгонки, поэтому конструктор базового класса примет обучающий набор.
  2. y: соответствующие зависимые переменные, необходимые для обучения с учителем (случайный лес - это метод обучения с учителем)
  3. n_trees: количество некоррелированных деревьев, которые мы объединяем, чтобы создать случайный лес.
  4. n_features: количество функций для выборки и передачи в каждое дерево, именно здесь происходит объединение функций. Это может быть sqrt, log2 или целое число. В случае sqrt количество функций, выбранных для каждого дерева, представляет собой квадратный корень из общего числа функций и логарифмическую базу 2 из общего числа функций в случае log2.
  5. sample_size: количество строк, выбранных случайным образом и переданных в каждое дерево. Обычно оно равно общему количеству строк, но в некоторых случаях может быть уменьшено для увеличения производительности и уменьшения корреляции деревьев (упаковка деревьев - это совершенно отдельный метод машинного обучения).
  6. глубина: глубина каждого дерева решений. Более высокая глубина означает большее количество разбиений, что увеличивает тенденцию к чрезмерной подгонке каждого дерева, но, поскольку мы агрегируем несколько некоррелированных деревьев, чрезмерная подгонка отдельных деревьев едва ли беспокоит весь лес.
  7. min_leaf: минимальное количество строк, необходимое в узле для дальнейшего разделения. Чем ниже min_leaf, тем выше глубина дерева.

Начнем с определения нашего случайного класса леса.

  1. __init__: конструктор, просто определяющий случайный лес с помощью наших параметров и создающий необходимое количество деревьев.
  2. create_tree: создает новое дерево решений, вызывая конструктор класса DecisionTree, который на данный момент считается черным ящиком. Мы напишем его код позже. Каждое дерево получает случайное подмножество функций (упаковка функций) и случайный набор строк (деревья упаковки, хотя это необязательно, я написал это, чтобы показать возможность)
  3. прогноз: прогноз нашего случайного леса - это просто среднее значение всех прогнозов дерева решений.

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

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

Класс дерева решений

У него будут следующие параметры: -

  1. indxs: этот параметр существует для отслеживания того, какие индексы исходного набора идут вправо, а какие - в левое дерево. Следовательно, каждое дерево имеет параметр «indxs», в котором хранятся индексы содержащихся в нем строк. Прогнозирование производится путем усреднения этих строк.
  2. min_leaf: минимальное количество выборок строк, необходимых для конечного узла, чтобы вызвать разделение. Каждый листовой узел будет иметь образцы строк меньше min_leaf, потому что они больше не могут быть разделены (игнорируя ограничение глубины).
  3. глубина: максимальная глубина или максимальное количество возможных разделений в каждом дереве.

Мы используем декоратор свойств, чтобы сделать наш код более лаконичным.

  1. __init__: конструктор дерева решений. В нем есть несколько интересных фрагментов, на которые стоит обратить внимание:

a. if idxs is None: idxs=np.arange(len(y)) в случае, если мы не указываем индексы строк в вычислениях этого конкретного дерева, просто возьмите все строки.

б. self.val = np.mean(y[idxs]) каждое дерево решений предсказывает значение, которое представляет собой среднее значение всех содержащихся в нем строк. Переменная self.val содержит прогноз для каждого узла дерева. Для корневого узла значением будет просто среднее значение всех наблюдений, потому что оно содержит все строки, поскольку мы еще не делали разделения. Я использовал здесь термин «узел», потому что, по сути, дерево решений - это просто узел с деревьями решений справа и одним слева.

c.self.score = float(‘inf’) оценка узла рассчитывается на основе того, насколько «хорошо» он разделяет исходный набор данных. Мы определим этот «колодец» позже, а пока просто предположим, что у нас есть способ измерить такую ​​величину. Кроме того, оценка для нашего узла установлена ​​на бесконечность, потому что мы еще не сделали никаких разделений, поэтому наше несуществующее разделение бесконечно плохо, что указывает на то, что любое разделение будет лучше, чем отсутствие разделения.

d. self.find_varsplit() мы делаем наш первый сплит!

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

3. split_name: декоратор свойств, возвращающий имя столбца, который мы разделяем. var_idx - это индекс этого столбца, мы вычислим этот индекс в функции find_better_split вместе со значением столбца, на который мы разбиваем

4. split_col: декоратор свойств, возвращающий столбец с индексом var_idx с элементами в индексах, заданных переменной indxs. По сути, разделяет столбец с выбранными строками.

5. find_better_split: эта функция находит наилучшее возможное разделение в определенном столбце, это сложно, поэтому мы рассмотрели его как черный ящик в приведенном выше коде. Давайте определимся позже.

4. is_leaf: листовой узел - это тот, который никогда не разделялся, поэтому он имеет бесконечную оценку (как упоминалось выше), поэтому эта функция используется для идентификации листовых узлов. Также в случае, если мы пересекли максимальную глубину, т.е. self.depth ‹= 0, это листовой узел, так как мы не можем идти дальше.

Как найти лучший сплит?

Деревья решений обучаются путем рекурсивного разделения данных на две половины в зависимости от определенных условий. Если тестовый набор имеет 10 столбцов с 10 точками данных (значениями) в каждом столбце, всего возможно 10x10 = 100 разбиений, наша задача - найти, какое из этих разбиений лучше всего для наших данных.

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

Чтобы ускорить процесс, мы можем сделать копию столбца и отсортировать ее для вычисления средневзвешенного значения, разделив значение по индексу n+1th, используя значение суммы и сумму квадратов значений двух половин, созданных разделением по индексу nth. Это основано на следующей формуле стандартного отклонения:

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

Приступите к сортировке каждого столбца

Теперь делаем разбиения по индексу последовательно

Используя простой жадный подход, мы обнаруживаем, что разбиение, выполненное по индексу = 2, является наилучшим возможным разбиением, поскольку оно имеет наименьшее количество баллов. Позже мы выполняем те же действия для всех столбцов и сравниваем их все, чтобы найти лучший (минимальный) результат.

Ниже приведен простой код для приведенных выше графических представлений:

Следующий фрагмент кода интересен и требует пояснений:

  1. функция std_agg вычисляет стандартное отклонение, используя сумму и сумму квадратов значений
  2. curr_score = lhs_std*lhs_cnt + rhs_std*rhs_cnt оценка разделения для каждой итерации - это просто средневзвешенное значение стандартного отклонения двух половин с количеством строк в каждой половине в качестве их весов. Более низкий балл способствует более низкой дисперсии, более низкая дисперсия облегчает группировку похожих данных, что приводит к более точным прогнозам.
  3. if curr_score<self.score:
    self.var_idx,self.score,self.split = var_idx,curr_score,xi     всякий раз, когда текущая оценка лучше (меньше, чем текущая оценка в self.score), мы обновим текущую оценку и сохраним этот столбец в переменной self.var_idx (помните, что это переменная, которая помогает выбрать столбец для двух из наших декораторов свойств) и сохранить значение, по которому выполняется разбиение, в переменной self.split.

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

  1. for i in range(self.c): self.find_better_split(i) этот цикл просматривает каждый столбец и пытается найти наилучшее разбиение в этом столбце. К моменту завершения этого цикла мы исчерпали все возможные разбиения по всем столбцам и нашли наилучшее возможное разбиение. Столбец, на который нужно разделить, сохраняется в переменной self.var_idx, а значение этого столбца, которое мы разделяем, сохраняется в переменной self.split. Теперь мы рекурсивно формируем две половины, то есть правое и левое деревья решений, пока не дойдем до листового узла.
  2. if self.is_leaf: return если мы достигли листового узла, нам больше не нужно искать лучшие расщепления и просто заканчивать это дерево.
  3. self.lhs содержит левое дерево решений. Строки, которые он получает, хранятся в lhs, которые являются индексами всех таких значений в выбранном столбце, которые меньше или равны значению разделения, хранящемуся в split.value. Переменная lf_indxs содержит выборку функций (столбцов), которые получает левое дерево (упаковка функций).
  4. self.rhs содержит правильное дерево решений. rhs хранит индексы строк, переданных в правильное дерево решений. rhs вычисляется аналогично lhs, переменная rf_indxs содержит выборку функций (столбцов), которые получает правое дерево (упаковка функций).

Заключение

Вот полный код

Цель этой публикации - познакомить читателей и меня с общей работой случайных лесов для лучшего применения и отладки в будущем. Случайные леса имеют гораздо больше параметров и связанных с ними сложностей, которые я не мог описать в одном посте. Чтобы изучить более надежный и полноценный код, я предлагаю вам прочитать Код случайного леса модуля sklearn с открытым исходным кодом.

Я хотел бы поблагодарить Джереми Ховарда и Рэйчел Томас за курс машинного обучения fast.ai, который позволил мне написать этот пост. Фактически, весь мой код здесь создан после небольших изменений исходного материала курса fast.ai.

Если я допустил ошибки / был неясен в своих объяснениях, сообщите мне об этом в ответах. Спасибо за чтение.