При построении дерева узлы принятия решений означают

9.4. дерево решений задачи

9.4. дерево решений задачи: Производственный менеджмент, В. А. Козловского, 2002 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Учебник адресован тем, кто готовится к карьере менеджера, принимающего непо-средственное участие в процессе производства продукции или предоставления услуг в широ-ком межотраслевом разрезе.

9.4. дерево решений задачи

Кроме использования платежной матрицы для решения данного типа задач, как уже указывалось, можно строить дерево решений. Например, для рассматриваемой в примере 9.1 задачи дерево имеет следующий вид (рис. 9.2).

Рис. 9.2. Дерево решений к примеру 9.1

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

• в узлах состояния внешней среды платежи «сворачиваются» в значения ЕМУ с соответствующими им весами-вероятностями;

• в узлах принятия решений происходит выбор лучших альтернатив, например, по критерию EMV=> max.

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

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

Оптовый склад обслуживает кинои фотолаборатории, в том числе отпускает им проявитель. Статистика уровня продаж: 11 упаковок продаются с вероятностью 45\%, 12 упаковок — с вероятностью 35\%, 13 упаковок 20\%. Прибыль от реализации одной упаковки — 35 руб. Непроданные упаковки в конце недели уничтожаются, при этом потери составляют 56 руб. с каждой упаковки. Какой недельный запас проявителя является Для склада оптимальным?

Отметим, что сумма вероятностей продажи 11, 12 и 13 упаковок равна 100\%. Это означает, что никаких других объемов недельных продаж не зарегистрировано и в расчет они не могут быть включены. Рассчитаем платежи:

а) проданы 11 упаковок: 35 х 11 = 385 руб., при запасе в И упаковок;

б) проданы 11 упаковок при запасе в 12, а одна упаковка уничтожена1 385-56 = 329 руб.; в) проданы 12 упаковок (весь запас): 35 х 12 = 420 руб., наличие спроса из 13 упаковок здесь ничего не меняет;

г) при запасе в 13 упаковок возможны три варианта: продажа 11 упаковок (385 56 х 2 = 273 руб., две упаковки уничтожены), продажа 12 упаковок (420 — 56 = 364 руб., одна упаковка уничтожена), продажа 13 упаковок (35×13 = 455 руб.).

Результаты расчета сведены в табл. 9.2. Расчет ЕМУ показывает, что лучший вариант решения запасать 11 упаковок. Рассчитаем предельную цену полной информации о продажах (алгоритм ее расчета будет показан в следующем разделе):

EVPI = 385 х 0,45 + 420 х 0,35 + 455 х 0,20 385 = 26,25 руб. Дерево решений этой задачи имеет следующий вид:

Рис. 9.3. Дерево решений к примеру 9.2

Источник

Как разобраться в дереве принятия решений и сделать его на Python

Совсем скоро, 20 ноября, у нас стартует новый поток «Математика и Machine Learning для Data Science», и в преддверии этого мы делимся с вами полезным переводом с подробным, иллюстрированным объяснением дерева решений, разъяснением энтропии дерева решений с формулами и простыми примерами, вводом понятия «информационный выигрыш», которое игнорируется большинством умозрительно-простых туториалов. Статья рассчитана на любящих математику новичков, которые хотят больше разобраться в работе дерева принятия решений. Для полной ясности взят совсем маленький набор данных. В конце статьи — ссылка на код на Github.

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

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

Лист/терминальный узел — узел, который не разделяется на другие узлы, называется терминальный узел, или лист.

Набор данных

Я взяла совсем маленький набор данных, содержащий индекс массы тела (BMI), возраст (Age) и целевую переменную Diabetes (диабет). Давайте спрогнозируем, будет у человека данного возраста и индекса массы тела диабет или нет.

Представление набора данных

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

Вот так в дереве решений происходит разбиение.

Важные теоретические определения

Энтропия

Энтропия — это мера случайности или неопределенности. Уровень энтропии колеблется от 0 до 1 . Когда энтропия равна 0, это означает, что подмножество чистое, то есть в нем нет случайных элементов. Когда энтропия равна 1, это означает высокую степень случайности. Энтропия обозначается символами H(S).

Формула энтропии

Энтропия вычисляется так: -(p(0) * log(P(0)) + p(1) * log(P(1)))

Связь между энтропией и вероятностью

Когда энтропия равна 0, это означает, что подмножество «чистое», то есть в нем нет энтропии: либо все «да», либо все голоса «нет». Когда она равна 1, то это означает высокую степень случайности. Построим график вероятности P(1) вероятности принадлежности к классу 1 в зависимости от энтропии. Из объяснения выше мы знаем, что:

Если P(1) равно 0, то энтропия равна 0
Если P(1) равно 1, то энтропия равна 0
Если P(1) равно 0,5, то энтропия равна 1

Уровень энтропии всегда находится в диапазоне от 0 до 1.

Информационный выигрыш

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

Как работает дерево решений

В нашем наборе данных два атрибута, BMI и Age. В базе данных семь записей. Построим дерево решений для нашего набора данных.

1. Корневой узел

В дереве решений начнем с корневого узла. Возьмем все записи (в нашем наборе данных их семь) в качестве обучающих выборок.

В корневом узле наблюдаем три голоса за и четыре против.
Вероятность принадлежности к классу 0 равна 4/7. Четыре из семи записей принадлежат к классу 0.
P(0) = 4/7
Вероятность принадлежности к классу 1 равна 3/7. То есть три из семи записей принадлежат классу 1.
P(1) = 3/7.

Вычисляем энтропию корневого узла:

2. Как происходит разбиение?

У нас есть два атрибута — BMI и Age. Как на основе этих атрибутов происходит разбиение? Как проверить эффективность разбиения?

1. При выборе атрибута BMI в качестве переменной разделения и ≤30 в качестве точки разделения мы получим одно чистое подмножество.

Точки разбиения рассматриваются для каждой точки набора данных. Таким образом, если точки данных уникальны, то для n точек данных будет n-1 точек разбиения. То есть в зависимости от выбранных точки и переменной разбиения мы получаем высокий информационный выигрыш и выбираем разделение с этим выигрышем. В большом наборе данных принято считать только точки разделения при определенных процентах распределения значений: 10, 20, 30%. У нас набор данных небольшой, поэтому, видя все точки разделения данных, я выбрала в качестве точки разделения значения ≤30.

Энтропия чистого подмножества равна нулю. Теперь рассчитаем энтропию другого подмножества. Здесь у нас три голоса за и один против.

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

2. Выберем атрибут Age в качестве переменной разбиения и ≤45 в качестве точки разбиения.

Давайте сначала вычислим энтропию подмножества True. У него есть одно да и одно нет. Это высокий уровень неопределенности. Энтропия равна 1. Теперь рассчитаем энтропию подмножества False. В нем два голоса за и три против.

3. Рассчитаем информационный выигрыш.

Мы должны выбрать атрибут, имеющий высокий информационный выигрыш. В нашем примере такую ценность имеет только атрибут BMI. Таким образом, атрибут BMI выбирается в качестве переменной разбиения. После разбиения по атрибуту BMI мы получаем одно чистое подмножество (листовой узел) и одно нечистое подмножество. Снова разделим это нечистое подмножество на основе атрибута Age. Теперь у нас есть два чистых подмножества (листовой узел).

Итак, мы создали дерево решений с чистыми подмножествами.

Напишем это на Python с помощью sklearn

1. Импортируем библиотеки.

import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns 

2. Загрузим данные.

df=pd.read_csv("Diabetes1.csv") df.head() 

3. Разделим переменные на x и y.

Атрибуты BMI и Age принимаются за x.
Атрибут Diabetes (целевая переменная) принимается за y.

x=df.iloc[. 2] y=df.iloc[:,2:] x.head(3) 

4. Построим модель с помощью sklearn

from sklearn import tree model=tree.DecisionTreeClassifier(criterion="entropy") model.fit(x,y) 

Вывод: DecisionTreeClassifier (criterion=«entropy»)

5. Оценка модели

Вывод: 1.0 . Мы взяли очень маленький набор данных, поэтому оценка равна 1.

6. Прогнозирование с помощью модели

Давайте предскажем, будет ли диабет у человека 47 лет с ИМТ 29. Напомню, что эти данные есть в нашем наборе данных.

Вывод: array([‘no’], dtype=object)
Прогноз — нет, такой же, как и в наборе данных. Теперь спрогнозируем, будет ли диабет у человека 47 лет с индексом массы тела 45. Отмечу, что этих данных в нашем наборе нет.

Вывод: array([‘yes’], dtype=object)

7. Визуализация модели:

Код и набор данных из этой статьи доступны на GitHub.

Приходите изучать математику к нам на курс «Математика и Machine Learning для Data Science» а промокод HABR, добавит 10 % к скидке на баннере.

Рекомендуемые статьи

Источник