Дерево решений и случайный лес с нуля

Всестороннее введение неспециалиста в дерево решений и алгоритм случайного леса

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

P.S. Эта статья вдохновлена ​​более ранними статьями Дерева решений от Joachim Valente и Random Forest от Dario Radečić, но идеи доработаны и усовершенствованы для улучшения алгоритма и облегчения понимания.

1. Алгоритм дерева решений

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

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

1.1. Примесь Джини

Функция стоимости, определяющая разделение родительского узла, называется примесью Джини. По сути, это концепция количественной оценки того, насколько однородным или «чистым» является узел по отношению к распределению целей в узел. Узел считается чистым (G=0), если все обучающие выборки в узле принадлежат к одному классу, а узел с большим количеством обучающих выборок из разных классов будет иметь примесь Джини, близкую к 1.

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

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

1.2. Пример классификации фруктов

Возьмем, к примеру, табличные данные fruit_name в качестве цели и mass, width , height , color_score в качестве признаков. Как может выглядеть дерево решений (максимальная глубина = 2), когда мы обучаем эти данные одной такой модели?

P.S. Для простоты демонстрации бинарное разделение считается случайным, и его не следует рассматривать как оптимальное разделение.

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

1.3. Прогноз во время вывода

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

В приведенном выше тестовом примере, поскольку масса = 160 > 155, путь решения идет к правому дочернему узлу от корневого узла. С этой точки, поскольку высота = 7,4≤7,7, он переходит в левый дочерний узел, который затем является конечным узлом без дальнейшего разделения.

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

1.4. Кодирование дерева решений с нуля

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

1.4.1. Создайте экземпляр класса узла

После импорта необходимых библиотек создаем класс Node с несколькими сопутствующими атрибутами. Обычно предполагается, что это родительский узел.

Во-первых, self.predicted_class будет хранить предсказанный класс в каждом (родительском) узле. Да, верно, каждый узел должен иметь класс большинства в качестве прогнозируемого класса, даже для корневого узла. И этот атрибут особенно важен в кодах, особенно для терминальных узлов, когда во время логического вывода должен быть получен предсказанный класс.

self.feature_index и self.threshold в первую очередь записывают оптимальную функцию и соответствующее оптимальное пороговое значение функции в родительском узле, с которым будет происходить разделение для формирования дочерних узлов.

self.left и self.right — чрезвычайно важные атрибуты, которые используются для рекурсивного создания экземпляров дочерних узлов. Следовательно, эти атрибуты, по сути, являются еще одним классом Node, который, в свою очередь, также может иметь атрибуты self.left и self.right в качестве дочерних узлов.

1.4.2. Создать экземпляр класса дерева решений

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

self.random_state контролирует случайность оценщика, в частности перестановку признаков. Функции всегда случайным образом переставляются при каждом разделении. Когда max_features ‹ n_features , алгоритм будет выбирать max_features случайным образом при каждом разделении, прежде чем найти среди них наилучшее разделение. Но наилучший найденный раскол может различаться в разных прогонах, даже если max_features =n_features. Это так, если улучшение критерия одинаково для нескольких расщеплений и одно расщепление должно быть выбрано случайным образом.

Наконец, self.tree является корнем Node, содержащим все остальные дочерние Node в качестве атрибутов, рекурсивно увеличивающихся при вызове функции для роста дерева.

1.4.3. Метод подгонки

Метод fit класса DecisionTree принимает обучающий набор данных в форме Pandas DataFrame/Series или массива Numpy, а затем определяет количество классов, количество функций и максимальные функции. Наконец, вызывается функция self.grow_tree для рекурсивного построения дерева решений.

1.4.4. Метод выращивания дерева

Метод grow_tree сначала получает данные из метода fit, а затем создает экземпляр родительского узла Node и определяет свой прогнозируемый класс родительского узла. Когда условие self.max_depth выполнено, вызывается функция self.best_split для поиска оптимального идентификатора функции и соответствующего оптимального порогового значения для разделения на дочерние узлы.

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

Затем соответствующие подмножества данных рекурсивно вызываются в одну и ту же функцию grow_tree и сохраняются как атрибуты родителя Node как node.left и node.right.

Затем возвращается родительский объект Node.

1.4.5. Лучший метод разделения

Метод best_split принимает данные из родительского узла в методе grow_tree , затем проверяет примесь Джини родительского узла. Если родительский узел уже чистый (G=0), best_feat_id и best_threshold возвращаются как None . В противном случае метод переходит к скремблированию и рандомизации индексов признаков на основе максимального количества признаков.

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

Для каждой пары индекса признаков и порога признаков вычисляется среднее значение примеси Джини. Пара индекса функции и порога функции, которая соответствует наименьшей средней примеси Джини (при условии, что она ниже, чем примесь Джини родительского узла), возвращается как best_feat_id и best_threshold .

1.4.6. Метод прогнозирования

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

1.4.7. Примерный метод прогнозирования

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

Полные коды алгоритма дерева решений представлены на Github. Показатели точности очень сопоставимы с реализацией scikit-learn, и мы приглашаем вас попробовать ее.

2. Алгоритм случайного леса

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

Алгоритм случайного леса основан на идее голосования «слабых» учащихся (деревьев решений), что дает аналогию с деревьями, составляющими лес. Элемент случайности имеет несколько аспектов:

1. Каждое дерево соответствует подмножеству всего набора данных, поэтому каждое дерево будет расти по-разному, с разными правилами.
2. Если весь набор данных загружается случайным образом с заменой, для каждого дерева каждое дерево по-прежнему будет иметь немного разное распределение данных и, следовательно, будет расти по-разному, с разными правилами.
3. Даже если весь набор данных загружается без замены, каждое дерево все равно может расти по-разному благодаря рандомизированному порядку или подмножеству функций, рассматриваемых для оптимального разделения в Древо решений.

Этот алгоритм от Random Forest называется Bootstrap Aggregating или бэггинг. По сути, это концепция объединения нескольких моделей (деревьев решений), привязанных к набору данных, для повышения производительности за счет уменьшения дисперсии и предотвращения чрезмерного подбора отдельных моделей.

В итоге,

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

2.1. Кодирование случайного леса с нуля

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

2.1.1. Создайте экземпляр класса Random Forest

После импорта необходимых библиотек (включая модуль для алгоритма дерева решений) создаем класс RandomForest с сопутствующими атрибутами:

• self.num_trees : количество классификаторов дерева решений для голосования, используемых для классификации.
• self.subsample_size: Доля от общего количества обучающих примеров, использованных для обучения каждого дерева решений.
• self.max_depth : максимальная глубина каждого дерева решений. Если None, то узлы расширяются до тех пор, пока все листья не станут самыми чистыми.
• self.max_features: Для каждого дерева решений при каждом разделении от родительского узла к дочерним узлам учитывайте только «максимальные функции», чтобы найти пороговое разделение.
• self.bootstrap : Начальная выборка обучающих примеров с заменой или без нее.
• self.random_state : Управляет случайностью оценки. Функции всегда случайным образом переставляются при каждом разделении в каждом дереве решений, а бутстрап-выборка переставляется случайным образом.
• self.decision_tree: список, содержащий объекты дерева решений после их построения. Изначально список пуст.

2.1.2. Метод подгонки

Во время обучения метод fit класса RandomForest берет обучающий набор данных в форме массива Pandas DataFrame/Series или Numpy и последовательно строит каждое дерево решений (импортированный модуль) на рандомизированной начальной загрузке набора обучающих данных, который затем добавляется как объект к атрибуту self.decision_tree класса RandomForest. Рандомизированная выборка с начальной загрузкой получена с помощью метода sample.

2.1.3. Образец метода

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

2.1.4. Метод прогнозирования

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

Полные коды алгоритма Random Forest показаны на Github. Опять же, наши показатели точности очень сопоставимы с реализацией scikit-learn.

3. Заключение

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

В будущем я с нетерпением жду возможности рассказать о других алгоритмах машинного обучения с нуля, таких как ванильные нейронные сети (многослойный персептрон), CNN и RNN, максимально простым способом. Оставайтесь с нами и следите за мной на Linkedin и Github.

Обновление (28 июля 2022 г.): я завершил серию из трех статей о логистической регрессии и нейронных сетях с нуля. Ознакомьтесь с ними, чтобы узнать больше:

Ваше здоровье! _/\_

Поддержите меня! — Если вы не подписаны на Medium и вам нравится мой контент, подумайте о том, чтобы поддержать меня, присоединившись к Medium по моей реферальной ссылке. ».