Определить корневой узел дерева

Осваивайте машинное обучение: деревья решений с нуля с помощью Python

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

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

Статья построена следующим образом:

• Введение в деревья решений
• Математика за деревьями решений
• Рекурсивный ускоренный курс
• Реализация с нуля
• Оценка модели
• Сравнение с Scikit-Learn
• Заключение

Вы можете скачать соответствующую записную книжку здесь.

Введение в деревья решений

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

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

Давайте сначала рассмотрим пример дерева решений:

Как видите, существует несколько типов узлов:

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

В зависимости от размера набора данных (как в строках, так и в столбцах), вероятно, существуют тысячи или миллионы способов упорядочивания узлов и их условий. Итак, как определить корневой узел?

Как определить корневой узел

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

Чтобы дополнительно решить, какая из нечистых характеристик является наиболее чистой, мы можем использовать метрику Энтропия. Мы обсудим формулу и расчеты позже, но вы должны помнить, что значение энтропии варьируется от 0 (наилучшее) до 1 (наихудшее).

Затем в качестве корневого узла используется переменная с наименьшей энтропией.

Тренировочный процесс

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

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

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

Таким образом, дерево строится рекурсивно. Процесс рекурсии может продолжаться бесконечно, поэтому нам придется указать некоторые условия выхода вручную. Самые распространенные из них — максимальная глубина и минимальная выборка в узле. Оба будут рассмотрены позже, после реализации.

Процесс прогнозирования

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

Как только листовой узел достигнут, возвращается наиболее распространенное значение.

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

Математика за деревьями решений

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

Начнем с энтропии. Как упоминалось ранее, он измеряет чистоту разделения на уровне узла. Его значение варьируется от 0 (чистый) до 1 (нечистый).

Как видите, это относительно простое уравнение, поэтому давайте посмотрим на него в действии. Представьте, что вы хотите рассчитать чистоту следующего вектора:

Подводя итог, нули и единицы — это метки класса со следующими счетчиками:

Расчет энтропии настолько прост, насколько это возможно с этой точки (с округлением до пяти десятичных знаков):

Результат 0,88 указывает на то, что раскол далек от чистого. Давайте теперь повторим вычисления на Python. Следующий код реализует формулу entropy(s) и вычисляет ее по тому же вектору:

Результаты показаны на следующем изображении:

Как видите, результаты идентичны, что говорит о том, что формула была применена правильно.

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

Информационный прирост можно рассчитать по следующей формуле:

Давайте посмотрим на пример разделения и вычислим прирост информации:

Как видите, значения энтропии были рассчитаны заранее, поэтому нам не нужно тратить на них время. Расчет прироста информации теперь представляет собой тривиальный процесс:

Давайте теперь реализуем это на Python. Следующий фрагмент кода реализует функцию information_gain() и вычисляет ее для ранее обсужденного разделения:

Результаты показаны на следующем изображении:

Как видите, значения совпадают.

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

Рекурсивный ускоренный курс

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

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

Давайте посмотрим на простейший возможный пример — рекурсивную функцию, которая возвращает факториал целого числа:

Результаты показаны на следующем изображении:

Как видите, функция вызывает сама себя, пока введенное число не станет равным 1. Это условие выхода нашей функции.

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

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

Реализация с нуля

Нам понадобятся два класса:

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

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

• __init__() — конструктор, хранит значения для min_samples_split и max_depth . Это гиперпараметры. Первый используется для указания минимального количества выборок, необходимых для разделения узла, а второй определяет максимальную глубину дерева. Оба используются в рекурсивных функциях как условия выхода.
• _entropy(s) – вычисляет примесь входного вектора s
• _information_gain(parent, left_child, right_child) вычисляет значение информационного прироста разделения между родителем и двумя детьми
• Функция _best_split(X, y) вычисляет наилучшие параметры разделения для входных объектов X и целевой переменной y . Это достигается путем перебора каждого столбца в X и каждого порогового значения в каждом столбце, чтобы найти оптимальное разбиение с использованием увеличения информации.
• _build(X, y, depth) функция рекурсивно строит дерево решений до тех пор, пока не будут выполнены критерии остановки (гиперпараметры в конструкторе)
• Функция fit(X, y) вызывает функцию _build() и сохраняет построенное дерево в конструкторе.
• _predict(x) функция проходит по дереву для классификации одного экземпляра
• Функция predict(X) применяет функцию _predict() к каждому экземпляру в матрице X .

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

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

Оценка модели

Давайте теперь протестируем наш классификатор. Мы будем использовать набор данных Iris из Scikit-Learn. Следующий фрагмент кода загружает набор данных и разделяет его на функции ( X ) и цель ( y ):

Теперь давайте разделим набор данных на обучающую и тестовую части. Следующий фрагмент кода делает именно это в соотношении 80:20:

А теперь займемся тренировкой. Приведенный ниже фрагмент кода обучает модель с гиперпараметрами по умолчанию и делает прогнозы на тестовом наборе:

Давайте посмотрим на сгенерированные прогнозы ( preds ):

А теперь собственно метки классов ( y_test ):

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

Как и ожидалось, будет напечатано значение 1.0 . Не позволяйте этому обмануть вас — набор данных Iris невероятно легко правильно классифицировать, особенно если вы получите хороший «случайный» набор тестов. Тем не менее, давайте сравним наш классификатор с классификатором, встроенным в Scikit-Learn.

Сравнение с Scikit-Learn

Мы хотим знать, хороша ли наша модель, поэтому давайте сравним ее с тем, что, как мы знаем, хорошо работает — классом DecisionTreeClassifier от Scikit-Learn.

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

Как и следовало ожидать, мы получили оценку точности 1.0 .

На сегодня все. Подведем итоги в следующем разделе.

Заключение

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

Теперь вы знаете, как реализовать алгоритм классификатора дерева решений с нуля. Означает ли это, что вам следует отказаться от де-факто стандартных библиотек машинного обучения? Нет, совсем нет. Позвольте мне уточнить.

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

Благодарим за чтение. Следите за новостями в блоге, если вас интересуют другие статьи о машинном обучении с нуля.

Учить больше

Оставайся на связи

• Следуйте за мной на Medium, чтобы увидеть больше подобных историй
• Подпишитесь на мою рассылку»
• Подключиться к LinkedIn
• Загляните на мой сайт

Источник