Что такое модель дерева решений?
Деревья решений — это контролируемая модель машинного обучения, которая использует помеченные входные и целевые данные для обучения моделей. Деревья решений представляют процесс принятия решений с помощью ветвящихся древовидных структур. Они принимают решения на основе ответов на предыдущие наборы вопросов (метки/узлы). Они имитируют человеческое мышление посредством логического простого для понимания потока, облегчая ученым данных и заинтересованным сторонам понимание и интерпретацию процесса и результатов модели. В отличие от линейных моделей, деревья решений могут работать с нелинейными отношениями между переменными.
Концепция деревьев решений существовала задолго до моделей машинного обучения. Они использовались в экономике, бизнесе, операциях и других областях для анализа принятия организационных решений [1]. Простой логический алгоритм работы деревьев решений:
Структура дерева решений
Деревья решений строятся с использованием рекурсивного секционирования. Дерево решений рисуется вверх ногами, его корень находится наверху. Корневые узлы начинаются со всеми обучающими данными. Начиная с корневого узла, каждый узел можно разделить на левый и правый дочерние узлы. На изображении выше красные прямоугольные текстовые поля с указанными условиями являются узлами дерева. На основе этих условий/кодов дерево разбивается на ветви/ребра. Затем эти узлы могут быть разделены, и они станут родительскими узлами своих результирующих дочерних узлов. Конец ветки, который больше не разделяется, называется листом/решением. Набор данных производственного уровня имеет различные функции и, следовательно, может иметь гораздо более глубокое дерево с множеством узлов, ветвей и листьев.
Типы деревьев решений
Деревья решений в основном используются для решения проблем классификации с помощью модели для категоризации или классификации объекта. В машинном обучении деревья решений также используются для решения проблем регрессии. Этот подход используется в прогностической аналитике для прогнозирования результатов на основе невидимых данных, таких как прогнозирование цен на дома, доходов отдельных лиц и т. д. Scikit-learn, библиотека Python, которая поддерживает машинное обучение, предоставляет функции, позволяющие использовать деревья решений регрессии и классификации. через DecisionTreeRegressor() и DecisionTreeClassifier() соответственно.
Как принимается решение о разделении деревьев решений?
Разделение данных в оптимальной точке разделения на каждом узле имеет решающее значение для эффективной модели дерева решений. Но как нам решить, какие функции для каждого узла? Чтобы решить эту проблему, существует несколько алгоритмов построения деревьев решений, которые используют разные метрики для расчета оптимального разделения.
Алгоритмы дерева решений, которые будут обсуждаться в этой статье:
- CART (деревья классификации и регрессии)
- ID3 (Итеративный дихотомайзер 3)
В следующем разделе будет представлен краткий обзор этих алгоритмов дерева решений вместе с метриками, используемыми в каждом алгоритме для улучшения качества разделения.
CART (деревья классификации и регрессии):
CART — это алгоритм дерева решений, который обрабатывает как задачи классификации, так и задачи регрессии. В дереве решений узлы разбиваются на дочерние узлы на основе порогового значения атрибута. CART использует индекс Джини и уменьшение дисперсии в качестве показателей для определения этого порога. Для деревьев регрессии классификации CART использует Gini Impurity в качестве показателя для разделения наборов данных на дерево решений. CART также можно применять к многоклассовым функциям. Для деревьев решений регрессии критерий среднеквадратичной ошибки, который равен уменьшению дисперсии, используется в качестве критерия выбора признаков и минимизирует потери L2 с использованием среднего значения каждого терминала. узел [2].
В пакете scikit-learn (sklearn) для Python, который популярен среди специалистов по данным для реализации моделей машинного обучения, используется оптимизированная версия алгоритма CART.
Индекс Джини
Индекс Джини используется, когда целевая переменная является категориальной переменной. Индекс Джини измеряет вероятность неправильной классификации случайного экземпляра при случайном выборе. Индекс Джини или примесь Джини рассчитывается путем вычитания суммы квадратов вероятностей каждого класса из единицы. Он варьируется от 0 до 1. Чем ниже индекс Джини, тем лучше тем ниже вероятность неправильной классификации [4]. Формула для расчета индекса Джини или примеси Джини определяется следующим образом:
Уменьшение дисперсии
Уменьшение дисперсии — это один из показателей, используемых в деревьях решений регрессии, когда целевая переменная непрерывна. Утверждение этой метрики состоит в том, чтобы найти функции, которые эффективно уменьшают дисперсию выходной переменной. Стандартная формула дисперсии используется для расчета однородности или чистоты узла. Если узел полностью однороден, его дисперсия равна 0.
ID3 (итеративный дихотомайзер 3)
ID3 — это алгоритм дерева решений классификации, использующий жадный подход к построению дерева решений путем выбора лучших признаков, дающих максимальный прирост информации или минимальную энтропию[5]. Алгоритм ID3 может итеративно делить объекты на две или более групп на каждом шаге. В общем, алгоритм ID3 в основном используется в задачах классификации без каких-либо непрерывных переменных.
Что такое энтропия?
Энтропия — это метрика, которая измеряет примесь или неопределенность группы наблюдений. Он определяет, как дерево решений разбивает данные [3]. Проще говоря, энтропия измеряет, насколько «смешанным» или неоднородным является столбец. В дереве решений «смешанные» данные разбиваются на основе значений признака, связанного с каждой точкой данных. С каждым разбиением данные становятся менее «смешанными» и более однородными, что приводит к снижению энтропии. Формула для расчета энтропии предназначена для набора данных S с c классами, где p(i) — вероятность случайного выбора примера в классе i [6]:
Энтропия или мера примеси может принимать значение от 0 до 1. Энтропия, равная 0, указывает на чистый или однородный набор данных. Энтропия, равная 1, указывает на нечистый или неоднородный набор данных. Он представляет собой степень неопределенности в наборе данных/узле.
Что такое получение информации?
Прирост информации можно определить как меру того, сколько информации предоставляет функция о классе. Учитывая, что энтропия измеряет нечистоту или неоднородность набора данных, можно измерить эффективность атрибута. Уменьшение энтропии после разделения данных по атрибуту приводит к увеличению объема информации. Прирост информации показывает, насколько уменьшилась неопределенность в наборе данных/узле после разделения по признаку f[5]. Функция с наибольшим приростом информации используется для разделения набора данных в этом конкретном узле.
Прирост информации о степени неопределенности для уменьшения набора данных S после разделения по атрибуту A определяется выражением, где Sv представляет дочерние узлы после разделения:
Подгонка в деревьях решений
Несмотря на то, что деревья решений являются одним из широко используемых алгоритмов машинного обучения с учителем, они также имеют некоторые недостатки, которых следует опасаться специалистам по данным. Одним из основных недостатков деревьев решений является проблема переоснащения.Переоснащение — это когда модель слишком близко подходит к обучающим данным, поэтому может стать менее точной при столкновении с новыми данными или прогнозировании будущих результатов. Чтобы соответствовать данным (даже зашумленным), он продолжает генерировать новые узлы, и в конечном итоге дерево становится слишком сложным для интерпретации. Дерево решений хорошо предсказывает данные, но может быть неточным для новых данных [7]. Существуют различные методы предотвращения переобучения модели дерева решений, которые будут обсуждаться в другой статье из серии деревьев решений.
Ссылки
[2] https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html
[3] https://www.section.io/engineering-education/entropy-information-gain-machine-learning/
[5] https://iq.opengenus.org/id3-algorithm/
[6] https://www.section.io/engineering-education/entropy-information-gain-machine-learning/
[7] http://theprofessionalspoint.blogspot.com/2019/02/advantages-and-disadvantages-of.html
