мл | Алгоритм дерева решений и код с использованием Python.

Древо решений

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

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

Прежде чем мы погрузимся в это, позвольте мне спросить вас об этом

Почему дерево решений?

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

ну, может быть много причин, но я полагаю, что некоторые из них

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

Например : если мы классифицируем заявку на банковский кредит для клиента, дерево решений может выглядеть так:

Здесь мы можем увидеть логику того, как он принимает решение.

Это просто и понятно.

Итак, что такое дерево решений??

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

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

Хорошо, а как это сделать??

Есть пара алгоритмов для построения дерева решений, мы говорим только о некоторых из них.

CART (деревья классификации и регрессии) → в качестве показателя используется индекс Джини (классификация).
ID3 (итеративный дихотомайзер 3) → использует функцию энтропии и прирост информации в качестве показателей.

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

Классификация с использованием алгоритма ID3.

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

У нас есть четыре значения X (прогноз, температура, влажность и ветер), которые являются категоричными, и одно значение y (игра Y или N), также являющееся категорическим.

Чтобы создать дерево, нам сначала нужно иметь корневой узел, и мы знаем, что узлы - это функции/атрибуты (прогноз, температура, влажность и ветер),

Для задачи бинарной классификации

поэтому нам нужно изучить сопоставление (что всегда делает машинное обучение) между X и y.

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

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

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

хорошо, так как мы выбираем лучший атрибут?

Ответ: используйте атрибут с наибольшим приростом информациив ID3

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

Для задачи бинарной классификации

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

Хорошо, я понял, если это не имеет смысла для вас, позвольте мне объяснить вам.
Вычислите энтропию для набора данных о погоде:

Шаги:

1.compute the entropy for data-set2.for every attribute/feature:
       1.calculate entropy for all categorical values
       2.take average information entropy for the current attribute
       3.calculate gain for the current attribute
3. pick the highest gain attribute.
4. Repeat until we get the tree we desired.

Какого черта???

Хорошо, я понял, если это не имеет смысла для вас, позвольте мне объяснить вам.

Вычислите энтропию для набора данных о погоде:

Для каждой функции рассчитать энтропию и прирост информации

Аналогично мы можем рассчитать для двух других атрибутов (влажность и температура).

Выберите самый высокий атрибут усиления.

Итак, наш узел — это Outlook.

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

Классификация с использованием алгоритма CART:

В CART мы используем индекс Джини в качестве метрики,

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

наша целевая переменная является двоичной переменной, что означает, что она принимает два значения (Да и Нет). Комбинаций может быть 4.

Actual=1 predicted 1 1 0 , 0,1, 0 0 P(Target=1).P(Target=1) + P(Target=1).P(Target=0) + P(Target=0).P(Target=1) + P(Target=0).P(Target=0) = 1 P(Target=1).P(Target=0) + P(Target=0).P(Target=1) = 1 - P^2(Target=0) - P^2(Target=1)

Индекс Джини для переменной Binary Target:

= 1 — P² (цель = 0) — P² (цель = 1)

Индекс Джини

Оценка Джини дает представление о том, насколько хорошо разделение, по тому, насколько смешаны классы в двух группах, созданных в результате разделения. Идеальное разделение приводит к показателю Джини, равному 0, тогда как в худшем случае разделение приводит к 50/50 классам.

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

Для переменной Binary Target значение максимального индекса Джини

= 1 — (1/2)² — (1/2)²

= 1–2*(1/2)²
= 1- 2*(1/4)
= 1–0.5
= 0.5

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

Максимальное значение индекса Джини может быть, когда все целевые значения распределены поровну.
Аналогично для номинальной переменной с уровнем k максимальное значение индекса Джини составляет
= 1–1/k
Минимальное значение Индекс Джини будет равен 0, если все наблюдения относятся к одному ярлыку.

Шаги:

1.compute the gini index for data-set2.for every attribute/feature:
       1.calculate gini index for all categorical values
       2.take average information entropy for the current attribute 
       3.calculate the gini gain3. pick the best gini gain attribute.
4. Repeat until we get the tree we desired.

Вычисления аналогичны ID3, за исключением изменения формулы.

например: вычислить индекс Джини для набора данных