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

Инструмент поддержки принятия решений

Традиционно деревья решений создавались вручную.

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

Деревья решений обычно используются в исследовании операций , в частности в анализе решений , ^[1] чтобы помочь определить стратегию, которая с наибольшей вероятностью достигнет цели, но также являются популярным инструментом в машинном обучении .

Обзор

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

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

Дерево решений состоит из трех типов узлов: ^[2]

1. Узлы принятия решений – обычно представлены квадратами.
2. Узлы вероятности – обычно представлены кружками
3. Конечные узлы – обычно представлены треугольниками.

Деревья решений обычно используются в исследовании операций и управлении операциями . Если на практике решения должны приниматься онлайн без отзыва в условиях неполного знания, дерево решений должно быть параллельно с вероятностной моделью в качестве модели наилучшего выбора или алгоритма модели онлайн-выбора . ^{[ требуется ссылка ]} Другое применение деревьев решений — в качестве описательного средства для расчета условных вероятностей .

Деревья решений, диаграммы влияния , функции полезности и другие инструменты и методы анализа решений преподаются студентам бакалавриата в школах бизнеса, экономики здравоохранения и общественного здравоохранения и являются примерами методов исследования операций или науки управления . Эти инструменты также используются для прогнозирования решений домовладельцев в обычных и чрезвычайных ситуациях. ^{[3] [4]}

Строительные блоки дерева решений

Элементы дерева принятия решений

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

Правила принятия решений

Дерево решений можно линеаризовать в правила принятия решений , ^[5] где результатом является содержимое листового узла, а условия вдоль пути образуют конъюнкцию в предложении if. В общем случае правила имеют вид:

если условие1 и условие2 и условие3, то результат.

Правила принятия решений могут быть сгенерированы путем построения правил ассоциации с целевой переменной справа. Они также могут обозначать временные или причинно-следственные связи. ^[6]

Дерево решений с использованием символов блок-схемы

Обычно дерево решений рисуется с использованием символов блок-схемы , поскольку многим это проще читать и понимать. Обратите внимание, что в расчете "Proceed" дерева, показанного ниже, есть концептуальная ошибка; ошибка касается расчета "затрат", присужденных в судебном иске.

Пример анализа

Анализ может учитывать предпочтения или функцию полезности лица, принимающего решение (например, компании) , например:

Основная интерпретация в этой ситуации заключается в том, что компания предпочитает риск и выплаты B при реалистичных коэффициентах предпочтения риска (более 400 тыс. долларов — в этом диапазоне неприятия риска компании необходимо будет смоделировать третью стратегию: «Ни A, ни B»).

Другой пример, часто используемый в курсах по исследованию операций , — распределение спасателей на пляжах (также известный как пример «Жизнь — это пляж»). ^[7] В этом примере описываются два пляжа со спасателями, которых нужно распределить на каждом пляже. Существует максимальный бюджет B , который можно распределить между двумя пляжами (в общей сложности), и с помощью таблицы предельной доходности аналитики могут решить, сколько спасателей следует выделить на каждый пляж.

В этом примере можно нарисовать дерево решений, иллюстрирующее принципы убывающей доходности на пляже №1.

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

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

Спасатели

Диаграмма влияния

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

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

Индукция ассоциативного правила

Деревья решений также можно рассматривать как генеративные модели правил индукции из эмпирических данных. Оптимальное дерево решений тогда определяется как дерево, которое учитывает большую часть данных, минимизируя при этом количество уровней (или «вопросов»). ^[8] Было разработано несколько алгоритмов для генерации таких оптимальных деревьев, таких как ID3 /4/5, ^[9] CLS, ASSISTANT и CART.

Преимущества и недостатки

Среди инструментов поддержки принятия решений деревья решений (и диаграммы влияния ) имеют ряд преимуществ. Деревья решений:

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

Недостатки деревьев решений:

• Они нестабильны, то есть небольшое изменение данных может привести к значительному изменению структуры оптимального дерева решений.
• Они часто относительно неточны. Многие другие предикторы работают лучше с похожими данными. Это можно исправить, заменив одно дерево решений случайным лесом деревьев решений, но случайный лес не так легко интерпретировать, как одно дерево решений.
• Для данных, включающих категориальные переменные с различным количеством уровней, прирост информации в деревьях решений смещен в пользу атрибутов с большим количеством уровней. ^[10]
• Расчеты могут оказаться очень сложными, особенно если многие значения неопределенны и/или если многие результаты связаны между собой.

Оптимизация дерева решений

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

Увеличение количества уровней дерева

Точность дерева решений может меняться в зависимости от глубины дерева решений. Во многих случаях листья дерева являются чистыми узлами . ^[11] Когда узел является чистым, это означает, что все данные в этом узле принадлежат к одному классу. ^[12] Например, если классы в наборе данных — «Рак» и «Не рак», листовой узел будет считаться чистым, когда все данные выборки в листовом узле являются частью только одного класса: либо «рак», либо «не рак». Важно отметить, что более глубокое дерево не всегда лучше при оптимизации дерева решений. Более глубокое дерево может отрицательно влиять на время выполнения. Если используется определенный алгоритм классификации, то более глубокое дерево может означать, что время выполнения этого алгоритма классификации значительно замедляется. Существует также вероятность того, что фактический алгоритм, строящий дерево решений, станет значительно медленнее по мере того, как дерево становится глубже. Если используемый алгоритм построения дерева разделяет чистые узлы, то может наблюдаться снижение общей точности классификатора дерева. Иногда углубление в дерево может привести к снижению точности в целом, поэтому очень важно протестировать изменение глубины дерева решений и выбрать глубину, которая дает наилучшие результаты. Подводя итог, обратите внимание на пункты ниже, мы определим число D как глубину дерева.

Возможные преимущества увеличения числа D:

• Точность модели классификации дерева решений увеличивается.

Возможные недостатки увеличения D

•  Проблемы с выполнением
• Снижение точности в целом
• Чистое разделение узлов при углублении может вызвать проблемы.

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

Выбор функций разделения узлов

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

Основные преимущества и недостатки информационного прироста и функции фи

• Одним из основных недостатков прироста информации является то, что признак, который выбирается в качестве следующего узла в дереве, имеет тенденцию иметь больше уникальных значений. ^[13]
• Преимущество информационного прироста заключается в том, что он имеет тенденцию выбирать наиболее влиятельные признаки, которые находятся близко к корню дерева. Это очень хорошая мера для определения релевантности некоторых признаков.
• Функция фи также является хорошим средством для определения релевантности некоторых признаков на основе их «качества».

Это формула функции прироста информации. Формула утверждает, что прирост информации является функцией энтропии узла дерева решений за вычетом энтропии кандидата, разделенного на узел t дерева решений.

${\displaystyle I_{\textrm {gain}}(s)=H(t)-H(s,t)}$

Это формула функции фи. Функция фи максимизируется, когда выбранная функция разделяет выборки таким образом, что производит однородные разделения и имеет примерно одинаковое количество выборок в каждом разделении.

${\displaystyle \Phi (s,t)=(2*P_{L}*P_{R})*Q(s|t)}$

Мы установим D, который является глубиной дерева решений, которое мы строим, на три (D = 3). У нас также есть следующий набор данных образцов рака и нерака и мутационные признаки, которые либо есть, либо нет в образцах. Если образец имеет мутацию признака, то образец положителен для этой мутации, и он будет представлен единицей. Если образец не имеет мутации признака, то образец отрицателен для этой мутации, и он будет представлен нулем.

Подводя итог, C означает рак, а NC означает нерак. Буква M означает мутацию , и если образец имеет определенную мутацию, она будет отображаться в таблице как единица, а в противном случае как ноль.

Теперь мы можем использовать формулы для вычисления значений функции phi и значений прироста информации для каждого M в наборе данных. После того, как все значения будут рассчитаны, можно построить дерево. Первое, что нужно сделать, это выбрать корневой узел. В приросте информации и функции phi мы считаем оптимальным разделением мутацию, которая дает наибольшее значение прироста информации или функции phi. Теперь предположим, что M1 имеет наибольшее значение функции phi, а M4 имеет наибольшее значение прироста информации. Мутация M1 будет корнем нашего дерева функции phi, а M4 будет корнем нашего дерева прироста информации. Вы можете наблюдать корневые узлы ниже

Рисунок 1: Левый узел — корневой узел дерева, которое мы строим, используя функцию фи для разделения узлов. Правый узел — корневой узел дерева, которое мы строим, используя прирост информации для разделения узлов.

Теперь, как только мы выбрали корневой узел, мы можем разделить образцы на две группы в зависимости от того, является ли образец положительным или отрицательным для мутации корневого узла. Группы будут называться группой A и группой B. Например, если мы используем M1 для разделения образцов в корневом узле, мы получим образцы NC2 и C2 в группе A, а остальные образцы NC4, NC3, NC1, C1 в группе B.

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

Полученное дерево с использованием прироста информации для разделения узлов

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

Матрица путаницы прироста информации:

Матрица путаницы функции Фи:

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

Другие методы

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

Оценка дерева решений

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

Давайте рассмотрим матрицу путаницы ниже. Матрица путаницы показывает нам, что построенный классификатор модели дерева решений дал 11 истинно положительных результатов, 1 ложноположительный результат, 45 ложноотрицательных результатов и 105 истинно отрицательных результатов.

Теперь мы вычислим значения точности, чувствительности, специфичности, прецизионности, частоты пропусков, частоты ложных обнаружений и частоты ложных пропусков.

Точность:

${\displaystyle Accuracy=(TP+TN)/(TP+TN+FP+FN)}$

${\displaystyle (11+105)\div 162=71.60\%}$

Чувствительность (TPR – истинно положительный показатель): ^[14]

${\displaystyle TPR=TP/(TP+FN)}$

${\displaystyle (11)\div (11+45)=19.64\%}$

Специфичность (TNR – истинно отрицательный показатель):

${\displaystyle TNR=TN/(TN+FP)}$

${\displaystyle 105\div (105+1)=99.06\%}$

Точность (PPV – положительная прогностическая ценность):

${\displaystyle PPV=TP/(TP+FP)}$

${\displaystyle 11/(11+1)=91.66\%}$

Коэффициент ложноотрицательных результатов (ЛОР):

${\displaystyle FNR=FN/(FN+TP)}$

${\displaystyle 45\div (45+11)=80.35\%}$

Коэффициент ложных срабатываний (FDR):

${\displaystyle FDR=FP/(FP+TP)}$

${\displaystyle 1\div (1+11)=8.30\%}$

Коэффициент ложного пропуска (FOR):

${\displaystyle FOR=FN/(FN+TN)}$

${\displaystyle 45\div (45+105)=30.00\%}$

После того, как мы рассчитали ключевые показатели, мы можем сделать некоторые предварительные выводы о производительности построенной модели дерева решений. Точность, которую мы рассчитали, составила 71,60%. Значение точности хорошее для начала, но мы хотели бы, чтобы наши модели были максимально точными, сохраняя при этом общую производительность. Значение чувствительности 19,64% означает, что из всех, кто был фактически положительным на рак, тест был положительным. Если мы посмотрим на значение специфичности 99,06%, мы знаем, что из всех образцов, которые были фактически отрицательными на рак, тест был фактически отрицательным. Когда дело доходит до чувствительности и специфичности, важно иметь баланс между двумя значениями, поэтому, если мы можем уменьшить нашу специфичность, чтобы увеличить чувствительность, это окажется полезным. ^[15] Это всего лишь несколько примеров того, как использовать эти значения и значения, стоящие за ними, для оценки модели дерева решений и улучшения на следующей итерации.

Смотрите также

• Дерево поведения (искусственный интеллект, робототехника и управление)  – Математическая модель выполнения плана
• Boosting (машинное обучение)  – Метод в машинном обучении
• Цикл принятия решения  – последовательность шагов для принятия решения
• Список решений
• Матрица принятия решений
• Таблица решений  – таблица, определяющая действия на основе условий.
• Модель дерева решений  – Модель вычислительной сложности вычислений
• Обоснование дизайна  — подробное документирование причин, лежащих в основе решений, принятых при проектировании системы или артефакта.Pages displaying wikidata descriptions as a fallback
• DRAKON  – Инструмент для отображения алгоритмов
• Цепь Маркова  – Случайный процесс, независимый от прошлой истории
• Случайный лес  – ансамблевый метод машинного обучения на основе деревьев
• Порядковый подход к приоритетам  – метод анализа решений по нескольким критериям
• Алгоритм шансов  – Метод вычисления оптимальных стратегий для задач последнего успеха
• Топологическая комбинаторика
• Таблица истинности  – Математическая таблица, используемая в логике.

Ссылки

1. фон Винтерфельдт, Детлоф; Эдвардс, Уорд (1986). «Деревья решений». Анализ решений и поведенческие исследования . Издательство Кембриджского университета. С. 63–89. ISBN 0-521-27304-8.
2. Камински, Б.; Якубчик, М.; Шуфель, П. (2017). «Структура анализа чувствительности деревьев решений». Central European Journal of Operations Research . 26 (1): 135–159. doi :10.1007/s10100-017-0479-6. PMC 5767274. PMID  29375266 . 
3. Сюй, Нинчжэ; Ловреглио, Руджеро; Кулиговски, Эрика Д.; Кова, Томас Дж.; Нильссон, Даниэль; Чжао, Силей (1 марта 2023 г.). «Прогнозирование и оценка принятия решений об эвакуации при лесных пожарах с использованием машинного обучения: результаты пожара в Кинкейде в 2019 году». Fire Technology . 59 (2): 793–825. doi :10.1007/s10694-023-01363-1. ISSN  1572-8099.
4. Диас-Рамирес, Дженни; Эстрада-Гарсия, Хуан Альберто; Фигероа-Саяго, Хулиана (1 декабря 2023 г.). «Прогнозирование предпочтений в выборе транспортного средства в университетском округе с помощью моделей на основе дерева решений». Взаимодействие города и окружающей среды . 20 : 100118. doi : 10.1016/j.cacint.2023.100118 . ISSN  2590-2520.
5. Куинлан, Дж. Р. (1987). «Упрощение деревьев решений». Международный журнал исследований человека и машины . 27 (3): 221–234. CiteSeerX 10.1.1.18.4267 . doi :10.1016/S0020-7373(87)80053-6. 
6. K. Karimi и HJ Hamilton (2011), «Генерация и интерпретация временных правил принятия решений», Международный журнал компьютерных информационных систем и приложений промышленного управления, том 3
7. Вагнер, Харви М. (1 сентября 1975 г.). Принципы исследования операций: с приложениями к управленческим решениям (2-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice Hall. ISBN 9780137095926.
8. Р. Куинлан, «Изучение эффективных процедур классификации», Машинное обучение: подход искусственного интеллекта , Михальски, Карбонелл и Митчелл (ред.), Морган Кауфманн, 1983, стр. 463–482. doi :10.1007/978-3-662-12405-5_15
9. Utgoff, PE (1989). Инкрементальная индукция деревьев решений. Машинное обучение, 4(2), 161–186. doi :10.1023/A:1022699900025
10. Дэн, Х.; Рунгер, Г.; Тув, Э. (2011). Меры смещения важности для многозначных атрибутов и решений. Труды 21-й Международной конференции по искусственным нейронным сетям (ICANN).
11. Larose, Chantal, Daniel (2014). Discovering Knowledge in Data . Хобокен, Нью-Джерси: John Wiley & Sons. стр. 167. ISBN 9780470908747.{{cite book}}: CS1 maint: multiple names: authors list (link)
12. Plapinger, Thomas (29 июля 2017 г.). «Что такое дерево решений?». На пути к науке о данных . Архивировано из оригинала 10 декабря 2021 г. Получено 5 декабря 2021 г.
13. Тао, Кристофер (6 сентября 2020 г.). «Не используйте дерево решений подобным образом». На пути к науке о данных . Архивировано из оригинала 10 декабря 2021 г. Получено 10 декабря 2021 г.
14. "False Positive Rate | Split Glossary". Split . Получено 10 декабря 2021 г. .
15. "Чувствительность против специфичности". Анализ и разделения из технологических сетей . Получено 10 декабря 2021 г.

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

• Подробные руководства и примеры по дереву решений
• Галерея примеров деревьев решений
• Деревья решений с градиентным усилением