Что такое дерево решений?

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

Как строится дерево решений?

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

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

Как мы определяем, насколько информативна функция?

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

Классификация с использованием Quinlan ID3 (итеративный деоптимизатор версии 3):

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

Формула расчета энтропии:

→ Энтропия максимальна, когда выборки распределены равномерно.

→pi — это вероятность различных выборок данных, которые есть в наборе данных.

Давайте посмотрим, как мы можем построить дерево решений, показанное выше, с помощью ID3:

Вот набор данных для дерева решений:

Функции: крайний срок, вечеринка, лень. Ярлык: Активность

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

Формула получения информации о любой функции F :

Шаг 1: энтропия (S)→ Используя уравнение, я рассчитываю вероятность различных классов ярлыков (вечеринка, паб, исследование, телевидение).

P(party) = 5/10 = 1/2 , P(pub) = 1/10 , P(study) = 3/10 , P(tv) = 1/10

Entropy(S) = -P(party)log2(P(party))-P(pub)log2(P(pub))-P(study)log2(P(study))-P(tv)log2(P(tv)).

Шаг 2. Выберите любую функцию и рассчитайте энтропию (Sf) для каждого значения f этой функции F. Затем подставьте ее в формулу ниже:

Например: давайте рассмотрим крайние значения этой функции (срочно, близко, нет)

→ |S| = 10 , |S urgent| = 3 , |S none| = 3 , |S near| = 4

Энтропия (S срочно) → Поскольку срочность имеет значения меток (учеба, вечеринка), поэтому рассчитайте вероятность учебы и вечеринки и выполните действия, описанные в шаге 1.

Аналогичным образом рассчитайте энтропию для других значений крайнего срока функции и подставьте в уравнение III

Теперь суммируем их и подставляем в уравнение II:

InformationGain(Deadline,S) = Entropy(S) -(0.28+0.6+0.28)

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

При подсчете было обнаружено, что ведомая сторона имеет самый высокий прирост информации, после чего она станет корнем дерева.

Шаг 4) Добавьте ветвь из узла для каждого возможного значения этой функции. Функция Party имеет два значения да и нет

Шаг 5) Теперь для каждой проверки значения:

если все примеры имеют одинаковую метку → вернуть лист с этой меткой. (Чистый узел)

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

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

Наконец, это приведет к дереву, показанному выше.

Преимущества: он может бороться с шумом в наборе данных.

Проблема:

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

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

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

Формула для расчета примеси Джини: уравнение 1

N(i) → обозначает долю точек данных, принадлежащих
классу i.

Давайте посмотрим, как мы можем построить дерево решений, показанное выше, с помощью CART:

Используемый набор данных такой же, как мы использовали выше

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

Формула для получения информации о любом признаке F : Уравнение II

Шаг 1: G(S)→ Используя уравнение, я вычисляю N различных классов ярлыков (вечеринка, паб, учеба, телевидение).

N(party) = 5/10 = 1/2 , N(pub) = 1/10 , N(study) = 3/10 , N(tv) = 1/10

G(S) = 1 -(N(party)²+N(pub)²+N(study)²+N(tv)²) = 1-(0.25+0.01+0.09+0.01) = 1–0.36 = 0.64

Шаг 2. Выберите любую характеристику и рассчитайте G(Sf) для каждого значения f этой характеристики F. Затем подставьте полученное значение в приведенную ниже формулу:

Например: давайте рассмотрим крайние значения этой функции (срочно, близко, нет)

→ |S| = 10 , |S urgent| = 3 , |S none| = 3 , |S near| = 4

G(S срочно) → Так как срочное имеет значения меток (учеба, вечеринка), рассчитайте N учебы и вечеринки и выполните действия, описанные в шаге 1.

Точно так же рассчитайте примесь Джини для других значений крайнего срока функции и введите в уравнение III.

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

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

Все остальные шаги аналогичны алгоритму ID3.

Конец статьи.

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

Надеюсь, это помогло :)