Как строить дерево вероятностей

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

Для построения дерева решений не существует универсального набора символов, но чаще всего квадраты (□) используются для представления «решений», а круги (○) для представления «результатов». Поэтому я буду использовать в своей статье именно эти символы.

Дерево решений и задача, требующая многошагового принятия решений

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

Например, может существовать неопределенность как в отношении объема продаж, так и величины затрат. Более того, значение некоторых переменных может зависеть от значения других переменных: например, если будет продано 100,000 единиц продукта, себестоимость единицы продукта составит $4, но если будет продано 120,000 единиц, себестоимость единицы снизится до $3.80. Таким образом, возможны различные исходы ситуации, при этом некоторые из них будут зависеть от предыдущих исходов. Дерево решений представляет собой полезный метод разделения сложной задачи на более мелкие и более управляемые подзадачи.

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

Построение дерева решений

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

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

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

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

После построение дерева решений необходимо оценить решение.

Оценка решения

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

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

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

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

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

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

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

Пример 1
Компания принимает решение, стоит ли разрабатывать и запускать новый продукт. Ожидается, что затраты на разработку составят $400,000, при этом вероятность того, продукт окажется успешным, составляет 70%, а вероятность неудачи, соответственно, 30%. Ниже приведена оценка прибыли от продажи продукта, в зависимости от уровня спроса – высокого, среднего или низкого, а также соответствующие каждому уровню вероятности:

В случае неудачи имеется 60% вероятность, что результаты разработки можно будет продать за $50,000, однако существует 40% вероятность, что продать эти результаты будет невозможно.

Базовое дерево решений представлено ниже:

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

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

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

ОЗ в А = (0.2 x $1,000,000) + (0.5 x $800,000) + (0.3 x $600,000) = $780,000.
ОЗ в В = (0.6 x $50,000) + (0.4 x $0) = $30,000.
ОЗ в С = (0.7 x $780,000) + (0.3 x $30,000) = $555,000

Ожидаемые значения можно указать на диаграмме.

После выполнения расчетов можно двигаться дальше влево к точке принятия решений D. Для принятия решения в точке D нужно сравнить ожидаемое значение верхней ветви дерева (которая, учитывая отсутствие точек исходов, имеет единственный исход, вероятность которого равна 100%) с ожидаемым значением нижней ветви, за вычетом соответствующих затрат. Таким образом, в точке принятия решений D нужно сравнить ожидаемое значение отказа от разработки продукта, которое равно $0, с ожидаемым значением решения разрабатывать продукт которое за вычетом затрат в размере $400,000, составит $155,000.

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

Часто существует несколько способов представления дерева решений. В нашем примере, фактически, имеется пять исходов решения начать разработку продукта:

1. Продукт будет успешным и обеспечит высокую прибыль в размере $1,000,000.
2. Продукт будет успешным и обеспечит среднюю прибыль в размере $800,000.
3. Продукт будет успешным и обеспечит небольшую прибыль в размере $600,000.
4. Продукт будет неудачным, но результаты разработки будут проданы за $50,000.
5. Продукт будет неудачным и не принесет никакого дохода.

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

Теперь вы можете видеть, что вероятности для ветвей дерева, выходящих из точки результатов А, изменились. Это произошло потому, что в данном случае указаны совместные вероятности, которые являются комбинацией вероятности успеха или неудачи (0,7 и 0,3) с вероятностью высокой, низкой или средней прибыли (0.2, 0.5 и 0.3 соответственно). Совместные вероятности рассчитываются путем умножения двух вероятностей, соответствующих каждому исходу:

Успех и высокая прибыль: 0.7 x 0.2 = 0.14
Успех и средняя прибыль: 0.7 x 0.5 = 0.35
Успех и невысокая прибыль: 0.7 x 0.3 = 0.21
Неудача и продажа результатов разработки: 0.3 x 0.6 = 0.18
Неудача и отсутствие дохода от продажи результатов разработки: 0.3 x 0.4 = 0.12

Сумма всех совместных вероятностей должна быть равна 1, если это не так, вы сделали ошибку в расчетах.

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

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

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

Стоимость полной и неполной информации

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

Полная информация

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

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

Ожидаемое значение успеха при наличии полной информации = 0.7 x $380,000 = $266,000

Ожидаемое значение неудачи при наличии полной информации = 0.3 x $0 = $0. Таким образом, общее ожидаемое значение при наличии полной информации = $266,000

Независимо от того, какой метод используется, стоимость полной информации рассчитывается как разница между ожидаемым значением исхода при наличии полной информации и ожидаемым значением исхода в ее отсутствие, т. е. $266,000 – $155,000 = $111,000. Полученное значение представляет собой максимальную сумму, которую имеет смысл заплатить за полную информацию.

Неполная информация

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

Статья написана членом экзаменационного совета по курсу «Управление эффективностью бизнеса».

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

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

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

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

Принятие решений с помощью дерева возможных вариантов производится поэтапно:

1. Построение дерева решений (графа без циклов). Дерево строится по определенным правилам: вершины альтернативных решений, вершины событий, дуги решений, конечные решения — листья вводятся и обозначаются определенным образом в нужном порядке.
2. Анализ дерева решений : подсчет вероятностей и математических ожиданий (стоимостных оценок решения, EMV), расчет оптимистического и пессимистического прогноза, выбор оптимального решения.

Понравилось? Добавьте в закладки

Примеры решений задач: Дерево решений

Задача 1. Вы рассматриваете перспективы создания новой консалтинговой службы. Объем необходимых вложений на начальном этапе $200 тыс. Существует 60%-ная вероятность, что спрос будет высоким в 1-й год. Если спрос будет высоким в первый год, то в последующие годы вероятности высокого и низкого спроса составят 80% и 20% соответственно. Если спрос будет низким в 1-й год, то в последующие годы вероятности высокого и низкого спроса составят 40% и 60% соответственно. При высоком спросе прогнозируемые доходы составят 500 тыс. дол. в год; при низком спросе прогнозируемые доходы равны 300 тыс. дол. в год. Вы можете прекратить предоставлять услуги в любой момент. Затраты, помимо связанных с использованием компьютера, прогнозируются в размере 140 тыс. дол. в год, вне зависимости от уровня спроса.

Если Вы решите не вкладывать деньги в консалтинговую службу, то сможете вложить их на практически безрисковой основе под 20% в год.
Если будет решено организовать консалтинговую службу, Вам необходимо будет решить вопрос с проведением компьютерных расчетов, составляющих основу деятельности. Один возможный вариант — купить сервер.
Срок морального устаревания его 5 лет. Затраты будут состоять из первоначальных расходов в размере 150 тыс. долларов и ежегодных расходов на эксплуатацию в размере 20 тыс.
Альтернативный вариант — арендовать компьютерные ресурсы по мере необходимости. В этом случае затраты на аренду будут пропорциональны спросу и составят 30% доходной части за вычетом оговоренных постоянных расходов в 140 тыс. Во всех случаях никаких других издержек нет.

a. Постройте «древо решений», иллюстрирующее эти варианты и охватывающее 3 года.
b. Стоит организовать консалтинговую службу или безрисковый доход выгоднее? Рассмотрите итоги деятельности за два и три года.
c. Что лучше — купить компьютер или арендовать?
d. Предположим, что после 3 лет деятельности вы сможете продать службу, как отдельный бизнес в среднем за 350 тыс. долларов. Какому ежегодному проценту прироста соответствует полученный вами доход?
e. Четко сформулируйте любые дополнительные допущения, которые вам потребуется сделать.

Задача 2. Фермер может выращивать либо кукурузу, либо соевые бобы. Вероятность того, что цены на будущий урожай этих культур повысятся, останутся на том же уровне или понизятся, равна соответственно 0,25, 0,30 и 0,45. Если цены возрастут, урожай кукурузы даст 30 000 долл. чистого дохода, а урожай соевых бобов — 10 000 долл. Если цены останутся неизменными, фермер лишь покроет расходы. Но если цены станут ниже, урожай кукурузы и соевых бобов приведет к потерям в 35 000 и 5 000 долл. соответственно. Постройте дерево решений. Какую культуру следует выращивать фермеру? Каково ожидаемое значение его прибыли?

Задача 3. Предприятие рассматривает варианты капитальных вложений. Первый вариант предусматривает строительство нового цеха для увеличения объема выпуска продукции стоимостью М1 = 500 млн. руб. При этом варианте возможны большой спрос (годовой доход в размере R1 = 230 млн. руб. в течение 5 последующих лет) с вероятностью p1 = 0,7 и низкий спрос (ежегодные убытки R2 = 90 млн. руб. с вероятностью p2 = 0,3.
Второй вариант предусматривает создание нового предприятия для выпуска новой продукции Стоимостью М1 = 700 млн. руб. При этом варианте возможны большой спрос (годовой доход в размере R1 = 450 млн. руб. в течение 5 последующих лет) с вероятностью p1 = 0,6 и низкий спрос (ежегодные убытки R2 = 150 млн. руб. с вероятностью p2 = 0,4.
При третьем варианте предлагается отложить инвестиции на 1 год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью p1 = 0,8 и p2 = 0,2 соответственно. В случае позитивной информации можно осуществить инвестиции по указанным выше расценкам, в вероятности большого и низкого спроса меняются на p1 = 0,9 и p2 = 0,1 соответственно. Доходы на последующие годы остаются на том же уровне. В случае негативной информации инвестиции осуществляться не будут.
Все расчеты выражены в текущих ценах и не должны дисконтироваться. Нарисовать дерево решений. Определить наиболее эффективную последовательность действий, основываясь на ожидаемых доходах. Какова ожидаемая стоимостная оценка наилучшего решения?

Задача 4. Рассматривается проект покупки доли (пакета акций) в инвестиционном проекте. Пакет стоит 7 млн., и по завершению проект принесет доход 12 млн. с вероятностью 0,6 или ничего с вероятностью 0,4.
При этом через некоторое время будет опубликован прогноз аналитической фирмы относительно успеха этого проекта. Прогноз верен с вероятностью 0,7, то есть, равны 0,7 условные вероятности.
Однако, в случае положительного прогноза пакет порождает до 10,6 млн., а в случае отрицательного подешевеет до 3,4 млн. Требуется составить стратегию действий: покупать ли долю, или ждать прогноза, и совершать ли покупку при том или ином результате прогноза.

Задача 5. Компания «Большая нефть» хочет знать, стоит ли бурить нефтяную скважину на одном из участков, купленных ранее в перспективном месте. Бурение, проведенное на множестве соседних участков, показало, что перспективы не так уж хороши. Вероятность найти нефть на глубине не больше 400 м составляет около 50%. При этом стоимость бурения составит 1.5 млн., а стоимость нефти, за вычетом всех расходов, кроме расходов на бурение, составит 6 млн. Если нефть не найдена на малой глубине, не исключена возможность найти ее при более глубоком бурении. Расходы на бурение, вероятность найти нефть и приведенная стоимость нефти для этих случаев даны в таблице.
a. Постройте дерево решений, показывающее последовательные решения о разработке скважины, которые должна принять компания «Большая нефть». На какую среднюю прибыль компания может рассчитывать?
b. Скважину какой глубины нужно быть готовыми пробурить? (Стоит ли остановиться при достижении определенной глубины, или бурить до предельной глубины?)
c. Какова вероятность найти нефть при бурении (при необходимости) до выбранной вами предельной глубины? Какова полная вероятность найти нефть при готовности бурить до 1500 м?

Деревья решений: общие принципы

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

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

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

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

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

Основополагающие идеи, послужившие толчком к появлению и развитию деревьев решений, были заложены в 1950-х годах в области исследований моделирования человеческого поведения с помощью компьютерных систем. Среди них следует выделить работы К. Ховеленда «Компьютерное моделирование мышления»[1] и Е. Ханта и др. «Эксперименты по индукции»[2].

Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с именами Джона Р. Куинлена[3], который разработал алгоритм ID3 и его усовершенствованные модификации С4.5 и С5.0, а так же Лео Бреймана[4], который предложил алгоритм CART и метод случайного леса.

Терминология

Введем в рассмотрение основные понятия, используемые в теории деревьев решений.

Название	Описание
Объект	Пример, шаблон, наблюдение
Атрибут	Признак, независимая переменная, свойство
Целевая переменная	Зависимая переменная, метка класса
Узел	Внутренний узел дерева, узел проверки
Корневой узел	Начальный узел дерева решений
Лист	Конечный узел дерева, узел решения, терминальный узел
Решающее правило	Условие в узле, проверка

Структура дерева решений

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

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

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

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

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

Задачи

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

• Классификация — отнесение объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения.
• Регрессия (численное предсказание) — предсказание числового значения независимой переменной для заданного входного вектора.
• Описание объектов — набор правил в дереве решений позволяет компактно описывать объекты. Поэтому вместо сложных структур, описывающих объекты, можно хранить деревья решений.

Процесс построения

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

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

В основе большинства популярных алгоритмов обучения деревьев решений лежит принцип «разделяй и властвуй». Алгоритмически этот принцип реализуется следующим образом. Пусть задано обучающее множество S , содержащее n примеров, для каждого из которых задана метка класса C_i(i=1..k) , и m атрибутов A_j(j=1..m) , которые, как предполагается, определяют принадлежность объекта к тому или иному классу. Тогда возможны три случая:

1. Все примеры множества S имеют одинаковую метку класса C_i (т.е. все обучающие примеры относятся только к одному классу). Очевидно, что обучение в этом случае не имеет смысла, поскольку все примеры, предъявляемые модели, будут одного класса, который и «научится» распознавать модель. Само дерево решений в этом случае будет представлять собой лист, ассоциированный с классом C_i . Практическое использование такого дерева бессмысленно, поскольку любой новый объект оно будет относить только к этому классу.
2. Множество S вообще не содержит примеров, т.е. является пустым множеством. В этом случае для него тоже будет создан лист (применять правило, чтобы создать узел, к пустому множеству бессмысленно), класс которого будет выбран из другого множества (например, класс, который наиболее часто встречается в родительском множестве).
3. Множество S содержит обучающие примеры всех классов C_k . В этом случае требуется разбить множество S на подмножества, ассоциированные с классами. Для этого выбирается один из атрибутов A_j множества S который содержит два и более уникальных значения (a_1,a_2. a_p) , где p — число уникальных значений признака. Затем множество S разбивается на p подмножеств (S_1,S_2. S_p) , каждое из которых включает примеры, содержащие соответствующее значение атрибута. Затем выбирается следующий атрибут и разбиение повторяется. Это процедура будет рекурсивно повторяться до тех пор, пока все примеры в результирующих подмножествах не окажутся одного класса.

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

В настоящее время разработано значительное число алгоритмов обучения деревья решений: ID3, CART, C4.5, C5.0, NewId, ITrule, CHAID, CN2 и т.д. Но наибольшее распространение и популярность получили следующие:

• ID3 (Iterative Dichotomizer 3) — алгоритм позволяет работать только с дискретной целевой переменной, поэтому деревья решений, построенные с помощью данного алгоритма, являются классифицирующими. Число потомков в узле дерева не ограничено. Не может работать с пропущенными данными.
• C4.5 — усовершенствованная версия алгоритма ID3, в которую добавлена возможность работы с пропущенными значениями атрибутов (по версии издания Springer Science в 2008 году алгоритм занял 1-е место в топ-10 наиболее популярных алгоритмов Data Mining).
• CART (Classification and Regression Tree) — алгоритм обучения деревьев решений, позволяющий использовать как дискретную, так и непрерывную целевую переменную, то есть решать как задачи классификации, так и регрессии. Алгоритм строит деревья, которые в каждом узле имеют только два потомка.

Основные этапы построения

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

1. Выбор атрибута, по которому будет производиться разбиение в данном узле (атрибута разбиения).
2. Выбор критерия остановки обучения.
3. Выбор метода отсечения ветвей (упрощения).
4. Оценка точности построенного дерева.

Рассмотрим эти этапы ниже.

Выбор атрибута разбиения

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

Теоретико-информационный критерий

Как следует из названия, критерий основан на понятиях теории информации, а именно — информационной энтропии.

где n — число классов в исходном подмножестве, N_i — число примеров i-го класса, N — общее число примеров в подмножестве.

Таким образом, энтропия может рассматриваться как мера неоднородности подмножества по представленным в нём классам. Когда классы представлены в равных долях и неопределённость классификации наибольшая, энтропия также максимальна. Если все примеры в узле относятся к одному классу, т.е. N=N_i , логарифм от единицы обращает энтропию в ноль.

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

где \text(S) — информация, связанная с подмножеством S до разбиения, \text(S_A) — информация, связанная с подмножеством, полученными при разбиении по атрибуту A .

Таким образом, задача выбора атрибута разбиения в узле заключается в максимизации величины \text(A) , называемой приростом информации (от англ. gain — прирост, увеличение). Поэтому сам теоретико-информационный подход известен как критерий прироста информации. Он впервые был применён в алгоритме ID3, а затем в C4.5 и других алгоритмах.

Статистический подход

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

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

Индекс Джини может быть рассчитан по формуле:

где Q — результирующее множество, n — число классов в нём, p_i — вероятность i-го класса (выраженная как относительная частота примеров соответствующего класса). Очевидно, что данный показатель меняется от 0 до 1. При этом он равен 0, если все примеры Q относятся к одному классу, и равен 1, когда классы представлены в равных пропорциях и равновероятны. Тогда лучшим будет то разбиение, для которого значение индекса Джини будут минимальным.

Критерий остановки алгоритма

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

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

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

1. Ранняя остановка — алгоритм будет остановлен, как только будет достигнуто заданное значение некоторого критерия, например процентной доли правильно распознанных примеров. Единственным преимуществом подхода является снижение времени обучения. Главным недостатком является то, что ранняя остановка всегда делается в ущерб точности дерева, поэтому многие авторы рекомендуют отдавать предпочтение отсечению ветвей.
2. Ограничение глубины дерева — задание максимального числа разбиений в ветвях, по достижении которого обучение останавливается. Данный метод также ведёт к снижению точности дерева.
3. Задание минимально допустимого числа примеров в узле — запретить алгоритму создавать узлы с числом примеров меньше заданного (например, 5). Это позволит избежать создания тривиальных разбиений и, соответственно, малозначимых правил.

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

Отсечение ветвей

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

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

К сожалению, это задача относится к классу NP-полных задач, что было показано Л. Хайфилем (L. Hyafill) и Р. Ривестом (R. Rivest), и, как известно, этот класс задач не имеет эффективных методов решения.

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

1. Построить полное дерево (чтобы все листья содержали примеры одного класса).
2. Определить два показателя: относительную точность модели — отношение числа правильно распознанных примеров к общему числу примеров, и абсолютную ошибку — число неправильно классифицированных примеров.
3. Удалить из дерева листья и узлы, отсечение которых не приведёт к значимому уменьшению точности модели или увеличению ошибки.

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

Извлечение правил

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

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

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

Преимущества алгоритма

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

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

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

Области применения

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

Деревья решений успешно применяются на практике в следующих областях:

• Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
• Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например, проверка качества сварки) и т.д.
• Медицина. Диагностика заболеваний.
• Молекулярная биология. Анализ строения аминокислот.
• Торговля. Классификация клиентов и товаров.

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

1. Hovland, C. I. (1960). Computer simulation of thinking. American Psychologist, 15(11), 687-693.
2. Hunt, Earl B.; Janet Marin; Philip J. Stone (1966). Experiments in Induction. New York: Academic Press. ISBN 978-0-12-362350-8.
3. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1):81-106.
4. Quinlan, J. Ross. C4.5: Programs for Machine learning. Morgan Kaufmann Publishers 1993.
5. Breiman, Leo, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
6. Murthy, S. Automatic construction of decision trees from data: A Multi-disciplinary survey.1997.
7. Buntine, W. A theory of classification rules. 1992.
8. Machine Learning, Neural and Statistical Classification. Editors D. Mitchie et.al. 1994.
9. Шеннон, К. Работы по теории информации и кибернетике. М. Иностранная литература, 1963.
10. Айвазян С. А., Мхитарян В. С Прикладная статистика и основы эконометрики, М. Юнити, 1998.

Другие материалы по теме:

Дерево вероятностей

В этой статье я покажу вам очень простой способ решения некоторых задач по теории вероятностей.
Рассмотрим задачу. Трое друзей Вася, Петя и Слава купили торт, и решили его съесть. Они разделили торт на три равных части. Внезапно появился четвертый друг Коля, и друзья решили отрезать ему по кусочку от своей доли. Вася отрезал 1/3 от своего куска, Петя 1/4, а Слава – половину. Какую часть всего торта получил в итоге Коля?

Изобразим ситуацию, описанную в задаче в виде такой схемы:

Сначала торт разрезали на три равные части, и каждому из трех друзей досталось по 1/3 торта.

Затем пришел Коля и каждый мальчик отрезал ему соответствующую часть своего куска:

Чтобы найти дробь от числа, нужно число умножить на эту дробь. То есть Вася отдает Коле часть торта, Петя — часть торта, а Слава часть торта.

Ответ: 0,019

Вероятно, Ваш браузер не поддерживается. Чтобы использовать тренажёр «Час ЕГЭ», попробуйте скачать
Firefox

И.В. Фельдман, репетитор по математике.

Для вас другие записи этой рубрики:

• Миникурс «Теория вероятностей»
• Задачи по теории вероятностей-2. Задание В5 (2015)
• Миникурс «Теория вероятностей»
• Задачи по теории вероятностей-1. Задание В5 (2015)
• Задачи-шутки по теории вероятностей
• Элементы комбинаторики