Алгоритм построения дерева решений: методы управления

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

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

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

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

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

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

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

С сайта: http://knoow.net/ru/ekonomika-i-biznes-ru/upravlenie/derevo-prinyatiya-resheniy/

Анализ дерева решений в менеджменте

Анализ дерева решений [англ. Decision Tree Analysis] — это метод, который описывает процесс принятия решения посредством рассмотрения альтернативных вариантов и последствий их выбора.

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

Описание

Дерево решений рисуется слева на право. При формировании дерева используются четыре следующих типа графических обозначений:

  • Квадраты — места принятия решений.
  • Круги — места появления исходов.
  • Пунктирные линии — возможные решения.
  • Треугольники или прямые линии — возможные исходы.

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

Пример

Перед руководством одной иностранной автомобильной компании стоит задча выпускать в России новую модель своего автомобиля или нет. Для этого необходимо решить, монтировать или нет на заводе новый конвейер по производству автомобиля, который сконструирован по новой технологии и отличается от уже существующих. Если новый конвейер будет работать безперебойно, то компания получит прибыль 600 млн. В противном случае, при отказе конвейера компания может потерять 470 млн. По предварительным оценкам руководства компании, существует вероятность 70%, что новый конвейер откажет.

Есть предложение создать экспериментальный конвейер, а затем решить, монтировать или нет новый конвейер. Экспериментальный конвейер обойдется компании в 95 млн. Еще руководство компании считает, что существует 50% шансов, что экспериментальный конвейер будет работать нормально. Если экспериментальный конвейер будет работать, то с вероятностью 80% новый конвейер также будет работать. Если же экспериментальный конвейер откажет, то есть вероятность 40%, что новый конвейер заработает.

   

В узле F возможны исходы «конвейер работает» с вероятностью 0,3 (что приносит прибыль 600) и «конвейер не работает» с вероятностью 0,7 (что приносит убыток -470) следовательно оценка узла F. EMV( F) = 0,3 x 600 + 0,7 х ( -470) = -149. Это число мы пишем над узлом F.

EMV(G) = 0.

В узле 4 мы выбираем между решением «монтируем новый конвейер» (оценка этого решения EMV( F) = -149) и решением «не монтируем новый конвейер» (оценка этого решения EMV(G) = 0): EMV(4) = max {EMV( F), EMV(G)} = max { -149, 0} = 0 = EMV(G). Эту оценку мы пишем над узлом 4, а решение «монтируем новый конвейер» отбрасываем и зачеркиваем.

Аналогично:

EMV( B) = 0,8 х 600 + 0,2 х (-470) = 480 — 94 = 386.

EMV(С) = 0.

EMV(2) = max {EMV(В), EMV(С} = max {386, 0} = 386 = EMV(B). Поэтому в узле 2 отбрасываем возможное решение «не монтируем новый конвейер».

EMV(D) = 0,4 х 600 + 0,6 х (-470) = 240 — 282 = -42.

EMV( E) = 0.

EMV(3) = max {EMV(D), EMV(E)} = max { -42, 0} = 0 = EMV( E). Поэтому в узле 3 отбрасываем возможное решение «монтируем новый конвейер».

ЕМV(A) = 0,5 х 386 + 0,5 х 0 — 95 = 98.

EMV(1) = max {EMV(A), EMV(4)} = max {98; 0} = 98 = EMV( A). Поэтому в узле 1 отбрасываем возможное решение «не монтируем экспериментальный конвейер».

Ожидаемая стоимостная оценка наилучшего решения равна 98 млн. рублей. Строим новый конвейер. Если экспериментальный конвейер работает, то монтируем новый конвейер. Если экспериментальный конвейер не работает, то новый конвейер не монтируем.

С сайта: http://mahamba.com/ru/analiz-dereva-resheniy

100% способ решения Ваших бизнес-проблем

Сегодня я хочу поговорить с Вами о том, как можно быстро определить суть какой-либо проблемы, не тратя на нее особо много времени.

Вероятно, Вам приходилось встречать людей, которые обладают талантом интуитивно находить суть проблемы, но, к сожалению, такие люди – большая редкость.

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

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

Буквально недавно ко мне обратился собственник компании, производящей косметические продукты, с просьбой помочь найти способы повышения рентабельности линейки шампуней А.

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

Начнем с вопроса: «Насколько можно повысить рентабельность линейки шампуней А?» Всем нам известно, что прибыль определяется продажной ценой, объемом продаж и себестоимостью продукта. На раннем этапе постановки диагноза важно считать одинаково приоритетными все три переменные.

В этом конкретном случае повышение рентабельности шампуня А будет зависеть от ответов на два вопроса:

  • можно ли зарабатывать больше прибыли, которую приносит шампунь А в данном сегменте рынка?
  • можно ли повысить рентабельность шампуня А при существующей продажной цене, снизив его себестоимость?

Далее, первый вопрос разбиваем также на два подвопроса:

  1. Можно ли увеличить объем продаж? Варианты решений могут быть следующими:
    • улучшение работы с существующими каналами сбыта;
    • выход в те каналы сбыта, где то сих пор не присутствовали (интернет-магазин, специализированные косметические сети, фармацевтические сети);
    • расширение географии продаж;
    • активное проведение промо-мероприятий и повышение осведомленности конечных покупателей при помощи рекламных кампаний;
    • рестайлинг упаковки;
    • выход в новые рыночные сегменты;
    • оптимизация ассортиментной линейки (сокращение или расширение позиций).
  2. Можно ли повысить отпускную цену? Необходимо проанализировать следующие аспекты:
    • насколько у Вас гибкое и корректное ценообразование для всех каналов сбыта?
    • возможно ли повысить цену для отдельных каналов сбыта или для разных географических регионов?
    • каково поведение основных конкурентов (можно ли повысить цены «следуя за лидером»)?
    • можете ли Вы повысить цену, видоизменив продукт (другой объем, новый состав с улучшенными свойствами)?

Что касается снижения себестоимости, то анализируем следующие факторы:

  1. Можете ли Вы сократить постоянные расходы (сократить лишний вспомогательный персонал, контролировать дебиторскую и кредиторскую задолженности, сократить ненужные основные средства)?
  2. Можете ли Вы сократить переменные расходы? Решения могут быть следующими:
    • улучшить методы закупок, сменить поставщиков;
    • улучшить контроль производственного процесса;
    • изменить систему мотивации персонала (ввести методы стимулирования);
    • улучшить обучение персонала;
    • произвести замену старого оборудования;
    • усилить контроль качества продукции (снизить процент брака).

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

С сайта: http://strategy4business.ru/100-metodika-resheniya-Vashih-problem/

Метод дерева решений и другие методы на основе графов

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

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

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

Дерево решений состоит из следующих элементов: дуг, узлов решений, узлов событий и конечных узлов (исходов).

Рассмотрим сначала простейший пример применения метода дерева решений и решим следующую задачу.

Пример 1. Решить методом дерева решений, какую сумму вы потратите на продукты в определённый день.

Решение. Альтернативные события на первом этапе: гости придут и гости не придут. Отображаем эти события в дереве решений в виде вершин событий (кружочков). Примем, что, если гости придут, на продукты придётся потратить крупную сумму. Это один из исходов (конечных узлов в дереве решений) в данной задаче.

В случае, если гости не придут, возможны два альтернативных события: в доме много продуктов и в доме мало продуктов.

Отображаем эти события в дереве решений в виде вершин событий (кружочков), к которым ведут дуги из события «гости не придут». В случае, если в доме много продуктов, вы потратите на продукты малую сумму. В случае, если в доме мало продуктов, вы потратите на продукты среднюю сумму.

Дерево решений для этой задачи будет следующим:

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

Предположим, вероятность этого события равна 0,3. Тогда от единицы отнимем 0,3 и получим 0,7 — вероятность того, что гости не придут. События, следующие из этого события также могут быть связаны с вероятностями.

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

Предположим, вероятность того, что в доме много продуктов, равна 0,4. Тогда 1 — 0,4 = 0,6 — вероятность того, что в доме мало продуктов. Итак, имея оценки вероятностей альтернативных событий, мы решая ту или иную задачу методом дерева решений, можем прогнозировать исходы. Как это сделать, мы узнаем, когда рассмотрим второй пример.

Продолжим двигаться к более сложным примерам. Определим дерево решений более подробно. Дерево решений строится в виде графа-дерева, обладающего следующими свойствами:

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

При решении прикладных задач методом дерева решений поступают следующим образом:

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

Пример 2. Решить методом дерева решений задачу прогнозирования приобретений и убытков при альтернативах решений.

Строительная фирма собирается принять решение о строительстве жилого комплекса (ЖК) в элитном районе. Сначала требуется принять решение: проводить ли информационно-рекламную кампанию. Она стоит 500000 условных единиц (у.е.). Опыт показывает, что лишь в 25 % случаев этот шаг обеспечивает успех на рынке.

Если информационно-рекламная кампания успешна, требуется принять решение: строить ли большой или малый ЖК. Строительство малого ЖК обойдётся в 50000000, при этом можно построить 300 квартир. Строительство большого ЖК обойдётся в 200000000, при этом можно построить 900 квартир.

Имеются исследования прогноза спроса. Они показывают, что существует вероятность в 40 % того, что произойдёт падение спроса на элитное жильё.

По предварительным расчётам, средние цены на квартиры будут определяться следующим образом:

Большой ЖК Малый ЖК
Спрос снизится 100 000 150 000
Спрос не снизится 250 000 400 000

Рассчитано, что расходы фирмы перед и в период продажи всех квартир в ЖК составят 5000000, независимо от величины ЖК.

Требуется принять решение: проводить ли информационно-рекламную кампанию и начинать строительство ЖК.
Строим дерево решений:

Последствия альтернативных решений получены при расчётах, которые приведены ниже.

Шаг 1 (не учитываются вероятности событий).

Малый ЖК

Спрос не снизится

Доходы Расходы Прибыль
400000 * 300 = 120000000 50000000 + 5000000 = 55000000 120000000 — 55000000 = 65000000

Спрос снизится

Доходы Расходы Прибыль
150000 * 300 = 45000000 50000000 + 5000000 = 55000000 45000000 — 55000000 = -10000000

Большой ЖК

Спрос не снизится

Доходы Расходы Прибыль
250000 * 900 = 225000000 200000000 + 5000000 = 205000000 225000000 — 205000000 = 20000000

Спрос снизится

Доходы Расходы Прибыль
100000 * 900 = 90000000 200000000 + 5000000 = 205000000 90000000 — 205000000 = -115000000

Шаг 2 (учитываются вероятности событий).

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

Расходы
Малый ЖК 0,60 * 65000000 + 0,40 * (-10000000) = 35000000
Большой ЖК 0,60 * 20000000 + 0,40 * (-115000000) = -34000000

Теперь следует рассчитать приобретения при вершине 3 дерева решений (проводить информационно-рекламную кампанию). Для этого нужно рассчитать приобретения при вершинах 4 (неуспешная информационно-рекламная кампания) и 5 (успешная информационно-рекламная кампания).

Наступление события при вершине 5 (строительство ЖК) означает максимальную прибыль 35000000, которую только можно получить при выборе данного решения. Наступление события при вершине 4 (неуспешная информационно-рекламная кампания) означает убытки в 500000.

Теперь можно рассчитать приобретения при вершине 3 дерева решений (проводить информационно-рекламную кампанию): 0,25 * 35000000 + 0,75 * (-500000) = 8750000 — 375000 = 8375000.

В результате применения метода дерева решений выбирается следующая альтернатива: начать информационно-рекламную кампанию и готовиться к строительству ЖК, отдавая предпочтение малому ЖК.

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

Нет времени вникать в решение? Можно заказать работу!Дерево игры очень похоже на дерево решений.

Теория игр вообще занимается попыткой выразить особенности столкновения интересов через действия, которые имеют место в салонных играх. Правила любой салонной игры устанавливают последовательность вполне определённых ходов, причём каждый ход для данного игрока соответствует выбору одной из множества альтернатив.

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

Таким образом, значение каждого хода в игре зависит от других ходов. Если создать отвлечённое представление всех ходов игры и указать, какие выборы привели к каждому ходу, то можно узнать отвлечённую связь каждого хода со всеми другими ходами, которые повлияли на него или на которые он может повлиять.

Пример 3. В некоторой игре (на каком-то этапе партии) игроку 1 нужно выбрать между королём червей, двойкой пик и валетом бубен, а в другой игре игрок, также называемый игроком 1, должен выбрать между тем, чтобы пасовать, назначать игру или вистовать. В обоих случаях нужно выбрать между тремя альтернативами. Это можно представить на рисунке ниже.

Пример 4. Число, связанное с каждым ходом, указывает, какой игрок делает выбор на данном ходе. Следовательно, если имеется n игроков, то будут употребляться числа от 1 до n.

Пусть n=4, тогда каждый ход, за исключением первого, назначается одному из игроков. Первому ходу приписывается обозначение «0». Ход с обозначением «0» является случайным ходом, как, например, тасовка карт перед партией покера. С каждым случайным ходом, который необязательно должен быть первым ходом, нужно связать распределение вероятностей или весов по нескольким альтернативным выборам. Если случайным ходом является бросание уравновешенной монеты, то в ходе имеются две альтернативы, и каждая из них может осуществиться с вероятностью 1/2.

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

Исследование системы с перенесением его свойств на модель называется моделированием. Математическое моделирование позволяет абстрагироваться от физических и прочих специфических свойств объекта. Математическая модель — это упрощённое и самодостаточное в понятийном плане отображение реальности.

Определение 1. Математическая модель — задание системы или явления любого происхождения и любой природы в виде математических объектов и взаимосвязей.

Определение 2. Математическая модель — приближенное описание какого-либо класса явлений внешнего мира, выраженное с помощью математической символики.

Любая математическая модель предполагает наличие объектов и взаимосвязей между ними.

Сформулируем основные принципы моделирования.

  1. Выбор модели существенно влияет на процесс решения задачи и на само решение.
  2. Степени детализации модели могут быть разными.
  3. Более подробная детализация означает бОльшую сложность модели.
  4. Лучшие модели — те, которые лучше отображают реальность.
  5. Желательно использовать одновременно несколько моделей.

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

  • вершины и рёбра — физические объекты, объекты-рёбра физически связывают вершины;
  • вершины — физические или нефизические объекты, рёбра связывают вершины в зависимости от структурных или функциональных свойств вершин;
  • вершины — физические или нефизические объекты, возможно, в различных состояниях, зависящих от времени и развития, рёбра показывают временнУю, эволюционную или причинно-следственную связь между вершинами.

Есть два условия создания эффективной математической модели системы в виде графа:

  1. определены важнейшие подсистемы или состояния моделируемой системы, которые отображаются в виде вершин графа;
  2. определены важнейшие отношения между объектами-вершинами.

Чаще используются модели, в которых основную роль играют вершины графа, а не его рёбра.

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

Системы со свойствами непрерывности целесообразнее моделировать с помощью уравнений математической физики.

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

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

  1. Блок-схема компьютерной программы (вершины — команды, рёбра — переходы между команды), используемая для разработки и тестирования самой программы.
  2. Граф подпрограмм (вершины — подпрограммы, рёбра — порядок вызова подпрограмм), используемый для проектирования и анализа компьютерных программ.
  3. Граф структуры данных (вершины — данные или простейшие типы данных, рёбра — отношения между данными), используемый для проектирования и оптимизации структур данных.
  4. Граф зависимости команд машинного кода (вершины — команды, рёбра — зависимости между командами), используемый в оптимизационном компилировании и конвейеризации работы процессора.
  5. Граф процессов операционной системы (вершины — процессы операционной системы, рёбра — акты генерирования процессов), используемый в моделировании работы операционной системы.
  6. Граф конечного автомата (вершины — состояния автомата, рёбра — переходы), используемый в исследовании конечных автоматов и языков и в инженерии программного обеспечения.
  7. Граф утверждений математической теории (вершины — утверждения, рёбра — отношения логического следования), используемый для доказательства математических заключений и анализа математических теорий.
  8. Функциональный граф (вершины — элементы множества, рёбра — отношения логического следования), имеющий широкое использование в математике.
  9. Граф величин-зависимостей (вершины — численные величины и взаимосвязи между ними, рёбра — отношения вовлечённости величины), используемый в решении различных математических задач.
  10. Граф метрики (вершины — любые физические или нефизические объекты или их множества, рёбра — геометрическая, структурная, функциональная или эволюционная близость этих объектов), используемый для анализа больших множеств.
  11. Дерево решений (вершины — критические состояния, рёбра — решения), используемый в принятии решений в экономике, управлении, диагностике инженерных систем.
  12. Системный граф (вершины — компоненты системы, рёбра — взаимодействие компонент), используемый в проектировании и анализе систем.
  13. Граф обратных связей (вершины — параметры какого-либо процесса, ориентированные рёбра с весами «+» или «-» — зависимость изменений параметров, соответствующих вершинам), используемый в исследованиях изменений составных частей процессов или объектов.
  14. Граф причинно-следственных связей (вершины — состояния какой-либо системы, ориентированные рёбра — причинно-следственные связи), используемый в исследованиях больших систем и сложных процессов.
  15. Граф конфликтов (вершины — состояния какой-либо системы, рёбра — конфликты между состояниями), используемый в анализе систем.
  16. Граф игры (вершины — игровые состояния, рёбра — разрешённые правилами игры переходы между состояниями (ходы)), используемый в разработке победных стратегий в играх.
  17. Компьютерная сеть (вершины — компьютеры или коммуникационные узлы, рёбра — линии связи), используемая в проектировании и анализе компьютерных сетей.
  18. Социальный граф (вершины — люди или множества людей, рёбра — отношения знакомства, экономические отношения или другие отношения), используемый в анализе общества и планировании развития.
  19. Организационный граф (вершины — люди или множества людей, рёбра — отношения, характеризующие организации, например, частные фирмы, иерархии), используемый в создании организаций и управлении ими.
  20. Граф проекта (вершины — работы или состояния проекта, рёбра — отношения между работами или работы, соединяющие состояния), используемый в руководстве проектами.
  21. Генеалогическое древо (вершины — люди, рёбра — отношение «родители-дети»), используемый в личных исследованиях.
  22. Граф экономических агентов (вершины — экономические агенты — люди, фирмы и др., рёбра — экономические отношения), используемый в экономических исследованиях и планировании.
  23. Макроэкономический граф финансового потока (вершины — отрасли экономики, рёбра — финансовые потоки), используемый в экономических исследованиях и планировании.
  24. Граф дорог (вершины — города, рёбра — дороги), используемый в развитии транспортной сети.
  25. Граф улиц (вершины — перекрёстки, рёбра — улицы), используемый в анализе и планировании потока городского транспорта.
  26. Граф электрической цепи (вершины — электромагнитно-активные элементы, рёбра — провода и контакты), используемый в построении и анализе электрических счем.
  27. Цепь питания (вершины — породы животных, рёбра — отношения питания), используемый в анализе биосистем.
  28. Дерево эволюции (вершины — породы или популяции, рёбра — отношения эволюционного происхождения), используемый в биологии.
  29. Граф химических реакций (вершины — векторы количества химических веществ, рёбра — химические реакции), используемый в анализе химических реакций.
  30. Граф предшественников химического вещества (вершины — химические вещества, полученные в процессе производства, рёбра — изменения веществ-предшественников в процессе производства), используемый в химической промышленности.
  31. Граф реакционной способности химических веществ (вершины — химические вещества, рёбра — способности к реакции), используемый в анализе сложных химических реакций.
  32. Граф взрывоопасности (вершины — химические вещества, рёбра — возможности взрывной реакции между ними), используемый для нужд безопасности труда.
  33. Граф помех радиосвязи (вершины — радиостанции, рёбра — взаимное перекрытие полос радиоволн), используемый в планировании радиосвязи.
  34. Политический граф (вершины — государства, рёбра — границы), используемый в геополитике.
  35. Граф кровеносных сосудов (вершины — узлы кровеносных сосудов, рёбра — кровеносные сосуды), используемый в медицине.
  36. Граф нейронов (вершины — нейроны, рёбра — места соприкосновения нейронов), используемый в медицине.
  37. Граф приготовления кулинарного изделия (вершины — состояния готовности кулинарного изделия, рёбра — переходы между состояниями в процессе приготовлении), используемый в кулинарии.

С сайта: https://function-x.ru/graphs4_modeling_decision_tree_game_tree.html

Использование деревьев решений в задачах прогнозной аналитики

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

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

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

Деревья решений могут оценивать значения категориальных атрибутов (конечное число дискретных значений), а также  количественных. В первом случае говорят о задаче классификации – отнесении объекта к одному из «классов», определяемых атрибутом (например, Да/Нет, Хорошо/Удовлетворительно/Плохо и т. Во втором случае говорят о задаче регрессии, то есть об оценке количественной величины.

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

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

Но нас интересуют только деревья, которые наиболее точно оценивают значение атрибута, с минимальной ошибкой, а также позволяют выявлять зависимость между атрибутами и успешно выполнять прогнозирование значений атрибутов на новых данных. К сожалению, не существует хороших алгоритмов, позволяющих гарантированно найти такое «оптимальное» дерево (за приемлемое время). Однако существуют достаточно хорошие алгоритмы, которые пытаются построить «почти оптимальное» дерево, выполняя на каждой итерации определенный «локальный» критерий оптимальности в надежде, что получившееся дерево тоже в целом будет «оптимальным». Такие алгоритмы называются «жадными». Именно такой алгоритм мы и рассмотрим.

Алгоритм построения дерева решений

Принцип построения дерева следующий. Дерево строится «сверху вниз» от корня.

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

Главный вопрос – как выбирать атрибуты.

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

Энтропия

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

Данная функция представляет собой так называемую энтропию.

Энтропия возникла в теории информации и описывает количество информации (в битах), которое необходимо, чтобы закодировать сообщение о принадлежности случайно выбранного объекта (строки) из нашего набора X к одному из классов и передать его получателю. Если класс только один, получателю ничего не нужно передавать, энтропия равна 0 (принимается, что 0log20 = 0). Если все классы равновероятны, то потребуется log2c бит (c – общее количество классов) – максимум функции энтропии.

Далее, для выбора атрибута, для каждого атрибута A вычисляется так называемый прирост информации:

Где values(A) – все принимаемые значения атрибута A, Xa – подмножество набора данных, где A = a, |X| – количество элементов во множестве. Данная величина описывает ожидаемое уменьшение энтропии после разбиения набора данных по выбранному атрибуту.

Второе слагаемое – это сумма энтропий для каждого подмножества, взятая со своим весом. Общая разница описывает, как уменьшится энтропия, сколько мы сэкономим бит для кодирования класса случайного объекта из набора X, если мы знаем значения атрибута A и разобьем набор данных на подмножества по данному атрибуту.

Алгоритм выбирает атрибут, соответствующий максимальному значению прироста информации.

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

Процесс останавливается, когда созданные подмножества стали достаточно однородны (преобладает один класс), а именно когда max(Gain(X,A)) становится меньше некоторого заданного параметра Θ (величина, близкая к 0). Как альтернативный вариант, можно контролировать само множество X, и когда оно стало достаточно мало или стало полностью однородным (только один класс), останавливать процесс.

Жадный алгоритм построения дерева решений

Более структурно алгоритм можно представить следующим образом:

  1. Если max(Gain(X,A)) < Θ, создать лист с меткой преобладающего класса.
  2. Если не осталось атрибутов для разбиения, создать лист с меткой преобладающего класса.
  3. Иначе:
    • выбрать атрибут, соответствующий максимуму Gain(X,A);
    • создать ветку для каждого значения атрибута;
    • для каждой ветки:
      1. построить подмножество Xa, исключив при этом атрибут A из множества атрибутов;
      2. рекурсивно вызвать алгоритм для подмножества Xa.

Если атрибут количественный (например, вещественное число), то разбиение по нему выполняется в форме теста A ≤ a0 и формируются две ветки (истина и ложь). Существует способ оптимального подбора a0 также с использованием идеи прироста информации.

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

Как это работает

Рассмотренный алгоритм был предложен его автором Джоном Квинланом (Quinlan) и известен как алгоритм ID3 (Iterative Dichotomiser версии 3).

Давайте на небольшом примере рассмотрим, как ID3 выбирает атрибуты, так как это ключевой момент. Пример совершенно неполиткорректный, но, тем не менее, удобен для иллюстрации и использовался и самим Квинланом.

Рост Волосы Глаза Привлекательность?
Низкий Блонд Карие Нет
Высокий Темные Карие Нет
Высокий Блонд Голубые Да
Высокий Темные Голубые Нет
Низкий Темные Голубые Нет
Высокий Красные Голубые Да
Высокий Блонд Карие Нет
Низкий Блонд Голубые Да

Нашим целевым атрибутом для дерева решений будет атрибут «Привлекательность?». Еще раз отмечу, что пример неполиткорректный и не имеет никакого отношения к реальности J

Вычислим энтропию с учетом, что у нас простая бинарная классификация Да/Нет по целевому атрибуту.

Теперь для каждого атрибута оценим прирост информации:

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

И это видно невооруженным глазом, если посмотреть в исходную таблицу данных: («Волосы»=Темные) сразу влечет («Привлекательность?»=Нет), («Волосы»=Красные) сразу влечет («Привлекательность?»=Да). Про Блонд ничего сказать нельзя. Атрибут «Рост», наоборот, самый неинформативный и значения практически не имеет.

Полностью достроить дерево предлагаю вам самостоятельно.

Алгоритм ID3 реализован в Prognoz Platform в модуле интеллектуального анализа данных.

Он позволяет построить дерево решений и визуализировать его в виде правил «Если.

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

Деревья решений обладают определенными особенностями. Начнем с преимуществ:

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

Не обошлось и без недостатков. Среди них:

  • нестабильность процесса. Нередко небольшие изменения в наборе данных могут приводить к построению совершенно другого дерева. Это связано с иерархичностью дерева. Изменения в узле на верхнем уровне ведут к изменениям во всем дереве ниже.
  • сложность контроля размера дерева. Размер дерева является критическим фактором, определяющим качество решения задачи. При использовании простых критериев остановки деревья часто растут или очень короткими, или очень большими.
  • неадекватность разделения на классы в сложных случаях. В простейших деревьях решений разбиение в узлах происходит по значению одного атрибута, параллельно, так сказать, осям координат. В данном случае каждый атрибут – это ось координат со своими значениями. И дерево «нарезает» все пространство на «параллелепипеды», внутри которых и группируются точки набора данных, соответствующие тому или иному классу. Иногда такое разделение не может точно описать сложные области, образуемые точками, принадлежащими определенному классу.
  • критерий прироста информации характеризуется склонностью предпочитать атрибуты, имеющие большое число различных значений. В предельном случае у каждой строки может быть свое значение атрибута. Тогда второе слагаемое в будет равно 0, и прирост будет максимальным.

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

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

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

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

С сайта: http://www.prognoz.ru/blog/platform/decision-tree-in-predictive-analytics/

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

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

Метод построения дерева решений

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

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

Применение дерева решений

Дерево решений – это популярный метод, применяющийся в самых разнообразных сферах нашей жизни:

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

Как же построить дерево решений?

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

2. Необходимо начать с отображения структуры проблемы в «стволе» будущего дерева решений (справа).

3. Ветви – это альтернативные решения, которые теоретически могут быть приняты в данной ситуации, а также возможные следствия принятия этих альтернативных решений. Ветви берут свое начало из одной точки (исходных данных), а «разрастаются» до получения конечного результата.

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

Ветви бывают двух видов:

  • пунктирные линии, которые соединяют квадраты — возможные решения;
  • сплошные линии, соединяющие кружки возможных конечных результатов.

4. Узлы — это ключевые события, а линии, соединяющие узлы – это работы по реализации проекта. Квадратные узлы – это места, где решение принимается. Круглые узлы – появление результатов. Поскольку, принимая решения, мы не можем влиять на появление исхода, нам нужно вычислить вероятность их появления.

5. Помимо этого, на дереве решений необходимо отобразить всю информацию о времени работ, их стоимости, а также вероятности принятия каждого решения;

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

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

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

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

С сайта: https://womanadvice.ru/derevo-resheniy

Что такое дерево принятия решений ХАССП? Практическое применение

Дерево принятия решений ХАССП можно охарактеризовать одним словом – инструмент. Инструмент для решения вопроса, нужна ли критическая контрольная точка на рассматриваемом этапе процесса или нет.

Дерево применяется, если выявлен высокий уровень риска. Оно требует от нас объективных ответов на последовательные вопросы, исходом которых будет решение: данный этап – это ККТ или нет?

Как применять дерево принятия решений ХАССП?

Для лучшего понимания, как применить данный инструмент на практике, давайте с вами рассмотрим облегченный вариант блок-схемы процесса производства мучных кондитерских изделий с одним видом опасности – биологической (остальные виды опасностей принимаем как не учитываемые, т.е. с низким уровнем риска).

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

Теперь вернемся к нашему примеру. Берем следующую блок-схему:

1. Замес теста

2. Формование изделий

3. Выпечка

Биологическая опасность существует на каждом из перечисленных этапов: опасность загрязнения продукта болезнетворными микроорганизмами при несоблюдении элементарных санитарно-гигиенических требований на производстве и правил личной гигиены.

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

В каких случаях дерево принятия решений не требуется

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

В каких случаях  требуется

Что может произойти на этапе выпечки?  Технологам производства и общепита конечно же известно, что при выпечке, как и при любой термической обработке продукта, необходимо соблюдать технологические параметры: температура и время.

Контроль необходим не только для качества изделия, но и для безопасности потребителя.

Таким образом, на этапе термической обработки всегда будет высокий (учитываемый) риск возникновения биологической опасности.

Поэтому на этапе выпечки применяем дерево принятия решений ХАССП и отвечаем на поставленные вопросы:

1. Первый вопрос: Существуют ли меры контроля? Да (ведь мы контролируем параметры выпечки – температуру и время).

2. По стрелке ответа «Да» получаем второй вопрос: Мера контроля специально предназначена для предотвращения риска возникновения опасности или снижения риска до приемлемого уровня? Да (мы контролируем температуру и время на этапе выпечки, чтобы обеспечить безопасности продукции).

3. По стрелке ответа «Да» получаем, что данный этап является критической контрольной точкой, без контроля или недостатка контроля мы рискуем получить небезопасный продукт.

Могут быть иные ситуации, когда потребуется ответить на все вопросы дерева, чтобы определить, является ли данный этап ККТ.

Дальнейшие действия, предполагаемые ХАССП для ККТ – это отдельная тема и принципы ХАССП, которую не следует откладывать надолго.

С сайта: http://haccp24.ru/chto-takoe-derevo-prinyatiya-recheniya-haccp/

Оставить комментарий