Метод «Деревьев решений».
Дерево решений - это схематическое представление проблемы принятия решений. Ветви дерева решений представляют собой различные события (решения), а его вершины - ключевые состояния, в которых возникает необходимость выбора.
Чаще всего дерево решений является нисходящим, то есть строится сверху вниз. Выделяют следующие этапы построения дерева решений:
1. Первоначально обозначают ключевую проблему. Это будет вершина дерева.
2. Для каждого момента определяют все возможные варианты дальнейших событий, которые могут оказать влияние на ключевую проблему. Это будут исходящие от вершины дуги дерева.
3. Обозначают время наступления событий.
4. Каждой дуге прописывают денежную и вероятностную характеристики.
5. Проводят анализ полученных результатов.
Основа наиболее простой структуры дерева решений - ответы на вопросы "да" и "нет".
Пример. Рассмотрим пример дерева решений, задача которого - ответить на вопрос "пойти ли гулять?". Чтобы решить эту задачу, необходимо ответить на ряд вопросов, которые находятся в узлах дерева. Вершина дерева "на улице солнечно" является узлом проверки. Если на этот вопрос получен положительный ответ, то переходим к левой ветви дерева, если отрицательный - то к правой. Движение продолжается до тех пор, пока не будет получен окончательный ответ.
Дерево решений "пойти ли гулять?"
/\
/ \
/ \
/ На \
/ улице \
┌───────────────────/ солнечно?\───────────────────┐
│ \ / │
┌─┴─┐ \ / ┌─┴─┐
│ да│ \ / │нет│
└─┬─┘ \ / └─┬─┘
│ \ / │
/\ \/ /\
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
┌────/ Температура\────┐ ┌─────/ Идет ли \────┐
│ \ воздуха / │ │ \ дождь? / │
│ \ высокая? / │ │ \ / │
│ \ / │ │ \ / │
│ \ / │ │ \ / │
│ \ / │ │ \ / │
│ \ / │ │ \ / │
│ \/ │ │ \/ │
├───┐ ┌───┤ ├───┐ ┌───┤
│ да│ │нет│ │ да│ │нет│
├───┘ └───┤ ├───┘ └───┤
│ │ │ │
├─────────┐ ┌───────┤ ├─────────┐ ┌───────┤
│Не ходить│ │ Идти │ │Не ходить│ │ Идти │
└─────────┘ └───────┘ └─────────┘ └───────┘
Рисунок 14
Для каждой дуги дерева могут быть определены числовые характеристики, например величина прибыли по проекту и вероятность ее получения. В этом случае оно помогает учесть все возможные варианты действия и соотнести с ними финансовые результаты. Для формулирования сценариев развития проекта необходимо располагать достоверной информацией с учетом вероятности и времени наступления событий. Затем переходят к сравнению альтернатив.
Недостатками дерева решений является ограниченное число вариантов решения проблемы. В процессе построения дерева решений необходимо обращать внимание на его размер. Оно не должно быть слишком перегруженным, так как это уменьшает способность к обобщению и способность давать верные ответы.
Преимущества метода.
Интуитивность деревьев решений Возможность извлекать правила из базы данных на естественном языке Не требует от пользователя выбора входных атрибутов Точность моделей Разработан ряд масштабируемых алгоритмов Быстрый процесс обучения Обработка пропущенных значений Работа и с числовыми, и с категориальными типами данных.
Процесс конструирования. Основные этапы алгоритмов конструирования деревьев: "построение" или "создание" дерева (tree building) "сокращение" дерева (tree pruning).
Критерии
расщепления. "мера информационного
выигрыша" (information gain measure) индекс Gini,
т.е. gini(T), определяется по формуле:
Большое
дерево не означает, что оно "подходящее"
