Дерево принятия решений альтернатива

Лекция 1. Основные положения теории принятия решений

Вводятся основные понятия теории принятия решений: альтернатива, критерий, ресурсы и др. Приводится схема принятия решений. Описываются основные этапы принятия решений: формулирование проблемы, выявление целей, формирование критериев, генерирование альтернатив и их особенности. Приводится список основных терминов.

1.1. Определения

Основные понятия принятия решений проиллюстрируем на примере древнейшего Соломонова решения.

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

Царь велел принести меч и сказал: «Поделите ребёнка на две части и отдайте им по половине». Первая женщина воскликнула: «Не убивайте его, отдайте ей». А вторая сказала: «Пусть поделят, чтобы не достался ни тебе, ни мне». Тогда царь сказал: «Отдайте ребенка первой женщине, она его мать!» Он полагал, что настоящая мать не допустит гибели сына даже путем потери его для себя.

Какие варианты принятия решения были у царя Соломона?

• отдать ребёнка первой женщине (x₁);
• отдать ребенка второй женщине (x₂);
• не давать никому (x₃);
• получить дополнительную информацию для принятия одного из первых двух решений (x₄).

Можно считать, что при случайном выборе (из первых двух вариантов) вероятность правильного решения составляет 0,5. Царь выбрал двухступенчатый способ принятия решения (рис. 1). Вначале он выбрал промежуточный вариант x₄. На основе полученной в нём информации, характеризующей психологию матери, он выбрал достоверный вариантx₁. Определение. Варианты принятия решения на каждом шаге называются альтернативами. В примере исходное множество альтернатив разбито на 2 подмножества:и, где верхние индексы у вариантов решения обозначают шаг принятия решения. Альтернативы, сопоставленные висячим вершинам дерева, являются окончательными вариантами принятия решения. Альтернативыx₁,x₂называютсяповторяющимися. Альтернативах₄называетсяпромежуточной. Определение. Признак, применяемый для сравнения альтернатив и выбора лучшей из них, называется критерием оценки альтернатив. В примере под критерием Y₁понимается «материнский инстинкт», а под критерием Y₂– «родственные узы». Моделью всевозможных вариантов выбора альтернатив является дерево решений. Многошаговая процедура принятия решения описываетсяпутем в дереве решений. В примере выбранным является путь. Графически принятие решения в описанном примере выражается следующим образом. Рис. 1. Дерево определения судьбы ребёнка В системном анализе система, в функционировании которой проявилось некоторое нежелательное явление, формулируемое как проблема, называется проблемосодержащей (в примере – это две женщины, обратившиеся к царю). Система, предназначенная для решения проблемы (в примере царь), называется проблеморазрешающей. В теории управления проблемосодержащая система называется объектом управления, а система, разрешающая проблему, субъектом управления. Определение. Принципиальной особенностью системы принятия решения, включающей проблемосодержащую и проблеморазрешающую подсистемы, является наличие человека в составе субъекта управления. Человек в этом случае называется лицом, принимающим решение (ЛПР). Различного рода системы автоматизации, в которых решающую роль играет человек, получили название автоматизированные системы управления (АСУ). Они делятся на информационно-справочныеиинформационно-советующие. Первые основываются на базах данных и базах знаний. Вторые дополнительно включают системы поддержки принятия решений. Их особенностями являются наличие вычислительных блоков для оценки альтернатив, блоков логического вывода в экспертных системах и механизма распределения функций принятия решения между человеком и ЭВМ посредством диалоговой процедуры.

Источник

Альтернативное дерево решений — Alternating decision tree

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

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

• 1 История
• 2 Мотивация
• 3 Древовидная структура альтернативных решений
  • 3.1 Пример

  История

  ADTrees были представлены Йоавом Фройндом и Лью Мэйсоном. Однако представленный алгоритм содержал несколько типографских ошибок. Разъяснения и оптимизации были позже представлены Бернхардом Пфарингером, Джеффри Холмсом и Ричардом Киркби. Реализации доступны в Weka и JBoost.

  Мотивация

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

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

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

  Структура дерева альтернативных решений

  Дерево альтернативных решений состоит из узлов решений и узлов прогнозирования. Узлы принятия решений определяют условие предиката. Узлы прогноза содержат одно число. ADTrees всегда имеют узлы прогнозирования как корневые, так и конечные. Экземпляр классифицируется ADTree, следуя всем путям, для которых все узлы решения истинны, и суммируя все пройденные узлы прогнозирования. Это отличается от бинарных деревьев классификации, таких как CART (Дерево классификации и регрессии ) или C4.5, в которых экземпляр следует только по одному пути через дерево.

  Пример

  Следующее дерево было построено с использованием JBoost в наборе данных спамба (доступно в репозитории машинного обучения UCI). В этом примере спам кодируется как 1, а обычная электронная почта — как -1.

  

  В следующей таблице содержится часть информации для одного экземпляра.

  Классифицируемый экземпляр

  Feature	Значение
  char_freq_bang	0,08
  word_freq_hp	0,4 ​​
  capital_run_length_longest	4
  char_freq_dollar	0
  word_freq_remove	0.9
  word_freq_george	0
  Другие функции	.

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

  Основным элементом алгоритма ADTree является правило. Одно правило состоит из предварительного условия, условия и двух оценок. Условие — это предикат формы «значение атрибута ». Предусловие — это просто логическое соединение условий. Оценка правила включает пару вложенных операторов if:

  1 if(предварительное условие) 2 if (условие) 3 return score_one 4 else 5 return score_two 6 end if 7 else 8 return 0 9 end if

  Алгоритм также требует нескольких вспомогательных функций:

  • W + (c) (c)> возвращает сумму весов всех положительно помеченных примеров, которые удовлетворяют предикату c
  • W — (c) (c)> возвращает сумму весов всех отрицательно помеченных примеров, которые удовлетворяют предикату c
  • W (c) = W + (c) + W — (c) (c) + W _ (c)> возвращает сумму веса всех примеров, удовлетворяющих предикату c

  Алгоритм выглядит следующим образом:

  1 function ad_tree 2 input Набор из m обучающих экземпляров 3 4 w i = 1 / m для всех i 5 $a\; =\; 1\; 2\; ln\; W\; +\; (true)\; W\; -\; (true)\; >\; >\; (true)>\; (true)>>>$ 6 R 0 = правило с оценками а и 0, предварительным условием «истина» и условием «истина». 7 $P\; =\; >\; =\; \backslash \; >$ 8 $C\; =\; >\; =>$ набор всех возможных условий 9 для$j\; =\; 1\dots \; T$10 $p\; \in \; P,\; c\; \in \; C\; >,\; c\; \backslash \; in\; >>$получить значения, которые минимизируют $z\; =\; 2\; (W\; +\; (p\; \wedge \; c)\; W\; -\; (\; п\; \wedge \; с)\; +\; W\; +\; (п\; \wedge \; \neg \; c)\; W\; -\; (п\; \wedge \; \neg \; c))\; +\; W\; (\neg \; p)\; (p\; \backslash \; wedge\; c)\; W\; \_\; (p\; \backslash \; wedge\; c)>>\; +\; (p\; \backslash \; wedge\; \backslash \; neg\; c)\; W\; \_\; (p\; \backslash \; wedge\; \backslash \; neg\; c)>>\; \backslash \; right)\; +\; W\; (\; \backslash \; neg\; p)>$ 11 $P\; +\; =\; p\; \wedge \; c\; +\; p\; \wedge \; \neg \; c\; >\; +\; =\; p\; \backslash \; wedge\; c\; +\; p\; \backslash \; wedge\; \backslash \; neg\; c>$ 12 $a\; 1\; =\; 1\; 2\; ln\; W\; +\; (p\; \wedge \; c)\; +\; 1\; W\; -\; (p\; \wedge \; c)\; +\; 1\; =\; >\; >\; (p\; \backslash \; wedge\; c)\; +1>\; (p\; \backslash \; wedge\; c)\; +1>>>$ 13  14 R j = новое правило с предусловием p, условием c и весами a 1 и a 2 15  16 конец для 17 return набор R j

  Набор P >> увеличивается на два предварительных условия в каждой итерации, и можно получить древовидная структура набора правил с указанием предусловия, которое используется в каждом последующем правиле.

  Эмпирические результаты

  Рисунок 6 в исходной статье демонстрирует, что ADTrees обычно столь же устойчивы, как усиленные деревья решений и увеличенные пни принятия решений. Как правило, эквивалентной точности можно добиться с помощью гораздо более простой древовидной структуры, чем алгоритмы рекурсивного разделения.

  Ссылки

  Внешние ссылки

  • Введение в Boosting и ADTrees (содержит множество графических примеров чередующихся деревьев решений на практике).
  • Программное обеспечение JBoost, реализующее ADTrees.

  Источник