Введение в алгоритм дерева решений

Введение:

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

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

Построение дерева решений:

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

Представление дерева решений:

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

Некоторые важные термины:

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

Узел решения: узлы, полученные после разделения корневых узлов, называются узлами решения.

Листовой узел: узлы, дальнейшее разделение которых невозможно, называются листовыми узлами или конечными узлами.

Поддерево: Раздел поддерева этого дерева решений называется поддеревом.

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

Методы:

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

2. Получение информации

3. Тест хи-квадрат

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

Индекс Джини — это показатель, который определяет, насколько точна классификация. Индекс Джини присваивает оценку от 0 до 1, где 0 представляет все наблюдения, принадлежащие одному классу, а 1 представляет случайное распределение элементов внутри классов. Индекс Джини является одним из показателей оценки, используемых для оценки модели дерева решений. Примесь Джини, равная 0,5, указывает на то, что элементы равномерно распределены по некоторым классам. Математическое обозначение меры примеси Джини дается следующей формулой:

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

Пример примеси Джини:

Рассмотрим следующую таблицу данных, где для каждого элемента (строки) у нас есть две переменные, описывающие его, и соответствующая метка класса.

● Базовый уровень разделения для Var1:

Var1 имеет 4 экземпляра (4/10), равных 1, и 6 экземпляров (6/10), равных 0.

● Для Var1 == 1 и Class == A:

1/4 экземпляра имеют класс равный А.

● Для Var1 == 1 и Class == B:

3/4 экземпляра имеют класс, равный B.

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

Вот 1-((1/4)² + (3/4)²) = 0,375

● Для Var1 == 0 и Class == A:

4/6 экземпляров имеют класс равный А.

● Для Var1 == 0 и Class == B:

2/6 экземпляров имеют класс, равный B.

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

Вот 1-((4/6)² + (2/6)²) = 0,4444

● Затем мы взвешиваем и суммируем каждое из разделений на основе базового уровня/доли данных, которые занимает каждое разделение.

● 4/10 * 0.375 + 6/10 * 0.444 = 0.41667

2. Получение информации

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

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

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

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

Рассчитайте энтропию выходного атрибута (до разделения) по формуле

Здесь p — вероятность успеха, q — вероятность отказа узла. Скажем, из 10 значений данных 5 относятся к True и 5 относятся к False, тогда c вычисляется как 2, p_1 и p_2 вычисляются как ½.

Пример получения информации:

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

Рассчитайте энтропию выходного атрибута (до разделения) по формуле

Здесь p — вероятность успеха, q — вероятность отказа узла. Скажем, из 10 значений данных 5 относятся к True и 5 относятся к False, тогда c вычисляется как 2, p_1 и p_2 вычисляются как ½.

Рассчитайте энтропию всех входных атрибутов по формуле

T - выходной атрибут,

X — входной атрибут,

P (c) - вероятность относительно возможной точки данных, присутствующей в X, и

E(c) — это энтропия относительно «истины», относящаяся к возможной точке данных.

Предположим, что входной атрибут (приоритет) имеет два упомянутых возможных значения: низкое и высокое. Что касается низкого уровня, есть 5 связанных точек данных, из которых 2 относятся к True и 3 относятся к False. Что касается высокого уровня, остальные 5 точек данных связаны, где 4 относятся к Истина, а 1 относится к Ложь. Тогда E(T, X) будет равно

В E(2, 3) p равно 2, а q равно 3.

В E(4, 1) p равно 4, а q равно 1.

Вычислите то же самое несколько раз для всех входных атрибутов в данном наборе данных.

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

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

Повторите шаги 1–4, разделив набор данных в соответствии с разделением. Этот алгоритм выполняется до тех пор, пока все данные не будут классифицированы.

3. Тест хи-квадрат

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

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

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

Когда остановить обучение?

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

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

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

Есть больше гиперпараметров, таких как:

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

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

Подробнее об этих гиперпараметрах можно прочитать здесь.

Обрезка

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

В основном существует 2 способа обрезки:

(i) Предварительная обрезка — мы можем остановить рост дерева раньше, что означает, что мы можем обрезать/удалить/вырезать узел, если он имеет низкую важность во время выращивания дерева.

(ii) Постобрезка — как только наше дерево построено до глубины, мы можем начать обрезать узлы в зависимости от их значимости.

Приложения дерева решений

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

● Управление бизнесом

● Управление взаимоотношениями с клиентами

● Обнаружение мошеннических заявлений

● Энергопотребление

● Управление здравоохранением

● Диагностика неисправностей

Преимущества и недостатки

Преимущества:

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

Недостатки:

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

Конец Примечание:

Спасибо за прочтение!!