A дерево решений - это инструмент поддержки принятия решений, который использует древовидную модель решений и их возможных последствий, включая случайные результаты событий, затраты на ресурсы и утилита. Это один из способов отобразить алгоритм , который содержит только условные операторы управления.
Деревья решений обычно используются в исследовании операций, в частности в анализе решений, чтобы помочь определить стратегию, которая с наибольшей вероятностью приведет к цели, но также являются популярным инструментом в машинном обучении.
Дерево решений - это структура, подобная блок-схеме, в которой каждый внутренний узел представляет «тест» на атрибут (например, выпадает ли подбрасывание монеты орлом или решкой), каждая ветвь представляет результат теста, и каждый листовой узел представляет метку класса (решение принимается после вычисления всех атрибутов). Пути от корня к листу представляют собой правила классификации.
В анализе решений дерево решений и тесно связанная диаграмма влияния используются в качестве визуального и аналитического инструмента поддержки принятия решений, где ожидаемые значения (или ожидаемая полезность ) конкурирующих альтернатив.
Дерево решений состоит из трех типов узлов:
Деревья решений обычно используются в исследовании операций и управлении операциями. Если на практике решения должны приниматься в интерактивном режиме без отзыва при неполных знаниях, дерево решений должно сопровождаться моделью вероятности в качестве модели наилучшего выбора или модели онлайн-выбора алгоритмом. Другое использование деревьев решений - это описательное средство для расчета условных вероятностей.
деревьев решений, диаграмм влияния, функций полезности и других анализа решений инструменты и методы преподаются студентам бакалавриата в школах бизнеса, экономики здравоохранения и общественного здравоохранения и являются примерами методов исследования операций или методов управления.
.
Нарисованное слева направо дерево решений имеет только узлы пакетной передачи (пути разделения), но не узлы приемников (сходящиеся пути). Поэтому при ручном использовании они могут вырасти очень большими, и их часто трудно полностью нарисовать вручную. Традиционно деревья решений создавались вручную - как показывает приведенный в стороне пример - хотя все чаще используется специализированное программное обеспечение.
Дерево решений может быть линеаризовано в правила принятия решений, где результатом является содержимое конечного узла и условия по пути образуют союз в предложении if. В общем, правила имеют вид:
Правила принятия решений могут быть сгенерированы путем построения правил связывания с целевой переменной справа. Они также могут обозначать временные или причинно-следственные отношения.
Обычно дерево решений строится с использованием блок-схемы символы, так как многим их легче читать и понимать.
Анализ может учитывать предпочтения лица, принимающего решения (например, компании) или функцию полезности, например:
Базовая Интерпретация в этой ситуации состоит в том, что компания предпочитает риск и выплаты B при реалистичных коэффициентах предпочтения риска (более 400 тыс. долларов - в этом диапазоне неприятия риска компании потребуется смоделировать третью стратегию, «Ни A, ни B»).
Другой пример, обычно используемый в курсах исследования операций, - это размещение спасателей на пляжах (также известный как «Life's a Beach»). Пример описывает два пляжа со спасателями, которые должны быть распределены на каждом пляже. Существует максимальный бюджет B, который может быть распределен между двумя пляжами (в сумме), и, используя таблицу предельных доходов, аналитики могут решить, сколько спасателей выделить на каждый пляж.
Спасатели на каждом пляже | Всего предотвращено утопление, пляж №1 | Утопления предотвращены в целом, пляж №2 |
---|---|---|
1 | 3 | 1 |
2 | 0 | 4 |
В этом примере можно нарисовать дерево решений для иллюстрации принципы убывающей доходности на пляже №1.
Дерево решений на пляжеДерево решений показывает, что при последовательном распределении спасателей размещение первого спасателя на пляже №1 будет оптимальным, если есть бюджет только на 1 спасателя. Но если есть бюджет на двух охранников, то размещение обоих на пляже №2 предотвратит большее число случаев утопления.
СпасателиБольшая часть информации в дереве решений может быть представлена более компактно в виде диаграммы влияния, сосредоточив внимание на проблемах и взаимосвязях между событиями.
Прямоугольник слева представляет решение, овалы представляют действия, а ромбик представляет результаты.Деревья решений также можно рассматривать как генеративные модели правил индукции по эмпирическим данным. Затем оптимальное дерево решений определяется как дерево, которое учитывает большую часть данных, минимизируя при этом количество уровней (или «вопросов»). Было разработано несколько алгоритмов для создания таких оптимальных деревьев, таких как ID3 / 4/5, CLS, ASSISTANT и CART.
Среди инструментов поддержки принятия решений деревья решений (и диаграммы влияния ) имеют несколько преимуществ. Деревья решений:
Недостатки деревьев решений:
На Викискладе есть материалы, связанные с диаграммами решений. |