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

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

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

Стоимость сплита:

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

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

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

1.computing the entropy :
2.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.

Классификация с использованием алгоритма 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²(Target=0) — P²(Target=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 максимальное значение индекса Джини равно

= 1–1/k

Минимальное значение индекса Джини будет равно 0, если все наблюдения относятся к одной метке.

Шаги:

1.compute the gini index for data-set
2.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 gain
3. pick the best gini gain attribute.
4. Repeat until we get the tree we desired

Почему дерево решений называют жадным алгоритмом?

Поскольку алгоритм является рекурсивным по своей природе, и сформированная группа может быть разделена с использованием некоторой стратегии, и выбирается разделение с наименьшей стоимостью, и из-за этого желания снизить стоимость дерево решений называется «жадным алгоритмом».

Подпишитесь на меня в Linkedin и Github, чтобы узнавать больше об обновлениях и проектах по науке о данных.