НОУ ИНТУИТ | Лекция | Методы классификации и прогнозирования. Деревья решений

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

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

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

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

Принятие решений с помощью дерева возможных вариантов производится поэтапно:

  1. Построение дерева решений (графа без циклов). Дерево строится по определенным правилам: вершины альтернативных решений, вершины событий, дуги решений, конечные решения — листья вводятся и обозначаются определенным образом в нужном порядке.
  2. Анализ дерева решений: подсчет вероятностей и математических ожиданий (стоимостных оценок решения, EMV), расчет оптимистического и пессимистического прогноза, выбор оптимального решения.

Еще интересное: Дерево решений в теории игр,
Найти ветку поудобнее: изучаем дерево решений

Примеры решений задач: Дерево решений

Задача 1. Вы рассматриваете перспективы создания новой консалтинговой службы. Объем необходимых вложений на начальном этапе $200 тыс. Существует 60%-ная вероятность, что спрос будет высоким в 1-й год. Если спрос будет высоким в первый год, то в последующие годы вероятности высокого и низкого спроса составят 80% и 20% соответственно. Если спрос будет низким в 1-й год, то в последующие годы вероятности высокого и низкого спроса составят 40% и 60% соответственно. При высоком спросе прогнозируемые доходы составят 500 тыс. дол. в год; при низком спросе прогнозируемые доходы равны 300 тыс. дол. в год. Вы можете прекратить предоставлять услуги в любой момент. Затраты, помимо связанных с использованием компьютера, прогнозируются в размере 140 тыс. дол. в год, вне зависимости от уровня спроса.

Если Вы решите не вкладывать деньги в консалтинговую службу, то сможете вложить их на практически безрисковой основе под 20% в год.
Если будет решено организовать консалтинговую службу, Вам необходимо будет решить вопрос с проведением компьютерных расчетов, составляющих основу деятельности. Один возможный вариант — купить сервер.
Срок морального устаревания его 5 лет. Затраты будут состоять из первоначальных расходов в размере 150 тыс. долларов и ежегодных расходов на эксплуатацию в размере 20 тыс.
Альтернативный вариант — арендовать компьютерные ресурсы по мере необходимости. В этом случае затраты на аренду будут пропорциональны спросу и составят 30% доходной части за вычетом оговоренных постоянных расходов в 140 тыс. Во всех случаях никаких других издержек нет.

a. Постройте «древо решений», иллюстрирующее эти варианты и охватывающее 3 года.
b. Стоит организовать консалтинговую службу или безрисковый доход выгоднее? Рассмотрите итоги деятельности за два и три года.
c. Что лучше — купить компьютер или арендовать?
d. Предположим, что после 3 лет деятельности вы сможете продать службу, как отдельный бизнес в среднем за 350 тыс. долларов. Какому ежегодному проценту прироста соответствует полученный вами доход?
e. Четко сформулируйте любые дополнительные допущения, которые вам потребуется сделать.

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

Задача 2. Фермер может выращивать либо кукурузу, либо соевые бобы. Вероятность того, что цены на будущий урожай этих культур повысятся, останутся на том же уровне или понизятся, равна соответственно 0,25, 0,30 и 0,45. Если цены возрастут, урожай кукурузы даст 30 000 долл. чистого дохода, а урожай соевых бобов — 10 000 долл. Если цены останутся неизменными, фермер лишь покроет расходы. Но если цены станут ниже, урожай кукурузы и соевых бобов приведет к потерям в 35 000 и 5 000 долл. соответственно. Постройте дерево решений. Какую культуру следует выращивать фермеру? Каково ожидаемое значение его прибыли?

Дерево решений в задаче фермера (Excel)

Задача 3. Предприятие рассматривает варианты капитальных вложений. Первый вариант предусматривает строительство нового цеха для увеличения объема выпуска продукции стоимостью М1 = 500 млн. руб. При этом варианте возможны большой спрос (годовой доход в размере R1 = 230 млн. руб. в течение 5 последующих лет) с вероятностью p1 = 0,7 и низкий спрос (ежегодные убытки R2 = 90 млн. руб. с вероятностью p2 = 0,3.
Второй вариант предусматривает создание нового предприятия для выпуска новой продукции Стоимостью М1 = 700 млн. руб. При этом варианте возможны большой спрос (годовой доход в размере R1 = 450 млн. руб. в течение 5 последующих лет) с вероятностью p1 = 0,6 и низкий спрос (ежегодные убытки R2 = 150 млн. руб. с вероятностью p2 = 0,4.
При третьем варианте предлагается отложить инвестиции на 1 год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью p1 = 0,8 и p2 = 0,2 соответственно. В случае позитивной информации можно осуществить инвестиции по указанным выше расценкам, в вероятности большого и низкого спроса меняются на p1 = 0,9 и p2 = 0,1 соответственно. Доходы на последующие годы остаются на том же уровне. В случае негативной информации инвестиции осуществляться не будут.
Все расчеты выражены в текущих ценах и не должны дисконтироваться. Нарисовать дерево решений. Определить наиболее эффективную последовательность действий, основываясь на ожидаемых доходах.

Какова ожидаемая стоимостная оценка наилучшего решения?

Дерево решений в задаче капиталовложений

Задача 4. Рассматривается проект покупки доли (пакета акций) в инвестиционном проекте. Пакет стоит 7 млн., и по завершению проект принесет доход 12 млн. с вероятностью 0,6 или ничего с вероятностью 0,4.
При этом через некоторое время будет опубликован прогноз аналитической фирмы относительно успеха этого проекта. Прогноз верен с вероятностью 0,7, то есть, равны 0,7 условные вероятности.
Однако, в случае положительного прогноза пакет порождает до 10,6 млн., а в случае отрицательного подешевеет до 3,4 млн. Требуется составить стратегию действий: покупать ли долю, или ждать прогноза, и совершать ли покупку при том или ином результате прогноза.

Задача покупки акций

Задача 5. Компания «Большая нефть» хочет знать, стоит ли бурить нефтяную скважину на одном из участков, купленных ранее в перспективном месте. Бурение, проведенное на множестве соседних участков, показало, что перспективы не так уж хороши. Вероятность найти нефть на глубине не больше 400 м составляет около 50%. При этом стоимость бурения составит 1.5 млн., а стоимость нефти, за вычетом всех расходов, кроме расходов на бурение, составит 6 млн. Если нефть не найдена на малой глубине, не исключена возможность найти ее при более глубоком бурении. Расходы на бурение, вероятность найти нефть и приведенная стоимость нефти для этих случаев даны в таблице.
a. Постройте дерево решений, показывающее последовательные решения о разработке скважины, которые должна принять компания «Большая нефть». На какую среднюю прибыль компания может рассчитывать?
b. Скважину какой глубины нужно быть готовыми пробурить? (Стоит ли остановиться при достижении определенной глубины, или бурить до предельной глубины?)
c. Какова вероятность найти нефть при бурении (при необходимости) до выбранной вами предельной глубины? Какова полная вероятность найти нефть при готовности бурить до 1500 м?

Дерево решений для нефтедобычи

Примеры по ЭМММ бесплатно

Содержание > Процедуры > Анализ

Деревья классификации

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

Смотрите обучающее видео по  теме  «Деревья классификации»

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

Содержание:

Для запуска процедуры:

1. Выберите зависимую переменную — просто перетащите ее из структуры.  Зависимая переменная может быть Альтернативной или Числовой.
2. Выберите независимые переменные — перетащите их из структуры  Независимые переменные могут быть Альтернативными, Поливариантыми или Числовыми. Так же вы можете в качестве переменной выбрать отдельное значение любой переменной (оно будет рассматриваться как бинарная переменная). Если Вы Выбрали Поливариантную переменную, то обьемы выборки, стоящие за каждым узлом дерева могут быть указаны не совсем корректно — поскольку количество ответов будет превышать количество ответивших. Поэтому, возможно вместо поливариантной переменной лучше выбрать несколько ее ключевых значений.
3. Настройте «Расчеты: 

  • Пропуски по зависимой переменной — нужно ли при построении дерева учитывать пропущенные значения по зависимой переменной.
  • Пропуски по независимым переменным  —  нужно ли при построении дерева учитывать пропущенные значения по независимым переменным.
  • Первая переменная фиксирована — Программа сама решает, какие переменные из независимых нужно взять, чтобы построить дерево и какая из них должны быть первой. Но Если отметить этот пункт, то первая независимая переменная будет обязательно включена в дерево, причем она будет в качестве первого основания классификации.
  • Критерий (основание сравнения) — на основании какого параметра программа сравнивает группы (узлы).
    • Если Вы выбрали в качестве зависимой Альтернативную переменную, то нужно использовать критерий Хи-квадрат, а основанием сравнения групп будут доли (проценты). Если же Вы выбрали в качестве зависимой Числовую переменную — то Вы можете выбрать критерий сравнения:
    • Коэффициент Эта эффективен, если зависимая переменная имеет распределение близкое к нормальному. В этом случае сравнение групп будет осуществляться с помощью средних. 
    • Медианный критерий можно использовать если распределение сильно отличается от нормального и средние величины становятся абстрактны. В этом случае сравнение груп будет осуществляться при помощи медианы. 
    • Критерий Крускала-Уоллиса — можно использовать подобно медианному, когда распределение сильно отличается от нормального. В отличие от Медианного критерия здесь в качестве основания сравнения будут использоваться средние ранги. 
  • Минимально узел-ОТЕЦ — узел дерева какого объема еще доступен для расщепления. Так, если указан узел-ОТЕЦ равный 100, то узлы меньшего объема уже будут конечными узлами дерева, поскольку они не будут разделяться. Узлы же больше 100 программа возможно будет разделять на меньшие. Чем больше анализируемый объем данных, тем более крупные группы стоит рассматривать в качестве узлов.
  • Минимально узел-СЫН —  какого объема минимально должны быть конечные (терминальные) узлы дерева. Программа старается объединять значения исходных переменных так, чтобы не было маленьких узлов, меньших, чем указано в этом пункте.

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

  • Макс. уровней дерева — сколько уровней максимально может иметь дерево. При больших выборках и небольших значениях узлов ОТЕЦ и СЫН, дерево может оказаться очень объемным. С помощью этого параметра вы можете ограничить его рост. 
  • Макс. ошибка критерия —  максимальная вероятность ошибки (значимость), при которой различия между узлами считаются статистически обоснованными. Если различия между узлами слишком малы, то данное разделение признается необоснованным и не учитывается при построении дерева. Ошибка не учитывается только  в случае фиксированной первой переменной- она будет включена в дерево в любом случае. Рекомендуемая ошибка — от 0,05 до 0,10.

4. После выбора настроек нажимайте [Пересчитать].

Содержание

Алгоритм построения дерева

    При построении дерева используется алгоритм CHAID. Программа  группирует значения независимых переменных таким образом, чтобы различия между итоговыми группами были максимальными, при этом группы были достаточно большими, для возможности дальнейшего разделения.
    На первом уровне программа берет либо фиксированную переменную, или ту, которая максимально дифференцирует зависимую переменную  (что определяется при помощи  критерия(см. ниже).  Далее, если группы, образующие выбранную переменную позволяют (превышают минимально узел-ОТЕЦ), то программа повторяет разделение, выбирая каждый раз максимально дифференцирующую переменную для каждой группы. Разделение происходит до тех пор, пока это позволяют объемы групп (узел-ОТЕЦ) и пока различия между группами признаются статистически обоснованными по макс. ошибке критерия. 
    В качестве критерия при использовании средних применяется коэффициент Eta,  значимость которого определяется при помощи F-критерия Фишера. На каждом уровне программа берет ту независимую переменную,  у которой коэффициент Eta  с зависимой переменной является максимальным. Если средние не используются, то берется критерий Хи-квадрат. На каждом уровне программа берет ту независимую переменную, у которой Хи-квадрат, поделенный на количество степеней свободы (DF) является наибольшим. Если вероятность ошибки выбранного разделения превышает максимальную  ошибку критерия, то данная переменная не учитывается.

Содержание

Оценка результатов

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

Оно рассчитывается как отклонение каждого индивидуального значения от среднего в каждом терминальном (конечном узле). Итоговое стандартное отклонение стоит сравнить со стандартным отклонением в первом (верхнем) узле дерева*. Чем меньше итоговое стандартное отклонение по сравнению с начальным, тем более точно при помощи дерева можно прогнозировать значения зависимой переменной. Качество улучшения можно выразить в процентах (Итоговое стандартное отклонение-Начальное стандартное отклонение)/Начальное стандартное отклонение*100%. Данный показатель покажет насколько % уменьшается ошибка прогнозирования.
    В случае, когда вы не используете средние, программа приведет под деревом таблицу классификации, из которой можно узнать, какие прогнозы может построить программа относительно наблюдаемых объектов. Каждый наблюдаемый объект программа  попытается классифицировать, используя конечные листы дерева, полагая, что любой объект, входящий в конечный лист, равен значению, имеющему максимальную долю в данном листе (выделена серым фоном). Если программа правильно классифицирует объект, то наблюдаемое и ожидаемое значение у него будут совпадать. Если программа классифицирует неправильно, то наблюдаемое и ожидаемое значение будут различаться.Интегральным классификатором будет  процент правильно классифицированных объектов.  Его нужно сравнивать с наибольшей долей в первом(начальном) узле*. Качество улучшения можно выразить в процентах:  %Правильной классификации-Наибольший% в первом узле. Данный показатель покажет насколько % улучшается прогнозирование. Стоит иметь ввиду, что существенно ошибка прогнозирования может уменьшиться в том случае, если изначальное распределение  в первомузле близко к равномерному. В бинарном случае это 50 на 50. Если изначальное распределение 90 на 10, то очень сложно увеличить процент правильной классификации. Поэтому иногда, при достаточно больших выборках, проводят предварительное выравнивание выборок — удаляют из большей выборки случайные объекты, так чтобы ее объем сравнялся с меньшей выборкой.  Сделать это можно с помощью процедуры «Преобразовать/Выровнять группы». Кроме того, алгоритм CHAID нацелен не на увеличение % правильной классификации (это побочный эффект), а на максимальную дифференциацию распределения в узлах.
* Примечание: поскольку по некоторым переменным часть данных может быть невалидна, то фактически берется не значение, указанное в первом узле,  а  то значение, которое бы было в первом узле, если оставить только данные, валидные по всем переменным.

Содержание

Отображение результатов

  • Способ отображения вы можете выбрать  на вкладке «Отображение» в параметрах дерева. Дерево может быть отображено в виде ветвящихся таблиц или диаграмм.  В случае использования средних диаграммы пока не предусмотрены — выбирайте способ отображения — таблица.  В случае не использования средних, на наш взгляд наиболее эффективной является круговая диаграмма.
  • Диаграмма пропорциональна частоте- если отметить этот пункт, то круг или прямоугольник диаграммы будет пропорционален объему узла, что очень наглядно позволит увидеть как уменьшаются группы с каждым уровнем дерева. Однако, в случае использования Поливариантных переменных, отмечать этот пункт не рекомендуется — суммы  могут быть больше чем 100% и размер диаграммы может выйти за пределы отведенного места. 
  • Шрифт текста в узлах — определяет шрифт, которым наносятся надписи на диаграмме. Учитывая, что некоторые подписи могут быть слишком длинными — крупный шрифт не рекомендуется.
  • Ширина бокса таблицы — какой ширины будет узел, отображающий таблицу. Если зависимая переменная содержит слишком длинные формулировки значений — они будут обрезаны.
  • Ширина бокса диаграммы — в данном случае сторона квадрата, выделяемого под диаграмму.
  • Максимально строк — сколько максимально строк может отводиться на название узла дерева. Если в узле объединено много исходных значений и значения имеют длинные формулировки, то название узла будет обрезанным. Если вы видите в названии узла троеточие, то значит места не хватило для полного названия. В этом случае возможно стоит увеличить максимальное количество строк.
  • Масштаб — выбор масштаба изображения. К сожалению, при масштабировании сильно уменьшается качество картинки, поэтому, возможно масштабирование лучше производить в других программах, скопировав туда изображение.

У каждого узла дерева есть два активных элемента:

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

Содержание

Копирование результатов

  • С помощью основной кнопки [Копировать], расположенной вверху, в строке быстрого вызова основных процедур программы, вы можете скопировать изображение в формате Windows Meta file (WMF). Это удобно при вставке в другие программы Windows, работающие с этим форматом — Microsoft Word, Excel, Power Point и другие. При этом, при масштабировании картинки, качество ее не будет   существенно теряться, поскольку картинка будет перерисовываться заново в новом масштабе.
  • Для тех программ, которые не поддерживают формат  WMF и для публикации в сети Internet, внизу окна есть кнопка [Копировать .BMP]. В этом случае программа копирует изображение как картинку (bitmap), которая может быть вставлена в любой графический редактор (например Paint) и сохранена в нужном формате (.bmp. .jpg, .png и т.д.).
  • Чтобы скопировать в буфер обмена Таблицу классификации, используйте кнопку [Копировать таблицу] внизу окна.

 Содержание

Сохранение результатов классификации

Вкладка «Сохранить»в настройках процедуры позволяет сохранить результаты классификации.

  • Что сохраняем?  — Если качество классификации вас устраивает, то Вы можете сохранить предсказанные значения зависимой переменной в виде новой переменной. 
    • Выбор опции «Все предсказанные значения» приведет к тому, что в новой переменной будут определены только предсказанные значения. 
    • Если же выбрать вариант «Предсказания для пропусков», то в новой переменной будут сохраняться известные значения, за исключением пропусков, где будут вычисляться теоретические значения. Использование этой опции позволяет восстановить отсутствующие данные по зависимой переменной, при условии наличия данных по независимым переменным.

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

    • «Итоговая классификация» — сохраняет в качестве новой переменной итоговые узлы(листы) дерева. С помощью этой переменной можно в дальнейшем получить тот же результат классификации используя Двухмерное распределение.
  • Пропусками считать — если процедура используется для восстановления пропусков по зависимой переменной, здесь вы можете уточнить, что считается пропусками — пустые ячейки и(или) значения, помеченные как пропущенные.
  • После установки настроек нажмите кнопку [Сохранить]. Программа создаст новую переменную (в конце структуры) и рассчитает по ней данные. Тип данных будет зависеть от выбранного Критерия (основания сравенения). 
    • Если выбран Хи-квадрат (для Альтернативных переменных), то будут сохранятся коды предсказанных значений (номера вариантов ответа), то есть те значения, которые имеют наибольшую частоту в каждом узле.
    • Если выбран коэффициент Эта, (для Числовых переменных), то будут сохраняться средние для каждого узла. 
    • Если выбран Медианный критерий, (для Числовых переменных), то будут сохраняться медианы  для каждого узла. 
    • Если выбран критерий Крускала-Уоллиса, то то будут сохраняться средние для каждого узла, хотя возможно это не очень эффективно. Вместе с тем, средние ранги, на основе которых действует этот критерий, сохранять нет смысла — они не могут заменить пропущенные значения.

Содержание

.

.

Множество единичных критериев крайне важно сгруппиро­вать и структуризовать в виде дерева критериев. Как правило, дерево содержитот трех до шести уровней.

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

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, всœе критерии классифицируются на два типа:

– единичные критерии;

– комплексные критерии.

Принципиальное отличие комплексных критериев от единичных заключаются в их измерении. Единичные из­меряются в физических единицах, их значения являются основой для определœения всœех комплексных. Все комплексные критерии измеряются в относительных единицах в интервале от нуля до единицы. Значения, близкие к нулю, указывают на низкую полезность объекта по данному комплексному критерию и, напротив — значения, близкие к единице, – на высокую полезность.

Дерево критериев отражает перечень единичных и комплек­сных критериев и их логическую взаимосвязь. Для ин­тегральной оценки объектов дерево должно быть дополнено функциональными связями между единичными и комплексны­ми критериями, ᴛ.ᴇ. должны быть заданы операторы агрегиро­вания всœех комплексных показателœей по дереву и указана вся необходимая для агрегирования информация. Следовательно, При построении дерева критериев единичные и комплек­сные критерии идентифицируются индексами, определяющими их положение в структуре.

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

Ниже приведен пример дерева критериев для задачи выбора мобильного телœефона.

Курсивом выделœены единичные критерии.

К – обобщенный критерий выбора

К1цена телœефона

К2 – качество телœефона (потребительские свойство)

К2,1 – функциональные критерии

К2,1,1 – желательные функции

К2,1,1,1 – съемка

К2,1,1,1,1видеокамера

К2,1,1,1,2фотокамера

К2,1,1,1радиоприемник

К2,1,1,1громкая связь

К2,1,2 – возможные функции

К2,1,2,1будильник

К2,1,2,2игры

К2,2 – эргономические критерии

К2,2,1размер дисплея

К2,2,2тип клавиатуры

К2,2,3размеры корпуса


Читайте также

  • — Построение дерева критериев

    Этапы решения МКЗ с многоуровневой системой критериев В практических задачах число критериев может достигать нескольких десятков. Применять функции полезности и проверять различные свойства типа независимости по полезности или по предпочтению даже для… [читать подробнее].

  • Добавить комментарий

    Закрыть меню