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

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

Каждый лист представляет собой значение целевой переменной, измененной в ходе движения от корня  по листу. Каждый внутренний узел соответствует  одной из входных переменных. Дерево может быть также «изучено» разделением  исходных наборов переменных на подмножества, основанные на тестировании значений атрибутов. Это процесс, который  повторяется на каждом из полученных подмножеств. Рекурсия завершается  тогда, когда подмножество в узле имеет те же значения целевой переменной, таким образом, оно не добавляет  ценности для предсказаний. Процесс, идущий «сверху вниз», индукция деревьев решений (TDIDT)^[1], является примером поглощающего «жадного» алгоритма, и на сегодняшний день является наиболее распространенной стратегией деревьев решений для данных, но это не единственная возможная стратегия. В интеллектуальном анализе данных, деревья решений могут быть использованы в качестве математических и вычислительных методов, чтобы помочь описать, классифицировать и обобщить набор данных, которые могут быть записаны следующим образом:

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

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

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

 

Процесс принятия решений с помощью  дерева решений в общем случае предполагает выполнение следующих  пяти этапов. 
  
    Этап 1. Формулирование задачи. Прежде всего необходимо отбросить не относящиеся к проблеме факторы, а среди множества оставшихся выделить существенные и несущественные. Это позволит привести описание задачи принятия решения к поддающейся анализу форме. Должны быть выполнены следующие основные процедуры: определение возможностей сбора информации для экспериментирования и реальных действий; составление перечня событий, которые с определенной вероятностью могут произойти; установление временного порядка расположения событий, в исходах которых содержится полезная и доступная информация, и тех последовательных действий, которые можно предпринять. 
    Этап 2 Построение дерева решений, т.е. графическое представление последовательности возможных альтернативных действий с учетом соответствующих внешних условий, начиная с «корня» и завершая «листочками».  
    Этап 3. Оценка вероятностей состояний среды, т.е. сопоставление шансов возникновения каждого конкретного события. Следует отметить, что указанные вероятности определяются либо на основании имеющейся статистики, либо экспертным путем. 
    Этап 4. Установление выигрышей (или проигрышей, как выигрышей со знаком минус) для каждой возможной комбинации альтернатив (действий) и состояний среды. 
    Этап 5. Решение задачи, состоящее в определении на дереве решений «веточки», для которой установленный на этапе 4 выигрыш является максимальным. 
 

 

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

Таблица 1 

 

Номер стратегии	Действия компании	Выигрыш, руб., при  состоянии экономической среды
		благоприятном	неблагоприятном
1	Строительство крупного предприятия (а1)	200 000	-180 000
2	Строительство малого предприятия (а2)	100 000	-20 000
3	Продажа патента (а3)	10 000	10 000

 

  
    Примечание. Вероятность благоприятного и неблагоприятного состояний экономической среды равна 0,5. 
  
    На основе данной таблицы выигрышей (потерь) можно построить дерево решений (рис. 1). 
  
    Процедура принятия решения заключается в вычислении для каждой вершины дерева (при движении справа налево) ожидаемых денежных оценок, отбрасывании неперспективных ветвей и выборе ветвей, которым соответствует максимальное значение ОДО. 
  
    Определим средний ожидаемый выигрыш (ОДО): 
    для вершины 1 ОДО1 = 0,5 x 200 000 + 0,5(–180 000) = 10 000 руб.; 
    для вершины 2 ОДО2 = 0,5 x 100 000 + 0,5(–20 000) = 40 000 руб.; 
    для вершины 3 ОДО3 = 10 000 руб. 
  
    Вывод. Наиболее целесообразно выбрать стратегию а2, т.е. строить малое предприятие, а ветви (стратегии) а1 и а3 дерева решений можно отбросить. ОДО наилучшего решения равна 40 000 руб. Следует отметить, что наличие состояния с вероятностями 50% неудачи и 50% удачи на практике часто означает, что истинные вероятности игроку скорее всего неизвестны и он всего лишь принимает такую гипотезу (так называемое предположение «fifty—fifty» — пятьдесят на пятьдесят). 
 

 
Рис. 1. Дерево решений без  дополнительного обследования конъюнктуры  рынка 

 
    Усложним рассмотренную выше задачу. 
  
    Пусть перед тем, как принимать решение о строительстве, руководство компании должно определить, заказывать ли дополнительное исследование состояния рынка или нет, причем предоставляемая услуга обойдется компании в 10 000 руб. Руководство понимает, что дополнительное исследование по-прежнему не способно дать абсолютно точной информации, но оно поможет уточнить ожидаемые оценки конъюнктуры рынка, изменив тем самым значения вероятностей. 
     
    Относительно фирмы, которой можно заказать прогноз, известно, что она способна уточнить значения вероятностей благоприятного или неблагоприятного исхода. Возможности фирмы в виде условных вероятностей благоприятности и неблагоприятности рынка сбыта представлены в таблице 2. Например, когда фирма утверждает, что рынок благоприятный, то с вероятностью 0,78 этот прогноз оправдывается (с вероятностью 0,22 могут возникнуть неблагоприятные условия), прогноз о неблагоприятности рынка оправдывается с вероятностью 0,73.

Достоинства метода [править]

Среди прочих методов Data Mining, метод дерева принятия решений имеет несколько достоинств:

• Прост в понимании и интерпретации. Люди способны интерпретировать результаты модели дерева принятия решений после краткого объяснения
• Не требует подготовки данных. Прочие техники требуют нормализации данных, добавления дамми-переменных, а также удаления пропущенных данных.
• Способен работать как с категориальными, так и с интервальными переменными. Прочие методы работают лишь с теми данными, где присутствует лишь один тип переменных. Например, метод отношений может быть применен только на номинальных переменных, а метод нейронных сетей только на переменных, измеренных по интервальной шкале.
• Использует модель «белого ящика». Если определенная ситуация наблюдается в модели, то её можно объяснить при помощи булевой логики. Примером «черного ящика» может быть искусственная нейронная сеть, так как результаты данной модели поддаются объяснению с трудом.
• Позволяет оценить модель при помощи статистических тестов. Это дает возможность оценить надежность модели.
• Является надежным методом. Метод хорошо работает даже в том случае, если были нарушены первоначальные предположения, включенные в модель.
• Позволяет работать с большим объемом информации без специальных подготовительных процедур. Данный метод не требует специального оборудования для работы с большими базами данных.

Недостатки метода [править]

• Проблема получения оптимального дерева решений является NP-полной с точки зрения некоторых аспектов оптимальности даже для простых задач^[7][8]. Таким образом, практическое применение алгоритма деревьев решений основано на эвристических алгоритмах, таких как алгоритм «жадности», где единственно оптимальное решение выбирается локально в каждом узле. Такие алгоритмы не могут обеспечить оптимальность всего дерева в целом.
• Те, кто изучает метод дерева принятия решений, могут создавать слишком сложные конструкции, которые не достаточно полно представляют данные. Данная проблема называется проблемой «чрезмерной подгонки»^[9] Для того, чтобы избежать данной проблемы, необходимо использовать Метод «регулирования глубины дерева».
• Существуют концепты, которые сложно понять из модели, так как модель описывает их сложным путем. Данное явление может быть вызвано проблемами XOR, четности или мультиплексарности. В этом случае мы имеем дело с непомерно большими деревьями. Существует несколько подходов решения данной проблемы, например, попытка изменить репрезентацию концепта в модели (составление новых суждений)^[10], или использование алгоритмов, которые более полно описывают и репрезентируют концепт (например, метод статистических отношений, индуктивная логика программирования).
• Для данных, которые включают категориальные переменные с большим набором уровней (закрытий), больший информационный вес присваивается тем атрибутам, которые имеют большее количество уровней.^[11]