Древо решений - Decision tree
А Древо решений это поддержка при принятии решения инструмент, который использует древовидный модель решений и их возможных последствий, в том числе шанс результаты событий, затраты на ресурсы и полезность. Это один из способов отобразить алгоритм который содержит только условные операторы управления.
Деревья решений обычно используются в исследование операций особенно в анализ решений, чтобы помочь определить стратегию, которая, скорее всего, принесет Цель, но также являются популярным инструментом в машинное обучение.
Обзор
Дерево решений - это блок-схема -подобная структура, в которой каждый внутренний узел представляет «тест» на атрибуте (например, выпадает ли подбрасывание монеты орлом или решкой), каждая ветвь представляет результат теста, а каждый листовой узел представляет метку класса (решение, принимаемое после вычисление всех атрибутов). Пути от корня к листу представляют собой правила классификации.
В анализ решений, дерево решений и тесно связанные диаграмма влияния используются как визуальный и аналитический инструмент поддержки принятия решений, где ожидаемые значения (или же ожидаемая полезность ) конкурирующих альтернатив.
Дерево решений состоит из узлов трех типов:[1]
- Узлы принятия решения - обычно представлены квадратами
- Узлы вероятности - обычно представлены кружками
- Конечные узлы - обычно представлены треугольниками
Деревья решений обычно используются в исследование операций и управление операциями. Если на практике решения должны приниматься онлайн без отзыва при неполных знаниях, дерево решений должно сопровождаться вероятность модель как лучшая модель выбора или онлайн-модель выбора алгоритм. Еще одно использование деревьев решений - это описательное средство для вычисления условные вероятности.
Деревья решений, диаграммы влияния, служебные функции, и другие анализ решений инструменты и методы преподаются студентам бакалавриата в школах бизнеса, экономики здравоохранения и общественного здравоохранения и являются примерами операционных исследований или Наука управления методы.
Строительные блоки дерева решений
Элементы дерева решений
Нарисованное слева направо дерево решений имеет только узлы пакетов (пути разделения), но не узлы приемников (сходящиеся пути). Поэтому при ручном использовании они могут вырасти очень большими, и их часто трудно полностью нарисовать вручную. Традиционно деревья решений создавались вручную - как показывает приведенный в стороне пример - хотя все чаще используется специализированное программное обеспечение.
Правила принятия решений
Дерево решений может быть линеаризованный в правила принятия решений,[2] где результатом является содержимое конечного узла, а условия на пути образуют соединение в предложении if. В общем, правила имеют вид:
- если condition1 и condition2 и condition3 тогда исход.
Правила принятия решений могут быть сгенерированы путем построения правила ассоциации с целевой переменной справа. Они также могут обозначать временный или же причинный связи.[3]
Дерево решений с использованием символов блок-схемы
Обычно дерево решений строится с использованием блок-схема символы, так как многим их легче читать и понимать.
Пример анализа
Анализ может учитывать факторы, принимающие решения (например, компании) предпочтение или же вспомогательная функция, Например:
Основная интерпретация в этой ситуации состоит в том, что компания предпочитает риск и выплаты B при реалистичных коэффициентах предпочтения риска (более 400 тыс. Долларов - в этом диапазоне неприятия риска компании потребуется смоделировать третью стратегию, «Ни A, ни B») .
Другой пример, обычно используемый в исследование операций Курсы - это распределение спасателей на пляжах (также известный как «Life's a Beach»).[4] Пример описывает два пляжа со спасателями, которые должны быть распределены на каждом пляже. Есть максимальный бюджет B которые могут быть распределены между двумя пляжами (в сумме), и, используя таблицу предельной прибыли, аналитики могут решить, сколько спасателей выделить на каждый пляж.
| Спасатели на каждом пляже | Всего предотвращено утопление, пляж №1 | Всего предотвращено утопление, пляж №2 |
|---|---|---|
| 1 | 3 | 1 |
| 2 | 0 | 4 |
В этом примере можно нарисовать дерево решений, чтобы проиллюстрировать принципы убывающая отдача на пляже №1.
Дерево решений показывает, что при последовательном распределении спасателей размещение первого спасателя на пляже №1 будет оптимальным, если есть бюджет только на 1 спасателя. Но если есть бюджет на двух охранников, то размещение обоих на пляже №2 предотвратит большее число случаев утопления.
Диаграмма влияния
Большая часть информации в дереве решений может быть представлена более компактно в виде диаграмма влияния, акцентируя внимание на вопросах и отношениях между событиями.
Индукция правила ассоциации
Деревья решений также можно рассматривать как генеративные модели правил индукции по эмпирическим данным. Затем оптимальное дерево решений определяется как дерево, которое учитывает большую часть данных, минимизируя при этом количество уровней (или «вопросов»).[5] Было разработано несколько алгоритмов для генерации таких оптимальных деревьев, например ID3 /4/5,[6] CLS, АССИСТЕНТ и КОРЗИНА.
Преимущества и недостатки
Среди инструментов поддержки принятия решений деревья решений (и диаграммы влияния ) имеют несколько преимуществ. Деревья решений:
- Просты для понимания и интерпретации. Люди смогут понять модели дерева решений после краткого объяснения.
- Имеют ценность даже при небольшом количестве достоверных данных. Важная информация может быть получена на основе описания экспертами ситуации (ее альтернатив, вероятностей и затрат) и их предпочтений в отношении результатов.
- Помогите определить худшие, лучшие и ожидаемые значения для различных сценариев.
- Использовать белая коробка модель. Если данный результат предоставляется моделью.
- Можно комбинировать с другими методами принятия решений.
Недостатки деревьев решений:
- Они нестабильны, что означает, что небольшое изменение данных может привести к значительному изменению структуры оптимального дерева решений.
- Часто они относительно неточны. Многие другие предикторы лучше работают с аналогичными данными. Это можно исправить, заменив одно дерево решений на случайный лес деревьев решений, но случайный лес не так легко интерпретировать, как одно дерево решений.
- Для данных, включающих категориальные переменные с разным количеством уровней, получение информации в деревьях решений смещен в пользу атрибутов с большим количеством уровней.[7]
- Расчеты могут быть очень сложными, особенно если многие значения являются неопределенными и / или если многие результаты связаны.
Смотрите также
Рекомендации
- ^ Камински, Б .; Якубчик, М .; Шуфель, П. (2017). «Структура для анализа чувствительности деревьев решений». Центральноевропейский журнал исследований операций. 26 (1): 135–159. Дои:10.1007 / s10100-017-0479-6. ЧВК 5767274. PMID 29375266.
- ^ Куинлан, Дж. Р. (1987). «Упрощение деревьев решений». Международный журнал человеко-машинных исследований. 27 (3): 221–234. CiteSeerX 10.1.1.18.4267. Дои:10.1016 / S0020-7373 (87) 80053-6.
- ^ К. Карими и Х. Дж. Гамильтон (2011 г.) "Генерация и интерпретация временных правил принятия решений ", Международный журнал компьютерных информационных систем и приложений промышленного управления, том 3
- ^ Вагнер, Харви М. (1 сентября 1975 г.). Принципы исследования операций: в применении к управленческим решениям (2-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice Hall. ISBN 9780137095926.
- ^ Р. Куинлан, «Изучение эффективных процедур классификации», Машинное обучение: подход искусственного интеллекта, Михальски, Карбонелл и Митчелл (ред.), Морган Кауфманн, 1983, стр. 463–482. Дои:10.1007/978-3-662-12405-5_15
- ^ Утгофф, П. Э. (1989). Инкрементальная индукция деревьев решений. Машинное обучение, 4 (2), 161–186. Дои:10.1023 / А: 1022699900025
- ^ Deng, H .; Runger, G .; Тув, Э. (2011). Меры смещения важности для многозначных атрибутов и решений. Материалы 21-й Международной конференции по искусственным нейронным сетям (ICANN).