Элементы технологии принятия решений это дерево целей
Обновлено: 18.09.2024
Процесс выбора решения с технологической точки зрения можно представить в виде последовательности этапов и процедур, имеющих между собой прямые и обратные связи.
Рассмотрение возникших проблем в строгой логической последовательности дает возможность плодотворно сочетать формальные и эвристические методы в процессе подготовки и принятия решений и добиваться более высокого их качества.
В зависимости от того, на каких аспектах в процессе решения делается акцент, этот процесс можно разделить на отдельные этапы, руководствуясь различными
принципами /11/.
Рассмотрим последовательность действий по целенаправленному выбору лучшего варианта из выявленного их множества и роль руководителя в этом процессе. Процесс реализуется, как правило, путем итеративного (повторяемого) приближения к требуемым результатам и содержит ряд этапов (рис.6.2).
Рассмотрим эти этапы.
1. Выявление и анализ проблемной ситуации.
Анализируется исходная информация о состоянии объекта исследования и внешней среды; определяется место и роль анализируемых объектов и объектов более высокого порядка; осуществляется выявление, структуризация и ранжирование проблем.
Прежде всего, определяются стратегические направления решения выявленных проблем для последующего формирования целей. Например, каким путем решать проблему нехватки воды в регионе: повышением эффективности использования имеющихся водных ресурсов, переброской воды из других регионов или как-то иначе.
Стратегические варианты решения выявленных проблем излагаются в сценарии. Под сценарием понимается вербально (словесное)-аналитическое описание существующего и прогнозируемого состояний объекта, принципиальных подходов к решению проблемы.
Сценарий содержит предварительный расчет ресурсов, необходимых для решения проблем в рамках различных стратегических направлений и реализации.
Конечным результатом работы на первом шаге этапа является выявление так называемых базовых, кардинальных проблем, решение которых необходимо осуществить в первую очередь, ранжирование этих проблем и выбор стратегического направления их решения с предварительной ресурсной оценкой (конец этапа).
Рис.6. 2 . Этапы выработки и реализации решений
2. Формирование целей.
Определяются цели решения кардинальных проблем. На практике используются различные способы задания целей: от простого перечня до построения графа (дерева) целей с характеристиками их приоритетов. Цели должны иметь четкие формулировки и количественные характеристики, по которым можно судить о степени их достижения.
3. Выявление полного перечня альтернатив.
На этом этапе определяется как можно более полная совокупность вариантов (способов, средств) достижения целей (конец этапа).
Надо иметь в виду, что обычно рассматривают два - три варианта решения с целью уменьшения трудоемкости анализа и вероятности грубой ошибки, хотя, конечно, шансы принять лучшее решение уменьшаются. Среди них вообще может не быть наилучшего. При большем наборе вариантов решений появляется гарантия, что среди них есть наилучший.
4. Выбор допустимых альтернатив.
Альтернативы, выявленные на третьем этапе, следует пропустить через “фильтр” различных ограничений (ресурсных, юридических, социальных, морально-этических и др.). Конечным результатом работ на данном шаге является множество альтернатив, удовлетворяющих принятым ограничениям.
5. Предварительный выбор лучшей альтернативы.
Проводится анализ допустимых альтернатив с точки зрения достижения поставленных целей, затрат ресурсов, соответствия конкретным условиям реализации альтернатив.
При решении достаточно сложных задач на основе количественных расчетов зачастую трудно выработать однозначные рекомендации о предпочтении одной альтернативы всем другим.
Возможно выделение группы предпочтительных альтернатив. Конечность этапа характеризуется вынесением суждения о предпочтительности альтернативы, которое и передается ЛПР.
6. Оценка альтернатив со стороны ЛПР.
Делая заключение, ЛПР может принимать в расчет дополнительные данные, неучтенные системными аналитиками. Таким образом, совместное использование интуиции, опыта и методов анализа (анализ выполняется специалистами) дает возможность наиболее полно учесть все аспекты решаемой проблемы. По существу, результаты анализа следует рассматривать как один из видов информации для ЛПР при принятии решения. Суждение ЛПР является конечным результатом на данном этапе.
7. Экспериментальная проверка альтернатив.
В случаях, если ЛПР затрудняется в окончательном выборе наилучшей альтернативы и при этом имеются соответствующие возможности, осуществляется экспериментальная проверка двух-трех наиболее предпочтительных альтернатив. Но такой подход характерен только для принятия решений в области научно-технической деятельности. Конечным результатом этапа является получение дополнительной информации.
8. Выбор единственного решения.
ЛПР принимает единственное решение. Если экспериментальной проверки нет, то шестой и восьмой этапы совмещаются.
9. Определение этапов, сроков и исполнителей принятого решения.
На этом этапе принятое решение делится на составные компоненты, имеющие конкретную временную, количественную и адресную привязку.
· “В какой последовательности делать?”.
10. Обеспечение работ по выполнению решения.
При этом осуществляются следующие мероприятия: доведение заданий до исполнителя, обеспечение исполнителей всем необходимым, выбор рациональных методов работы, подбор и обучение кадров, разъяснение исполнителям целей решения и их конкретной роли в его реализации, определение методов стимулирования эффективного выполнения заданий.
11. Выполнение решений. Контроль.
Осуществляется оперативный контроль за реализацией принятого решения, устраняются отклонения от путей реализации и вносятся в случае необходимости нужные коррективы. Конечным результатом на данном шаге является выполненное решение, т.е. достижение цели в установленные сроки и в пределах отпущенных ресурсов.
12. Оценка результатов реализации и обобщение накопленного опыта.
Производится оценка фактически полученного результата в сравнении с поставленной целью, анализ реализованного решения для обобщения, накопления опыта и дальнейшего его применения.
На этом, собственно, и заканчивается весь процесс подготовки, принятия и реализации решения. Здесь не выделены этапы сбора информации, построения моделей, выбора оценочных критериев.
Все это осуществляется на всех ступенях выбора решения. Например, определенные оценочные (в общем случае различные) критерии используются и при выборе альтернатив решения, и при определении степени выполнения решения и т.п. Практически достаточно четкое и последовательное разделение на этапы трудно осуществить, поскольку в той или иной мере они реализуются параллельно.
Обосновать и решить проблему с первого раза редко удается. Изменение в допустимых пределах ранее сформулированных целей дает возможность существенно повысить эффективность решения путем использования более действенных средств ее достижения. С этой целью предусмотрен возврат с любого этапа (шага) представленной на рис.6.2. схемы к любому предыдущему.
Таким образом, процесс носит итеративный характер, поэтому в ходе работы необходимо проявлять гибкость при возникновении новых факторов и ситуаций, вследствие чего проводить переоценку полученных результатов, а иногда менять и идеи, лежащие в основе решения. Такие переоценки нельзя считать напрасной тратой времени и труда. Но и нельзя постоянно менять цели и средства их достижения, так как это мешает четкой ориентации и деятельности фирмы.
Дерево решений - это метод, который применяется для принятия решений в условиях неопределенности и риска. Данный метод используется в случае, когда нужно принимать ряд последовательных решений. Дерево решений является графическим методом, который позволяет скоординировать элементы принятия решения, вероятные стратегии (Аi), их последствия (Ei,j) с вероятностными условиями и факторами внешней среды воздействия.
Начинается построение дерева решений с наиболее раннего решения, после разрабатываются возможные результаты и последствия каждого из действий (событий), после вновь определяется выбор направления действия (принимается решение) и так далее до тех пор, пока все последствия результатов решений не будут определены.
Дерево решений составляется на основании 5 последовательных элементов (рисунок 1):
Рисунок 1 – Элементы дерева решений
Простейшее решение
Простейшим решением является выбор из двух вариантов: "нет" или "да". (рисунок 2).
Рисунок 2 - Простейшее дерево решений
Последовательности решений можно смоделировать следующим образом (рисунок 3):
Рисунок 3 - Дерево (последовательность) принимаемых решений
1) решение: необходимо выбрать между тем, чтобы "Спать допоздна" или "Вставать рано"– простой выбор;
2) решение: необходимо выбрать между тем, чтобы "Работать спустя рукава" или "Работать усердно"– простой выбор;
3) событие: "Найдешь нефть" или нет случается с определенной вероятностью, которая зависит от принимаемых решений.
Поставленные задачи и варианты их решений приведены в таблицах 1 и 2, и отражены на рисунке 4 в виде дерева решений.
Жирным курсивом обозначен путь на дереве, являющийся самым предпочтительным (EV = 820000 долларов) и соответствующий решению, состоящему из элементов "Вставай рано" и "Работай усердно".
Таблица 1 - Вычисление ожидаемых результатов поиска нефти взвешенных по вероятности
| Решение: "Вставай рано" + "Работай усердно" | Возможное событие | |
| Не найти нефть | Найти нефть | |
| Событие: прибыль (убыток), долларов | -200 000 | 10000 000 |
| Событие: вероятность наступления события | 0,90 | 0,10 |
| Риск = Прибыль (убыток) × Вероятность, долларов | -180 000 | 1000 000 |
| Ожидаемое значение результата (EV), долларов | 1000000-180000 = 820 000 | |
Таблица 2 - Ожидаемые результаты решения "Когда встать и как работать"
Вероятность (найти нефть) = 5% (1- Вероятность) (не найти нефть) = 95%
Ожидаемое значение результатов решения: ( 0 , 05 × 10 000 000 ) + 0 , 95 × ( - 200 000 ) = 310000 долларов
Вероятность (найти нефть) = 10% (1- Вероятность) (не найти нефть) = 90%
Ожидаемое значение результатов решения: ( 0 , 1 × 10 000 000 ) + 0 , 9 × ( - 200 000 ) = 820 000 долларов
Вероятность (найти нефть) = 0% (1- Вероятность) (не найти нефть) = 100%
Ожидаемое значение результатов решения: ( 0 - 10 000 000 ) + 1 × ( - 200 000 ) = - 200 000 долларов
Вероятность (найти нефть) = 1% (1- Вероятность) (не найти нефть) = 99%
Ожидаемое значение результатов решения: ( 0 , 01 × 10 000 000 ) + ( 0 , 99 × ( - 200 000 ) = - 98 000 долларов
Рисунок 4 - Дерево решений с ожидаемыми значениями результатов(EV), долларов
Дополнительно учтем в примере, приведенном выше, изменение в зависимости от срока окупаемости стоимости проекта.
Установим, что сумма средств, необходимых для поиска нефти, расходуется сразу же. Если находим нефть, то все средства, вложенные в нефтеразведку покрываются сразу же, а доходы от продаж добытой нефти поступают через два года. Чтобы корректно учитывать все данные платежи и поступления, разбросанные во времени, необходимо привести все суммы денежных средств к текущей стоимости.
Установим, что ставка дисконтирования будет принимать значение, равное 20 процентов, тогда таблица 2 будет представлена в следующем виде (таблица 3), а дерево решений (рисунок 4) – в виде, показанном на рисунке 5.
Таблица 3 - Ожидаемая приведенная стоимость и результаты решения "Когда вставать и как работать" с учетом коэффициента дисконтирования
Вероятность (найти нефть) = 5% (1 – Вероятность) (не найти нефть) = 95%
Ожидаемая стоимость: 310000 долл.
Ожидаемая приведенная стоимость: ( 0 , 05 × 10 000 000 ) / 1 , 22 + 0 , 95 × ( - 200000 ) = 157 222 долл.
Вероятность (найти нефть) =10% (1 – Вероятность) (не найти нефть) = 90%
Ожидаемая стоимость: 820 000 долл.
Ожидаемая приведенная стоимость: ( 0 , 1 × 10 000 000 ) / 1 , 22 + 0 , 9 × ( - 200 000 ) = 514 444 долл.
Вероятность (найти нефть) = 0% (1 - Вероятность) (не найти нефть) = 100%
Ожидаемая стоимость: – 200000 долл.
Ожидаемая приведенная стоимость: ( 0 × 10 000 000 ) / 1 , 22 + 1 × ( - 200 000 ) = - 200 000 долл.
Вероятность (найти нефть) =1% (1 - Вероятность) (не найти нефть) = 99%
Ожидаемая стоимость: – 98000 долл.
Ожидаемая приведенная стоимость: ( 0 , 01 × 10 000 000 ) / 1 , 22 + 0 , 99 × ( - 200 000 ) = - 128 555 долл.
Самая эффективная последовательность решений та же (отображен жирной линией путь, который совпадает с решением "Вставай рано" + "Работай усердно", однако изменилось значение ожидаемого выигрыша (514444 долларов), в связи с тем, что учитывалась ставка дисконтирования.
Руководитель организации, выпускающего в настоящее время продукцию X1 в объеме V1тек. = 1000 единиц, считает, что необходимо расширять рынок продукции Х2.
Проведенные маркетинговые исследования определили вилки спроса на продукцию Х2 (V1max = 1000 единиц; V1min = 5000 единиц; V2max = 8000 единиц; V2min = 4000 единиц), а также вероятности низкого и высокого спроса (D1max = 0,7; D1min = 1 -D1max = 0,3; D2max = 0,6; D2min = 1-D2max = 0,4).
Выявлено, что даже минимальный уровень спроса намного превышает имеющиеся мощности организации, которые необходимо использовать для производства обоих видов продукции.
Определен уровень прибыли на единицу продукции каждого из видов (P1 = 1 денежных единиц; Р2 = 0,9 денежных единиц).
Рассчитаны затраты (К = 0,4 * 103 денежных единиц) на удвоение мощности организации (для одновременного производства продукта Х1 в существующем объеме и производства продукции Х2 в эквивалентном объеме) V1тек = 1000 единиц и V2экв = 900 единиц, на увеличение мощности организации под минимальный и максимальный спрос на текущую продукцию (K1min= = 1,4 * 103 денежных единиц и K1max = 2 * 103 денежных единиц) и под минимальный и максимальный уровень спроса на продукцию Х2 (К2 min = 0,8 * 103 денежных единиц и К1max = 1,2 * 103 денежных единиц соответственно).
Необходимо определить рациональность замены продукции и расширения мощностей, под одновременный выпуск продукции в том числе.
Дерево решений и рассчитанные последствия решения отображены на рисунке 5.
Рисунок 5 - Дерево решений с ожидаемыми значениями приведенных результатов (EV), долларов
Определив результаты решений при производстве продукции одного их видов (Х1 или Х2), выявим эффективные действия во второй точке решений.
Отбросим для этого иррациональные действия по расширению мощностей и данные об ожидаемом выигрыше перенесем в 4 графу. С учетом вероятности существующего спроса на продукты, проведем расчет средней эффективности действий в местах разветвления событий (3 графа). Выявлено, что продолжение производства продукта Х1, при параллельном расширении мощностей является более выгодным вариантом, чем переход на производство продукции Х2 вместо продукции X1.
Однако нами не учитывалась возможность параллельного производства продукции X1 и Х2 при расширении мощностей организации под максимальный уровень спроса. Поэтому проведем еще одно ответвление из первой точки принятия решения, соответствующее этому варианту решения. Эффективность этого варианта состоит из эффективности первого варианта и второго варианта (Э1 и Э2) за минусом вложений на первоначальное удвоение мощностей организации. Эффективность этого варианта самая высокая, поэтому варианты 1 и 2 необходимо вычеркнуть.
Вывод. Необходимо существенно развивать мощности и одновременно выпускать два вида продукции.
Рисунок 6 - Дерево принятия решений при определении стратегии организации
Представленная схема решения немного упрощена, так как мы не рассматривали варианты привлечения резервов по выпуску продукта одного вида при минимальном уровне спроса для производства продукции другого вида, лимиты по вложениям денежных средств (в условиях задачи для этого недостаточно данных).
Дерево решений — метод автоматического анализа больших массивов данных. В этой статье рассмотрим общие принципы работы и области применения.
Дерево решений — эффективный инструмент интеллектуального анализа данных и предсказательной аналитики. Он помогает в решении задач по классификации и регрессии.
Правила генерируются за счет обобщения множества отдельных наблюдений (обучающих примеров), описывающих предметную область. Поэтому их называют индуктивными правилами, а сам процесс обучения — индукцией деревьев решений.
В обучающем множестве для примеров должно быть задано целевое значение, так как деревья решений — модели, создаваемые на основе обучения с учителем. По типу переменной выделяют два типа деревьев:
дерево классификации — когда целевая переменная дискретная;
дерево регрессии — когда целевая переменная непрерывная.
Развитие инструмента началось в 1950-х годах. Тогда были предложены основные идеи в области исследований моделирования человеческого поведения с помощью компьютерных систем.
Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с Джоном Р. Куинленом (автором алгоритма ID3 и последующих модификаций С4.5 и С5.0) и Лео Брейманом, предложившим алгоритм CART и метод случайного леса.
Структура дерева решений
Рассмотрим понятие более подробно. Дерево решений — метод представления решающих правил в определенной иерархии, включающей в себя элементы двух типов — узлов (node) и листьев (leaf). Узлы включают в себя решающие правила и производят проверку примеров на соответствие выбранного атрибута обучающего множества.
Простой случай: примеры попадают в узел, проходят проверку и разбиваются на два подмножества:
первое — те, которые удовлетворяют установленное правило;
второе — те, которые не удовлетворяют установленное правило.
Далее к каждому подмножеству снова применяется правило, процедура повторяется. Это продолжается, пока не будет достигнуто условие остановки алгоритма. Последний узел, когда не осуществляется проверка и разбиение, становится листом.
Лист определяет решение для каждого попавшего в него примера. Для дерева классификации — это класс, ассоциируемый с узлом, а для дерева регрессии — соответствующий листу модальный интервал целевой переменной. В листе содержится не правило, а подмножество объектов, удовлетворяющих всем правилам ветви, которая заканчивается этим листом.
Пример попадает в лист, если соответствует всем правилам на пути к нему. К каждому листу есть только один путь. Таким образом, пример может попасть только в один лист, что обеспечивает единственность решения.
Терминология
Изучите основные понятия, которые используются в теории деревьев решений, чтобы в дальнейшем было проще усваивать новый материал.
Какие задачи решает дерево решений?
Его применяют для поддержки процессов принятия управленческих решений, используемых в статистистике, анализе данных и машинном обучении. Инструмент помогает решать следующие задачи:
Классификация. Отнесение объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные задачи.
Регрессия (численное предсказание). Предсказание числового значения независимой переменной для заданного входного вектора.
Описание объектов. Набор правил в дереве решений позволяет компактно описывать объекты. Поэтому вместо сложных структур, используемых для описания объектов, можно хранить деревья решений.
Процесс построения дерева решений
Основная задача при построении дерева решений — последовательно и рекурсивно разбить обучающее множество на подмножества с применением решающих правил в узлах. Но как долго надо разбивать? Этот процесс продолжают до того, пока все узлы в конце ветвей не станут листами.
Узел становится листом в двух случаях:
естественным образом — когда он содержит единственный объект или объект только одного класса;
после достижения заданного условия остановки алгоритм — например, минимально допустимое число примеров в узле или максимальная глубина дерева.
n примеров, для каждого из которых задана метка класса Ci(i = 1..k);
m атрибутов Aj(j = 1..m), которые определяют принадлежность объекта к тому или иному классу.
Тогда возможно три случая:
Множество S — пустое множество без примеров. Для него сформируется лист, класс которого выберется из другого множества. Например, самый распространенный из родительского множества класс.
Множество S состоит из обучающих примеров всех классов Ck. В таком случае множество разбивается на подмножества в соответствии с классами. Для этого выбирают один из атрибутов Aj множества S, состоящий из двух и более уникальных значений: a1, a2, …, ap), где p — число уникальных значений признака. Множество S разбивают на p подмножеств (S1, S2, …, Sp), состоящих из примеров с соответствующим значением атрибута. Процесс разбиения продолжается, но уже со следующим атрибутом. Он будет повторяться, пока все примеры в результирующих подмножества не окажутся одного класса.
Третья применяется в большинстве алгоритмов, используемых для построения деревьев решений. Эта методика формирует дерево сверху вниз, то есть от корневого узла к листьям.
Сегодня существует много алгоритмов обучения: ID3, CART, C4.5, C5.0, NewId, ITrule, CHAID, CN2 и другие. Самыми популярными считаются:
ID3 (Iterative Dichotomizer 3). Алгоритм позволяет работать только с дискретной целевой переменной. Деревья решений, построенные на основе ID3, получаются квалифицирующими. Число потомков в узле неограниченно. Алгоритм не работает с пропущенными данными.
CART (Classification and Regression Tree). Алгоритм решает задачи классификации и регрессии, так как позволяет использовать дискретную и непрерывную целевые переменные. CART строит деревья, в каждом узле которых только два потомка.
Основные этапы построения дерева решений
Построение осуществляется в 4 этапа:
Выбрать атрибут для осуществления разбиения в данном узле.
Определить критерий остановки обучения.
Выбрать метод отсечения ветвей.
Оценить точность построенного дерева.
Далее рассмотрим каждый подробнее.
Выбор атрибута разбиения
Разбиение должно осуществляться по определенному правилу, для которого и выбирают атрибут. Причем выбранный атрибут должен разбить множество наблюдений в узле так, чтобы результирующие подмножества содержали примеры с одинаковыми метками класса или были максимально приближены к этому. Иными словами — количество объектов из других классов в каждом из этих множеств должно быть как можно меньше.
Критериев существует много, но наибольшей популярностью пользуются теоретико-информационный и статистический.
Теоретико-информационный критерий
В основе критерия лежит информационная энтропия:
где n — число классов в исходном подмножестве, Ni — число примеров i-го класса, N — общее число примеров в подмножестве.
Энтропия рассматривается как мера неоднородности подмножества по представленным в нем классам. И даже если классы представлены в равных долях, а неопределенность классификации наибольшая, то энтропия тоже максимальная. Логарифм от единицы будет обращать энтропию в ноль, если все примеры узла относятся к одному классу.
Если выбранный атрибут разбиения Aj обеспечивает максимальное снижение энтропии результирующего подмножества относительно родительского, его можно считать наилучшим.
Но на деле об энтропии говорят редко. Специалисты уделяют внимание обратной величине — информации. В таком случае лучшим атрибутом будет тот, который обеспечит максимальный прирост информации результирующего узла относительно исходного:
где Info(S) — информация, связанная с подмножеством S до разбиения, Info(Sa) — информация, связанная с подмножеством, полученным при разбиении атрибута A.
Задача выбора атрибута в такой ситуации заключается в максимизации величины Gain(A), которую называют приростом информации. Поэтому теоретико-информационный подход также известен под название «критерий прироста информации.
Статистический подход
В основе этого метода лежит использования индекса Джини. Он показывает, как часто случайно выбранный пример обучающего множества будет распознан неправильно. Важное условие — целевые значения должны браться из определенного статистического распределения.
Если говорить проще, то индекс Джини показывает расстояние между распределениями целевых значений и предсказаниями модели. Минимальное значение показателя говорит о хорошей работе модели.
Индекс Джини рассчитывается по формуле:
где Q — результирующее множество, n — число классов в нем, pi — вероятность i-го класса (выраженная как относительная частота примеров соответствующего класса).
Значение показателя меняется от 0 до 1. Если индекс равен 0, значит, все примеры результирующего множества относятся к одному классу. Если равен 1, значит, классы представлены в равных пропорциях и равновероятны. Оптимальным считают то разбиение, для которого значение индекса Джини минимально.
Критерий остановки алгоритма
Переобучение в случае дерева решений имеет схожие с нейронными сетями последствия. Оно будет точно распознавать примеры из обучения, но не сможет работать с новыми данными. Еще один минус — структура переобученного дерева сложна и плохо поддается интерпретации.
Для этого используют несколько подходов:
Ранняя остановка. Алгоритм останавливается после достижения заданного значения критерия (например, процентной доли правильно распознанных примеров). Преимущество метода — сокращение временных затрат на обучение. Главный недостаток — ранняя остановка негативно сказывается на точности дерева. Из-за этого многие специалисты советуют отдавать предпочтение отсечению ветей.
Ограничение глубины дерева. Алгоритм останавливается после достижения установленного числа разбиений в ветвях. Этот подход также негативно сказывается на точности дерева.
Задание минимально допустимого числа примеров в узле. Устанавливается ограничение на создание узлов с числом примером меньше заданного (например, 7). В таком случае не будут создаваться тривиальные разбиения и малозначимые правила.
Этими подходами пользуются редко, потому что они не гарантируют лучшего результата. Чаще всего, они работают только в каких-то определенных случаях. Рекомендаций по использованию какого-либо метода нет, поэтому аналитикам приходится набирать практический опыт путем проб и ошибок.
Отсечение ветвей
Поэтому многие специалисты отдают предпочтение альтернативному варианту — построить все возможные деревья, а потом выбрать те, которые при разумной глубине обеспечивают приемлемый уровень ошибки распознавания. Основная задача в такой ситуации — поиск наиболее выгодного баланса между сложностью и точностью дерева.
Но и тут есть проблема: такая задача относится к классу NP-полных задач, а они, как известно, эффективных решений не имеют. Поэтому прибегают к методу отсечения ветвей, который реализуется в 3 шага:
Строительство полного дерева, в котором листья содержат примеры одного класса.
Определение двух показателей: относительную точность модели (отношение числа правильно распознанных примеров к общему числу примеров) и абсолютную ошибку (число неправильно классифицированных примеров).
Удаление листов и узлов, потеря которых минимально скажется на точности модели и увеличении ошибки.
Отсечение ветвей проводят противоположно росту дерева, то есть снизу вверх, путем последовательного преобразования узлов в листья.
Извлечение правил
Иногда упрощения дерева недостаточно, чтобы оно легко воспринималось и интерпретировалось. Тогда специалисты извлекают из дерева решающие правила и составляют из них наборы, описывающие классы.
Для извлечения правил нужно отслеживать все пути от корневого узла к листьям дерева. Каждый путь дает правило с множеством условий, представляющих собой проверку в каждом узле пути.
Если представить сложное дерево решений в виде решающих правил (вместо иерархической структуры узлов), оно будет проще восприниматься и интерпретироваться.
Преимущества и недостатки дерева решений
Преимущества:
Формируют четкие и понятные правила классификации. Например, «если возраст
Не можете принять решение или просчитать риски в бизнесе? Invme расскажет, как это сделать. Читайте нашу статью о дереве решений и узнайте, как его создать и как с ним работать.
Дерево решений можно представить как карту возможных результатов из ряда взаимосвязанных выборов
Что такое дерево решений
Дерево решений – это способ для принятия решений. Он используется не только в аналитике и в бизнесе, но он может быть применен и в жизни, когда нужно рассмотреть ту или иную проблему с разных сторон и принять правильное решение.
Дерево решений можно представить как карту возможных результатов из ряда взаимосвязанных выборов. Это помогает сопоставить возможные действия, основываясь на их стоимости вероятности и выгоде. Для этого используют модель принятия решений в виде дерева, что может быть полезно и в процессе обсуждения чего-либо, и для составления алгоритма, который математически определяет наилучший выбор.
Обычно дерево решений начинается с одного узла, который разветвляется на возможные результаты. Каждый из них продолжает схему и создает дополнительные узлы, которые продолжают развиваться по тому же признаку. Это придает модели древовидную форму: то есть переход от верхушки дерева - к веткам и множеству листьев.
Дерево решений обычно состоит из трёх типов узлов:
- Узлы решения — обычно представлены квадратами
- Вероятностные узлы — представляются в виде круга
- Замыкающие узлы — представляются в виде треугольника
Кто придумал дерево решений
Развитие дерева решений началось в 1950-х годах. Тогда были предложены основные идеи в области исследований моделирования человеческого поведения с помощью компьютерных систем.
Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с математиками Джоном Р. Куинленом и Лео Брейманом, предложившим алгоритм CART и метод случайного леса.
Почему такое название
Метод получил такое название из-за своей структуры, включающей в себя элементы двух типов — узлов (node) и листьев (leaf). Лист определяет решение для каждого попавшего в него примера, в нем содержится не правило, а подмножество объектов, удовлетворяющих всем правилам ветви, которая заканчивается этим листом. К каждому листу есть только один путь, поэтому пример или утверждение могут попасть только в один лист, что обеспечивает единственность решения.
Деревья решений представляют собой последовательные иерархические структуры, состоящие из узлов, которые содержат правила, т.е. логические конструкции вида "если … то …". Конечными узлами дерева являются "листья", соответствующие найденным решениям и объединяющие некоторое количество объектов классифицируемой выборки. Это похоже на то, как положение листа на дереве можно задать, указав ведущую к нему последовательность ветвей, начиная от корня и кончая самой последней веточкой, на которой лист растет.
Где используют дерево решений
В целом дерево решений можно применить практически к любой сфере (включая личные решения того или иного вопроса). Но все-таки чаще всего он используется в следующих областях:
- банковское дело – оценка кредитоспособности клиентов банка при выдаче кредитов;
- промышленность – контроль качества продукции (выявление дефектов), испытания без разрушений (например, проверка качества сварки) и т.д.;
- медицина – диагностика различных заболеваний;
- маркетинг – предсказание выбора покупателя, сегментация клиентской базы;
- молекулярная биология – анализ строения аминокислот и другие области.
В целом дерево решений можно применить практически к любой сфере
Дерево решений: пример
Например, вы решили задаться вопросом, как вам иметь больше денег к концу года, не влезая в долги. Это главный вопрос, от которого будут отходить все остальные.
Итак, главный вопрос разветвляется на две части: Доходы и Расходы. Доходы нужно повышать, расходы понижать. Как это сделать? От доходов идут разветвления: случайный выигрыш и работа. Выигрыш может быть легальным и нелегальным. Это может быть, скажем, выигрыш в лотерею или наследство.
Работа имеет еще больше разветвлений. Либо увеличение рабочих часов, либо больший заработок за час. Дальше это выливается в сверхурочные, вторую работу, переход в более высокооплачиваемую отрасль и др.
Расходы разветвляются на стоимость и количество покупок. Стоимость можно понижать за счет, например, распродаж. А количество покупок понижать в каждой из сфер: еда, одежда, развлечения, путешествия, другое.
Таким образом можно разобрать практически любую проблему и прийти к определенному решению. Структурированный вид помогает смотреть на все шире и брать во внимание множество нюансов, которые не всегда понятны в другом виде.
Обыкновенное дерево состоит из корня, ветвей, узлов (мест разветвления), листьев. Точно также дерево решений состоит из узлов (называемых также вершинами), обозначаемых окружностями; ветвей, обозначаемых отрезками, соединяющими узлы. Для удобства дерево решений изображают обычно слева направо или сверху вниз. Самая первая (левая или верхняя) вершина называется корнем. Цепочка "корень - ветвь - вершина - . - вершина" заканчивается вершиной, которую называют "листом". Из каждой внутренней вершины (т.е. не листа) может выходить две или более ветвей. Каждому такому узлу сопоставлена некоторая характеристика, а ветвям - области значения этой характеристики, причем эти области дают разбиение множества значений данной характеристики.
Плюсы и минусы дерева решений
Плюсы:
- Формирует четкие и понятные правила классификации. То есть деревья решений хорошо и быстро интерпретируются
- Деревья способны генерировать правила в областях, где специалисту трудно формализовать свои знания
- Быстро обучаются и прогнозируют
- Не требуется много параметров модели
- Поддерживают как числовые, так и категориальные признаки
- Быстро приводят к результату и решению проблемы
Минусы:
- Деревья решений очень чувствительны. Небольшие изменения обучающей выборки могут привести к глобальным корректировкам модели.
- Разделяющая граница имеет определенные ограничения, из-за чего дерево решений по качеству классификации уступает другим методам.
Читайте также: